Let $\{w_i\}_{i=1}^n$ be an optimal code such that $\{p_i\}_{i=1}^n$ are words' probability.prove $p_i=p_j \implies |w_i|-|w_j|\leq1$.

Question

Let $\{w_i\}_{i=1}^n$ be an optimal code such that $\{p_i\}_{i=1}^n$ are words' probability.

I have to prove the fact that $p_i=p_j \implies |w_i|-|w_j|\leq1$.

I read about binary Huffman codes and I know how to use this method, but I still have no idea how to approach this problem.

Any help is welcome.

Thanks !

Answer 1

Greedy algorithm works. Let $n \geq 2$ be an integer. Suppose leaves $i$ and $j$ are in the $(t+n)$-th layer (which means the distance between $i$ and the root is $t+n$) and the $t$-th layer, respectively. $p(i) = p(j)$ ($p$ denotes the probability of a vertex, no matter the vertex is a leaf or not). Consider the vertex $k$ at the $(t+1)$-th layer. Vertex $k$ could be a leaf layer or a merge layer. If $p(k) < p(i)$, swap $j$ and $k$. If $p(k) > p(i)$, swap $i$ and $k$. Otherwise, if $p(i) = p(j)$, do a "surgery" on the Huffman tree to improve it (rigorous proof is left to you).