1
$\begingroup$

Say I have following text: "abbcccddddeeeee". As you can see, each letter has a different frequency of occurence. When making a Huffman-Trie to encode this String, will this trie be unique?

I thought a bit on the problem and I can't come to a definite conclusion, but I think the trie will NOT be unique. Say the begin-situation:

a(1) b(2) c(3) d(4) e(5)

To make a trie, we take the lowest frequencies together and make a node above it with the sum of those frequencies. Because the frequencies are all ascending, there is only 1 way to take the lowest nodes. In this case, a and b. If we keep going on further, it wel never occur that we need to choose 2 subtries out of a larger collection, there will always be just 2. When seeing this, you could conclude the trie will be unique BUT. I see never stated in which order the two subtries need to be added. For example, to make the first new subtrie, we can put node a left OR right of node B. We can do this at each level and eventually, this will flip some bits in the end-result.

Am I correct?

$\endgroup$
  • $\begingroup$ No, Huffman trees are not unique, and moreover, there are minimum redundancy codes which are not Huffman codes. $\endgroup$ – Yuval Filmus Aug 15 '16 at 13:51
  • $\begingroup$ I'm talking about total prefix-free codes. I think every Huffman trie results in prefix-free codes or isn't it? $\endgroup$ – CedricCornelis Aug 15 '16 at 13:52
  • 1
    $\begingroup$ What research have you done? We expect you to search standard resources (e.g., Wikipedia, a standard textbook) for an answer before asking here. In this case, your question is already answered in the Wikipedia page on Huffman codes: "In general, a Huffman code need not be unique." There's little point in us repeating material that's already available in standard places. If your question is answered in the obvious place on Wikipedia, you probably ought to do more research before asking. $\endgroup$ – D.W. Aug 15 '16 at 22:48
4
$\begingroup$

2 3 4 5 is a counterexample:

4 5 5 (combine 2 and 3 to make 5, and reorder)

Now there are 2 choices for 4 to partner with: either the original 5, or the one formed by 2+3.

$\endgroup$
  • 1
    $\begingroup$ Aha, didn't see it the first time. So it's definitely not unique but always the most efficient bit-wise? $\endgroup$ – CedricCornelis Aug 15 '16 at 18:33
  • 2
    $\begingroup$ Come on. The answer to that question is in the second paragraph of the Wikipedia page. $\endgroup$ – j_random_hacker Aug 15 '16 at 18:46
  • $\begingroup$ I actually meant as efficient as possible, bitwise, using Huffman technique... $\endgroup$ – CedricCornelis Aug 17 '16 at 19:49
  • 1
    $\begingroup$ @CedricCornelis: Do you mean that your question is "Is the result of Huffman compression equally efficient, regardless of the way ties are broken?" If so, the answer to this question is again implied by the second paragraph of the Wikipedia page: it says that Huffman compression produces an optimally efficient code, so this means regardless of how ties are broken. $\endgroup$ – j_random_hacker Aug 17 '16 at 23:35

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.