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

Robert Edwards bob at cs.anu.edu.au
Thu May 12 03:13:58 MDT 2011

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?


Bob Edwards.

More information about the linux mailing list