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 | Count |
|---|---|
| a | 5 |
| b | 2 |
| c | 1 |
| d | 1 |
| r | 2 |
-
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.
-
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
-
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
-
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
-
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
| 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.
compression-lab-cli from the site's source with:
cargo build --release --bin compression-lab-cliSource and licence terms