Data Compression Using Huffman Algorithm

Data Compression:

Data Compression is also referred to as bit-rate reduction. This technique is used to reduce the size of large files. The advantage of data compression is that it helps us save disk space and time in data transmission.

There are mainly two types of data compression techniques -

1. Lossless Data Compressieon:

Lossless data compression is used to compress files without losing an original file’s quality and data. The file size is reduced, but the quality of data remains the same.

2. Lossy Data Compression:

Lossy data compression is used to compress larger files into smaller files. In this technique, some specific amount of data and quality are removed (loss) from the original file

In this Blog, we are going to understand Huffman Algorithm which is the Lossless Data Compression technique

Huffman Algorithm:

Theory:

It is a lossless data compression algorithm that is used to compress data for transmission or storage. One of the key benefits of Huffman coding is that it is optimal for a given set of data. It is a simple yet powerful data compression algorithm that has become a staple in the field of computer science. It is used in a wide variety of applications, including data transmission, data storage, and image and audio compression.

Intuition:

Suppose we have a txt file demo.txt

Size of above file = count(char) = 24 bytes = 24*8 = 192 bits

Above we are storing every character in 8 bits. The idea is to store every character in smaller bits .

For this, we are going to assign bits that will be lesser than 8 bits to every character using the Huffman algorithm. The higher the frequency of characters in the file lesser bits will be assigned to reduce more size which is logical.

Below is the frequency of elements and bits that are assigned to them

In the above image observe that most recurring elements are ‘ ‘ , ‘e’ , ‘s’. These characters are assigned the least bits 01,00,101.

Initially, every character was stored in 8 bits but using the above hashmap we can store ‘e’ in 2 bits, ‘s’ in 3 bits, etc. Now we just replace characters in the demo file using the above hashmap of bits.

The demo file is now stored in 86 bits from 192 bits. To decode this file we use the same hashmap.

Algorithm to create HashMap

1. We first find the frequency of characters in any file

def find_frequency(arr):
    # Simple Calulation of count or frequency of words in the list
    ele_freq = {}
    for i in range(len(arr)):
        if arr[i] not in ele_freq:
            ele_freq[arr[i]] = 1
        else:
            ele_freq[arr[i]]+=1
    return ele_freq

2. Using this frequency create a Huffman Tree

Get Akash Zalke’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Steps:

2.1) Sort the given frequency dictionary (we can sort using min heap also)

ele_freq = dict(sorted(ele_freq.items(),key=lambda x : x[1], reverse=True))

2.2) pop 2 least value elements

        l = ele_freq.popitem()
        r = ele_freq.popitem()

2.3) Now make node of these two elements if the node of them doesn’t exists in making nodes (making nodes is a dict which holds string_val : nodes address)

Left var is pointing towards left child (smaller) right var is poiting towards right child (bigger than or equal to left)

        making_nodes = {}
        if l[0] not in making_nodes:
            making_nodes[l[0]] = Node(None,None,l[0],l[1])
        left = making_nodes[l[0]]
        if r[0] not in making_nodes:
            making_nodes[r[0]] = Node(None,None,r[0],r[1])
        right = making_nodes[r[0]]

2.4) Make a parent node with above pop items as left and right child by combining their string and values assigned to them and add parent in making_nodes .

parent_node = Node(left,right,left.cur_str+right.cur_str,left.val+right.val)
making_nodes[parent_node.cur_str] = parent_node

2.5) Add this new string : value in the frequency dictionary

ele_freq[parent_node.cur_str] =  [parent_node.cur_str,parent_node.val]

Repeat the above steps till one element is remaining in the frequency dictionary . Below is the representation of how 2 elements will be removed (underlined by red ) and how combination of those elements will be inserted (underlined by blue)

Below is the Binary Tree which we created

3) Now we just traverse till leaf nodes and when we go left we append 0 and in right we append 1 and that we will be respective value of that code.

def traverse(root,huffman_codes,code):
    if not root.left and not root.right:
        huffman_codes[root.cur_str] = code
        return 
    if root.left:
        traverse(root.left,huffman_codes,code+'0')
    if root.right:
        traverse(root.right,huffman_codes,code+'1')  

So Below is the Hashmap(Huffman Codes) for our file :

4) We encode a file using this bits assigned to the charcter

def encode(huffman_codes,temp,encode_file_name):
    # we will write our encoded code in another file
    #Open as binary file as we are writing in binary 
    encode_file = open(encode_file_name, "wb")
    for x in temp:    
        binary_str = bytes(huffman_codes[x], 'utf-8')
        encode_file.write(binary_str)
    encode_file.close()

5) To decode we use same hashmap

def decode(huffman_codes,Encode_filename,Decode_filename):
    huffman_codes = {v: k for k, v in huffman_codes.items()}
    encode_file = open(Encode_filename,"rb")
    decode_file = open(Decode_filename, "w")
    binary_read = str(encode_file.read())
    match_code = ''
    for bit in binary_read[2:]:
        match_code+=bit
        if match_code in huffman_codes:
            decode_file.write(huffman_codes[match_code])
            match_code = ''
    decode_file.close()
    encode_file.close()

So this is how we compress a file using Huffman Algorithm.

GitHub Link For the code : https://github.com/AkashZalke/Huffman_coding