2
$\begingroup$

I am new to Huffman coding and I find myself facing a lot of confusion as to how to determine if a code is Huffman or not without having the probabilities associated to each codeword. I know one way is look at whether or not the code is prefix. If not, then it's not a Huffman code. If yes, then we need to check if it gives the shortest possible length, but we don't know the probabilities. How do we ensure the code guarantees the shortest possible length in such case? To illustrate my question, let us look at the following two examples:

Example 1: $\{00,01,10,110\}$

The code is a prefix code, but is the length minimal? I mean it's a bit unusual for me to see Huffman code for $4$ symbols that does not have one-bit codeword for one of its symbol (the symbol with highest probability), but them I thought maybe the first three symbols are equally probable. As such, I tried to find the Huffman code for $\{0.33,0.33,0.33,0.01\}$ and got $\{00,01,10,11\}$ with different orders (depending on the usage of $0,1$ or $1,0$ in the tree). This led me to thinking that the code under investigation might not be Huffman, yet I am still not sure.

Example 2: $\{01, 10\}$

Again another unusual prefix code as the obvious choice (and the one with minimal length) for two symbols would be $\{0, 1\}$. But could it be the case that $\{01, 10\}$ can possibly give a minimal length? I can not see any possible probabilities in which this is the case, thus I believe this is not a Huffman code.

Am I on the right track? Does there exist an actual method to check whether or nor a code is Huffman without having the probabilities?

$\endgroup$
  • $\begingroup$ In example 2, you can replace 01 with 0 and get a prefix code with shorter average length, and you can replace 10 with 1 as well. $\endgroup$ – gnasher729 Sep 15 '18 at 12:22
  • $\begingroup$ Not sure why somebody's voted to close this as "not about computer science". Could anybody voting to close for that reason please explain why? $\endgroup$ – David Richerby Sep 15 '18 at 18:56
3
$\begingroup$

If you have a Huffman code, and the codes have lengths $l_i$, then the sum over $2^{-l_i}$ must be equal to 1. In your case, that sum is 1/4 + 1/4 + 1/4 + 1/8 = 7/8 < 1, therefore not a Huffman code. You can replace the code 110 with 11.

(I am quite sure you can prove that for any prefix code, the sum is ≤ 1. And I'm quite sure you can prove that if the sum is less than 1, then there is some bit that you can remove from some code with the code remaining a prefix code, and since there is a finite number of bits to remove, the sum must become 1 eventually).

$\endgroup$
  • $\begingroup$ This is such a powerful result! Can I have a source stating this? I know about Kraft's inequality but did not know Huffman codes satisfy it with strict equality. $\endgroup$ – Lod Sep 14 '18 at 21:34
  • $\begingroup$ @Lod look at the process of assigning codes to nodes. it ensures that total codespace is always 1 $\endgroup$ – Bulat Sep 14 '18 at 21:37
  • $\begingroup$ @Bulat True, but a priori it might be possible that there are Huffman codes that are never generated by some algorithm. $\endgroup$ – gnasher729 Sep 15 '18 at 12:20
  • $\begingroup$ @gnasher729 Huffman algorithm is an algorithm that finds optimal encoding with concrete algorithm. Prefix codes aren't necessary Huffman ones. The question is correct with terminology ("how to determine if a code is Huffman or not") and your answer is partially correct. I will edit it. $\endgroup$ – Bulat Sep 15 '18 at 12:30
  • 1
    $\begingroup$ I don't care about "Huffman algorithm". All I care about is the codes. A Huffman code for a given set of probabilities is any prefix-code that minimises the expected code length. And a Huffman code is any code that is a Huffman code for some set of probabilities. $\endgroup$ – gnasher729 Sep 15 '18 at 22:34
1
$\begingroup$

When a frequency tree is built for a message upon its characters, the leaf nodes of the tree are the characters composing the message with their frequency and internal nodes just have a frequency sum of all its descendents.
The characteristic property of frequency trees for Huffman encoding is that, all internal nodes have exactly two children.

For your example 1, $\{00,01,10,110\}$, the frequency tree would be something like this (forgive me for how the tree looks like. Subtrees are denoted by + and the first subtree is the left subtree and the second is the right subtree):

(root)
+ (0)
|  + (0) (leaf)
|  + (1) (leaf)
+ (1)
   + (0) (leaf)
   + (1)
      + (0) (leaf)

The subtree $\{root,1,1\}$ has one child, not two. Hence, such a prefix code can not be a Huffman encoding for any message. Similarly for example two, subtrees $\{root,0\}$ and $\{root,1\}$ have exactly one child.

$\endgroup$

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.