Huffman prefix decoding: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Rebuild the deterministic tree from frequencies and walk one edge for each bit, emitting symbols at leaves.

Rebuild exactly the encoder tree from the frequency table and deterministic tie rule. Walk from the root according to each bit; at a leaf, emit the symbol and return to the root.

Open the 3D visualization

Huffman prefix decoding example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Huffman prefix decoding

Decoding a static Huffman payload and detecting truncated or inconsistent teaching streams.

Choosing an alternative

The encoder maps symbols to root-to-leaf paths. The decoder maps paths back to symbols and verifies the resulting frequency counts.

Worked example: input and state changes

Example input

a:3,b:1 | 1110

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Count symbols and initialize leaf frequencies.

    State at this checkpoint
    {
      "values": [
        3,
        1
      ],
      "active": [],
      "kind": "graph",
      "directed": true,
      "chosen": [],
      "visited": [],
      "nodeLabels": [
        "a",
        "b"
      ],
      "output": [],
      "result": 0
    }
  2. Step 2: Read bit 1; decoded a.

    State at this checkpoint
    {
      "values": [
        3,
        1,
        4
      ],
      "active": [
        2
      ],
      "kind": "graph",
      "directed": true,
      "chosen": [],
      "visited": [],
      "nodeLabels": [
        "a",
        "b",
        "merge"
      ],
      "output": [
        97
      ],
      "result": 0
    }
  3. Step 3: Read bit 1; decoded aa.

    State at this checkpoint
    {
      "values": [
        3,
        1,
        4
      ],
      "active": [
        2
      ],
      "kind": "graph",
      "directed": true,
      "chosen": [],
      "visited": [],
      "nodeLabels": [
        "a",
        "b",
        "merge"
      ],
      "output": [
        97,
        97
      ],
      "result": 0
    }
  4. Step 5: Read bit 0; decoded aaab.

    State at this checkpoint
    {
      "values": [
        3,
        1,
        4
      ],
      "active": [
        2
      ],
      "kind": "graph",
      "directed": true,
      "chosen": [],
      "visited": [],
      "nodeLabels": [
        "a",
        "b",
        "merge"
      ],
      "output": [
        97,
        97,
        97,
        98
      ],
      "result": 0
    }
  5. Step 6: Decoded aaab.

    State at this checkpoint
    {
      "values": [
        3,
        1,
        4
      ],
      "active": [],
      "kind": "graph",
      "directed": true,
      "chosen": [],
      "visited": [],
      "nodeLabels": [
        "a",
        "b",
        "merge"
      ],
      "output": [
        97,
        97,
        97,
        98
      ],
      "result": 4
    }

Expected final state

Decoded aaab.

Complexity and input bounds

Family: Strings. Time complexity: O(alphabet^2 + bit count).

Implementation detail: The input is symbol:frequency pairs and a bit string, with total frequency at most sixteen. Downloads accept 26 frequencies and up to 64 individual bits, returning decoded length or -1. Empty tables require an empty payload; output is unspecified on error. Histogram validation detects inconsistencies but is not a checksum.

Space complexity: O(alphabet size + decoded length) auxiliary storage and output, plus recorded frames.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

symbol:frequency pairs | bits. Total frequency at most 16; stream must reproduce those counts. Single-symbol code 0.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

Do not emit an incomplete final path. Single-symbol code 0 still consumes one bit per symbol. Reject nonbinary digits, excess output, and a histogram inconsistent with the supplied frequencies.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// frequencies has 26 nonnegative entries for a..z summing to at most 16; bits has n 0..64 individual binary digits. Rebuilds exactly the encoder tree (frequency, then smallest-symbol tie rule). Output capacity at least 16. Returns decoded count or -1 for invalid frequencies/bits, truncated codeword, excess output or histogram mismatch. Single-symbol code 0. Empty frequencies require no bits. Output unspecified on error. O(alphabet^2 + n) time, O(alphabet + decoded length) storage. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(frequencies, bits, n, output) {
    if (n < 0 || n > 64) { return -1; }
    let freq = Array(256).fill(0); let observed = Array(256).fill(0); let total = 0; let count = 0; let state = 0;
    for (let i = 0; i < 26; i++) { if (frequencies[i] < 0 || frequencies[i] > 16) { return -1; } freq[i] = frequencies[i]; total += freq[i]; }
    if (total > 16) { return -1; }
    if (total == 0) { if (n == 0) { return 0; } return -1; }
    let left = Array(256).fill(0); let right = Array(256).fill(0); let parent = Array(256).fill(0); let smallest = Array(256).fill(0); let nodes = 26; let active = 0; let root = -1; let a = -1; let b = -1;
    for (let i = 0; i < 256; i++) { left[i] = -1; right[i] = -1; parent[i] = -1; smallest[i] = i; }
    for (let i = 0; i < 26; i++) { if (freq[i] > 0) { active++; root = i; } }
    while (active > 1) { a = -1; for (let k = 0; k < nodes; k++) { if (freq[k] > 0 && parent[k] == -1) { if (a == -1 || freq[k] < freq[a] || (freq[k] == freq[a] && smallest[k] < smallest[a])) { a = k; } } } parent[a] = nodes; b = -1; for (let k = 0; k < nodes; k++) { if (freq[k] > 0 && parent[k] == -1) { if (b == -1 || freq[k] < freq[b] || (freq[k] == freq[b] && smallest[k] < smallest[b])) { b = k; } } } parent[b] = nodes; left[nodes] = a; right[nodes] = b; freq[nodes] = freq[a]+freq[b]; smallest[nodes] = smallest[a]; if (smallest[b] < smallest[nodes]) { smallest[nodes] = smallest[b]; } root = nodes; nodes++; active--; }
    
    state = root;
    for (let i = 0; i < n; i++) { if (bits[i] != 0 && bits[i] != 1) { return -1; } if (root < 26) { if (bits[i] != 0) { return -1; } state = root; } else { if (bits[i] == 0) { state = left[state]; } else { state = right[state]; } }
     if (state < 26) { if (count >= total) { return -1; } output[count] = state+97; count++; observed[state]++; state = root; }
    }
    if (state != root || count != total) { return -1; }
    for (let i = 0; i < 26; i++) { if (observed[i] != frequencies[i]) { return -1; } }
    return count;
}

Source

Original Huffman research for minimum-redundancy prefix coding. The teaching implementation adds a deterministic tie convention, bounded lowercase alphabet and explicit single-symbol bit convention.