Lines Matching +full:symbol +full:- +full:tree

4 LZ77 (Lempel-Ziv 1977, see reference below). It finds duplicated strings in
13 Literals or match lengths are compressed with one Huffman tree, and
14 match distances are compressed with another tree. The trees are stored
19 somewhat similar to the behavior of LZW-based _compress_.)
32 To avoid a worst-case situation, very long hash chains are arbitrarily
83 For inflate, which has 286 possible codes for the literal/length tree, the size
94 Ok, you want to know what this cleverly obfuscated inflate tree actually
95 looks like.  You are correct that it's not a Huffman tree.  It is simply a
96 lookup table for the first, let's say, nine bits of a Huffman symbol.  The
97 symbol could be as short as one bit or as long as 15 bits.  If a particular
98 symbol is shorter than nine bits, then that symbol's translation is duplicated
99 in all those entries that start with that symbol's bits.  For example, if the
100 symbol is four bits, then it's duplicated 32 times in a nine-bit table.  If a
101 symbol is nine bits long, it appears in the table once.
103 If the symbol is longer than nine bits, then that entry in the table points
105 entries as needed.  The idea is that most of the time the symbol will be short
113 the above example are gobbled), or it contains the translation for the symbol
118 longest symbol is?  The reason is that if you do that, you end up spending
119 more time filling in duplicate symbol entries than you do actually decoding.
121 kbytes.  You can imagine that filling in a 2^15 entry table for a 15-bit code
124 that's essentially a Huffman tree.  But then you spend too much time
125 traversing the tree while decoding, even for short symbols.
154 110: -> table X (gobble 3 bits)
155 111: -> table Y (gobble 3 bits)
183 compared to 16 entries for a Huffman tree (six two entry tables and one four
185 the symbols, it takes on the average 1.25 lookups per symbol.  That's compared
186 to one lookup for the single table, or 1.66 lookups per symbol for the
187 Huffman tree.
190 meaning of a particular symbol is often more than just a letter.  It can be a
193 added to the base value.  Or it might be the special end-of-block code.  The
198 Jean-loup Gailly        Mark Adler
206 pp. 337-343.