How do you fit a dictionary in 64kb RAM? Unix engineers solved it with clever data structures and compression tricks. Here's the fascinating story behind it.

Code Confessions is a platform or blog where developers share their experiences, challenges, and insights from their journey in software development. Through personal anecdotes, lessons learned, and reflections on coding practices, Code Confessions offers a candid and relatable perspective on the joys and struggles of being a programmer. Readers can find inspiration, empathy, and  lessons from the stories shared by fellow developers.

Confessions of a Code Addict

Unix engineers designed the Unix spell checker to perform fast spell checks using just 64kB of RAM on the PDP-11. This was achieved through innovative techniques such as Bloom filters and Golomb coding for effective data compression and lookup efficiency. The solution included a clever linguistics-based stemming algorithm for reducing dictionary size and storing differences between sorted hash codes, ultimately achieving near-optimal compression ratios. These engineering insights remain relevant today in designing efficient systems under resource constraints.

How Unix Spell Ran in 64kB RAM

A Compressed Hashing Scheme for Dictionary Lookups

Mathematical Modelling of the Hash Code Differences

A Compression Scheme for Geometrically Distributed Integers (Golomb’s code)

‘For instance, “appled” would not be caught by it because after removing the “ed” suffix, “apple” would be a valid word.’
If I removed “ed” from “appled”, I get “appl” and that’s surely not a valid word?
(I assume the algorithm would replace “i” with “y” in cases like “applied” or “fancied”.)