CPSC 220 Fall 2004
Your assignment is to complete the spell checker from program 4 by adding
the folling features:
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
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
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).