Unix Spell: The 64kB RAM Miracle
2025-01-19
In the 1970s, the Unix spell checker faced an incredible challenge: fitting a 250kB dictionary into a mere 64kB of RAM on a PDP-11. Douglas McIlroy's ingenious solution involved a multi-stage approach. Initially, a Bloom filter provided fast lookups, but as the dictionary grew, he developed a novel hash compression scheme. By recognizing that differences between sorted hash codes followed a geometric distribution, and employing Golomb coding, he achieved near-theoretical compression limits. Finally, partitioning the compressed data further improved lookup speed. This story is a masterclass in constrained optimization, showing how clever algorithms can overcome seemingly impossible limitations.
Development
compression