| 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 |
The lazy match evaluation is not performed for the fastest compression |
| 50 |
modes (speed options -1 to -3). For these fast modes, new strings |
| 51 |
are inserted in the hash table only when no match was found, or |
| 52 |
when the match is not too long. This degrades the compression ratio |
| 53 |
but saves time since there are both fewer insertions and fewer searches. |
| 54 |
|
| 55 |
Jean-loup Gailly |
| 56 |
[email protected] |
| 57 |
|
| 58 |
References: |
| 59 |
|
| 60 |
[LZ77] Ziv J., Lempel A., "A Universal Algorithm for Sequential Data |
| 61 |
Compression", IEEE Transactions on Information Theory", Vol. 23, No. 3, |
| 62 |
pp. 337-343. |
| 63 |
|
| 64 |
APPNOTE.TXT documentation file in PKZIP 1.93a. It is available by |
| 65 |
ftp in ftp.cso.uiuc.edu:/pc/exec-pc/pkz193a.exe [128.174.5.59] |
| 66 |
|
| 67 |
'Deflate' Compressed Data Format Specification: |
| 68 |
ftp://ftp.uu.net/pub/archiving/zip/doc/deflate-1.1.doc |