AFAIK most of them use some blend of edit distance (usually a modification of Levenshtein distance to support transpositions) and often a phonetic algorithm like Soundex[1].
Dictionaries are most often stored as a radix trie, and a bloom filter can be used to quickly check if a word is misspelled.
EDIT: I'm dumb, you said "from then". Whoops. If I had to guess it was probably similar, as radix trie + bloom filter is a very memory efficient way to store and search the dictionary.
Bloom filter: That's assuming your vocabulary is reasonably finite. http://www.ling.helsinki.fi/~fkarlsso/genkau2.html has a list of forms for a single finnish noun. That's including case, possessives and clitics, but you can also have compounding (eg. several nouns in a row as one word) and derivations into other parts of speech (verbs become nouns etc). And once you've found out it's misspelt, you need suggestions..
I used Word Writer 4 on the C64. Its spell-check system avoided loading the entire dictionary into memory or using an on-disk structured random-access database. Instead, it simply sorted the words in your document first, then stepped through this list while sequentially reading the sorted dictionary from disk. You could watch this process on the screen while it was happening.
Needless to say, spell checking was a lengthy task that you invoked sparingly. :)
Natural language processing is HARD, and is an ongoing topic of research. Making a spellchecker that works right is still a major feat of software engineering. I have to hand-tweak all the spellcheckers in all the software programs I use that include spellcheckers.
But it seems like to me the "progress" mentioned is more in the hardware than the software, in contrast to the emphasis on Software Engineering from the title.
We still could be stuck writing assembly on super fast hardware. Programming languages' UI has definitely improved, enabled to be sure by hardware (as in his Python/Perl example).
I would like to see some progress on the OSx spell checker. I am tired of going to google to get the correct spelling for words. It seems to be much better at correcting spelling.
Google's spellchecker has been watching billions of people correct their own typos keystroke-by-keystroke for years. It runs on a global network of computers with untold hoards of RAM and disk arrays with indefinite IOPS. Your OSx spellchecker gets updated... occasionally, and it runs on your Mac.
Makes me think that the equivalent of this '30 years ago' story with today's present as the past will be "they used to carry out complex operations on their OWN computers? Oh, they had non-instant network speeds, that explains it..."
OS X uses Hunspell, an open source tool used by many. Maybe you should be complaining that Google aren't contributing to Hunspell or anything that might replace it.
Others might also find interesting this video from 1982 where Brian Kernighan demonstrates building a simple spell checker using UNIX command line utilities: https://youtu.be/XvDZLjaCJuw?t=5m15s
That was a great watch...and if you keep on watching for a few more minutes, you can watch Lorinda L. Cherry rewrite his implementation using Unix pipes and then creating a talking calculator. The screencasting technology wasn't quite there yet ;), but both are really excellent demonstrations and eludications of the Unix philosophy and mindset that is pretty much unchanged and invaluable ~34 years later https://youtu.be/XvDZLjaCJuw?t=13m47s
I still remember getting a new computer for Christmas almost two decades ago and seeing Microsoft underline words red and correct spelling/grammar the first time. It felt like magic.
This is perhaps true for English, isolating language with clear word boundaries.
Making spellchecker for Russian (inflecting language), Japanese (I think they don't always put spaces between words, Koreans less so) or Finnish (agglutinating language) still takes good part of a decade, more or less.
Everything was a major feat if you go back far enough. Having started as a programmer in the early 80's every programming generation did things that seemed impossible to the prior one. Today the "generations" just happen faster.
I remember when I was about twelve or thirteen, seeing some mention of automatic spelling checking, trying to figure out how it could be done, and ending up very skeptical. It seemed to me there just wasn't enough regularity for any compact algorithm to do the job, so it just couldn't be done without literally having a list of every word in the English language, and even if you had a 64K machine, that wouldn't fit in memory alongside a word processor and your document.
Er... nope. Spellcheck is not just a matter of looking up a word in a hash table. Spellcheck is still a hard problem even if hardware and software make it a bit easier today than it was a couple decades ago. To elucidate, computers are still far too slow to do a simple brute force search for the closest matching words. One has to use binary searches, at least, or better, tree data structures to get good performance.
Spell-checking seems straightforward enough now, if you're just comparing words against a stored dictionary. The tricky part seems to be providing reasonable suggestions for a misspelled word.
Karlsson's Finnish spellchecker was already there around 1982(?), because it is rulebased, but very complex. Ruletables are sized almost like english dictionaries.
Google tries to compile Finnish language based on dictionaries, but fails everytime and will fail forever.
29 comments
[ 3.3 ms ] story [ 68.5 ms ] threadDictionaries are most often stored as a radix trie, and a bloom filter can be used to quickly check if a word is misspelled.
EDIT: I'm dumb, you said "from then". Whoops. If I had to guess it was probably similar, as radix trie + bloom filter is a very memory efficient way to store and search the dictionary.
1: https://en.wikipedia.org/wiki/Soundex
Needless to say, spell checking was a lengthy task that you invoked sparingly. :)
Much of that is just to provide automatic spell checking to millions of people concurrently.
I would doubt the actual spell checking software for a single language, excluding proper names, would be something a Mac can't run.
http://norvig.com/spell-correct.html
Making spellchecker for Russian (inflecting language), Japanese (I think they don't always put spaces between words, Koreans less so) or Finnish (agglutinating language) still takes good part of a decade, more or less.
Karlsson's Finnish spellchecker was already there around 1982(?), because it is rulebased, but very complex. Ruletables are sized almost like english dictionaries.
Google tries to compile Finnish language based on dictionaries, but fails everytime and will fail forever.