patternMinor
Is huffman-encoding with distinct frequencies of symbols unique?
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:
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?
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.