Dictionary Coders (& LZP)

You need crblib to compile this source. (changes frequently)

This code is covered by the Bloom Public License

The LZP Archives

• I invented LZP in 1995, when I was seeking a compressor with a very fast encoder and ratios similar to LZ77. I made LZP, and ended up writing a paper on it for the 1996 Data Compression Conference. LZP is primarily interesting for its smooth memory use/speed/compression scalability, which makes it easily retargetable for any application. Some of the companies that have used LZP are listed below. Notez : LZP is not patented by me or anyone else!

• LZP 1 source : 4.12 bpb and 10 megs/sec (new August 15, 1997 : sorry it took so long to put up!)

• LZP 3 source very simple, fast;

  note: this LZP3 is not the same as that in the LZP papers, but fills the same niche, and is significantly simpler (a little slower).

  Despite using arithcoding, this LZP-3 is about twice as fast as competing LZ77 algorithms.

• LZP 3 with order 2 literal coding (instead of the normal order 1)

• LZP 2 source like LZP3, but uses Huffman instead of Arithcoding. Faster, less compression. Uses new crblib HuffArray functionality.

• LZP Exes (465k Zip) Win32 686 Versions of this code. (new October 20, 1999 by popular demand)

• Also visit Arturo Campos' Page ; he's done lots of good experimenting and implementing.

Miscellaneous

• fast, simple LZW using a Trie
  Warning: LZW is patented by UniSys

• LZRW1,2,3,4
  This is a zip of the entire "LZRW directory" which was once on the net. (not my code)

  Ross Williams LZRW Crypt is back on the net!

The LZCB Archives

So, why is "LZCB20" my primary LZ77 coder? What happened to 1 though 19 ? Well, I won't answer that question, but I have dredged up some of the old missing LZCB's and restored them to compiling order. (can you believe there were 32 of them! Most of this code is from 1995, never posted to the net (like the vast majority of my code); LZCB11 - 14 were the LZP's; LZCB's 15-19 were very fast coders like LZRW3 and 4). I've now got:

• LZCB #20 a very high compression LZ engine; all higher-number LZCB's are based on this structure.

• LZCB #26 and 28 This is lzcb20 with optimal parsing ; LZCB28 is a normal Storer-Symanski walk-backwards style optimal parse. LZCB26 uses a heuristic I invented which seems to perform better in practice. The LZCB26 heuristic is to find all the matches for the stream, then select the very longest one, then the next longest, etc. For each length, it first selects the lowest offset matches of that length. If a match conflicts with a previous match it is truncated and pushed back on the queue.

  LZCB 26 now includes a self-extracting decoder.

• LZCB #21 also includes #22. Implements "PMR"s = Previous Match References. That is, we try to code references to matches already done. Helps almost as much as optimal parsing (very slow)! Decoder not implemented (but is a trivial extension on lzcb20 decode).

• LZCB #32 an optimal parser which codes without offsets. Uses "Match-Marker-References". Not as successful as it should be.

• LZCB #40-42 a new modification to the LZCB20-26-28 family (8-18-98); should be more adaptive now about working well on binary or text. The addition here is the use of better arithmetic coding contexts for match flags and offsets (uses a "markov chain" if you will). The my-style-optimal LZCB41 is quite a dandy, with a 2.4867 bpc average on the Corpus. All decoders are the same (lzcb40d).

• LZCB #43-45 same as lzcb40, but has a min match len of 3 instead of 4. This hurts except on the optimal lzcb45 (wierd-optimal-lzcb44 gets hurt). (8-19-98)

Back to the Source Code Index