unix

How Unix spell ran in 64 kB of RAM

2 months ago

Douglas McIlroy fit a 250kB dictionary into 64kB RAM for Unix spell using compression and hash differences.
The dictionary was reduced to 25,000 words via an affix removal algorithm that strips prefixes and suffixes.
Initial lookups used a Bloom filter with 400,000 bits and 11 hash functions, achieving a 1/2000 false positive rate.
When the dictionary grew to 30,000 words, Bloom filters became impractical due to memory limits.
A 27-bit hash code was chosen for low collision probability, but compression was needed to fit memory.
McIlroy computed the theoretical minimum compression at 13.57 bits per word using information theory.
Hash differences were modeled as a geometric distribution, enabling efficient compression with Golomb's code.
Golomb coding achieved 13.60 bits per word, remarkably close to the theoretical minimum.
Partitioning the compressed data into bins sped up lookups with minimal memory overhead (14 bits per word).
Unix spell evolved through three phases: affix removal, Bloom filter, and compressed hashing with Golomb codes.