In the 1970s, Douglas McIlroy faced the challenge of fitting a 250kB dictionary in 64kB of RAM for the Unix spell checker at AT&T. Rather than relying on generic compression techniques, he developed a compression algorithm that almost reached the theoretical limit of compression. McIlroy’s engineering feat included using a Bloom filter for fast lookups and later moving to hash compression techniques when the dictionary grew. His clever data structure design involved storing hash differences and using Golomb’s code for compression. This unique solution allowed the dictionary to be compact enough to fit in memory while maintaining fast performance.
https://blog.codingconfessions.com/p/how-unix-spell-ran-in-64kb-ram