1Zip's deflation algorithm is a variation of LZ77 (Lempel-Ziv 1977, see 2reference below). It finds duplicated strings in the input data. The 3second occurrence of a string is replaced by a pointer to the previous 4string, in the form of a pair (distance, length). Distances are 5limited to 32K bytes, and lengths are limited to 258 bytes. When a 6string does not occur anywhere in the previous 32K bytes, it is 7emitted as a sequence of literal bytes. (In this description, 8'string' must be taken as an arbitrary sequence of bytes, and is not 9restricted to printable characters.) 10 11Literals or match lengths are compressed with one Huffman tree, and 12match distances are compressed with another tree. The trees are stored 13in a compact form at the start of each block. The blocks can have any 14size (except that the compressed data for one block must fit in 15available memory). A block is terminated when zip determines that it 16would be useful to start another block with fresh trees. (This is 17somewhat similar to compress.) 18 19Duplicated strings are found using a hash table. All input strings of 20length 3 are inserted in the hash table. A hash index is computed for 21the next 3 bytes. If the hash chain for this index is not empty, all 22strings in the chain are compared with the current input string, and 23the longest match is selected. 24 25The hash chains are searched starting with the most recent strings, to 26favor small distances and thus take advantage of the Huffman encoding. 27The hash chains are singly linked. There are no deletions from the 28hash chains, the algorithm simply discards matches that are too old. 29 30To avoid a worst-case situation, very long hash chains are arbitrarily 31truncated at a certain length, determined by a runtime option (zip -1 32to -9). So zip does not always find the longest possible match but 33generally finds a match which is long enough. 34 35zip also defers the selection of matches with a lazy evaluation 36mechanism. After a match of length N has been found, zip searches for a 37longer match at the next input byte. If a longer match is found, the 38previous match is truncated to a length of one (thus producing a single 39literal byte) and the longer match is emitted afterwards. Otherwise, 40the original match is kept, and the next match search is attempted only 41N steps later. 42 43The lazy match evaluation is also subject to a runtime parameter. If 44the current match is long enough, zip reduces the search for a longer 45match, thus speeding up the whole process. If compression ratio is more 46important than speed, zip attempts a complete second search even if 47the first match is already long enough. 48 49The lazy match evaluation is not performed for the fastest compression 50modes (speed options -1 to -3). For these fast modes, new strings 51are inserted in the hash table only when no match was found, or 52when the match is not too long. This degrades the compression ratio 53but saves time since there are both fewer insertions and fewer searches. 54 55Jean-loup Gailly 56jloup@chorus.fr 57 58References: 59 60[LZ77] Ziv J., Lempel A., "A Universal Algorithm for Sequential Data 61Compression", IEEE Transactions on Information Theory", Vol. 23, No. 3, 62pp. 337-343. 63 64APPNOTE.TXT documentation file in PKZIP 1.93a. It is available by 65ftp in ftp.cso.uiuc.edu:/pc/exec-pc/pkz193a.exe [128.174.5.59] 66 67'Deflate' Compressed Data Format Specification: 68ftp://ftp.uu.net/pub/archiving/zip/doc/deflate-1.1.doc 69