22C:21 Project 3

Introduction

This project builds on Project 2. In this, you will generate suggested replacements in a much more efficient way.

Suggesting Replacements

The procedure for suggesting replacements, used in Project 2, was inefficient and somewhat simple-minded. Here is a more sohisticated and efficient algorithm for generating replacements. In Project 2 we defined a graph whose vertices are all possible strings and whose edges connect certain pairs of strings s and t. Let us call this the word graph. The edges in the word graph were of 4 types:

1. Deletion edges: t is obtained by deleting a letter in s,
2. Insertion edges: t is obtained by inserting a letter into s,
3. Substitution edges: t is obtained by substituting another letter for some letter in s, and
4. Swapping edges: t is obtained by swapping a pair of letters in s.

1. Deletion edges: Dropping the letter t from the word letter does not change the sound of the word much, because of the two consecutive t's in the word. Similarly, dropping the letter i or the second e in the word receive, does not change the sound of the word too much. So edges such as (letter, leter) and (receive, receve) are considered important whereas edges such as (letter, lette) and (receive, eceive) are not. This is because in the latter cases, the sound of the word changes significantly when the letter is dropped.
2. Insertion edges: If an edge (s, t) is an insertion edge, then it is also a deletion edge. Therefore, the above discussion holds for insertion edges as well. For example, I have often written neccessary for the word necessary. Since the mispelled word, obtained from the correctly spelled word via the insertion of an extra c, sounds similar to the original word, the edge (necessary, neccessary) is considered important.
3. Substition edges: If a pair of letters sound the same then a user is more likely to substitute one for another. For example, the letters c and s sound similar in some contexts and a user might type nesessary instead of necessary. This means that edges such as (necessary, nesessary) are considered important, whereas the edge (necessary, netessary) is not. In the latter case, replacing the letter c by a t drastically changes the sound of the word.
4. Swapping edges: If a pair of letters sound the same then swapping them will create a new word that sounds similar to the original word. For example, the swapping the letters e and i in receive yields a similar sounding word and so the edge (receive, recieve) is considered important whereas the edge (receive, erceive) is not.

	a	e
	c	s
	c 	k
	e	i
	g	j
	i	y
	o	u
	v	w
	s	z

• Deletion edges: If two similar sounding letters occur consecutively in a word s and one of them is deleted, to give us the word t, then the edge (s, t) is important. All other deletion edges are unimportant.
• Insertion edges: Since every deletion edge is an insertion edge as well, the important/unimportant tags for these kinds of edges are defined above.
• Substitution edges If the word t is obtained by substituting a letter in the word s by a similar sounding letter, then the edge (s, t) is important. All other substition edges are unimportant.
• Swapping edges: If a two similar sounding letters occur in a word s and these are swapped, to give us the word t, then the edge (s, t) is important. All other swapping edges are unimportant.

Here is how the idea of important and unimportant edges comes into play while searching for replacements. Given a mispelled word w, use the following steps to find replacements.

1. Do a breadth first search (BFS) on the word graph starting with w as the source and using just the important edges. New strings will be generated as BFS proceeds; check whether a string that is generated belongs to the dictionary (as in Project 2) or not. If a generated string does belong to the dictionary, enqueue it into a queue of replacement strings. Terminate BFS when either 10 replacement strings have been found or when 2000 strings have been generated. The number 2000 is somewhat arbitrary and should be fine-tuned for better performance. Note that BFS may proceed down several levels starting at the root, before it is terminated. Recall that in Project 2, the search went down just 2 levels. This was because in each level there were a lot of words (especially in the second level) and we could not afford to go down more levels. Here, since we are only using important edges, our search is narrower and can therefore afford to be deeper. Also, note that the queue of replacements contains words in the order in which they were generated and this order does correspond to a decreasing order of relevance of the replacement words.
2. Suppose that in Step (1), x replacement words have been found, where x is smaller than 10. In Step (2), the goal is to find the remaining 10 - x replacement words. In Step (2) we do a modified BFS. Starting with the mispelled word w, we use all edges (not just important edges) to generate level one. For subsequent levels we use just the important edges. As in Step (1), we terminate the BFS either when all the replacement words we seek have been found or we have generated 2000 words.

What to submit:

You are required to electronically submit by midnight 5-8 the following files: BuildDict.java, SpellCheck.java, Dictionary.java, Link.java, LinkList.java, and Record.java. Make sure that your file names are exactly as above and make sure that you do not submit any additional files.

A final word:

While I have specified quite a few details, I have left enough unspecified so as to leave you with a few design decisions to make. These decisions will affect the efficiency, robustness, and readability of your program. So make your choices with care.