A Spellchecker Used to Be a Major Feat of Software Engineering (2008)

Re:A Spellchecker Used to Be a Major Feat of Software Engine... by PeCaN on Thursday December 24, 2015 @02:34PM (#10789337)

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

[ Parent | on HN ]

Re:A Spellchecker Used to Be a Major Feat of Software Engine... by unhammer on Friday December 25, 2015 @02:42AM (#10790676)

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..

[ Parent | on HN ]

Re:A Spellchecker Used to Be a Major Feat of Software Engine... by doug1001 on Thursday December 24, 2015 @03:15PM (#10789456)

indeed, spell checker was the original use case for the Bloom Filter (i.e., the one discussed in the 1972 paper by Bloom)

[ Parent | on HN ]