How Unix spell ran in 64 kB of RAM

How Unix spell ran in 64 kB of RAM

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

How do you fit a 250 kB dictionary in 64 kB of RAM and still perform fast lookups? For reference, even with modern compression techniques like gzip -9, you can't compress this file below 85 kB. In the 1970s, Douglas McIlroy faced this exact challenge while implementing the spell checker for Unix at AT&T. The constraints of the PDP-11 computer meant the entire dictionary needed to fit in just 64 kB of RAM. A seemingly impossible task.

Instead of relying on generic compression techniques, he took advantage of the properties of the data and developed a compression algorithm that came within 0.03 bits of the theoretical limit of possible compression. To this day, it remains unbeaten. The story of Unix spell is more than just historical curiosity. It's a masterclass in engineering under constraints: how to analyze a problem from first principles, leverage mathematical insights, and design elegant solutions that work within strict resource limits.

TL;DR

If you're short on time, here's the key engineering story:

The Unix spell started in the 1970s as an afternoon prototype by Steve Johnson at AT&T, before Douglas McIlroy rewrote it to improve its performance and accuracy. McIlroy's first innovation was a clever linguistics-based stemming algorithm that reduced the dictionary to just 25,000 words while improving accuracy. For fast lookups, he initially used a Bloom filter-perhaps one of its first production uses. Interestingly, Dennis Ritchie provided the implementation. They tuned it to have such a low false positive rate that they could skip actual dictionary lookups.

When the dictionary grew to 30,000 words, the Bloom filter approach became impractical, leading to innovative hash compression techniques. They computed that 27-bit hash codes would keep collision probability acceptably low, but needed compression. McIlroy's solution was to store differences between sorted hash codes, after discovering these differences followed a geometric distribution. Using Golomb's code, a compression scheme designed for geometric distributions, he achieved 13.60 bits per word-remarkably close to the theoretical minimum of 13.57 bits. Finally, he partitioned the compressed data to speed up lookups, trading a small memory increase (final size ~14 bits per word) for significantly faster performance.

The rest of the article expands each of these points and gives a detailed explanation with all the math and logic behind them.

Origins of The Unix spell Command

In order to secure funding for Unix, Ken Thompson and Dennis Ritchie pitched Unix as a text processing system for the patents department to AT&T. Naturally, a text processing system needed a spell checker as well. The first version of Unix spell was written by Steve Johnson in 1975 which was a prototype. Jon Bentley mentions that Steve wrote it in one afternoon. Even though it worked, it was not very accurate. It was pretty simple. It would split the input file into a stream of words, do some light preprocessing such as remove numbers and special characters, convert to lower case, then sort, unique, and finally pass the list to the spell program which would simply check for the existence of those words in a dictionary on the disk. Because of its simplistic implementation, it was not very accurate, and also slow because of dictionary lookups on the disk.

After seeing the adoption of the initial version, Douglas McIlroy took up the project to rewrite it with the goal of improving the accuracy and performance of the tool. He worked on two separate fronts both involving some very clever engineering:

• Building an affix removal algorithm for reducing words to their stems, and a compact dictionary consisting of the stem words
• A compact data structure for loading the dictionary into memory for doing fast lookups

This article is going to be focused on the data structure design part, but let's spend a section to get an overview on the affix removal algorithm to see how it worked.

The Affix Removal Algorithm

Using a full fledged dictionary for doing lookups was slow because the computers those days had only a few kilobytes of main memory and using disk based lookups was even more slower. Douglas McIlroy came up with the idea of an algorithm which would iteratively remove common prefixes and suffixes from a word and look up a dictionary to see if the reduced word is present in it or not. The algorithm would follow the affix removal process until there were no affixes left to remove and if even after this the word was not present in the dictionary, then it would be flagged as a misspelling.

For instance, the algorithm would reduce the word "misrepresented" to "present" by removing the prefixes "mis", "re", and the suffix "ed". And because "present" is a valid word in the dictionary, it would not flag it as a misspelling. This affix removal technique was not 100% accurate and would sometimes let misspelled words pass through. But, such occurrences were deemed acceptable at that time. He also implemented a bunch of exceptions to these rules to avoid some of the common errors.

Overall, this algorithm resulted in a very compact dictionary. The final dictionary consisted of 25,000 words, which seemed possible to load into memory with a well engineered data structure. Let's move on to discussing how he managed to implement in-memory dictionary lookups with just 64 kB of memory.

A Bloom Filter based Lookup

Bloom published his work on Bloom filter in 1970 while the Unix spell was developed in the mid-1970s. At this time, Bloom filter was not even called Bloom filter. In his paper, Douglas calls it a "superimposed code scheme". Interestingly, the Bloom filter implementation he used was given to him by Dennis Ritchie.

Even though the dictionary size was 25,000 words, it was still not possible to load it as it is in just 64 kB of RAM. Besides, it also needed fast lookups. The first data structure that Douglas used was a Bloom filter. In the paper he doesn't call it Bloom filter, instead he refers to it as a "superimposed coding scheme", attributed to Bloom's paper from 1970. Interestingly, he gives the credit for the implementation of the Bloom filter he used to Dennis Ritchie.

A Bloom filter consists of a bit table initialized to all zeros. To add an item to the Bloom filter, you apply multiple hash functions to the item. Each hash function generates an index in the table, and that bit index is set to 1. If k hash functions are used, then, k different bit indices are turned on in the table. For a more detailed explanation of Bloom filter, please check out my article on Bloom filters.

Looking up an item, whether it exists in the table or not, requires the same procedure. You need to apply the k hash functions, and for each of them check if the corresponding bit is set to 1 in the table or not. If even one of the bits is not on, then it means that the item is not present in the dataset. However, if all the bits are set, then it indicates that the item might be present, but this may also be a false positive. False positives can occur because of hash collisions. When querying for an item, we cannot be 100% sure if a bit is on in the table because of the query item, or because of a hash collision with another item.

When using Bloom filter, you need to implement a strategy to handle false positives. For instance, in this case it could mean doing a full dictionary search. But that would defeat the whole purpose of using a Bloom filter, which was to save memory and do fast dictionary lookups. In the case of a spell checker, most of the words exist in the dictionary and only a fraction of words are misspelled, so we would be checking the full dictionary quite a lot. However, a Bloom filter can be tuned to achieve a desired false positive rate.

The following formula computes the false positive probability for a Bloom filter with a given size n, number of inserted items m, and number of hash functions k.

In his paper, Douglas mentions that a false positive probability of 1 in 2000 was acceptable to them, which meant that for such a low false positive rate, they did not need to consult the dictionary. As they had a dictionary of 25,000 items, the number of items was fixed. They fixed the bit table size at 400,000 bits because of the limited amount of memory. Based on these factors, using 11 hash functions allowed them to keep the false positive rate at around 1/2000.

Results of Using Bloom Filter

They used the Bloom filter based spell implementation for a while. In the paper, Douglas mentions that even though the false positive rate was acceptable, in the wild, they were encountering a lot of new words that needed to be added to the dictionary. This led to the dictionary size going up from 25,000 to 30,000. However, for a dictionary of this size, their Bloom filter required a bigger bit table size which was not possible for them. As a result, Douglas looked for alternate data structure designs to be able to fit a dictionary of 30,000 words in memory with similar lookup performance and accuracy.

A Compressed Hashing Scheme for Dictionary Lookups

As the dictionary size exploded from 25,000 to 30,000, Douglas needed a more memory efficient data structure to hold the dictionary in memory. A hash table was an attractive solution, but it would have consumed much more memory than a Bloom filter because it requires storing the hash, as well as, the actual words to handle collisions.

Instead of a full hash table, Douglas decided to store just the hashes of the words. The lookup required computing the hash of the input word, and then checking for its existence in the hashes using a scan. One intuition for doing so might have been that the individual words can be of varying lengths, but a hash function will naturally compress them down to a fixed number of bits, and that may possibly allow them to fit the hashes in memory. But hashes can collide, so they needed a large enough hash code to have an acceptably low probability of collisions.

Computing the Optimal Hash Code Size

If each word in the dictionary is hashed to a hash code of size b bits, then there are 2^b total possible hash codes in that space. If the size of the dictionary is v words, then the probability of a hash collision can be computed as:

They had a dictionary of 30,000 words, which is ~2^15 words. Moreover, he mentions that a collision probability of 1 in 2^12 was acceptable to them. This gave a hash code size of 27 bits. But 27-bit hash codes were too big: with 2^15 words, they needed 2^15 * 27 bits of memory, while the PDP-11 had only 2^15 * 16 bits (64 kB) of RAM-compression was essential.

The Theoretical Minimum Limit of Hash Code Compression

Before implementing any compression algorithm, we need to know what is the theoretical minimum number of bits we can achieve to compress this piece of data. It acts as a benchmark to tell us how well we are able to compress the data. This theoretical minimum is computed using the information content of the event which generated the data we are trying to compress. This concept comes from information theory which is the underpinning foundation for all of the data compression techniques.

Information Content of an Event

The basic idea behind information content is to use the probability of an event to determine how many bits are needed to encode it without loss of information. A highly likely event carries less information (for instance a 100% probable event has no information and needs 0 bits to encode), while a less probable event contains much more information and needs more bits. There is an inverse relationship between the probability of an event and its information content, which leads to the following formula:

Now, to compute the information content of a set of hash codes, we need to figure out the probability of generating them. If the size of a hash code is b bits, then there are a total of 2^b possible hash codes in that space. Out of that, we are selecting a set of v unique hash codes. Therefore, the probability of any one of these sets of being generated is:

Thus, the information content of these hash codes is:

To simplify things, we can use Stirling's approximation:

The paper makes another simplifying assumption that the number of words in the dictionary (30,000) is much smaller than the total number of hash codes (2^27), i.e., v << 2^b, this allows them to simplify (2^b - v) as 2^b in the above computation.

Using these two approximations leads to the following formula for the information content:

Plugging in v = 30,000 and b = 27, the minimum number of bits needed to encode a single hash code turns out to be 13.57, which was ~50% shorter than the original hash codes, and within the capacity of the PDP-11's memory.

A Delta Based Compression Scheme

At this point they knew how much compression they could achieve but the bigger question was how to get there. Instead of compressing the raw hash codes, what if they computed and stored the differences between successive hash codes (in their sorted order)? This is similar to how delta encoding works, but not quite the same. There were a couple of advantages of working with hash differences.

• By definition the differences were smaller than the raw hash codes
• And many of the difference value would repeat because the difference of several hash codes might be the same. This implied that it was easier to compress these differences than the hash codes.

Computation of Hash Differences

Hash differences were computed by sorting the hash codes and taking differences between consecutive values. For instance:

sorted hash codes: 5, 14, 21, 32, 55, 67
hash differences: 5, 9, 7, 11, 23, 12

Let's also see how the lookup of a word worked when they stored hash differences instead of the actual value. Looking Up a Wo...