3 ms·
A quick summary of the difference between this and existing implementations of deflate such as gzip or zlib: Deflate combines two compression techniques: Huffm
by JoshTriplett 14y ago
A quick summary of the difference between this and existing implementations of deflate such as gzip or zlib:
Deflate combines two compression techniques: Huffman coding to replace each value with a string of bits whose length depends on the frequency of that value, and backreferences of the form "go back N bytes and repeat M bytes from there". (Glossing over a pile of fun interactions between those two, such as Huffman-coding both literals and backreferences, and Huffman-coding the Huffman tables. Not to mention the ability to have M > N, repeating the earlier parts of the thing you backreferenced. See RFC1951, https://www.ietf.org/rfc/rfc1951 https://www.ietf.org/rfc/rfc1951 , for the full details.)
Existing deflate implementations use various heuristics to guess when they should encode the next bit of data as a literal symbol or a backreference, such as a hash table of possible strings to backreference; the compression level (-1 through -9) tunes those heuristics to take more or less time, most notably by changing the lengths of strings stored and searched for for in the hash table.
Zopfil says it uses "more exhaustive compression techniques" based on "iterating entropy modeling and a shortest path search algorithm to find a low bit cost path through the graph of all possible deflate representations." The entropy modeling allows Zopfil to estimate the effectiveness of a given approach to deflate. The path-search algorithm effectively treats the space of all possible deflate representations as a single-player game, with "moves" that change the representation in some incremental way, and then uses standard search algorithms to find a near-optimal representation.
(Without reading the source in detail, I don't know whether the search space includes the choice of Huffman tables, the set of possible backreferences, or both. I can see how either one could map onto a search space, though.)