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     ! 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.