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?
Is huffman-encoding with distinct frequencies of symbols unique?
algorithms;algorithm analysis;data compression;huffman coding