Lossless Compression Handbook

86 PART II/COMPRESSION TECHNIQUES

as the sum of the probabilities of the leaves it supports. Capocelli

et aL

[6] give bounds for a code

2

where ~ < Pmax < 4 with no other information on the other

pi,as

well as bounds for 1 <

Pmax ~

4

and for distributions for which only

Pmax

and

Pmin are

known. Buro [7], under the assumption that

P(ai) ~ 0

for all symbols and that Eq. (4.1) holds, characterizes the maximum expected length

in terms of ~b, the golden ratio!

Digression 4.1.

Although we have shown that the average length of Huffman codes are generally

quite close to the entropy of a given random source X, we have not seen how long an individual ...