Lines Matching +full:lookup +full:- +full:table

4 LZ77 (Lempel-Ziv 1977, see reference below). It finds duplicated strings in
19 somewhat similar to the behavior of LZW-based _compress_.)
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
32 To avoid a worst-case situation, very long hash chains are arbitrarily
53 are inserted in the hash table only when no match was found, or
67 inflate() sets up a first level table that covers some number of bits of
69 stream, and looks it up in the table.  The table will tell if the next
71 the value, else it will point to the next level table for which inflate()
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 then
84 of the first table is nine bits.  Also the distance trees have 30 possible
85 values, and the size of the first table is six bits.  Note that for each of
86 those cases, the table ended up one bit longer than the ``average'' code
92 2.2 More details on the inflate table lookup
96 lookup table for the first, let's say, nine bits of a Huffman symbol.  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
104 to another similar table for the remaining bits.  Again, there are duplicated
106 and there will only be one table look up.  (That's whole idea behind data
112 So a table entry either points to another table (in which case nine bits in
117 You may wonder: why not just have one lookup table for how ever many bits the
121 kbytes.  You can imagine that filling in a 2^15 entry table for a 15-bit code
123 other extreme, you could make a new table for every bit in the code.  In fact,
127 So the number of bits for the first lookup table is a trade of the time to
128 fill out the table vs. the time spent looking at the second level and above of
129 the table.
146 Let's make the first table three bits long (eight entries):
154 110: -> table X (gobble 3 bits)
155 111: -> table Y (gobble 3 bits)
158 many bits to gobble.  Or the entry points to another table, with the number of
159 bits to gobble implicit in the size of the table.
161 Table X is two bits long since the longest code starting with 110 is five bits
169 Table Y is three bits long since the longest code starting with 111 is six
182 be constructed.  That's compared to 64 entries for a single table.  Or
184 entry table).  Assuming that the code ideally represents the probability of
186 to one lookup for the single table, or 1.66 lookups per symbol for the
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.