Download "user manual"

Figure C.1– Huffman tree for the sequence abracadabra
This node will be the root of the tree. After the tree building process we
create the code for a given symbol, starting from the root and moving
towards the leaf corresponding to the symbol, starting with an empty code,
and whenever we go to a left son, we append 0 to it, whenever we go to a
right son, we append 1. When we arrive to the leaf, the code for the symbol
is ready.
This procedure is repeated for all symbols. Figure C.1 illustrates an example
of the Huffman tree and the codes for symbols after processing a sequence
abracadabra (a very classic word used in compression examples).
While building the tree, if there are two nodes with the same frequency we
can choose any of them thus means that there are more than one possible
Huffman tree for our data.
Although the Huffman coding is simple, rebuilding the tree after processing
each character is quite complicated. It was shown by Gallager that its
maximum inefficiency, (the maximum difference between the expected
code length and the optimum) is bounded by:
(C.3)
p m + log 2
2 log 2 e
≈ p m + 0,086
e
where pm is the probability of occurrence of the most frequent symbol.
248