Why common letters get short codes in a ZIP file: Huffman coding
30seconds
ASCII spends 8 bits on every letter, whether it is a common e or a rare z. In 1951 a graduate student, David Huffman, found a way to give frequent symbols short codes and rare ones long codes, with a tree you build from the bottom up.
Type your own message, merge the two lightest symbols one step at a time, and watch the codes appear and the bit count fall. Then see why the method is optimal for whole-bit codes and where it still hides, from ZIP and PNG files to JPEG and MP3.
Deep dive · 4 min
More in Computing
View all →
How a computer finds one flipped bit and fixes it: Hamming's code
A bit can flip in memory, on a disk or in a radio signal, and nothing tells you which one went wrong. In 1950 Richard Hamming published a code that finds the…
Why 0.1 + 0.2 isn't 0.3: flip the 64 bits a computer uses for decimals
Type 0.1 + 0.2 into almost any programming language and you get 0.30000000000000004. Nothing is broken. Computers count in powers of two, and a tenth is an…
How a Bloom filter says "definitely not" using just a few bits
How can a computer check whether a word is on a huge list using only a few bits per entry? A Bloom filter flips a handful of switches for every word you add…
How one extra digit on your bank card catches your typos
The last digit of your bank card number isn't part of your account. It's a check digit, computed from the other fifteen by a recipe an IBM engineer patented in…
How computers fake grey using only black and white dots
Old Mac screens, cheap printers and some modern games can only show two colours: black and white. Yet they still draw soft shadows and smooth skies. The trick…
How a computer adds 7 + 1 using nothing but switches
A computer chip has no idea what numbers are. It only has switches: billions of transistors that are either on or off. Yet wire a few of those switches into…