Huffman coding is a popular algorithm used for lossless data compression. It assigns shorter codes to more frequent characters and longer codes to less frequent characters, optimizing space when storing or transmitting data.
How does it work?
Huffman coding works by creating an optimal binary tree. Here's how the algorithm builds the tree and generates the binary codes:
Step 1: Frequency Analysis - Count the frequency of each character in the input text.
Step 2: Create Leaf Nodes - Each character is represented as a node with its frequency.
Step 3: Build the Tree - Combine the two least frequent nodes until only one node (the root) remains. This node represents the entire tree.
Step 4: Generate Codes - Traverse the tree from root to leaf, assigning a '0' for left moves and '1' for right moves to create binary codes for each character.
Example: Constructing the Huffman Tree for "abccba"
Step 1: Frequency Table
a: 2
b: 2
c: 2
Step 2: Create Leaf Nodes
Node A: 2 (a)
Node B: 2 (b)
Node C: 2 (c)
Step 3: Build the Tree
Combine the two least frequent nodes (A and B) into a new node:
New Node (AB): 4 (a + b)
Now, combine the new node (AB) with C:
New Node (ABC): 6 (a + b + c)
Step 4: Generate Binary Codes
a: 00
b: 01
c: 1
Now, you can encode any text using these codes!
How to Play the Game
In this game, your task is to decode an encoded binary string using the Huffman codes.
You will be shown a table with character frequencies and a binary-encoded string.
Use the frequency table and the binary string to guess the original word.
Enter your guess in the input box and submit it to check if you're correct!
If your guess is correct, you escape the room and win the game!