= Deflate Huffman coding
{c}
For a compressed block, <Deflate Huffman coding> uses one <alphabet> for <Deflate literal bytes>, length symbols and the end-of-block symbol, and another <alphabet> for distance symbols. Values 0 through 255 denote <Deflate literal bytes>, 256 ends the block, and 257 through 285 select lengths. A <Deflate backreference> is encoded as a length symbol, any length extra <bits>, a distance symbol, then any distance extra <bits>. Those extra <bits> select an offset within the symbol's prescribed range; they are not additional <codewords>.<DEFLATE Compressed Data Format Specification version 1.3 by L. Peter Deutsch>[RFC 1951, section 3.2.5, length and distance tables]{ref}
In the illustrative $(9,3)$ <Deflate backreference>, length 9 uses symbol 263 and distance 3 uses symbol 2; neither needs extra <bits>. Under the fixed <Huffman codes>, `A`, `B` and `C` each cost eight <bits>, symbol 263 costs seven, and distance symbol 2 costs five. Adding the seven-<bit> end-of-block symbol and three-<bit> block header gives $3+3\cdot8+7+5+7=46$ <bits>, packed into six <bytes> for a single final block. This is a cost calculation for the explicitly chosen instructions, not a displayed compressed stream.<DEFLATE Compressed Data Format Specification version 1.3 by L. Peter Deutsch>[RFC 1951, sections 3.2.5 and 3.2.6: length 9, distance 3 and fixed code lengths]{ref}
Dynamic blocks transmit <codeword lengths> from which the decoder reconstructs the prescribed <prefix codes>. The code descriptions themselves use a smaller <Huffman code> and repeat instructions for successive <codeword lengths>, including runs of zero lengths. Here <run-length encoding> describes repeated code lengths, a separate role from copying repeated data <bytes>. Fixed blocks use predefined <Huffman codes> and avoid transmitting those descriptions.<DEFLATE Compressed Data Format Specification version 1.3 by L. Peter Deutsch>[RFC 1951, sections 3.2.2, 3.2.6 and 3.2.7: code reconstruction, fixed codes and dynamic code-length repeats]{ref}
Back to article page
