Coding theory (Huffman coding)

Problem

Input: alphabet $\{1,\dots ,n\}$ and the frequencies $f_1,\dots ,f_n$ at which each letter occurs.

Output: a prefix-free (no two codes share the same code sequence) code made up of $c_1,c_2,\dots ,c_n$ corresponding to each character, where $c_i\in \{0,1{\}}^{\ast }$.

Solution space is given by the set of possible encodings $c_1,\dots ,c_n$ for the alphabet. We are trying to minimize the cost of the encoding by considering the different frequencies in the alphabet. This is captured by the following objective function:

$$f=\sum _{i=1}^n{f}_i\cdot |c_i|$$

Optimizing over binary trees

This is related to creating an Optimal static binary search tree.

Assume we have a coding for the alphabet. We can construct a binary tree where the left branch corresponds to a $0$ and the right branch corresponds to a $1$. Keep adding nodes for every digit. The coding is prefix-free, so the leaves of this tree correspond to unique characters in the alphabet.

Therefore, we can reframe the problem as such: given the frequencies of each character $f_1,\dots ,f_n$, we want to construct a binary tree such that we minimize the following objective function:

$$\sum _{i=1}^n{f}_i\cdot \text{depth}(i,T)$$

This is because the depth of a character $i$ in the tree corresponds to the length of the encoding for it. To optimize the tree, it should be “full,” meaning all internal nodes have 2 children (otherwise, we can replace the leaf with its parent and still have a prefix-free coding).

Two properties about the optimal solutions

Here, we break our proof of correctness down into two parts. We want to prove the following two facts:

1. Any full binary tree with $\ge 2$ leaves must have 2 leaves such that they are siblings of the same parent at the deepest level.
2. Suppose $\text{OPT}$ is a full binary tree that minimizes $f(\text{OPT})$. Then, there must exist a ${\text{OPT}}^{\prime }$ such that $f_n$ and $f_{n-1}$ (the frequencies of two characters) are the smallest and their corresponding leaves appear as siblings in the deepest node. Furthermore, $f(\text{OPT})=f({\text{OPT}}^{\prime })$.

Todo

I did not take notes for the proofs. Oops

We can construct a ${\text{OPT}}^{\prime }$ by swapping the two nodes at the deepest level with $n$ and $n-1$, which are guaranteed to exist by fact 1, thereby proving fact 2.

Narrowing the solution space

Proving these two facts allows us to restrict the solution space that our exchange argument needs to travel through to get from $\text{OPT}$ to $G$, our greedy solution.

In particular, let $K_1$ be the set of solutions that are full binary trees where the leaves $1,\dots ,n$ have characters $n,n-1$ as siblings in the deepest node. We will only need to look at these solutions, simplifying our argument.

Then we can reframe the optimization problem again: we want to output a full binary tree $T\in K_1$ that minimizes

$$f(T)=f_n\cdot \text{depth}(n,T)+f_{n-1}\cdot \text{depth}(n-1,T)+\cdots +f_1\cdot \text{depth}(1,T)$$

Algorithm

Note that $\pi (n-1)=\pi (n)$, where $\pi (n)$ is the parent of node $n$.

1. Set aside nodes $n$, $n-1$ where $f_n$ and $f_{n-1}$ have the smallest frequencies. Consider $\pi (n-1)$, which is the parent of the two nodes.
2. Calculate $f_{\pi (n,n-1)}=f_n+f_{n+1}$.
3. Recurse on the nodes $1,2,3,\dots ,n-2,\pi (n,n-1)$, as well as the frequencies $f_1,f_2,\dots ,f_{n-2},f_{\pi (n,n-1)}$.