Unix spell checker fit dictionary into 64KB RAM using data structures and compression

The Challenge of Limited Memory

In the 1970s, Douglas McIlroy faced the task of implementing a spell checker for Unix on a PDP-11 computer, which had a memory constraint of just 64KB RAM. The dictionary alone was 250KB, making it a significant challenge to store and access efficiently within the available memory.

Linguistic Stemming and Bloom Filters

McIlroy's initial innovations included a linguistics-based stemming algorithm that reduced the dictionary to 25,000 words while improving accuracy. For fast lookups, he employed a Bloom filter, an early production use of the data structure, with an implementation provided by Dennis Ritchie. This allowed for a low false positive rate, often bypassing full dictionary lookups.

Innovative Hash Compression

As the dictionary grew to 30,000 words, the Bloom filter approach became impractical. McIlroy then developed innovative hash compression techniques. He computed that 27-bit hash codes were needed for acceptable collision probability and devised a method to store differences between sorted hash codes, which followed a geometric distribution.

Golomb's Code for Optimal Compression

Using Golomb's code, a compression scheme suited for geometric distributions, McIlroy achieved 13.60 bits per word, remarkably close to the theoretical minimum of 13.57 bits. He further partitioned the compressed data to speed up lookups, resulting in a final memory footprint of approximately 14 bits per word for improved performance.