Return to algorith.doc CVS log

Up to [MW Coherent from dump] / coherent / b / bin / zip

Annotation of coherent/b/bin/zip/algorith.doc, revision 1.1.1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.