Hi!
Welcome back to Data Structures and Algorithms class.
This is the last lecture, Huffman Tree and its Application in coding, for chapter 5 -- binary tree.
ASCII code is binary equal-length code
With single byte code for characters and Double byte code for Chinese.
Under equal-length condition, we actuallly assume that all characters will be used with same frequency.
For n different characters, we need log2n bits to coding them.
If characters are used with different frequency
equal-length code will waste space
Let's look at these characters
There are 8 characters
Character E, as a vowel, has high using frequency and Z has low using frequency
Equal-length coding is not a good deal
We hope high frequency characters have short code
to shorten total code length
Even low frequency characters have long code.
This strategy will decrease storage it needed
Our data is usually stored in external memory and need to transport on network
If we shorten the coding length, we can reduce time of visiting external memory
Visit external memory is much slower
than visit memory
Commonly, visit external memory takes 1 million times of time than visit memory
Space-time trade-off is different for external memory
We need to reduce space consuming meanwhile reduce time consuming
We want shorter code without losing of information to reduce time of visit external memory
For unequal-length code
We hope it is a prefix code, which is satisfied by equal-length code
For equal-length code, every code has same length
Thus no code is prefix of any other code
We want this feature for unequal-length code
Let's look at this coding strategy
They are coded based on binary tree path
Each codes ended on leaf nodes
Obviously, leaf nodes are not prefix of any other leaf nodes
We then get a prefix code. Here is the code table
For binary string "000110"
We can translate it into character string without ambiguous based on the code table
Let's look at another code
It seems shorter than previous one
But it is illegal and useless
We cannot use it to explain binary string
For instance, for binary string "000110"
there are lots of possibilities. Look at code C-0
0 exists in code of Z, code of K and code of E
Thus we don't know when to stop when translate binary into characters
So this is illegal
We already see this binary tree before, if we define left branch as 0 and right branch as 1
We can easily get code on leaf nodes
Huffman coding tree is a kind of binary tree with consideration of weights
We can construct code with minimum
summation of external path length
And we can get an unequal-length code
Basic idea of Huffman coding tree is that
for n characters
they have using frequency W0 to Wn-1
If we give out a coding strategy
With binary tree
codes in fact are external paths of each node
For a tree with paths weights equal to using frequencies
Minimum coding length means
minimum weighted summation of external paths
We need to construct such a coding tree
Obviously, bigger weight leaf is nearer to root
in order to get shorter code. smaller weight leaf is farer to root
And we can get the smallest summation of external paths binary tree
We can apply greedy strategy to construct such a tree
First, we sort all characters by their using frequencies, or say weights
Second, we take two smallest weight characters
combine them and get a new node
weight of the new node equals to summation of the original two nodes
We put this combined node back to characters
Repeat such a greedy procedure until all characters are processed
Let's look at an example. We take smallest two -- 2 and 3
We get a node with weight 5, and put it back as a sub-tree
Every other single nodes are sub-Huffman-trees as well
We combine those Huffman trees again and again
We take two smallest nodes now, they are 5 and 5
We get a node with weight 10
Continue, we take nodes with weights 10 and 7, combine
take 11 and 13, combine them as new sub-tree, repeat
until all nodes are processed
All characters are on leaf nodes. We then get a Huffman tree
How to get code from the Huffman tree? We can define
left branch as 0 and right branch as 1. Or you can use other definition
Such as inverse them, left as 1 and right as 0. This is just a personal style.
We put codes into a code table
When we need to encode characters
We look at the table directly
and get corresponding binary string
Let's see how to use the code table
We need to encode a character string
for instance, d0, d5 and d11
We put their codes together sequentially
And get corresponding binary string
When we need to decode a binary string
We read it from left to right
until a character is confirmed by read binary string
We find it from root
We we meet 0, we look into left branch, 1 for right branch until we meet a leaf node
Then we get a corresponding character
And we back to root, continue the procedure
Until the whole binary string is decoded
If this is a legal code, we can process it to end with nothing left
Let's see an example
Here is a binary string waiting for decoding
We visit the Huffman tree from root. Visit "111" and we get corresponding character -- d12
And we back to root
visit 10110 and we get corresponding character -- d12
We finish decoding by this way
If the binary string is legal
This will get to an end without inexplicable characters
Let's see how to realize it. Combination of two sub-tree is the name of the game.
Initially, we have n Huffman trees
We take out two trees with smallest weights and combine them
as a new tree. Then we reduce number of sub-trees by 1
Until we have only one sub-tree -- the Huffman tree
When we construct Huffman tree
We firstly put n sub-trees
into a minimum heap. Weight of sub-trees are using frequency of characters
When we finish build the heap
There are n Huffman Trees in the heap
We operate the heap n-1 times
each time
we take out two nodes from heap with minimum weights
And combine them, get a new tree with weight of summation of two sub-trees' weights
We insert this new tree
into the heap
The heap deleted 2 nodes and inserted 1 nodes, size of the heap decreased by 1
We do delete-combination-insert
n-1 times
And then we get a Huffman tree, or say, the wanted coding tree
Let's proof correctness of Huffman Tree
First, we need to see whether Huffman code is prefix code
Is there any node stands for character
is prefix of any other code node
Obviously it isn't. Because each code is ended on leaf node
Leaf node cannot be prefix of any other node. Thus, this is prefix node
And we need to proof the construction can get the best coding strategy
We proof the greedy condition
We need to proof each step of construction
we take two smallest weight trees and combine them get a new one is correct
we can get the best choice. This is the optimal structure.
Based on such feature, we discuss whether we can get best solution for whole problem
Here is a lemma
For a Huffman tree with more than 2 nodes
The lowest two using frequency characters are brothers
and their depth is no sallower than any other node
In another word, they are in the deepest level.
There may have other nodes in the same level, but no node have deeper depth
Assume y1 and y2 are nodes
with the smallest weights
The father of them is y, with weight of their summation
If there is a node x with child x1 and x2
Obviously, weight of x is no less than weight of y
When we construct Huffman tree with node y
We will choose node y first but not node x
because y has smaller weight
Thus, following condition is impossible
x is deeper than y, is impossible. weight of x is no less than weight of y, x should be shallower than x
Let's see the optimal structure
Huffman tree can get a structure with minimum summation of external paths' weights.
We proof it with induction.
Initially, when n equals to 2
We get a tree with minimum summation of external paths' weights
under such condition, it has only two possibilities
w1 on the left, w0 on the right or w0 on the left and w1 on the right
They have same summation of weighted paths' weights
If we can use Huffman tree get a structure
with minimum summation of external weights
for n-1 leaf nodes
we then use inductive method for n nodes
we assume weight of n nodes are w0 to wn-1
which are sorted, w0 and w1 are the smallest two
We apply Huffman coding tree to those nodes
w0 and w1 will be chosen first
they combined and get a bigger sub-tree v, v is their father
According to the lemma, v is the deepest father in Huffman tree
And correspondingly, w0 and w1
are the deepest two leaf nodes
we substitute v with a leaf node v'
weight of v' is summation of w0 and w1
We get another tree T' with n-1 nodes
According to our induction hypothesis, T' has minimum external paths length
We expand V' as w1 and w1
After the expansion
T' is reduced to T
And we then proof that T has the minimum external paths length
Based on such induction, we proved the theorem, Huffman tree can get the best coding.
Let's see efficiency of Huffman code
estimate how much space is saved by Huffman tree
We are assume in character set
each character has length Ci and frequency Pi
The expectation of code length is ΣCiPi
We can also express this by times of use
for each character and in total
For such a coding tree, we get the average code length is 3.38
If we apply equal length code to
this 13 characters set
we need code length of Ceil of log of 13 to the base 2, 4 bits
Thus, Huffman code only needs
84% space of equal-length code
We increase time efficient meanwhile
Because encoded string is stored in external memory
or transport on network. If we need more space for same information
we also need more time to get information
Huffman tree best fits unequal frequencies character set
And widely applied on data communication, file compression.
It is also applied on external sorting. We usually see zip file
compress file with Huffman and other compression algorithms
Here are some reflects on what we see. Binary tree can extend to b-tree( ternary tree, quadtree or octree )
b-tree has b children for each node. We may cannot construct full b-tree
Thus we need some virtual nodes
to construct full b-tree
We need some node with weight 0 to construct full b-tree
So, we need how many virtual nodes?
Please prove your answer.
Of course node with weight 0 will be in the deepest level
the leaf level
You can also research on how Huffman Tree applied on compression software
Thank you