applets.

Text Squeezer

← All apps

About Text Squeezer

How a computer makes a file smaller without losing a single letter. Type or paste up to 5,000 characters on the despatch note, or pick a sample, and three ways of packing it are worked out at once: HUFFMAN codes (short codes for common letters; press STEP or BUILD to watch the tree grow from the letter counts), RUN-LENGTH (each run of the same letter as a count and the letter) and REPEATS (an LZ77-style coder: "go back so many letters and copy so many"). The boxes on the left compare the sizes; UNPACK AND CHECK decodes all three and compares them with the original. CAN'T SQUEEZE shows where it stops working. Your text never leaves this tab and nothing is stored; COPY LINK puts it in the link only if you ask.

THE STORY

Squeezing messages is older than computers. Morse code (Samuel Morse and Alfred Vail, around 1840) already gave the commonest letters the shortest signals: E is a single dot and T a single dash. The usual story is that Vail judged which letters were common by counting the type in a printer's cases.

In 1948 Claude Shannon's paper A Mathematical Theory of Communication showed there is a floor: a text whose letters are picked with given chances needs at least a certain number of bits a letter on average, its entropy. Shannon and Robert Fano each described a way of building codes from letter counts, splitting from the top down, but it wasn't always the best possible.

In 1951 David Huffman was a graduate student in Fano's information theory class at MIT. Students could take the final exam or write a term paper, and the paper was to find the most efficient code. Huffman was about to give up and revise for the exam when he thought of building the tree from the bottom instead: keep joining the two rarest. He proved it can't be beaten by any code that gives each letter its own bit pattern, and published it in 1952.

Abraham Lempel and Jacob Ziv, at the Technion in Haifa, took a different road: don't count letters, point back at text you've already sent. Their papers of 1977 and 1978 (LZ77 and LZ78) are behind most of the general-purpose squeezing done today. The layout used here, a one-bit flag before each piece, is a 1982 refinement by James Storer and Thomas Szymanski. The zip format's usual method and PNG pictures do both: repeats first, then Huffman codes for what's left.

Run-length encoding is the simplest of all and works where long runs are common, like the white space on a scanned page; fax machines send each line of dots as run lengths, which are then given Huffman-style codes.

HOW IT WORKS

Plain: every ordinary character is one byte, 8 bits (letters outside plain English, like é or emoji, take 2 to 4 bytes, as in UTF-8).

Huffman: count each letter, put each count in its own box, then keep putting the two lightest boxes into a new box until one is left. The path from the top to a letter, 0 for the lighter side and 1 for the other, is its code. No code is the start of another, so the bits can be read back without gaps. The receiver needs the table too: here 8 bits for how many letters, then each letter and its code length (5 bits). From the lengths alone the receiver can rebuild codes of the same lengths (canonical codes: each letter keeps its code length, though the codes themselves may differ from the tree's), so the count of bits is the same. On a short text the table can cost more than it saves. The dashed line is Shannon's letter-by-letter limit for this text; Huffman's bits, before the table is added, always land within one bit a letter of it.

Run-length: each run is a count byte (1 to 255) and the letter: 16 bits a run (more for é or emoji), so ordinary writing, where almost every run is one letter long, doubles in size.

Repeats: at each point look back up to 4,095 letters for the longest stretch (3 to 18 letters) that matches what comes next. If there is one, send a 1, 12 bits for how far back and 4 bits for how long (17 bits); if not, a 0 and the letter (9 bits, more for é or emoji). A copy may run into itself: "back 1, copy 10" makes ten of the last letter. Because it uses the order of the letters, it can beat the letter-by-letter limit; Huffman can't.

Why random won't squeeze: there are 2n different files of n bits but only 2n − 1 files shorter than that, so no method can shrink every file. A method only wins by spotting a pattern, and random letters have none beyond which letters are allowed: random letters from k kinds need log₂ k bits each, however clever the method.

FURTHER WATCHING AND READING

DESPATCH NOTE

CONTENTS
LETTERS0
KINDS0
PLAIN0 bits

PACKED SIZE bits

letter-by-letter limitHuffman's code table

Decode all three and compare them with the original, letter by letter.

The text goes in the link, nowhere else.