How Unix Spell Ran in 64 kB of RAM: A Masterclass in Engineering
In the 1970s, Douglas McIlroy faced the challenge of fitting a 250kB dictionary into just 64kB of RAM on a PDP-11. He solved this by developing a stemming algorithm to reduce word counts and designing a compression scheme using Golomb codes that nearly reached the theoretical limit. This approach, combined with a tuned Bloom filter, created a spell checker that remains a benchmark for efficient engineering under strict constraints.
Instead of relying on generic compression techniques, he took advantage of the properties of the data and developed a compression algorithm that came within 0.03 bits of the theoretical limit of possible compression.