Editing Deflate (section)

=== Bit reduction ===
{{Further|Huffman coding}}
The second compression stage consists of replacing commonly used symbols with shorter representations and less commonly used symbols with longer representations. The method used is [[Huffman coding]] which creates an unprefixed tree of non-overlapping intervals, where the length of each sequence is inversely proportional to the logarithm of the probability of that symbol needing to be encoded. The more likely it is that a symbol has to be encoded, the shorter its bit-sequence will be.

A tree is created, containing space for 288 symbols:
* 0–255: represent the literal bytes/symbols 0–255.
* 256: end of block – stop processing if last block, otherwise start processing next block.
* 257–285: combined with extra-bits, a match length of 3–258 bytes.
* 286, 287: not used, reserved and illegal but still part of the tree.

A match length code will always be followed by a distance code. Based on the distance code read, further "extra" bits may be read in order to produce the final distance. The distance tree contains space for 32 symbols:
* 0–3: distances 1–4
* 4–5: distances 5–8, 1 extra bit
* 6–7: distances 9–16, 2 extra bits
* 8–9: distances 17–32, 3 extra bits
* ...
* 26–27: distances 8,193–16,384, 12 extra bits
* 28–29: distances 16,385–32,768, 13 extra bits
* 30–31: not used, reserved and illegal but still part of the tree

For the match distance symbols 2–29, the number of extra bits can be calculated as <math>\left\lfloor\frac{n}{2}\right\rfloor-1</math>.

The two codes (the 288-symbol length/literal tree and the 32-symbol distance tree) are themselves encoded as [[canonical Huffman code]]s by giving the bit length of the code for each symbol. The bit lengths are themselves [[Run-length encoding|run-length encoded]] to produce as compact a representation as possible. As an alternative to including the tree representation, the "static tree" option provides standard fixed Huffman trees. The compressed size using the static trees can be computed using the same statistics (the number of times each symbol appears) as are used to generate the dynamic trees, so it is easy for a compressor to choose whichever is smaller.