Commit | Line | Data |
---|---|---|
c801d85f KB |
1 | 1. Compression algorithm (deflate) |
2 | ||
3 | The deflation algorithm used by gzip (also zip and zlib) is a variation of | |
4 | LZ77 (Lempel-Ziv 1977, see reference below). It finds duplicated strings in | |
5 | the input data. The second occurrence of a string is replaced by a | |
6 | pointer to the previous string, in the form of a pair (distance, | |
7 | length). Distances are limited to 32K bytes, and lengths are limited | |
8 | to 258 bytes. When a string does not occur anywhere in the previous | |
9 | 32K bytes, it is emitted as a sequence of literal bytes. (In this | |
10 | description, `string' must be taken as an arbitrary sequence of bytes, | |
11 | and is not restricted to printable characters.) | |
12 | ||
13 | Literals or match lengths are compressed with one Huffman tree, and | |
14 | match distances are compressed with another tree. The trees are stored | |
15 | in a compact form at the start of each block. The blocks can have any | |
16 | size (except that the compressed data for one block must fit in | |
17 | available memory). A block is terminated when deflate() determines that | |
18 | it would be useful to start another block with fresh trees. (This is | |
19 | somewhat similar to the behavior of LZW-based _compress_.) | |
20 | ||
21 | Duplicated strings are found using a hash table. All input strings of | |
22 | length 3 are inserted in the hash table. A hash index is computed for | |
23 | the next 3 bytes. If the hash chain for this index is not empty, all | |
24 | strings in the chain are compared with the current input string, and | |
25 | the longest match is selected. | |
26 | ||
27 | The hash chains are searched starting with the most recent strings, to | |
28 | favor small distances and thus take advantage of the Huffman encoding. | |
29 | The hash chains are singly linked. There are no deletions from the | |
30 | hash chains, the algorithm simply discards matches that are too old. | |
31 | ||
32 | To avoid a worst-case situation, very long hash chains are arbitrarily | |
33 | truncated at a certain length, determined by a runtime option (level | |
34 | parameter of deflateInit). So deflate() does not always find the longest | |
35 | possible match but generally finds a match which is long enough. | |
36 | ||
37 | deflate() also defers the selection of matches with a lazy evaluation | |
38 | mechanism. After a match of length N has been found, deflate() searches for | |
39 | a longer match at the next input byte. If a longer match is found, the | |
40 | previous match is truncated to a length of one (thus producing a single | |
41 | literal byte) and the process of lazy evaluation begins again. Otherwise, | |
42 | the original match is kept, and the next match search is attempted only N | |
43 | steps later. | |
44 | ||
45 | The lazy match evaluation is also subject to a runtime parameter. If | |
46 | the current match is long enough, deflate() reduces the search for a longer | |
47 | match, thus speeding up the whole process. If compression ratio is more | |
48 | important than speed, deflate() attempts a complete second search even if | |
49 | the first match is already long enough. | |
50 | ||
51 | The lazy match evaluation is not performed for the fastest compression | |
52 | modes (level parameter 1 to 3). For these fast modes, new strings | |
53 | are inserted in the hash table only when no match was found, or | |
54 | when the match is not too long. This degrades the compression ratio | |
55 | but saves time since there are both fewer insertions and fewer searches. | |
56 | ||
57 | ||
58 | 2. Decompression algorithm (inflate) | |
59 | ||
60 | 2.1 Introduction | |
61 | ||
62 | The real question is, given a Huffman tree, how to decode fast. The most | |
63 | important realization is that shorter codes are much more common than | |
64 | longer codes, so pay attention to decoding the short codes fast, and let | |
65 | the long codes take longer to decode. | |
66 | ||
67 | inflate() sets up a first level table that covers some number of bits of | |
68 | input less than the length of longest code. It gets that many bits from the | |
69 | stream, and looks it up in the table. The table will tell if the next | |
70 | code is that many bits or less and how many, and if it is, it will tell | |
71 | the value, else it will point to the next level table for which inflate() | |
72 | grabs more bits and tries to decode a longer code. | |
73 | ||
74 | How many bits to make the first lookup is a tradeoff between the time it | |
75 | takes to decode and the time it takes to build the table. If building the | |
76 | table took no time (and if you had infinite memory), then there would only | |
77 | be a first level table to cover all the way to the longest code. However, | |
78 | building the table ends up taking a lot longer for more bits since short | |
79 | codes are replicated many times in such a table. What inflate() does is | |
80 | simply to make the number of bits in the first table a variable, and set it | |
81 | for the maximum speed. | |
82 | ||
83 | inflate() sends new trees relatively often, so it is possibly set for a | |
84 | smaller first level table than an application that has only one tree for | |
85 | all the data. For inflate, which has 286 possible codes for the | |
86 | literal/length tree, the size of the first table is nine bits. Also the | |
87 | distance trees have 30 possible values, and the size of the first table is | |
88 | six bits. Note that for each of those cases, the table ended up one bit | |
89 | longer than the ``average'' code length, i.e. the code length of an | |
90 | approximately flat code which would be a little more than eight bits for | |
91 | 286 symbols and a little less than five bits for 30 symbols. It would be | |
92 | interesting to see if optimizing the first level table for other | |
93 | applications gave values within a bit or two of the flat code size. | |
94 | ||
95 | ||
96 | 2.2 More details on the inflate table lookup | |
97 | ||
98 | Ok, you want to know what this cleverly obfuscated inflate tree actually | |
99 | looks like. You are correct that it's not a Huffman tree. It is simply a | |
100 | lookup table for the first, let's say, nine bits of a Huffman symbol. The | |
101 | symbol could be as short as one bit or as long as 15 bits. If a particular | |
102 | symbol is shorter than nine bits, then that symbol's translation is duplicated | |
103 | in all those entries that start with that symbol's bits. For example, if the | |
104 | symbol is four bits, then it's duplicated 32 times in a nine-bit table. If a | |
105 | symbol is nine bits long, it appears in the table once. | |
106 | ||
107 | If the symbol is longer than nine bits, then that entry in the table points | |
108 | to another similar table for the remaining bits. Again, there are duplicated | |
109 | entries as needed. The idea is that most of the time the symbol will be short | |
110 | and there will only be one table look up. (That's whole idea behind data | |
111 | compression in the first place.) For the less frequent long symbols, there | |
112 | will be two lookups. If you had a compression method with really long | |
113 | symbols, you could have as many levels of lookups as is efficient. For | |
114 | inflate, two is enough. | |
115 | ||
116 | So a table entry either points to another table (in which case nine bits in | |
117 | the above example are gobbled), or it contains the translation for the symbol | |
118 | and the number of bits to gobble. Then you start again with the next | |
119 | ungobbled bit. | |
120 | ||
121 | You may wonder: why not just have one lookup table for how ever many bits the | |
122 | longest symbol is? The reason is that if you do that, you end up spending | |
123 | more time filling in duplicate symbol entries than you do actually decoding. | |
124 | At least for deflate's output that generates new trees every several 10's of | |
125 | kbytes. You can imagine that filling in a 2^15 entry table for a 15-bit code | |
126 | would take too long if you're only decoding several thousand symbols. At the | |
127 | other extreme, you could make a new table for every bit in the code. In fact, | |
128 | that's essentially a Huffman tree. But then you spend two much time | |
129 | traversing the tree while decoding, even for short symbols. | |
130 | ||
131 | So the number of bits for the first lookup table is a trade of the time to | |
132 | fill out the table vs. the time spent looking at the second level and above of | |
133 | the table. | |
134 | ||
135 | Here is an example, scaled down: | |
136 | ||
137 | The code being decoded, with 10 symbols, from 1 to 6 bits long: | |
138 | ||
139 | A: 0 | |
140 | B: 10 | |
141 | C: 1100 | |
142 | D: 11010 | |
143 | E: 11011 | |
144 | F: 11100 | |
145 | G: 11101 | |
146 | H: 11110 | |
147 | I: 111110 | |
148 | J: 111111 | |
149 | ||
150 | Let's make the first table three bits long (eight entries): | |
151 | ||
152 | 000: A,1 | |
153 | 001: A,1 | |
154 | 010: A,1 | |
155 | 011: A,1 | |
156 | 100: B,2 | |
157 | 101: B,2 | |
158 | 110: -> table X (gobble 3 bits) | |
159 | 111: -> table Y (gobble 3 bits) | |
160 | ||
161 | Each entry is what the bits decode to and how many bits that is, i.e. how | |
162 | many bits to gobble. Or the entry points to another table, with the number of | |
163 | bits to gobble implicit in the size of the table. | |
164 | ||
165 | Table X is two bits long since the longest code starting with 110 is five bits | |
166 | long: | |
167 | ||
168 | 00: C,1 | |
169 | 01: C,1 | |
170 | 10: D,2 | |
171 | 11: E,2 | |
172 | ||
173 | Table Y is three bits long since the longest code starting with 111 is six | |
174 | bits long: | |
175 | ||
176 | 000: F,2 | |
177 | 001: F,2 | |
178 | 010: G,2 | |
179 | 011: G,2 | |
180 | 100: H,2 | |
181 | 101: H,2 | |
182 | 110: I,3 | |
183 | 111: J,3 | |
184 | ||
185 | So what we have here are three tables with a total of 20 entries that had to | |
186 | be constructed. That's compared to 64 entries for a single table. Or | |
187 | compared to 16 entries for a Huffman tree (six two entry tables and one four | |
188 | entry table). Assuming that the code ideally represents the probability of | |
189 | the symbols, it takes on the average 1.25 lookups per symbol. That's compared | |
190 | to one lookup for the single table, or 1.66 lookups per symbol for the | |
191 | Huffman tree. | |
192 | ||
193 | There, I think that gives you a picture of what's going on. For inflate, the | |
194 | meaning of a particular symbol is often more than just a letter. It can be a | |
195 | byte (a "literal"), or it can be either a length or a distance which | |
196 | indicates a base value and a number of bits to fetch after the code that is | |
197 | added to the base value. Or it might be the special end-of-block code. The | |
198 | data structures created in inftrees.c try to encode all that information | |
199 | compactly in the tables. | |
200 | ||
201 | ||
202 | Jean-loup Gailly Mark Adler | |
203 | jloup@gzip.org madler@alumni.caltech.edu | |
204 | ||
205 | ||
206 | References: | |
207 | ||
208 | [LZ77] Ziv J., Lempel A., ``A Universal Algorithm for Sequential Data | |
209 | Compression,'' IEEE Transactions on Information Theory, Vol. 23, No. 3, | |
210 | pp. 337-343. | |
211 | ||
212 | ``DEFLATE Compressed Data Format Specification'' available in | |
213 | ftp://ds.internic.net/rfc/rfc1951.txt |