[clug] Anyone using 'snappy', Google's fast compression?

[Robert Edwards]

On 12/05/11 16:33, David Austin wrote:
> On Thu, May 12, 2011 at 4:26 PM, Mike Carden<mike.carden at gmail.com>  wrote:
>
>>> led me to this GOOG project:
>>> <http://code.google.com/p/snappy/>
>>
>> Well I hadn't heard of it and it looks interesting.
>>
>> Slightly tangentially, I was reading today about the stream
>> compression employed by LTO 5 tape libraries. It grabs a data block,
>> caches it then has a stab at compressing it. Then it compares the
>> compressed block to the original and writes out the smaller of the two
>> to tape - avoiding the trap of making the data bigger if it was
>> already compressed or is incompressible.
>>
>> This is probably old hat to anyone who has worked with the guts of
>> compression implementations before, but I was struck by its simplicity
>> and usefulness.
>>
>
> Note that the tape still has to store an extra bit per block to record
> if the compressed or original block is stored.  Thus, it can require
> small increases in size.
>
> There exists no lossless compression algorithm that can reduce
> the size of all inputs (if it did exist, run it on the output again and
> again).
>
> David

If my memory serves (and it demonstrably doesn't so much any more), 
according to Paul (paulus) Mackerras, one of the inventors of rsync,
the US Patent Office did issue a patent at one point for an invention
that compresses _any_ N-bit sequence into an N-1 bit sequence. Don't
remember the full story, but I think someone pointed out that this was
effectively impossible and the patent was nullified. Anyone know the
full story?

Cheers,

Bob Edwards.