Huffman Decoding

As described in the encoding algorithm, the coding table for, “who are you” is as below:

 Code     Frequency

111       2

a  000      1

e  001      1

h      100       1

o  01  2

r   1011    1

u   1010      1

w   1101     1

y   1100       1   

Hence, we can code, “who are you” as 11011000111100010110011111100011010

How do we decode this binary code? We will need the Huffman tree that we built when we encoded our input text. Scroll down on the link below and observe the Huffman tree in the last iteration (Queue Length = 1):

· https://nhrec.org/~schinnab/Huffman_Encoding_Example.txt

Pseudocode for the “deCode” method in Tree.java:

Utilizing the Huffman tree, we will follow the steps below to decode the binary code:

1) Create a StringBuilder variable, S to store the decoded word. It starts off being empty.

2) Start at the root.

3) Loop through the binary code from left to right:

a. If you see a 1, go to the right node

else, go to the left node

b. Continue Step a) until you reach a leaf node. This is your decoded character. Append the character in the leaf node to S. Step 3) will be repeated until the binary code is completely parsed.

4) Return S.