0
$\begingroup$

Under Huffman Encoding, what circumstances codeword length of each character be equal?(suppose number of character is power of 2)

I think if all frequency of characters is same then codeword length of all characters be the same. Surprisingly, if there are two characters that differences between frequency of two characters be $2$, and frequency of other be equal then codeword length of all characters be the same.

Main problem is, can i say, for each constant $c$, if there are two character that difference of frequency be $c$, and all remaining of characters have equal frequency then codeword length of each character be equal?

$\endgroup$
0
$\begingroup$

Assume there are 2^n symbols, n >= 2, and the frequencies of the most common and the two least common symbols are f, g, and h. We could use a code of n-1 bits for the most common and n+1 bits for the two least common symbols. This will reduce the average code length if f > g+h.

You were specifically asking for the frequencies 2^-n + c/2, 2^-n, and 2^-n - c/2, so that’s the case for c > 2^-n / 2.

$\endgroup$
3
  • $\begingroup$ Thanks. According to your explanation, can we say my proposition is true? $\endgroup$ – user132812 Mar 18 at 11:04
  • $\begingroup$ My proposition: for each constant $c$, if there are two character that difference of frequency be $c$, and all remaining of characters have equal frequency then codeword length of each character be equal? $\endgroup$ – user132812 Mar 18 at 11:05
  • $\begingroup$ Not if c > 2^-n / 2. Code lengths will change. And you can’t change just two lengths, you need to change at least three. $\endgroup$ – gnasher729 Mar 18 at 11:24

Your Answer

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