1. Huffman Coding
Every wondered how compression algorithms like bzip2, zip, pdf, etc.. work? They
use a variety of (lossless) compression algorithms, one of the most important stage being a
method called Huffman coding.
A normal character occupies 1 byte of space. For example the string
“Welcometofelicity” occupies 20 bytes or 160 bits, if we use ASCII coding. But since there
are only 10 distinct characters, we can use 4 bits to encode, reducing to 80 bits.
The basic idea of Huffman coding is to use a different map from a character to its
binary representation, and allow variable bit-length encoding of characters, further reducing
the size. The compression is achieved by using less number of bits to represent a character
that occurs more number of times. The algorithm to find such an optimal encoding works by
constructing a binary tree as follows:
Step1: Get frequencies of characters from input string. Construct an array F of trees, where
the trees are all originally containing only one node. A node is a pair: (char, freq)
F = [ (W, 1), (e, 3), (l, 2), (c, 2), (o, 2), (m, 1), (t, 2), (f, 1), (i, 2), (y, 1) ]
Step2: We sort this array of trees in non-decreasing order of frequency (of the root node):
F = [ (W, 1), (m, 1), (f, 1), (y, 1), (l, 2), (c, 2), (o, 2), (t, 2), (i, 2), (e, 3) ]
Step3: If there is only one element in F, goto Step5, else create a new tree with root as
(c, f) where c is an auxiliary character, not in the input string, and f is the sum of frequencies
of the first two nodes. Make the first two nodes as the left and right child of the root node
and replace them, with this new tree:
F = [ (x1, 2), (f, 1), (y, 1), (l, 2), (c, 2), (o, 2), (t, 2), (i, 2), (e, 3) ]
/ \
(W, 1) (m, 1)
Step4: GoTo Step2
Step5: F now contains a single binary tree:
Step6: We now assign codes to each character based on the path from the root to that
character. It will be a sequence of 0s & 1s, based on whether we move to the left or right of
a node during the traversal:
l:000 c:001 o:010 t:011 w:1000 m:1001 f:1010 y:1011 i:110 e:111
Total bits required to encode input string: 4+4+4+4+6+6+6+6+6+9 = 55
Compression ratio (%) = CompressedSize/UncompressedSize = (55/80)*100 = 68.75 %
Your task in to now optimally compress the input using Huffman coding.
Input Format
Input will be some text, containing a sequence of type-able ASCII characters. Read till EOF.
Let the number of distinct characters in input be n. (You have to compress everything
including spaces, newlines, tabs, and any character in the input).
Output Format
Output n+1 lines, the first n lines containing a character, followed by a space and its prefix
code in binary. The last line should contain the compression ratio (%), exactly up to 2 places
after decimal. If there are multiple solutions, any one will do.
Sample Input
Welcometofelicity
Sample Output
l 000
c 001
o 010
t 011
w 1000
m 1001
f 1010
y 1011
I 110
e 111
68.75