Before you begin, type update21 to copy the homework files into your directory. Then move to the current homework directory by typing: cd cs21/homework/6. Your solution should be entered into the file spellChecker.py.

You should work alone on this homework.

Introduction

For this assignment you will implement an automated spell checker. It will read in a text document and locate words that might be misspelled. Your program will work by comparing each word in the document to a large dictionary of words. Any word that is not found in the dictionary, will be reported.

Sample Run of the Spell Checker

Suppose you wanted to spell check the following file named text1 (which is available in cs21/homework/6):

Hllo,

I'm home for the holidys and was hopting we could get togethersoon.
Let me knw if that wil work for you.

Susan

Your program should produce the following interaction with the user:

Welcome to the automated spell checker!
Using an American English dictionary with 96274 words.

Enter name of text file to spell check >> text1

The following words were NOT found in the dictionary:

Hllo
holidys
hopting
togethersoon
knw
wil

Requirements

• Read all of the words stored in the file /usr/share/dict/american-english into a list in your program. This will serve as your dictionary. Note that the words are stored one per line in this file. This means that each word is followed by a newline character, \n, which must be removed before storing the word into your list.
• To report the number of words in the dictionary, you should test the actual length of the list you create.
• Use binary search to look up each word from the document in the dictionary. NOTE: You must use the binary search function in its original form. Do not change the return values or insert additional code into the function.
• For each word, first search for it in it's original case. If it is not found, then search for it again in lower case. Only if it is not found under both of these conditions should you report it as a misspelled word.
• Remove any trailing punctuation from the words before looking them up.

Extra Credit: Suggesting Corrections

This portion is not required, and should only be attempted once you complete what is described above.

Most modern spell checkers offer a very useful feature. As they spell check a document they make suggestions about possible replacement words for misspelled words. As an example of this, try xemacs text1 and click on the "Spell" button at the top center of the screen. Notice that your screen splits into two, and at the top are a number of suggestions for the highlighted word. You can press the space bar to leave a word alone or choose a letter for a particular replacement. You can press CTRL-g to quit the spell checking at any time.

Try to implement a few basic strategies for making reasonable suggestions for corrections. You can simply print your suggestions with the report of each misspelled word.