How Unix spell ran in 64 kB of RAM
4 hours 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.