Recall in lectures that we presented a Huffman tree that was constructed by examining the frequency of characters on Wikipedia:
{{/Labs/01/Images/fig3.svg}} 
The corresponding Huffman coding for this tree is:  
{{/Labs/01/Images/HuffmanTreeCode}}  



Using this coding, we can decode the sequence  

1100010100010100110100001100111001111011100111

as:
11000 = C (remaining bits: 10100010100110100001100111001111011100111)

1010 = O (remaining bits: 0010100110100001100111001111011100111) 

001010 = M (remaining bits: 0110100001100111001111011100111)

011010 = P (remaining bits: 0001100111001111011100111) 

000 = [space] (remaining bits: 1100111001111011100111)  

1100111 = 1 (remaining bits: 001111011100111)  

00111101 = 0 (remaining bits: 1100111)  

1100111 = 1 (no remaining bits, end of sequence) 

Resulting in the string 'COMP 101'.  
### Exercise  
Use this Huffman coding to decode the following bits: 11010011001001001100110101001  

Answer? 

---  



Encoding information using a Huffman coding follows the opposite direction (look up the symbol and emit the corresponding code). This is straightforward when the table describing the Huffman coding is sorted by symbol:

{{/Labs/01/Images/HuffmanBySymbol.png}} 
Now, we can quickly confirm that the sequence ‘QWERTY’ would be encoded as 1000100001(Q) 100011(W) 111(E) 1011(R​) 0101(T) 0010000(Y) 1000100001100011111101101010010000 (34 bits).