0
$\begingroup$

Studying for my finals. I saw the following question:

Prove or disprove: If in a given text the frequency of the letter A is 0.5, then the number of bits encoding in the Hoffman code for the text is 1.

In the solution they said that this statement is true but didn't explain why. I'm trying to prove this statement for myself but struggling how to "show it". Why it's true?

$\endgroup$
1
  • 1
    $\begingroup$ the huffman code is built by the inverse frequencies so 1/0.5 = 2 states, 1 bit $\endgroup$
    – Nikos M.
    Jul 27 at 20:10
1
$\begingroup$

Suppose that no symbol has frequency $0$ (otherwise the claim is false).

Consider the tree $T$ built by the standard greedy algorithm to construct the Huffman code. This algorithm maintains a forest $F$ where each node $v$ is associated with a frequency $f_v$. Initially $F$ contains a collection of isolated vertices, one per input symbol (with the corresponding frequencies). Then the algorithm greedly selects the two trees $T_1, T_2 \in F$ rooted in the vertices with minimum frequencies and replaces them with the tree obtained by merging $T_1$ and $T_2$ into a single tree via the addition of new root $r$. The frequency $f_r$ of $r$ is the sum of the frequencies of the roots of $T_1$ and $T_2$.

Let $a$ be the node corresponding to symbol $A$ and suppose towards a contradiction that the depth of $a$ in $T$ is at least $2$. Let $a'$ and $b$ be the parent and the sibling of $a$ in $T$, respectively. Since $a'$ cannot be the root (it has depth $\ge 1$), it must have a sibling $x$. Some vertex $y$ of the subtree of $T$ rooted in $x$ was the root of a tree in $F$ when the isolated vertex $a$ was merged. Therefore the frequency of $y$ is at least the frequency of $a$ (othewise either $a$ or $b$ would have been merged with $y$ instead).

This is a contradiction since $f_a + f_b + f_y \ge 0.5 + f_b + 0.5 = 1 + f_b > 1$.

$\endgroup$
2
  • $\begingroup$ Thank you! I have two small questions. 1) Why $f_a+f_b+f_y>1$ is a contradiction? 2) if we get $d_{T}\left(a\right)=1$ what does it say about the number of bits of $a$ (where $d_T$ is the depth)? $\endgroup$
    – vesii
    Jul 28 at 10:23
  • 1
    $\begingroup$ The sum of the frequencies cannot exceed $1$. Think of the frequency as the probability of seeing certain symbol. The number of bits in the Huffman code of the symbol is the depth of that symbol in the tree. $\endgroup$
    – Steven
    Jul 28 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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