1
$\begingroup$

How would you prove that Huffman coding $C$ is a prefix code, i.e $$\forall x,y \in C,\ \forall z \in \lbrace 0,1\rbrace^*,\ x\not=y||z$$

Using induction according to the number of items to code? The base step would be easy, but I don't know how to prove the inductive step.

$\endgroup$
  • 3
    $\begingroup$ I'm voting to close this question as off-topic because entropy coding is not a part of cryptography. $\endgroup$ – otus Apr 13 '16 at 13:41
2
$\begingroup$

Let $T$ be an optimum prefix code tree, and let $b$ and $c$ be two siblings at the maximum depth of the tree (must exist because $T$ is full). Assume without loss of generality that $f (b) \le f(c)$ and $f(x) \le f(y)$ (if this is not true, then rename these characters). Since $x$ and $y$ have the two smallest frequencies it follows that $f(x) \le f(b)$ (they may be equal) and $f(y) \le f(c)$ (may be equal). Because $b$ and $c$ are at the deepest level of the tree we know that $d(b) \ge d(x)$ and $d(c) \ge d(y)$. Now switch the positions of $x$ and $b$ in the tree resulting in a different tree $T′$ and see how the cost changes. Since $T$ is optimum,

$$\begin{align} B(T) &\le B(T′) \\ &= B(T) − f(x)d(x) − f(b)d(b) + f(x)d(b) + f(b)d(x) \\ &= B(T) − (f(b) − f(x))(d(b) − d(x)) \\ &\le B(T) \end{align}$$

Therefore, $B(T′) = B(T)$, that is, $T′$ is an optimum tree. By switching $y$ with $c$ we get a new tree $T ′′$ which by a similar argument is optimum. The final tree $T′′$ satisfies the statement of the claim.

$\endgroup$
  • $\begingroup$ Thx for answer - what are the functions $f()$ and $d()$? And what is $x,y$? Thanks :) $\endgroup$ – GorTeX Apr 13 '16 at 14:25
  • $\begingroup$ f(x) is the frequency of x. d(x) denotes the depth of x's leaf. $\endgroup$ – Hakan ALTAŞ Apr 14 '16 at 15:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.