CPSC 220 Fall 2004
Program 5: A Functional Spell Checker

• Improved suggestions: When you find a misspelled word, use edit distance to make suggestions. Compute the edit distance between the misspelled word and each word in the dictionary; enter the dictionary words that have an edit distance of 3 or less into a priority queue, with the edit distance as the priority, and give the top N as suggestions, where N is a parameter set by the user. If there is no word with an edit distance of 3 or less, say "no suggestions."

• Suggestion caching: Compiling the list of suggestions above is expensive because it requires searching the entire dictionary. Furthermore, it is common to have the same word misspelled repeatedly in the same document. To address this, keep a cache of words and suggestions. When you encounter a misspelled word for the first time and construct its suggestion list, put the word and its list into a hash table. Check this table first each time you find a misspelled word; if you find your word, return the associated list instead of recomputing it.

• Add to dictionary: Give the user the option to add one or more words to the dictionary. Doing so should not change the dictionary file, so the effect will not last beyond the current session, but after adding a word all occurrences of that word should be unflagged (that is, accepted as being spelled correctly).

I expect a polished product out of this in two ways:

• Structure: Think carefully about the data structures you use and their interfaces. You will need to construct new classes and use them appropriately; work hard to keep your code uncluttered and readable. Be sure to document carefully.

• Interface: The interface should be clean and easy to use. Think about different ways the tool could be used and how to make it work well for each of them.

Finally, you must include a writeup in which you discuss the following:

• The overall structure of the program. Explain what classes you wrote, where they are used, and for what purpose. This should serve as a sort of technical road map for the program.

• Bugs. Clearly document any bugs you know of in the program. Bugs that I find that are not documented here will be penalized more heavily.

• Features. Document any additional features that you have chosen to provide, or particularly nice implementations of required features.

As on the last assignment, you may discuss both design and implementation with others in the class, and I encourage you to do so. However, you may not simply take any portion of someone else's code to use as your own. You must each turn in your own program unless you choose to pair program the entire assignment, in which case you may turn in a single program. You may use outside sources (books, websites, etc) as well but you must document any such source that you use. Furthermore, clearly indicate if you are using any code in your final product that you did not write (e.g., my Scanner class).