INFOTH Note 7: Huffman & Arithmetic Coding

7.1 Huffman Coding

The Algorithm

For a distribution (of appearance) $(p(x),x\in\mathcal X)$,

1. Sort the probability vector $\bold p$ in decreasing order,
2. “Merge” the two smallest probabilities,
3. Reorder (sort again) and go back to merging.

How to merge: assume we have 2 “symbols” now, say $a,b$

1. Generate a node $ab$ which has 2 children $a$ and $b$
2. Assign (e.g.) 0 to $a$ and $1$ to $b$ (to the edges)

Finally, we will get a Huffman tree, where each path from the root (all symbols) to a leaf (one symbol) is the codeword for that symbol.

Thus we get a prefix-free code.

Proof of Optimality

Optimality: Huffman Coding actually is a solution to minimize the expected length.

Proof.

1. In any optimal prefix-free code $c$, if $p(x)>p(x')$, then $l (c(x))\le l (c(x'))$ (the more probable one with less length)

   • If not, exchange $c(x)$ and $c(x')$ and get a strictly better code

2. There are at least 2 codewords having maximum length in the optimal code $c$.

   • If there is a unique $x$ with $l(c(x))=l_{max}=\max(l(c(y)),y\in\mathcal X)$

   • We can replace $c(x)$ by its prefix dropping the last bit, still making the code prefix free and strictly better than previous

From 2, we can assume that the codewords corresponding to two lowest-probability symbols (not necessarily the same probability) differ only in that last bit.

7.2 Arithmetic Coding

Sequential Property: Dynamic Update

Unlike Huffman Code which needs to build a codebook (map), in Arithmetic Code, we can sequentially code: We don’t map symbols to 0,1.

We can also keep decoding when the code sequence is still growing.

The Algorithm

Assume we have known the probabilities and $X_1,X_2,\dots$ are i.i.d. $p$.

We build an order for $\mathcal X$ hence we can compare sequences.

Define the CDF

for a length $n$, and we assign the block $\bold x^n$ an interval: $[F(\bold x^n)-p(\bold x^n), F(\bold x^n))\subseteq [0,1]$.

To encode a $n$-length block, we can finally choose any point in this interval such as the midpoint $\bar F(\bold x^n)$, and write the chosen [0,1] number as binary: $0.\overline{b_1b_2b_3\dots}$; the $b$’s is the codeword.

Dynamically Encoding

1. Seeing every new symbol, we partition our current interval w/ the probabilities and update the current interval as the corresponding part of the current interval.
2. Iterate.
3. Binary representation.

For example, we have $p(A)=0.5,p(B)=0.3,p(C)=0.2$. Encode AB

1. [0,0.5) for A, [0.5,0.8) for B, [0.8,1) for C.

   Seeing A. Enter [0,0.5).

2. [0.0.25) for A. [0.25,0.4) for B. [0.4,0.5) for C.

   Seeing B. Enter [0.25,0.4).

3. Choose one such as (0.25+0.4)/2, find the binary.

Properties

• Although it’s not optimal for any fixed blocked length $n$, it’s dynamic.
• The dynamically generated block codewords are prefix-free.

Finally, we have the length