HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is huffman-encoding with distinct frequencies of symbols unique?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
frequenciesdistinctuniquehuffmanwithencodingsymbols

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#62611, answer score: 6

Revisions (0)

No revisions yet.