542
Graphs and Trees
Suppose a code tree T exists, with leaves representing characters. For any
leaf i, its depth d(i) in T equals the number of bits in the code for the corresponding character. Let f(i) denote the percentage frequency of that character
in the data to be stored, and let S be the total number of characters to be stored.
Then, just as in Example 37, the total number of bits required is given by the
expression
S * c ∙
all leaves i
(d(i)f(i)) d
We seek to build an optimal tree T, one for which the expression
E(T ) = c ∙
all leaves i
(d(i)f(i)) d
(1)
is a minimum and hence the file size is a minimum.
This process could be done by trial and error, because there is only a finite
number of characters and thus only a finite number of ways to construct a tree and
assign characters to its leaves. However, the finite number quickly becomes very
large! Instead we will use the algorithm known as huffman encoding.
huffman encoding algorithm
Suppose, then, that we have m characters in a file and we know the percentage
frequency of each character. The algorithm to build the tree works by maintaining a list L of nodes that are roots of binary trees. Initially L will contain m roots,
each labeled with the frequency of one of the characters; the roots will be ordered
according to increasing frequency, and each will have no children. A pseudocode
description of the algorithm follows.
alGoritHm Huffmantree
HuffmanTree (node list L; integer m)
//Each of the m nodes in L has an associated frequency f, and L is
//ordered by increasing frequency; algorithm builds the Huffman tree
for (i = 1 to m − 1) do
create new node z
let x, y be the first two nodes in L
//minimum frequency nodes
f(z) = f(x) + f( y)
insert z in order into L
left child of z = node x
right child of z = node y
//x and y are no longer in L
end for
end HuffmanTree
Graphs and Trees
Suppose a code tree T exists, with leaves representing characters. For any
leaf i, its depth d(i) in T equals the number of bits in the code for the corresponding character. Let f(i) denote the percentage frequency of that character
in the data to be stored, and let S be the total number of characters to be stored.
Then, just as in Example 37, the total number of bits required is given by the
expression
S * c ∙
all leaves i
(d(i)f(i)) d
We seek to build an optimal tree T, one for which the expression
E(T ) = c ∙
all leaves i
(d(i)f(i)) d
(1)
is a minimum and hence the file size is a minimum.
This process could be done by trial and error, because there is only a finite
number of characters and thus only a finite number of ways to construct a tree and
assign characters to its leaves. However, the finite number quickly becomes very
large! Instead we will use the algorithm known as huffman encoding.
huffman encoding algorithm
Suppose, then, that we have m characters in a file and we know the percentage
frequency of each character. The algorithm to build the tree works by maintaining a list L of nodes that are roots of binary trees. Initially L will contain m roots,
each labeled with the frequency of one of the characters; the roots will be ordered
according to increasing frequency, and each will have no children. A pseudocode
description of the algorithm follows.
alGoritHm Huffmantree
HuffmanTree (node list L; integer m)
//Each of the m nodes in L has an associated frequency f, and L is
//ordered by increasing frequency; algorithm builds the Huffman tree
for (i = 1 to m − 1) do
create new node z
let x, y be the first two nodes in L
//minimum frequency nodes
f(z) = f(x) + f( y)
insert z in order into L
left child of z = node x
right child of z = node y
//x and y are no longer in L
end for
end HuffmanTree