Correctness of Huffman's algorithm

 First of all, I would like to give a bit of context and explain my motivation behind this article. I have gone through the book [1] and found that the proof of correctness is a bit less informative and making it a bit more hard for a reader to understand on their own. Then I checked some other lecture slides, materials and unfortunately found none of them helpful in understanding the proof easily. The first part of the proof, which is Lemma 16.2 is much better and has some illustrations to assist readers, hence I don’t think it requires more explanation. But the last part which is Lemma 16.3 lacks the required details, hence I thought of adding them here to assist other readers because I don’t want them to spend their time going through the painstaking process which I had when I was first reading the proof.

Lemma 16.3

Let $C$ be a given alphabet with frequency $c.freq$ defined for each character $c \in C$. Let $x$ and $y$ be two characters in $C$ with minimum frequency. Let $C^\prime$ be the alphabet $C$ with the characters $x$ and $y$ removed and a new character $z$ added, so that $C^\prime = C - \{x, y\}\; \cup \; \{z\}$. Define freq for $C^\prime$ as for $C$, except that $z.freq = x.freq + y.freq$. Let $T^\prime$ be any tree representing an optimal prefix code for the alphabet $C^\prime$. Then the tree $T$, obtained from $T^\prime$ by replacing the leaf node for $z$ with an internal node having $x$ and $y$ as children, represents an optimal prefix code for the alphabet $C$. 

Proof

We first show how to express the cost $B(T)$ of tree $T$ in terms of the cost $B(T^\prime)$ of the tree $T^\prime$, by considering the component costs in equation (16.4). Let’s first consider the two trees $T$ and $T^\prime$ with some sample alphabet for each represented by $C$ and $C^\prime$ respectively.

$C = \{f: 5,\; e: 9,\; c: 12,\; b: 13,\; d: 16,\; a: 45\}$  
$C^\prime = \{c: 12,\; b: 13,\; g: 14,\; d: 16,\; a: 45\}$

Now, let’s draw the two trees for the above two alphabet, denoted by $T$ and $T^\prime$ respectively. 


 



Now note that our $f$ and $e$ characters are equivalent to $x$ and $y$ in the general case respectively and our character $g$ is equivalent to the character $z$ in the general case.

For each character $c\; \in\; C - \{x,\; y\}$, we have that $d_T(c) = d_{T^\prime}(c)$, and hence $c.freq \cdot d_T(c) = c.freq \cdot d_{T^\prime}(c)$. Putting this into our instance, we have, $c\; \in\; C - \{f,\; e\} \equiv \{c, b, d, a\}$ and you may see that the depth of those characters are the same in both the trees $T$ and $T^\prime$ respectively. Also note that, $d_T(x) = d_T(y) = d_{T^\prime}(z) + 1$ is equivalent to $d_T(f) = d_T(e) = d_{T^\prime}(g) + 1$ in our instance.

Now we can obtain $T$ from the tree $T^\prime$ just by making the leaf node $g$ an internal node, and then adding $f$ and $e$ as it’s children. This is equivalent to changing the leaf node $z$ in $T^\prime$ into an internal node in $T$ and then adding $x$ and $y$ as it’s children in the general case.  

Now, we define the cost of the tree $T$ as,
$$B(T) = \sum_{c \in C}c.freq \cdot d_T(c)$$
Now the tree $T$, obtained from $T^\prime$ by inserting two characters $f$ and $e$ and then removing the character $g$. You may realize this if you compare the alphabet $C$ and $C^\prime$. This is equivalent to adding two characters $x$ and $y$ and then removing the character $z$ in our more general case. Now, using the above equation, we can write down the cost functions for two trees as  follows. Note that here after I’ll only consider the general case.

$$B(T) = B(T^\prime) + x.freq \cdot d_T(x) + y.freq \cdot d_T(y) - z.freq \cdot d_{T^\prime}(z)$$
$$x.freq \cdot d_T(x) + y.freq \cdot d_T(y) = (x.freq + y.freq) \cdot d_T(x) = (x.freq + y.freq) \cdot (d_{T^\prime}(z) + 1)$$
$$x.freq \cdot d_T(x) + y.freq \cdot d_T(y) = z.freq \cdot d_{T^\prime}(z) + x.freq + y.freq$$
$$B(T) = B(T^\prime) + x.freq + y.freq$$
$$B(T^\prime) = B(T) - x.freq - y.freq$$

We now prove the lemma by contradiction. Suppose that $T$ does not represent an optimal prefix code for $C$. Then there exists an optimal tree $T^{\prime\prime}$ such that $B(T^{\prime\prime}) \lt B(T)$. Without loss of generality (by Lemma 16.2), $T^{\prime\prime}$ has $x$ and $y$ as siblings. Let $T^{\prime\prime\prime}$ be the tree $T^{\prime\prime}$ with the common parent of $x$ and $y$ replaced by a leaf $z$ with frequency $z.freq = x.freq + y.freq$. Then

$$B(T^{\prime\prime \prime}) = B(T^{\prime \prime}) - x.freq - y.freq$$
$$B(T^{\prime\prime \prime}) \lt B(T) - x.freq - y.freq$$
$$B(T^{\prime\prime \prime}) \lt B(T^\prime)$$

yielding a contradiction to the assumption that $T^\prime$ represents an optimal prefix code for  $C^\prime$. Thus, $T$ must represent an optimal prefix code for the alphabet $C$. 

Conclusion

Now, given that $T^\prime$ is an optimal code tree for  $C^\prime$ which is $n - 1$ in size, we can conclude that $T$ yields an optimal tree for the alphabet $C$ of size $n$. And this proves the optimal substructure property of Huffman's algorithm.

References

[1] https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844

Comments

Post a Comment

Popular posts from this blog

Introducing Java Reactive Extentions in to a SpringBoot Micro Service

Image
Introduction Today we are going to take a look at Reactive Programming using Java8 and RxJava, which is a library for composing asynchronous and event-based programs by using observable sequences. RxJava stands for Reactive Extensions for the JVM. It extends the observer pattern [Gamma95] to support sequences of data/events and adds operators that allow you to compose sequences together declaratively while abstracting away concerns about things like low-level threading, synchronization, thread-safety and concurrent data structures [1]. Pre-Requisites : Having a good knowledge about Java8, Functional Programming and spring boot microservices. What is Reactive programming? In essence, Reactive programming is an asynchronous programming paradigm concerned with data streams. The system time, a list of entries from the DB/API, user clicks, everything can be a stream of data. Data from different streams can easily be combined and transformed, and in the end processed/observed by the
Read more

Optimal binary search trees

Image
Suppose that we are designing a program to translate text from English to French. For each occurrence of each English word in the text, we need to look up its French equivalent. We could perform these lookup operations by building a binary search tree with $n$ English words as keys and their French equivalents as satellite data. Because we will search the tree for each individual word in the text, we want the total time spent searching to be as low as possible. We could ensure an $Θ(log_2 \;n)$ search time per occurrence by using a red-black tree or any other balanced binary search tree. Words appear with different frequencies, however, and a frequently used word such as the may appear far from the root while a rarely used word appears near the root. Such an organization would slow down the translation, since the number of nodes visited when searching for a key in a binary search tree equals one plus the depth of the node containing the key. We want words that occur frequently in the t
Read more

Edit distance

Image
Biological applications often need to compare the DNA of two (or more) different organisms. A strand of DNA consists of a string of molecules called bases, where the possible bases are adenine, guanine, cytosine, and thymine. Representing each of these bases by its initial letter, we can express a strand of DNA as a string over the finite set $\{A, C, G, T\}$. For example, the DNA of one organism may be $S1 = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA$, and the DNA of another organism may be $S2 = GTCGTTCGGAATGCCGTTGCTCTGTAAA$. One reason to compare two strands of DNA is to determine how “similar” the two strands are, as some measure of how closely related the two organisms are. We can, and do, define similarity in many different ways. For example, we can say that two strands are similar if the number of changes needed to turn one into the other is small. [1] We formalize this notion of similarity in our Edit distance problem. 15-5 Edit distance - Problem Statement In order to transform one sour
Read more