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$

closed as off-topic by otus, yyyyyyy, DrLecter, e-sushi Apr 15 '16 at 22:01

  • This question does not appear to be about cryptography within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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.