This is a simple dictionary, which implements an efficien English word checker.
First we have preprocessed CMU pronouncing dictionary dictionary.txt. So we use the file to build the dictionary database.
If a word is detected to be mis-spelled, it would provide suggestions for the user. For example, if "structur" is a user's input, "structure" is a reasonable suggestion. To be more specific, the set of given mis-spelled words can be generated by the following operations.
- Insert: add a lowercase letter to all possible positions in the word.
- Delete: delete a character in the word.
- Substitute: substitute a character in the word with a lowercase letter.
- Transpose: exchange two neighboring characters in the word.
We say that the above set of words are all have distance of 1 from origin word. The dictionary find all words in dictionary that have distance less or equal to 2 from the input word.
A list of words to be looked for. File : input.txt input_500.txt
The output is in CSV format. The first column is the original word in the input file. The second column is "OK" if the given word is already in the dictionary, "NONE" if we can’t find any suggested in the dictionary, else be the suggested words in the dictionary separated by a space.
In order to improve efficiency, I use a hash table for the structure of the dictionary database. And used recursion to find all words have distance 1 and 2 from each input word.