Lesson 7

Let us consider a prefix code. Without loss of generality, assume that the corresponding tree is strictly binary: each node has either zero or two children (if there is a node with exactly one child, the code can obviously be improved). In this tree, the original symbols are located in the leaves. Let us also assign their frequencies \(p_{i}\) to these leaves. Then the redundancy coefficient can be written as: \[\sum_{i=1}^{n}p_{i}l_{i}=\sum_{i=1}^{n}p_{i} \cdot (\text{depth of leaf \(a_{i}\)}) \ .\] Now we do the following trick: going up from the leaves, write in each internal node the sum of the frequencies of its two children; do this for all internal nodes except the root.

The resulting tree has a simple but useful property: the redundancy coefficient of the code equals the sum of all numbers in the tree’s nodes. Indeed, each \(p_{i}\) appears in this sum exactly \(l_{i}\) times. This observation allows us to write a simple and efficient algorithm for constructing a prefix code with minimum redundancy. We only need to observe the following: let \(p_{1}, p_{2}\) be the two smallest frequencies (\(p_{1},p_{2} \le p_{3}, \dotsc, p_{n}\)); then there exists an optimal prefix code where \(p_{1}\) and \(p_{2}\) are the deepest sibling leaves. Indeed, any strictly binary tree has a pair of deepest sibling leaves. If these are not \(p_{1}, p_{2}\), we can swap them without worsening the code. The parent of the sibling leaves \(p_{1}, p_{2}\) is labeled \(p_{1}+p_{2}\). If we cut off the nodes \(p_{1}\) and \(p_{2}\), we get a tree whose leaves are \(p_{1}+p_{2}, p_{3}, \dotsc, p_{n}\), and it must be optimal! Thus, we reduce the problem to the same subtask.

This leads us to the following algorithm. Choose the two minimum frequencies \(p_{i}\) and \(p_{j}\), create two leaves labeled \(p_{i}\) and \(p_{j}\), and a parent labeled \(p_{i}+p_{j}\); replace \(p_{i}\) and \(p_{j}\) with \(p_{i}+p_{j}\). Repeating this \(n-1\) times, we build the optimal tree bottom-up. Since each iteration requires finding the minimum in a (changing) set, we use a heap to implement a priority queue. The runtime of the corresponding algorithm is \(O(n \log n)\).

from collections import namedtuple
from heapq import heappush, heappop
import networkx as nx

Element = namedtuple('Element', ['frequency', 'index'])


def huffman_code(p):
    assert sum(p) == 1.0

    tree = nx.DiGraph()

    heap = []
    for i in range(len(p)):
        heappush(heap, Element(p[i], i))

    for k in range(len(p), 2 * len(p) - 1):
        smallest = heappop(heap)
        second = heappop(heap)
        heappush(heap, Element(smallest.frequency + second.frequency, k))
        tree.add_edge(k, smallest.index)
        tree.add_edge(k, second.index)

    tree = nx.nx_agraph.to_agraph(tree)
    tree.layout(prog='dot')
    tree.draw("huffman_tree.png")


huffman_code((0.05, 0.2, 0.3, 0.27, 0.11, 0.07))