FoundationSource checked

Huffman Coding

Builds a prefix code that gives shorter bit strings to more frequent symbols.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Compression
Difficulty: Intermediate
Family: Prefix Coding
Tier: Foundation
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 22
Code example: Not ready
Visualization: Ready
Aliases: Huffman Encoding

Overview

Huffman Coding repeatedly merges the two least frequent symbols or subtrees to build a binary prefix tree. Traversing the tree assigns variable-length codes without ambiguity.

Core Concepts

prefix codefrequency tablebinary treepriority queue

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

When to Use

Use it for lossless compression when symbol frequencies are known or can be estimated.
Use it when prefix-free variable-length codes are needed.
Use canonical Huffman codes when compact code-table storage matters.

When Not to Use

Avoid it when symbol probabilities change rapidly unless the model is updated.
Avoid it when arithmetic or range coding is needed for closer-to-entropy compression.
Avoid it for very small messages where the code table dominates the size.

What It Does

Counts symbol frequencies
Builds prefix codes from a tree

Use Cases

Lossless file compression
Entropy coding
Teaching greedy algorithms

Inputs

Symbols and frequencies
Data to encode

Outputs

Prefix code table
Encoded bit stream

Key Formulas (1)

Expected code length

cost = ∑(frequency(symbol) · code_length(symbol))

cost = sum(frequency(symbol) * code_length(symbol))

Measures the weighted size that the Huffman tree greedily minimizes.

Pseudocode

1.Count how often each symbol appears
2.Put symbols into a priority queue by frequency
3.Repeatedly combine the two least frequent nodes
4.Use the final tree to assign bit codes
5.Replace each symbol with its code

Canonical Example

Input: text = 'AAAABBBCCDAA'
Output: compressed representation with repeated runs or shorter codes
Explanation: Huffman Coding: The algorithm replaces predictable or repeated structure with a more compact representation.

Implementation Notes

Use a min-priority queue ordered by frequency to build the tree.
Generate codes by walking left and right from the root.
Use canonicalization if the compressed format needs deterministic compact code descriptions.