RedLZ77 lz77 compression/decompression


see http://michael.dipperstein.com/lzss/

and http://www.binaryessence.com/dct/en000138.htm


a dictionary look-up compressor that performs best with very long repeating patterns.  e.g. [0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3].  use RedLZSS for better albeit slower compression.

works with Integer, Float and Symbol.  can also take a String instead of an Array.


see also: RedBase64 RedHuffman RedLZ78 RedLZSS RedLZW RedRLE


*compress(array)

returns an array with length, distance and value...

*decompress(array)

returns an array

<>window

maximum sliding window size.  default= 4096

<>length

maximum length for matching pattern.  default= 32



//--

a= [0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3];

b= RedLZ77.compress(a);

b.size/a.size; //compressed to 58%

c= RedLZ77.decompress(b);

a==c



a= "AABCBBABC"; //string instead of array

b= RedLZ77.compress(a);

c= RedLZ77.decompress(b);

a==c.join;



a= "abracadabra".ascii;

b= RedLZ77.compress(a);

c= RedLZ77.decompress(b);

a==c



a= "JOEYNJOEYNJOEYJOEYNJOEYNJOEYJOEYNJOEYNJOEYJOEYNJOEYNJOEY".ascii;

b= RedLZ77.compress(a);

b.size/a.size; //compressed to 41%

c= RedLZ77.decompress(b);

a==c



a= "Man is distinguished, not only by his reason, but by this singular passion from other animals, which is a lust of the mind, that by a perseverance of delight in the continued and indefatigable generation of knowledge, exceeds the short vehemence of any carnal pleasure.".ascii;

b= RedLZ77.compress(a);

b.size/a.size; //expanded to 117%

c= RedLZ77.decompress(b);

c.collect{|x| x.asAscii}.join;

a==c



a= {|i| [0, 0, 0, 0.1].choose}.dup(5000);

RedLZ77.window= 512; //decrease window and length to speed up compression

RedLZ77.length= 16;

b= RedLZ77.compress(a); //very slow to compress large arrays

b.size/a.size; //compressed to around 24% (20% with default window and length values)

c= RedLZ77.decompress(b); //fast to decompress

c.size

a==c