Problem Statement
Given a text file [Link] consisting only of lowercase alphabets (a–z).
The task is to compute the frequencies of each alphabet, generate the Huffman encoding tree,
use the coding scheme to encode the file into [Link], decode it back into [Link],
and verify correctness by comparing [Link] with [Link].
Explanation of Huffman Encoding
Huffman encoding is a lossless data compression algorithm.
It assigns variable-length binary codes to input characters, with shorter codes assigned to more
frequent characters.
The algorithm builds a binary tree (Huffman Tree) where each leaf node represents a character.
The path from the root to a leaf defines the character’s binary code:
left edge as 0 and right edge as 1.
This minimizes the total size of the encoded message.
Step-by-step Algorithm
1. Count the frequency of each character in [Link].
2. Create a priority queue (min-heap) of nodes, where each node stores a character and its
frequency.
3. While more than one node exists:
a. Extract the two nodes with the lowest frequency.
b. Create a new node with frequency = sum of the two nodes.
c. Assign left and right children as the two extracted nodes.
d. Insert the new node back into the priority queue.
4. The final node becomes the root of the Huffman tree.
5. Traverse the Huffman tree to assign codes to characters.
6. Encode [Link] into [Link] using the generated codes.
7. Decode [Link] back into [Link] using the Huffman tree.
8. Compare [Link] with [Link] to verify correctness.
Python Code
import heapq, os
class Node:
def __init__(self, char, freq):
[Link] = char
[Link] = freq
[Link] = None
[Link] = None
def __lt__(self, other):
return [Link] < [Link]
def build_huffman_tree(frequencies):
heap = [Node(ch, freq) for ch, freq in [Link]()]
[Link](heap)
while len(heap) > 1:
n1 = [Link](heap)
n2 = [Link](heap)
merged = Node(None, [Link] + [Link])
[Link], [Link] = n1, n2
[Link](heap, merged)
return heap[0]
def build_codes(node, code="", mapping={}):
if node:
if [Link] is not None:
mapping[[Link]] = code
build_codes([Link], code + "0", mapping)
build_codes([Link], code + "1", mapping)
return mapping
# Read [Link]
with open("[Link]", "r") as f:
text = [Link]().strip()
# Step 1: Frequency calculation
frequencies = {ch: [Link](ch) for ch in set(text)}
# Step 2: Build Huffman tree
root = build_huffman_tree(frequencies)
# Step 3: Build Huffman codes
codes = build_codes(root)
# Step 4: Encode
encoded_text = "".join(codes[ch] for ch in text)
with open("[Link]", "w") as f:
[Link](encoded_text)
# Step 5: Decode
decoded_text = ""
node = root
for bit in encoded_text:
node = [Link] if bit == "0" else [Link]
if [Link]:
decoded_text += [Link]
node = root
with open("[Link]", "w") as f:
[Link](decoded_text)
# Step 6: Verification
assert text == decoded_text, "Decoded text does not match original!"
print("Encoding-Decoding successful!")
Sample Run & Verification
Suppose [Link] contains: "huffmanencoding".
Frequencies:
h:1, u:1, f:2, m:2, a:1, n:2, e:1, c:1, o:1, d:1, i:1, g:1
Huffman Codes (example, may vary):
f: 00, m: 01, n: 100, h: 1010, u: 1011, a: 1100, e: 1101, c: 1110, ...
Encoded Text ([Link]): 101000011001...
Decoded Text ([Link]): "huffmanencoding"
Verification: [Link] matches [Link] → Correct!
Conclusion
Huffman encoding provides an efficient method of compressing text by assigning variable-length
codes
to characters based on frequency. The experiment successfully demonstrates the encoding and
decoding process,
verifying that the decoded text is identical to the original input, ensuring lossless compression.