Huffman coding algorithm is a minimal variable-length character coding algorithm based on the frequency of each character.The algorithm was developed by David Huffman. This is called "lossless" compression and is different from "lossy" compression used in audio and video files where the exact original cannot be reproduced. This is used in programs like Winzip, gzip, stuffit etc. The secret of compressing data lies in the fact that not all characters are equally common. For instance, in typical English text the letter 'e' is much more common than the letter 'z'. In fact there are roughly 70 'e's for every 'z'. If we could encode the letter 'e' with less than the usual 8 bits and in exchange let the letter 'z' be take more.
Huffman Coding program consists of 7 functions. The functions is explained below:
1. Determining Relative frequencies
The function input is a string. A dictionary of letters along with their number of occurrence is created.
def Freq(stri):
freq = {}
for ch in stri:
freq[ch] = freq.get(ch,0)+1
print freq
2. Sorting list of tuples
This function builds and sorts a list of tuples. This list will be the input for the main Huffman algorithm.
def SortFreq(freq):
tuples=[]
for all in freq:
tuples.append((freq[all],all))
tuples.sort()
print tuples
3. Building a Tree
This function pops two elements from the front of the list and combined into a new element. These 2 elements will have the least frequencies. The frequency of the new branch point is simply the sum of the frequencies of its two parts. Next we add this new element onto the list and sorted to find it's new position. The process is repeated until the list has a single element which represents the complete tree.
def BuildTree(tuples):
global string
while len(tuples)>1:
leastTwo=tuple(tuples[0:2])
rest=tuples[2:]
combFreq=leastTwo[0][0]+leastTwo[1][0]
tuples=rest+[(combFreq,leastTwo)]
tuples.sort()
print tuples
4. Trimming of the frequencies
This function trims the frequencies thus resulting in tuples containing only letters with no corresponding frequencies.
def Trim(tuples):
p=tuples[1];
if type(p)==type(""):
return p
else:
return (Trim(p[0]),Trim(p[1]))
This function assigns codes to the letters in the tree keeping track of the left and right turns in the variable "pat". There is a global dictionary "codes" which will be filled in along the way.
def Coding(node,pat=""):
global code
if type(node)==type(""):
code[node] = pat
else:
Coding(node[0],pat+'0')
Coding(node[1],pat+'1')
return code
6. Encoding a Text Stream
This function looks up the bit string for each character from the coded dictionary and replace it..
def encoding(str):
global code
result=""
for let in str:
result+=code[let]
return result
This function does the reverse process of encodeing. In this each "zero" in the bit stream means a left turn up the tree, each "one" a right turn. When a leaf is reached, its character is sent to the output and we restart at the base of the tree for the next character.
def decoding(tree,str):
result=""
p=tree
for num in str:
if num=='0':
p=p[0]
else:
p=p[1]
if type(p)==type(""):
result+=p
p=tree
return result
Output:
This program turns the original string "aaabccdeeeeeffg" into 44 bits that we represent with "00000010010100101010111111111101101110111000". The original text at one byte per character requires 120 bits.