Skip to content

# Compression Explorer

Watch two compressors work the same text one step at a time: a greedy LZ77 encoder searching a window of already-seen bytes and emitting either a back-reference (distance, length) or a literal, and a Huffman coder counting symbols and joining them into a code tree, merge by merge. Running tallies show what each would really cost against the raw input.

## Huffman coding

LZ77 removes repetition; Huffman removes imbalance. Count how often each symbol occurs, put the counts in a queue, and repeatedly join the two lightest into one node until a single tree is left: the common symbols end up near the root with short codes, the rare ones deep with long ones. Step the merges below and watch the codes appear the moment the tree closes.

Rendered when the site was built. No JavaScript required. With JavaScript on, this is replaced by an interactive stepper over the same construction, with the tree drawn merge by merge.

Symbol frequencies in abracadabra
Symbol | Count
--- | ---
a | 5
b | 2
c | 1
d | 1
r | 2

1.     start: 5 symbols
         queue: c:1  d:1  b:2  r:2  a:5
         Take the two lightest nodes, join them, put the parent back. Repeat until one tree is left.

2.     merge 1 of 4
         queue: c:1  d:1  b:2  r:2  a:5
         take: 'c' (1) + 'd' (1) = 2
         queue now: b:2  r:2  [c d]:2  a:5

3.     merge 2 of 4
         queue: b:2  r:2  [c d]:2  a:5
         take: 'b' (2) + 'r' (2) = 4
         queue now: [c d]:2  [b r]:4  a:5

4.     merge 3 of 4
         queue: [c d]:2  [b r]:4  a:5
         take: [c d] (2) + [b r] (4) = 6
         queue now: a:5  [c d b r]:6

5.     merge 4 of 4
         queue: a:5  [c d b r]:6
         take: 'a' (5) + [c d b r] (6) = 11
         queue now: [a c d b …]:11

Huffman code table for abracadabra
Symbol | Count | Code | Bits spent
--- | --- | --- | ---
a | 5 | 0 | 5
b | 2 | 110 | 6
c | 1 | 100 | 3
d | 1 | 101 | 3
r | 2 | 111 | 6

Raw
  88 bits
Encoded payload
  23 bits
Code table
  93 bits
What a decoder receives
  116 bits, larger than the raw input

    01101110100010101101110
    decode traversal (root → leaf per symbol)
      bits 0 @0: left  ⇒ 'a'
      bits 110 @1: right → right → left  ⇒ 'b'
      bits 111 @4: right → right → right  ⇒ 'r'
      bits 0 @7: left  ⇒ 'a'
      bits 100 @8: right → left → left  ⇒ 'c'
      bits 0 @11: left  ⇒ 'a'
      bits 101 @12: right → left → right  ⇒ 'd'
      bits 0 @15: left  ⇒ 'a'
    … 3 more symbols
    ---
    recovered 11 bytes: identical to the input

The worst case has a page of its own: the Entropy Fountain is a byte stream described entirely by its bit balance and histogram, with nothing repeating for a back-reference to reach. At the other end, the gzip stream these tokens would go into is one of the signatures File Header Forensics reads straight off a file's first bytes.

About this lab6 paragraphs

The LZ77 encoder is greedy: at each position it takes the longest match it can find and moves on, never backing up to check whether a shorter match here would have bought a longer one next time. Real encoders do look ahead, and that is most of the difference between this trace and a production deflate stream.

The window, look-ahead and minimum match are the whole LZ77 trade-off, and the sliders expose them: a bigger window reaches older repeats (a real format pays for that reach in distance bits), a longer look-ahead permits longer copies, and a lower minimum match takes back-references that cost more than the literals they replace. The defaults (unbounded window, 64-byte look-ahead, 3-byte minimum) are a teaching configuration, not gzip's.

Short or random input coming out larger than it went in is the encoder working, not failing. A back-reference costs more bits than a literal, so text with nothing to repeat has nothing to win. Try a phrase that repeats itself.

Huffman is charged for its code table here, and that is why eleven bytes of `abracadabra` come out bigger than they went in: 23 bits of payload against 88 raw looks like a rout until the 93 bits a decoder needs in order to read them are added. Leaving the header out is the arithmetic that makes entropy coding look free. A real format packs it far tighter than the simple 16-bits-per-symbol model used here, and a longer, more lopsided input wins even after paying for it. But the honest answer on a short string is that the algorithm grew it.

The tie-break is this implementation's, not the algorithm's. When two nodes weigh the same, the queue takes the one built first, so one input always yields one tree and the page can be goldened. A different tie-break gives a different code table that is exactly as good: Huffman guarantees an optimal length, not a unique one.

Both encoders run offline: `compression-lab-cli huffman` prints this construction, `compression-lab-cli lz77` (and `lz77-cli`, with the same `--window`/`--lookahead`/`--min-match` flags) prints the step trace, and `compression-lab-cli compare` tabulates both against the raw input.

Use it locally This lab has a native command line twin. Build `compression-lab-cli` from the site's source with:

    cargo build --release --bin compression-lab-cli

Source and licence terms