Problem

Input:alphabet ${1,…,n}$ and the frequencies $f_{1},…,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},…,c_{n}$ corresponding to each character, where $c_{i}∈{0,1}_{∗}$.

Solution space is given by the set of possible encodings $c_{1},…,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=i=1∑n f_{i}⋅∣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},…,f_{n}$, we want to construct a binary tree such that we minimize the following objective function:

$i=1∑n f_{i}⋅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:

- Any full binary tree with $≥2$ leaves must have 2 leaves such that they are siblings of the same parent at the deepest level.
- Suppose $OPT$ is a full binary tree that minimizes $f(OPT)$. Then, there must exist a $OPT_{′}$ 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(OPT)=f(OPT_{′})$.

Todo

I did not take notes for the proofs. Oops

We can construct a $OPT_{′}$ 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 $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,…,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∈K_{1}$ that minimizes

$f(T)=f_{n}⋅depth(n,T)+f_{n−1}⋅depth(n−1,T)+⋯+f_{1}⋅depth(1,T)$## Algorithm

Note that $π(n−1)=π(n)$, where $π(n)$ is the parent of node $n$.

- Set aside nodes $n$, $n−1$ where $f_{n}$ and $f_{n−1}$ have the smallest frequencies. Consider $π(n−1)$, which is the parent of the two nodes.
- Calculate $f_{π(n,n−1)}=f_{n}+f_{n+1}$.
- Recurse on the nodes $1,2,3,…,n−2,π(n,n−1)$, as well as the frequencies $f_{1},f_{2},…,f_{n−2},f_{π(n,n−1)}$.