4 ms·

Does anyone have a link to specific tricks used or even implementations of spellcheckers from then?

• PeCaN 11y ago
  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. 1: https://en.wikipedia.org/wiki/Soundex https://en.wikipedia.org/wiki/Soundex
  • doug1001 11y ago
    indeed, spell checker was the original use case for the Bloom Filter (i.e., the one discussed in the 1972 paper by Bloom)
  • unhammer 11y ago
    Bloom filter: That's assuming your vocabulary is reasonably finite. http://www.ling.helsinki.fi/~fkarlsso/genkau2.html 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..
• simmons 11y ago
  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. :)