How Deflater works (ctd)

Huffman encoding works on a stream of bits. It takes an "alphabet" of symbols (for example, the possible "symbols" could be the bytes 0-255, but it could be some arbitrary range of numbers/values), and re-codes each symbol in the alphabet as a sequence of bits, so that the sequence corresponding to each symbol reflects the frequency of that symbol. The most frequently occurring symbol will be represented by the shortest bit sequence, and with the length of each bit sequence being roughly inversely proportional to its frequency.

Possible Huffman encodings can be worked out by creating a "Huffman tree" as follows:

• Start with a list of "nodes" consisting of the symbols and their frequencies.
• Create a new node connecting the two least frequently occurring symbols.
• Label the branches with 0 and 1 (adopting some convention for whether the branch to the least or most frequent symbol gets 0): in this example, we'd connect A and C first.
• The newly created node gets a frequency which is the sum of the frequencies of the two children: in this case it would be 2+3=5 (Fig 1).
• Repeat these steps until you end up with a single node which is the "root" of the tree. So first we'd connect the newly created node with B (5 and 9 are still the lowest frequencies), as in Fig 2; Fig 3 shows the completed tree.
• Start at the root and trace down the branches until you get to a "leaf" node with one of the symbols: the sequence of 0s and 1s on the branches that you passed on the way give the sequence for encoding that symbol. So in Fig 3, tracing from the root to the symbol B gives a code of 01; C will have a code of 000; D, the most frequently occurring symbol, will have a single-bit code, 1.