A spellchecker used to be a major feat of software engineering (2008)

I'm particularly interested in this one, and I'm curious about how useful something like this would be to use.

> The second does not use a dictionary at all (Morris & Cherry 1975). Like the previous method, it divides the text into trigrams, but it creates a table of these, noting how often each one occurs in this particular piece of text. It then goes through the text again calculating an index of peculiarity for each word on the basis of the trigrams it contains. Given pkxie, for instance, it would probably find that this was the only word in the text containing pkx and kxi (and possibly xie too), so it would rate it highly peculiar. The word fairy, by contrast, would get a low rating since fai, air and iry probably all occur elsewhere, perhaps quite often, in the passage being analysed. Having completed its analysis, it draws the user's attention to any words with a high peculiarity index. Like the previous method, it would fail to spot a high proportion of ordinary spelling errors, but it is quite good at spotting typing errors, which it was designed for. An advantage that it has over all dictionary-based methods is that it is not tied to English; it will work on passages of, say, French, German or Greek.

(The Morris there is Bob Morris).

In my first job I worked for Tasman in Leeds and produced a Word Processor for IBM PC compatibles in 8086 assembler with some help, and then a spelling checker.

For the spelling checker I did a whole load of analysis on a 70,000 word list from Collins and produced a list of tokens to represent common strings of letters. However, in the end I really had to cut the original word list down to get the whole thing onto a single 360K floppy.

After I left Tasman, I was lying in bed one night still thinking about it and realised where I had gone wrong. The tokenising thing, which someone else had put me onto had blinded me. I had stared at word lists for months and hadn't pinned down the obvious pattern. All but 26 words in the 70,000 word list shares the bulk of their characters with the word before it.

So the solution is use 5 bits of the first byte as a count of chars from the word before, 3 bits indicate commons enddings (ship, s, ing) or that the following bytes are tokens for the rest of the word. With this I got the word list compressed to less than 2 bytes per word.

I took this back to Tasman. They put all 70,000 words and the spelling checker onto a 175K floppy for the ZX Spectrum +3.

[Edited for typos]

Just a hash map ain't gonna work. The only reason spell checking is perceived as a solved problem is availability of libraries. Here's an open source example https://github.com/hunspell/hunspell way above 10k lines of code.

I speak 4 languages, and in my experience what's in Microsoft Office is the best one I used so far.

https://norvig.com/spell-correct.html

A spell checker is not simply a list of words, it's a way to check mistakes according to a standard and to point towards ways to fix these mistakes. This not reducible to a look-up in a hashtable. It requires taking into account some complicated things about the definition of a word and the context in which it is written. You might think that's grammar checking but the boundary is not clear and in any case, any language processing application starts with tokenizing and deciding what counts as words and on what basis.

What is a word even ? Is "CIA" a word ? What about "C.I.A." ? What about C (as in the language) ? What about c (as in the speed of light) ? 2,4-Dinitrophenylhydrazine ? How does the spellchecker handle dashes and apostrophes ? What about proper nouns ?

Really, the example is poorly chosen.

For example, consider the erroneous phrase "he was put through the ringer." Although "ringer" matches a spelling in the dictionary, it doesn't make sense semantically (a "ringer" being a device that rings bells, a near-duplicate of something else, etc.) and the proper idiom is "put through the wringer" (since a wringer is/was a device to squeeze water out of a wet mop or wet laundry. Squeezing someone through a pair of rollers is particularly evocative.)

Although you do see "nerve-wracking" or "wracking" (i.e. wrecking) one's brain, the more traditional "racking" (literally to torture by stretching on a medieval rack) seems more appropriate (although the term "nervous wreck" is common.) Shakespeare may have exploited the pun of "wrack" vs. "rack," so perhaps we can also.

"Security breaches" and "security breeches" sound alike but have somewhat dissimilar meanings. Network and system administrators might consider donning the latter in preparation for the former.

A spellchecker is only a limited solution to the task of proofreading. I've never used the grammarly product, but at least from the ads it seems it can catch many things that human proofreaders would catch. There might still be domain-specific things that requires humans.

But the grammarly product has way more logic behind it than just using a simple table of words. No idea if it's parametric or uses an ML language model, or maybe a combination, but the feature set wouldn't be possible with just a table.

So instead of a lone employee being tasked to write a spellcheker, you suddenly have an entire industry focused on NLP. That's how the growth of the computing industry looks like :).

"For every cycle a hardware engineer saves, a software engineer will add two instructions."

I thought of that reading last paragraph:

"Fast forward to today. A program to load /usr/share/dict/words into a hash table is 3-5 lines of Perl or Python, depending on how terse you mind being."

1: https://news.ycombinator.com/item?id=25285862

    Spell chequer by Martha Snow


    Eye halve a spelling chequer
    It came with my pea sea
    It plainly marques four my revue
    Miss steaks eye kin knot sea.

    Eye strike a quay and type a word
    And weight four it two say
    Weather eye am wrong oar write
    It shows me strait a weigh.

    As soon as a mist ache is maid
    It nose bee fore two long
    And eye can put the error rite
    It's rare lea ever wrong.

    Eye have run this poem threw it
    I am shore your pleased two no
    It's letter perfect awl the weigh
    My chequer tolled me sew.

I've been considering adding one to my text editor. I found out I'm not as good a speller as I thought I was before spellcheckers :-/

I should start keeping notes when that happens as I'd really like to understand what I'm doing that causes them issues, it might help me when I'm struggling to spell a word and get stuck.

(Through it's a feat of properly incorporating linguistic knowledge into your spell checker.)

It just happens that for the English language terrible bad spell checkers are often still good enough.

https://youtu.be/tc4ROCJYbm0

(Shell coding starts at 8:40)

“Two different hashing methods have been implemented. The first, based on a simple superimposed code scheme first proposed by Bloom,9, 10 was supplied by D. M. Ritchie and succeeded in encoding a 25,000-word list into 50,000 bytes. A more elaborate method, in which values of a conventional hash func- tion are represented in a differential Huffman code, squeezed 30,000 words into 52,000 bytes. The stop list is handled by the same method in a different process.”

Doug McIlroy discussed the history of spell at Bell Labs here: https://www.cs.dartmouth.edu/~doug/spell.pdf

I remember emailing Doug to ask him about this and he was great, very helpful to me. Thanks Doug!

My professor (Josh Bloch, in his API design class at CMU) showed us this paper, then showed us his quick implementation using standard Java APIs in less time than the rest of the lecture.

[1] https://en.wikipedia.org/wiki/Key_Word_in_Context

[2] https://prl.ccs.neu.edu/img/p-tr-1971.pdf

2015 https://news.ycombinator.com/item?id=10789019

2012 https://news.ycombinator.com/item?id=4640658

2012 https://news.ycombinator.com/item?id=3466388

Discussed at the time: https://news.ycombinator.com/item?id=212221

[1] https://www.cs.hmc.edu/~geoff/ispell.html

[2] http://web.mit.edu/~mkgray/jik/sipbsrc/src/ispell-3.1/Contri...

I was in primary school (age 11) and we had a Microbee at home with 64KB of RAM and a copy of Turbo Pascal. My sister is/was dyslexic so with a bit of help from my older brother (who would have been in first year of computer science at the time) I wrote a spellchecker for her. It think it might have been a Christmas present, so I had probably been programming for less than a year at that stage, and only in the afternoons after I got back from school.

It read the whole document into memory (not the English dictionary, which was too big) in a tree structure. Pointing out that I could use a binary tree and teaching me how to use pointers was my brother's contribution. Then it read through an on-disk copy of the English dictionary. It wasn't a complete dictionary, so I didn't do any compression on the storage, and then asked the user (my sister) to review each word that wasn't in the dictionary, sending any issues out to the printer with a line number and the word in bold.

So if a kid with very little experience could do it, professionals would have had little trouble back then.

Writing a spell-checker on the computer we had before that though (the ZX-spectrum with 16KB of RAM and the only bulk storage being a cassette tape)... that would have been hard. We've definitely progressed since then.

But neither spell checking nor its more advanced siblings spelling correction or automatic spelling correction is solved. Here is an example:

"I want to by Apple"

"I want to be Apple"

"I want to buy Apple"

Because "by" is a genuine English word, a spellchecker based on a simple hashtable will not detect the error, which obviously exists. We need to look at the context of the whole sentence or even document. Today we can use deep learning and word embedding to solve/improve that problem.

A simple spelling corrector that is based on edit distance would always prefer "be" over "buy" because "be" is the more frequent word of both.

So the risk of all the easy accessible libraries for a certain task is, that you think the problem is solved, but you overlook many problems because the topic is much more diverse and deep than you would think at the first glance

Another point is that while hardware improved, also the expectations have risen. We expect milliseconds latency instead of seconds, we often require the software to work in a multi-tenant architecture with thousands or millions of concurrent users.

So even for seemingly simple and straightforward tasks, and despite all the exciting advances in hardware, always new challenges present themselves.

I was curious -- This Python script consumes 9.5 MB of RAM on my Mac, which is a whole lot of 1980s-era PCs. Sure, in most cases this one decision to use a terse but unoptimized data structure won't matter much on a modern computer, but it adds up!

I frequently copy and paste a word into Google just to get the correction auto suggested and auto searched for, whereas Apple operating systems will know it is spelled wrong as an unrecognized word but offer no suggestions

https://winworldpc.com/product/turbo-lightning/1x

I wish we had spell checking (with corrections) competitions.

Computer based chess is very cool.

But a little time spent on a computer based spellchecking competition would help a lot of native and non native speakers every day.

And I'm just talking English, to start.

I rarely need any spellchecking on smartphone because most spelling errors have been eliminated at the point of word entry.

Modern spell checkers are fairly interesting beasts. Do check out, use and let me know if i can help with any issues / features.

Now that I think about it spellcheckers were pretty sh!te not that long ago...

https://itnext.io/string-similarity-the-basic-know-your-algo...

http://www.addictivesoftware.com/addict.htm

https://norvig.com/spell-correct.html

Unix has had spell checking since PDP-11 days, in 64kB data. The secret was a Bloom filter.

By then it was fairly trivial.

    $a = file('words');
    $m = array_flip($a);

Nooo.. For gods sake at least use a trie. This kind of thing makes me want to like “annoying” algorithm interview questions.