A Spellchecker Used to Be a Major Feat of Software Engineering (opens in new tab)

Gzip compression will achieve around 6x compression on a sorted wordlist. So even the 2008 wordlist of 240K words would reduce to about 400K. Cut the list in half or more, use a compression better suited for a sorted wordlist, and you could have a useful wordlist that would fit temporarily in RAM even in 256K machines.

I think that drfanke is suggesting that you load in half the compressed dictionary ( or a third, or whatever percentage works), and then because the document has been sorted in alphabetical order, you simply start comparing words. When you get to a word that is alphabetically after the last entry in the current dictionary, you load the next segment of the dictionary. It's not a bad approach, and even has the interesting property of enabling a load of speed enhancements of the algo, because the next word in your document is going to be nearby to its spelling in the dictionary...

Does anyone know if this algo was ever actually used?

Compressed on disk/floppy. Decompress one block at a time as you scan through it.

Typical clock rates at that time would have been 5MHz. So let's say you have a 64KB document containing 16K words. For a merge sort that's 2^18 comparisons, each requiring a small number of CPU instructions, so it would take on the order of a quarter of a second. That's better than MS Word running on a modern system :-). Besides, no matter what you do, the bottleneck is going to be reading the dictionary off the floppy.

Definitely. I enjoy reading about these data structures/algorithms.

Seems a lot of these cool things came out in the 80s due to the limits of memory/computational speed.