Code Notes made by Vaibhav Rathod

Huffman Coding Compression

2 min read

Written by Vaibhav Rathod

Explanation

  • Huffman Coding is a lossless data compression algorithm that assigns variable-length codes to input characters based on their frequencies.
  • The idea is to give shorter codes to characters that appear more frequently and longer codes to less frequent characters. This results in compressed data representation.
  • It is widely used in file compression formats like ZIP and JPEG.

Steps

  • Build a frequency table of characters in the input.
  • Build a priority queue (min-heap) using the frequency of each character.
  • Build a Huffman Tree: Combine the two nodes with the lowest frequency until there is only one node left. This node is the root of the Huffman tree.
  • Generate Huffman codes: Traverse the tree to assign binary codes to each character.
  • Encode the input data using the generated Huffman codes.
  • Decode the data by traversing the Huffman tree.

Time Complexity

  • Building the frequency table: O(n), where n is the number of characters.
  • Building the heap: O(n log n), where n is the number of unique characters.
  • Encoding: O(n), where n is the length of the input.
import heapq
from collections import defaultdict
 
# Step 1: Build frequency table
def build_frequency_table(data):
    freq = defaultdict(int)
    for char in data:
        freq[char] += 1
    return freq
 
# Step 2: Build the Huffman Tree
def build_huffman_tree(freq):
    heap = [[weight, [char, ""]] for char, weight in freq.items()]
    heapq.heapify(heap)
    
    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    
    return sorted(heap[0][1:], key=lambda p: (len(p[-1]), p))
 
# Step 3: Encode data using the Huffman Tree
def encode(data, huffman_tree):
    huff_dict = {item[0]: item[1] for item in huffman_tree}
    return ''.join(huff_dict[char] for char in data)
 
# Example Usage
data = "this is an example for huffman encoding"
freq_table = build_frequency_table(data)
huffman_tree = build_huffman_tree(freq_table)
encoded_data = encode(data, huffman_tree)
 
print(f"Encoded Data: {encoded_data}")

Graph View

Backlinks

Recently Updated