Adaptative Huffman decoding

Question

I am currently studying compressions algorithms and I came across with Adaptative Huffman. Unlike "usual" Huffman, in this one we don't know the frequency of each symbol a priori. I came across with an exercise that I just can't figure it out.

Given the alphabet A = {1,2,3,4,5,6,7,8} and assuming an adaptive huffman encoder was used, determine the message corresponding to the bitstream 0110010000011010

I don't understand if I have to build the Huffman tree or if there is another way around without building the tree, because I tried to assign binary codes to each symbol of the alphabet: 1 for 000, 2 for 001, 3 for 010, 4 for 011,...(based on 2^e + r = 8, with an e = 3 and r = 0), but doesn't match with the correct awser.

Thank you for your time

Answer 1

There is no definitive version of adaptive Huffman, here are some assumptions I’ve made to come up with one possible solution:

• The coder is per-symbol adaptive
• The tree is built in-flight, you start with an empty tree that contains only the escape symbol
• Escape symbol always has a weight of 0
• Left branch is code bit 0, right branch is 1

At first, there are no branches in the tree stub, therefore it costs 0 bits to decode the escape symbol.

Next, the literal code 011=>4 is received. Two new nodes are added: parent node (weight 1) and symbol 4 (code 0, weight 1) . The escape symbol has code 1 and weight 0.

Next, code 0 is decoded =>4, symbol 4 has weight 2.

Next, code 0 is decoded =>4, symbol 4 has weight 3.

Next, code 1 is decoded =>escape. The literal code 000=>1 is received. Two new nodes are added: parent node (weight 1) and symbol 1 (code 10, weight 1) . The escape symbol has code 11 and weight 0.

and so on.. At some point nodes may have to be moved to correct an imbalance, but apparently not in this exercise.