The purpose of this programming assignment is to bring together everything we have learned over the last few weeks of the term. The assignment is to build a simple GUI text editor with a built-in spell checker.
A spell checker is a piece of software that compares words against a dictionary of known words. For words that are not in the dictionary, the spell checker provides a list of suggestions of words that are similar to the given word, in the hopes that one of the suggested words is actually the correct spelling of the unknown word.
To implement this functionality, we are going to use a Dictionary class, as outlined here.
package spell;
import java.util.ArrayList;
public class Dictionary {
private ArrayList<String> words;
private StringMetric metric;
public Dictionary() throws Exception {
// To do:
// 1) open the text file "dictionary.txt"
// 2) read all the words from that file and place them in the words ArrayList
// 3) initialize the metrics object
}
public boolean containsWord(String aWord) {
// To do: Use binary search to search the word list for aWord
return false;
}
public String[] closestWords(String aWord) {
// To do: using metric.distance, find all of the words
// in the words ArrayList that are close to aWord.
// Store those words temporarily in a second ArrayList of Strings.
// Return an array of Strings containing the close matches you found.
String[] result = new String[0];
return result;
}
}
Your job will be to fill in the missing code to make this class functional. In the project I have provided, there is a text file named 'dictionary.txt'. This file contains over 45,000 English words that will form the word list for your spell checking dictionary. The Dictionary class shown here will open up that file and read all of the words, placing them in the words ArrayList.
To search the Dictionary for a particular word, we can use an efficient search algorithm. One such algorithm is binary search. You will find the code for a version of binary search in section 6.7 of the text. You will have to modify that code to work with an ArrayList of Strings instead of an array of ints. In particular, instead of the usual >=, <, and == comparison tests that work with ints you will have to use the String class's compareToIgnoreCase method as described in section 8.2.3 of the textbook.
To find all of the words in the dictionary that are close to particular word, we will have to have some method that measures the 'closeness' of two strings. There are many algorithms available to compute the closeness of strings of text - the algorithm we will use is the Damerau-Levenshtein metric. This metric compares strings a and b and assigns a penalty of 1 for each instance where a letter in b is missing or replaced by a different letter, an extra letter appears in b, or where there is a transposition between two letters. For example, in this metric the distance between 'word' and 'werd' is 1, the distance between 'misspelling' and 'mispelling' is 1, and the distance between 'the' and 'teh' is 1. In many cases, misspelled words will fall within 1 or 2 of a dictionary word using this metric. Our Dictionary class's closestWords method with simply scan down the list of words in its ArrayList of English words looking for all the words that fall close to the target word in this metric and then return an array of all of those 'close' words.
Here is a class that implements the Damerau-Levenshtein metric via its distance method. Unfortunately, the logic behind this calculation is beyond the scope of this course. Those of you who go on to take more computer science will eventually learn how this method works.
package spell;
// A simple class to implement the Damerau-Levenshtein distance metric
// between two strings.
// Code is based on code found at http://www.merriampark.com/ld.htm with
// modification needed to handle transpositions found at
// http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
public class StringMetric {
private final int MAX_LENGTH = 24;
private int d[][] = new int[MAX_LENGTH+1][MAX_LENGTH+1];
public StringMetric() {
// Initialize the d matrix with base cases for
// dynamic programming.
for (int i = 0; i <= MAX_LENGTH; i++) {
d[i][0] = i;
}
for (int j = 0; j <= MAX_LENGTH; j++) {
d[0][j] = j;
}
}
private int minOf2 (int a, int b) {
if(a < b) return a;
else return b;
}
private int minOf3 (int a, int b, int c) {
int mi;
mi = a;
if (b < mi) {
mi = b;
}
if (c < mi) {
mi = c;
}
return mi;
}
// Compute Damerau-Levenshtein distance
public int distance (String s, String t) {
// Step 1
int n = s.length ();
int m = t.length ();
if (n == 0) {
return m;
}
else if(n > MAX_LENGTH)
n = MAX_LENGTH;
if (m == 0) {
return n;
} else if(m > MAX_LENGTH)
m = MAX_LENGTH;
// Step 2 is in constructor
// Step 3
for (int i = 1; i <= n; i++) {
char s_i = s.charAt (i - 1);
// Step 4
for (int j = 1; j <= m; j++) {
char t_j = t.charAt (j - 1);
// Step 5
int cost;
if (s_i == t_j) {
cost = 0;
}
else {
cost = 1;
}
// Step 6
d[i][j] = minOf3 (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);
// Modification for transpositions
if(i > 1 && j > 1 && s_i == t.charAt(j-2) && s.charAt(i-2) == t_j)
d[i][j] = minOf2(d[i][j],d[i-2][j-2] + cost);
}
}
// Step 7
return d[n][m];
}
public static void main(String[] args) {
StringMetric m = new StringMetric();
String correct = "misspelled";
String incorrect = "mispelled";
int d = m.distance(correct,incorrect);
System.out.println("The Damerau-Levenshtein distance between " + correct +
" and " + incorrect + " is " + d);
correct = "simplistic";
incorrect = "sipmleistic";
d = m.distance(correct,incorrect);
System.out.println("The Damerau-Levenshtein distance between " + correct +
" and " + incorrect + " is " + d);
}
}
This class is included in the project I will give you as a starting point.
The final ingredient necessary for a spell checker is some mechanism for isolating the words in a body of text and then checking them against the dictionary one by one. To help you do this part of the problem, I have created a WordIteration class. The text holds a single large String, text, and provides methods to iterate over the words in that text.
package spell;
import java.util.Scanner;
public class WordIteration {
private String text; // The underlying text to iterate over
private int wordStarts; // Where the current word starts
private int wordEnds; // One space past where the current word ends
public WordIteration(String theText) {
text = theText;
wordStarts = 0;
wordEnds = 0;
}
public int getWordStart() {
return wordStarts;
}
public int getWordEnd() {
return wordEnds;
}
public String getFullText() {
return text;
}
public void reset() {
wordStarts = 0;
wordEnds = 0;
}
// Scan forward from the current position to find the next word.
// Return a copy of that word, or null if we have reached the end.
public String nextWord() {
wordStarts = wordEnds;
while(wordStarts < text.length() && !Character.isLetter(text.charAt(wordStarts)))
wordStarts++;
if(wordStarts < text.length()) {
wordEnds = wordStarts;
while(wordEnds < text.length() && Character.isLetter(text.charAt(wordEnds)))
wordEnds++;
return text.substring(wordStarts, wordEnds);
}
else
return null;
}
// Replace the current word in the underlying text with newWord,
// adjusting the wordEnds value appropriately.
public void replaceWord(String newWord) {
String before = text.substring(0,wordStarts);
String after = text.substring(wordEnds);
text = before + newWord + after;
wordEnds = wordStarts + newWord.length();
}
// A short example program to demonstrate how to use this class and the
// Dictionary class.
public static void main(String[] args) {
String test = "Here are some werds that mihgt be mispelled.";
Scanner input = new Scanner(System.in);
Dictionary dict = null;
try {
dict = new Dictionary();
} catch (Exception ex) {
System.out.println("Could not load dictionary.");
System.exit(0);
}
WordIteration iter = new WordIteration(test);
String aWord = iter.nextWord();
while(aWord != null) {
if(!dict.containsWord(aWord)) {
String[] suggestions = dict.closestWords(aWord);
System.out.println("Enter a replacement for " + aWord);
System.out.println("Suggestions:");
for(int n = 0;n < suggestions.length;n++)
System.out.println(suggestions[n]);
System.out.println();
String replacement = input.next();
iter.replaceWord(replacement);
}
aWord = iter.nextWord();
}
System.out.println(iter.getFullText());
}
}
The nextWord method moves from the currently selected word to the next word in the text, returning a copy of the next word in the text. We can then take that word to the dictionary to see if it is in the dictionary. If the current word is not in the dictionary, we can ask the dictionary for a list of the words that are close to the current word. We can show the current word and the suggestions to the user and ask the user to type in the correct word to use as a replacement for the current word in the text string. The replaceWord method replaces the current word in the text with a replacement string.
As you can see here, the WordIterator class contains a short test program that demonstrates how to use the WordIterator class and the Dictionary class to scan for misspelled words and correct them.
The other part of this programming assignment is to construct an appropriate graphical user interface for our spell checking program.
The main window in the interface will consist of a menu bar and a scoll pane holding a JTextArea. The JTextArea class implements a full-featured multiline text editor.
|
As the first step in creating this GUI, set up a JFrame class that has a menu bar and a text area below the menu bar. Place a File menu in the menu bar with Open, Save, and Quit commands.
 |
Assuming that the text area object has variable name 'textArea', the following code implements the Open and Save commands.
private void openCommandActionPerformed(java.awt.event.ActionEvent evt) {
JFileChooser chooser = new JFileChooser();
int returnVal = chooser.showOpenDialog(this);
if (returnVal == JFileChooser.APPROVE_OPTION) {
File theFile = chooser.getSelectedFile();
try {
BufferedReader input = new BufferedReader(new FileReader(theFile));
StringBuilder builder = new StringBuilder();
String nextLine = input.readLine();
while (nextLine != null) {
builder.append(nextLine);
builder.append('\n');
nextLine = input.readLine();
}
input.close();
String allText = builder.toString();
textArea.setText(allText);
} catch (Exception ex) {
JOptionPane.showMessageDialog(this,
"Error while trying to read file: " + ex);
}
}
}
private void saveCommandActionPerformed(java.awt.event.ActionEvent evt) {
JFileChooser chooser = new JFileChooser();
int returnVal = chooser.showSaveDialog(this);
if (returnVal == JFileChooser.APPROVE_OPTION) {
File theFile = chooser.getSelectedFile();
try {
PrintWriter output = new PrintWriter(theFile);
output.write(textArea.getText());
output.close();
} catch (Exception ex) {
JOptionPane.showMessageDialog(this,
"Error while trying to save file: " + ex);
}
}
}
Build the simple text editor shown above, and verify that it can correctly open, modify, and save text.
The final part of the assignment is to combine the spell checking classes we developed earlier with the text editor we just built.
Start by adding a 'Spelling' menu with these two menu items. For later convenience, you might want to add a keyboard shortcut to the next word menu item.
 |
Selecting the 'Start Spell Check' should create a new WordIteration based on the text contained in the text area. Use the WordIteration to iterate over the words until you come across the first word that is not in the dictionary.
When your program encounters a word that is not in the dictionary, it should highlight it in the text area, and then put up a dialog box showing a list of suggested spellings for the word in question.
 |
The user should be able to select the replacement word they want from the list in the dialog and click the 'Select' button to transfer the desired spelling to the text field. Alternatively, the user could simply type the correct spelling in the text field directly. Clicking 'Done' should tell the WordIteration to replace the current word with the word in the text field, replace the entire text in the text area with the modified text, and then dismiss the dialog box.
When the user selects the 'Next Word' menu command, your program should use the WordIterator to scan for the next word not in the dictionary, and display the spelling dialog again.
Here is a handy method for your frame class to handle highlighting the current word in the text area and have the text area scroll automatically to the highlighted word. This code assumes that the WordIteration object we are using is named 'wordIter'.
private void selectCurrentWord() {
int wordStarts = wordIter.getWordStart();
int wordEnds = wordIter.getWordEnd();
textArea.setCaretPosition(wordStarts);
textArea.moveCaretPosition(wordEnds);
try {
Rectangle where = textArea.modelToView(wordEnds);
textArea.scrollRectToVisible(where);
} catch (BadLocationException ex) {
}
}