CIS 120: SpellChecker

All modern word processors, along with increasingly many other programs, have a built in spell check function that allows even the worst typist some level of efficiency. In this homework you will implement a rudimentary spell check program based on a dictionary and a list of corrections for misspelled words.

A few notes before we begin:

• To do well on this assignment, you must read the Javadocs for each class to be written! When completing each task below, first read the associated Javadoc so you know exactly what behavior the class should provide. The online tester will verify that you read the Javadocs and wrote your code to match the specifications listed therein. You will want to have the Javadocs open while you're coding.

• For this project, you have only three free submissions. Subsequent submissions will cost you 5 points.

  This means you won't be able to use the online testers to find your bugs! Writing your own tests will be critical to doing well.

• File, class, and method names must be exactly as described in the Javadocs. (You may, of course, add your own helper variables and methods.)

• An archive of files for this assignment are here: hw08.zip, but you should be set if you are using Codio.

• There is a challenge problem (worth no credit): see the Levenshtein class in the Javadocs.

Recall: I/O and Collections

This homework is designed for you to gain practice with Java I/O (see java.io) and the Java Collections Framework (see java.util). The I/O package is very large with lots of different classes to choose from -- we recommend taking a look at the following interfaces and classes:

*Scanner is technically in java.util (not java.io) because it implements the Iterable interface.

Step 0: A High Level Look

In order to create the spellchecker, you will implement the following classes:

1. TokenScanner: parses a text file and breaks it up into tokens (words and nonwords)
2. Dictionary: parses a text file and creates a collection of words in the dictionary
3. FileCorrector and SwapCorrector: given a misspelled word, suggests possible corrections from a dictionary or collection of corrections.
4. SpellChecker: links the TokenScanner, Dictionary and Corrector to interactively spellcheck a document.

In addition to the provided files described above, we also provide several test classes (DictionaryTest, TokenScannerTest, etc.) and sample text files with which to test your code.

Step 1: Breaking Files into Tokens

File(s) to submit: TokenScanner.java and MyTests.java for test cases

Similar to the Histogram demo from lecture, you will first start with a helper class for reading the words in a file. The purpose of this class, which implements the Iterator<String> interface, is to read an input file and split it up into strings, called tokens.

There are two sorts of tokens: words and non-words. Word tokens only contain word characters. Nonwords do not contain any word characters. (A word character is either a letter (see Character.isLetter) or an apostrophe.) Given an input stream of characters, the TokenScanner should alternate between producing word and nonword tokens.

A few things worth pointing out:

• Green tokens are word tokens, gold/yellow tokens are non-word tokens. Notice how we always alternate between the two types of tokens.
• The newline character ("\n") should not be skipped. Note that some operating systems may produce two characters to indicate newlines ("\r\n"). If these characters are present in the input, then they should be part of some (nonword) token.
• The assumption we made about word characters (being only letters and apostrophes) isn't perfect: notice how we split apart the word "e-mail". However, it's a reasonable simplification, and our SpellChecker will still work for the majority a document's text.

The class TokenScanner, because it implements Iterator<String>, must provide the following methods (be sure to brush up on the javadocs):

• hasNext() - Tells the client whether any more tokens remain in the file
• next() - Returns the next token as a String
• remove() - You won't implement this functionality, so your remove method can just contain:

  throw new UnsupportedOperationException();

1.1 Add tests

Read the TokenScanner javadocs, and then open up TokenScannerTest.java and examine the provided test cases.

Before you start your implementation, you should add more unit tests for this class to MyTests.java to exercise all of the intended behavior. What tests should you add? Think about various situations that could occur for your token scanner:

• The input is empty.
• The input contains a single word token.
• The input contains a single non-word token.
• The input contains both word tokens and nonword tokens, and ends with a word.
• The input contains both word tokens and nonword tokens, and ends with a non-word.

1.2 TokenScanner.java

Next, implement TokenScanner so that it passes your tests. Note that the constructor is allowed to throw an IOException, but the next method should catch them and throw NoSuchElementException so that it conforms to the Iterator signature.

Step 2: Building a Dictionary

File(s) to submit: Dictionary.java and MyTests.java for test cases

Before you can actually program the spellchecker you need a class that reads in words from the dictionary, stores them in memory, and provides efficient access to them. In this case, a dictionary is just a collection of 'legal' words, and does not store any definitions.

Begin by reading the Javadoc for the Dictionary class, to understand what it does.

2.1 Add Tests

Once you understand what the Dictionary class does, open DictionaryTest.java.

We only provide a few test cases in this file. Passing the given tests doesn't mean your code works for all inputs! Using the given test cases as a template, add test cases to MyTests.java for the following situations. By a test case, we mean that you should make the certain scenario happen, and check that the response matches what should happen, as outlined in the Javadocs. Use methods like assertEquals, assertTrue, assertFalse to verify the correct behavior (Recall that documentation for the assert methods can be found here).

Each bullet below should be its own test method:

• You check for a word that is in the dictionary.
• You check for a word that is NOT in the dictionary.
• You ask for the number of words in the dictionary. (Does it return the right thing? Hardcode in the answer you expect based on your test dictionary file.)
• You check that the empty string "" is not a word.
• You check for a word that is all uppercase, but the word appears in the dictionary file in lowercase.
• The dictionary file contains a blank line in the middle. (Remember: You can always make new .txt files to help write test cases.)
• The dictionary file has words in mixed case (e.g. eLePHant) and you check if one of those words is in the dictionary.
• The dictionary file has words with whitespace around them, and you check if one of those words is in the dictionary.
• The same word appears twice in the dictionary file, and you ask for the number of words in the dictionary.

Are there any other test situations or corner cases which may occur? We've left out some scenarios from the list above. You should write additional test cases for any other situations you think of.

2.2 Dictionary.java

Once you feel confident that your tests cover all aspects of the expected behavior, open up Dictionary.java. We have provided template methods, and you will have to fill in the implementation.

You should run your tests, find what fails, and correct the code until your test cases pass.

Using the Right Data Structure

Choosing the right data structure to store the dictionary is crucial. If the dictionary contains 1,000,000 words, you don't want to be re-reading and searching through all of those words each time isWord() is called. The implementation of the data structure is also important - different ways of storing data make different operations efficient. Ask yourself:

• Is a List the right data structure to store the dictionary? What benefits does a list have over a set or map? Are these necessary for a Dictionary?
  • The ArrayList class implements lists using resizeable arrays.
  • The LinkedList class implements lists using linked lists of nodes.
• Is a Set the right data structure to store the dictionary? How does the set differ from a list or a map? Do the properties of a Set fit the description of a Dictionary?
  • The TreeSet class implements ets by storing elements in a binary search tree.
  • We haven't covered hashing in detail, so do not use HashSet
• Is a Map the right data structure to store the dictionary? If so, what kind of map is it? (e.g. String to String, String to Integer, etc.)
  • The TreeMap class implements maps by storing keys in a sorted binary tree.
  • We haven't covered hashing in detail, so do not use HashMap

It is critical that your Dictionary works properly before moving on! Make sure that the method signatures match those in the Javadoc exactly.

Step 3: Adding Correctors

File(s) to submit: FileCorrector.java, SwapCorrector.java and MyTests.java for test cases.

Suppose while reading a file we encounter a word that is not in a dictionary. How could we fix it?

Corrector is an abstract class where the getCorrections method is abstract. An abstract class has some similarities to an interface; the biggest difference is that abstract classes can have some implemented methods. Here matchCase is implemented, but getCorrections is not. Any subclass of Corrector must implement getCorrections, and thus be able to provide corrections for a given misspelled word. You will implement two different kinds of Correctors:

1. FileCorrector - uses a reference text file containing common misspellings to provide suggestions for a misspelled word.
2. SwapCorrector - uses a Dictionary and suggests any words from it that are a single "swap" from the given incorrect word. For example, it might suggest "this" if the incorrect word was "thsi". A swap is two adjacent letters that are reversed in their positions.

3.1 Add Tests

Read the documentation for FileCorrector, and then add the following test cases (plus your own) to MyTests.java:

• The corrections file has extra whitespace around a line, or around the comma. You can (and should) create your own new .txt files to help write these test cases!
• We ask for a word that has no corrections.
• We ask for a word that has multiple corrections.
• The input file has some lines with mixed case (e.g. word,CoRRecTioN or WORD,correction) and you ask for that word's corrections.
• We ask for a fully uppercase word that has corrections. What case should the results have?
• We ask for that same word, but now lowercase, that has corrections. What case should the results have?

The list above isn't comprehensive, so make sure to add your own additional test cases for any other behavior described in the Javadocs.

3.2 FileCorrector.java

When you are finished adding test cases, write the FileCorrector class and ensure it passes your tests. Think carefully about which data structure is the best suited for storing the data read from the file.

3.3 Adding Tests

Repeat the above procedure for implementing SwapCorrector: look at the Javadocs and add necessary test cases

Here are some suggested test cases, but we've left out quite a few:

• The provided dictionary is null.
• You ask for corrections for a word that itself is already in the dictionary.
• You ask for corrections for a word that is mixed case.

3.4 SwapCorrector.java

Now, implement SwapCorrector.java

All IOExceptions that may result from the execution of the Correctors do not need to be caught.

Read the Javadocs closely for the Correctors and make sure to test all of the possible edge cases!

Step 4: Creating the SpellChecker

File(s) to submit: SpellChecker.java and MyTests.java for test cases

The end is near!

You need to put all of the classes together. A SpellChecker object takes in a Corrector and a Dictionary when constructed. When checkDocument is called, reads tokens from the input document, spell-checks any incorrect words, and writes the output to a file using a Writer object.

Most of SpellChecker has already been written, except for the method that processes the document and does the checking.

Sample Output/Interaction

Click here to see a sample of the output and interaction functionality we expect to see when running the finished program. You should closely emulate this output in your SpellChecker class.

4.1 checkDocument in SpellChecker.java

Complete the checkDocument method in SpellChecker.java so it matches the functionality above. Bear in mind the following:

• Read the Javadocs for the SpellChecker class first! :)

• Non-word tokens should be copied directly from the input document into the newly corrected file. Only word tokens should be checked for spelling and (possibly) replaced.

• If the user chooses option 1 ("replace with another word"), they can only enter single word replacements. This is taken care of for you by the provided getNextString helper method. You should use the submitted word verbatim; no need to correct the word case.

• If a word isn't in the dictionary, then we want to check if our Corrector has any suggestions for it. If more than one correction is available, then the possible corrections should be presented to the user in alphabetical order.

  TIP: To alphabetically sort a string set, use the following:

              // Suppose setOfCorrections is the Set<String> you got from a Corrector.
              List<String> sortedOptions = new LinkedList<String>(setOfCorrections);
              Collections.sort(sortedOptions);
  
              // sortedOptions is a sorted list, e.g. {"alpha", "beta"}
              // You can now use the List as you wish; see the List Javadocs.
              String first = sortedOptions.get(0); // "alpha"
              String second = sortedOptions.get(1); // "beta"
              

• IOExceptions don't need to be caught, but you should handle invalid user input appropriately.

  For example, if you give a user four options and they enter an invalid selection (such as 12 or "oaijeoijwef"), you should notify them and prompt for a selection again.

  TIP: We provide code to help you with this: see getNextInt and getNextString in the partial SpellChecker implementation provided.

• Your user display and options should match the sample output above. For example, do NOT number your options 1,2,3 instead of 0,1,2. We will test your code automatically with a file of user inputs.

Testing: Command Line or Running in Eclipse

The sample test case in SpellCheckerTest uses a file as the "user" input so it can run automatically.

The recommended way to run your spellchecker is from the command line. See the README in Codio for more information. From the root directory of your project in your workspace:
java -cp bin SpellCheckerRunner files/Gettysburg.txt files/Gettysburg-out.txt files/dictionary.txt files/misspellings.txt

Challenge Problem

If the drive to create the world's best spell checker has consumed you, you can implement a third type of corrector, Levenshtein.java. This kind of Corrector proposes words that are a Levenshtein distance of 1 away from the incorrect word. This is kudos-only and worth no points.

Submitting and Grade Breakdown

As usual, you will be submitting on the submissions page. You should submit a zip file named hw08-(time)submit.zip containing:

	src/Dictionary.java 
	src/FileCorrector.java 
	src/SwapCorrector.java 
	src/TokenScanner.java 
	src/SpellChecker.java 
	src/Levenshtein.java 
	test/MyTests.java
    

If you are using Codio

These files should be organized similar to above (with a src and test directory). The easiest option is to use the Zip menu item in Codio. Do not include any of the other provided files, since doing so may cause your submission to fail to compile.

If you are using Eclipse

• Alternative 1 - Zip your files from Eclipse using the instructions below.

Follow these instructions to create and upload hw08-submit.zip:

• Right click on project, select Export...
• Expand General, select Archive File
• Only select the files listed above (click on arrow in window on left and select files in the window on the right)
• Browse... -> Save as "hw07-submit" in Desktop/Documents/Downloads
• Select "Save in zip format"
• Finish
• Go to submission site, find file in Desktop/Documents/Downloads and then upload


• Alternative 2 - Copy-Paste your code in Codio and zip from there.

• 1: TokenScanner - 20%
• 2: Dictionary - 18%
• 3.2: FileCorrector - 18%
• 3.4: SwapCorrector - 16%
• 4: SpellChecker - 18%
• 5: Style - 5%, manually graded
• 6: Testing - 5%, manually graded
• Kudos: Levenshtein - 0%

Eclipse Instructions

Running the command line spellchecker in Eclipse: When you run the SpellChecker through Eclipse, you will need to refresh the Eclipse package in order to see the newly created output file.

1. Go to Run > Run Configurations.
2. Right click on Java Application and choose "New".
3. Under "Main class", you should put SpellCheckerRunner.
4. Switch from the "Main" tab to the "Arguments" tab.
5. Under "Program arguments:", you can put the inputs to the runner. For example:
6. You can give this configuration a name in the "Name:" bar at the top, so you can identify this from other runs.
7. Hit "Apply" and "Run".
8. The program will run in the "Console" tab, normally at the bottom below your code editors. (Your layout may be different.)

You can return to this configuration and change the arguments to run it with different input files, or to switch between different types of Correctors.

To edit a configuration, in the Run Configurations panel, select the named configuration under "Java Application" on the left side.

To re-run a configuration (after it has been set up), you can choose the configuration (as if you were editing it) and hit "Run". Alternatively, if you have recently run it, you can click the little arrow next to the green button at the top of Eclipse: