I need to implement a spell checker in C. Basically, I need all the standard operations... I need to be able to spell check a block of text, make word suggestions and dynamically add new words to the index.
I'd kind of like to write this myself, tho I really don't know where to begin.
Read up on Tree Traversal. The basic concept is as follows:
A really short example:
Dictionary:
apex apple appoint appointed
Tree: (* indicates valid end of word)
update: Thank you to Curt Sampson for pointing out that this data structure is called a Patricia Tree
A -> P -> E -> X*
\\-> P -> L -> E*
\\-> O -> I -> N -> T* -> E -> D*Document:
apple appint ape
Results:
A -> P -> P, but the second P does not have an I child node, so the search fails.
E node in A -> P -> E does not have the "valid end of word" flag set.
edit: For more details on spelling suggestions, look into Levenshtein Distance, which measures the smallest number of changes that must be made to convert one string into another. The best suggestions would be the dictionary words with the smallest Levenshtein Distance to the incorrectly spelled word.
Given you don't know where to begin, I'd suggest using an existing solution. See, for example, aspell (GLPL licenced). If you really have to implement it yourself, please tell us why.
One should look at prefixes and suffixes.
suddenly = sudden + ly.
by removing ly's you can get away storing just the root word.
Likewise preallocate = pre + allocate.
And lovingly = love + ing + ly gets a bit more complex, as the english rules for ing get invoked.
There is also the possibility of using some sort of hashing function to map a root word into a specific bit is a large bit map, as a constant time method of determining if the root word is spelled correctly.
You can get even more complex by trying to provide an alternate list of possible correct spellings to a misspelled word. You might research the soundex algorithm to get some ideas.
I would advise prototyping with a small set of words. Do a lot of testing, then scale up. It is a wonderful educational problem.
I've done this in class
You should consider python Natural Language Toolkit NLTK which is made specificaly to handle this.
It also allows to create text interpreters such as chatbots
The Open Office Spell checker Hunspell can be a good starting point. Here is the Homepage: Hunspell at Sourceforge
Splitting a word into root and suffix is knonw as the "Porter Stemming Algorithm" it's a good way of fitting an English ditionary into an amazingly small memory.
It's also useful for seach so "spell checker" will also find "spelling check" and "spell checking"
E James gives a great answer for how to tell if a word is valid. It probably depends on the spell checker for how they determine likely misspellings.
One such method, and the one that I would use is the Levenshteinn String Similarity which looks at how many letters must be added, removed, or swaped in a word in order to make another word.
If you say spelled: Country as Contry. The levenshtein string similarity would be 1 since you have to only add 1 letter to transform contry into country.
You could then loop through all possible correct spellings of words (only 171,000 english words and 3000 of those account for 95% of text). Determine those with the lowest levenshtein string similarity value, and then return the top X words that are most similar to the misspelled word.
There's a great python package called Fuzzy Wuzzy which implements this efficiently and generates a % similarity between two words or sentences based on this formula.
