In the 1970s, Douglas Mc Ilroy faced the challenge of fitting a 250‑kB dictionary into just 64 kB of RAM on a PDP‑11 while building the Unix spell checker. The PDP‑11’s limited main memory forced every byte to count, making the spell checker one of the earliest examples of in‑memory data structures on commodity hardware. Instead of generic compression, he leveraged the statistical properties of the data to devise an algorithm that came within 0.03 bits of the theoretical limit.

His first step was a linguistics‑based stemming algorithm created by Steve Johnson and refined by Mc Ilroy, which cut the dictionary to 25,000 words while preserving accuracy. For fast lookups he initially used a Bloom filter implemented by Dennis Ritchie, tuned to a very low false‑positive rate so that most queries could be answered without accessing the full dictionary.

When the dictionary grew, the Bloom filter became impractical. Mc Ilroy stored differences between sorted hash codes, which followed a geometric distribution, and applied Golomb code to achieve 13.60 bits per word—only 0.03 bits above the entropy limit of 13.57 bits. He then partitioned the compressed table, accepting a slight memory increase to ~14 bits per word for substantially faster lookups.

The result was a compact, in‑memory dictionary that looked up words in microseconds, demonstrating how deep mathematical insight and careful engineering can overcome severe resource constraints. This remains a classic example of optimal design under limits. Its techniques influenced later work on probabilistic data structures and compression, and the approach is still taught in algorithms courses today.