3 ms·
AFAIK most of them use some blend of edit distance (usually a modification of Levenshtein distance to support transpositions) and often a phonetic algorithm lik
by 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 agoindeed, spell checker was the original use case for the Bloom Filter (i.e., the one discussed in the 1972 paper by Bloom)
- unhammer 11y agoBloom 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..