Huffman Coding Simulator

Build a Huffman tree from character frequencies one merge at a time, read off the prefix codes and compare the bits with ASCII.

Text to encode

Characters that appear more often get shorter codes.

Text (up to 40 characters)

Building the Huffman tree

Each character starts as a leaf, weighted by how often it appears. The queue is sorted by frequency.

Step 1 / 10

Priority queue:C:1D:1B:2R:2A:5

Code table

Finish building the tree (press ⏭) to read off the codes.

ASCII (8 bits each)

bits

Fixed length

3 bits each

Huffman

bits

About This Simulation

This Huffman coding simulator turns a piece of text into a frequency table, builds the Huffman tree by repeatedly merging the two least frequent nodes, and reads off a variable-length binary code for each character. It then compares the encoded size with ASCII and with a fixed-length code.

Features

Frequency table built from your own text
Priority queue shown at every merge
Huffman tree drawn step by step with 0/1 branch labels
Final code table and encoded bit string
Size comparison against 8-bit ASCII and fixed-length codes

Topics covered

Huffman Coding
Prefix Codes
Greedy Algorithms
Priority Queues
Lossless Compression

Explanation

Huffman coding is a lossless compression algorithm that gives frequent characters short codes and rare characters long codes. Because no code is the beginning of another code (a prefix code), the encoded bits can be decoded without any separators.

How it works

Count how often each character appears and make a leaf node for each one, weighted by its frequency.
Put all the nodes in a priority queue ordered by frequency.
Remove the two nodes with the smallest frequencies and join them under a new node whose frequency is their sum.
Put the new node back in the queue and repeat until only one node, the root, is left.
Label every left branch 0 and every right branch 1. A character's code is the sequence of labels from the root to its leaf.

Why it matters

Huffman coding is a classic greedy algorithm taught in algorithms courses (CSE221) and is used inside real formats such as ZIP (DEFLATE), JPEG and MP3. It shows how knowing the data's statistics leads to better compression.

Frequently Asked Questions

Why is Huffman coding called a greedy algorithm?

At every step it makes the locally best choice, merging the two least frequent nodes, and this always gives an optimal prefix code.

What is a prefix code?

A set of codes where no code is the start of another. This means a bit string can be decoded by reading bits until they match a code, without needing separators.

Is the Huffman tree unique?

No. When frequencies tie, different choices give different trees and codes, but every valid Huffman tree gives the same total number of bits.

What is the time complexity of building a Huffman tree?

O(n log n) for n distinct characters when a binary heap is used as the priority queue.

Related Simulations

Data Representation