Class Levenshtein

java.lang.Object

Corrector

Levenshtein

public class Levenshtein
extends Corrector

A smart Corrector that uses "edit distance" to generate corrections.

NOTE: This corrector is a "challenge" problem and does not count towards your grade.

The Levenshtein distance between two words is the smallest number of edits needed to transform one word to the other. An "edit" can be either an:

• insertion of a letter
• deletion of a letter
• substitution of one letter for one other letter

A "letter" is one of a-z (we do not count apostrophes here). Note that swaps (thsi -> this) do not count as an edit.

This Corrector suggests any words in the dictionary that are exactly a distance of one edit away from the given incorrect word.

Constructor Summary

Constructors

Constructor and Description
Levenshtein(Dictionary dict) Constructs a Levenshtein Corrector using the argued Dictionary.

Method Summary

Methods

Modifier and Type	Method and Description
java.util.Set<java.lang.String>	getCorrections(java.lang.String wrong) Returns a set of proposed corrections for an incorrectly spelled word.
java.util.Set<java.lang.String>	getDeletions(java.lang.String s) A deletion is defined as a removing a single character.
java.util.Set<java.lang.String>	getInsertions(java.lang.String s) An insertion is defined as inserting a single character.
java.util.Set<java.lang.String>	getSubstitutions(java.lang.String s) A substitution is defined as replacing a single character with another.

Methods inherited from class Corrector

matchCase

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Levenshtein

public Levenshtein(Dictionary dict)

Constructs a Levenshtein Corrector using the argued Dictionary. Should throw an IllegalArgumentException if the aruged Dictionary is null.

Parameters:

dict - The Dictionary for this corrector

Throws:

java.lang.IllegalArgumentException - If the argued Dictionary is null

Method Detail

getDeletions

public java.util.Set<java.lang.String> getDeletions(java.lang.String s)

A deletion is defined as a removing a single character. For example, deletions for the word "yes" are { "es", "ys", "ye" }

Parameters:

s - The input string

Returns:

All the words that are one deletion away from s

getSubstitutions

public java.util.Set<java.lang.String> getSubstitutions(java.lang.String s)

A substitution is defined as replacing a single character with another. Here, we will only substitute with the lowercase letters a-z. For example, some of the substitutions for "yes" include { "aes", "bes", "ces", ... "yex", "yey", "yez" }

Parameters:

s - The input string

Returns:

All the words that are one substitution away from s

getInsertions

public java.util.Set<java.lang.String> getInsertions(java.lang.String s)

An insertion is defined as inserting a single character. Here, we will only insert lowercase letters a-z. For example, some of insertions for "yes" include { "ayes", "byes", "cyes", ... "yaes", "ybes", "yces", ... "yesx", "yesy", "yesz" }

Parameters:

s - The input string

Returns:

All words that are one insertion away from s

getCorrections

public java.util.Set<java.lang.String> getCorrections(java.lang.String wrong)

Returns a set of proposed corrections for an incorrectly spelled word. The corrections should match the case of the input; the matchCase method is helpful here.

For any input that is *not* a valid word, throw an IllegalArgumentException. A valid word is any sequence of letters (as determined by Character.isLetter) or apostrophes characters. The set of corrections will be all of the corrections that are a single deletion or single insertion or single substitution away from the argued word according to the above defintions.

Specified by:

getCorrections in class Corrector

Parameters:

wrong - The misspelled word

Returns:

A (potentially empty) set of proposed corrections

Throws:

java.lang.IllegalArgumentException - If the input is not a valid word (i.e. not composed of only letters and/or apostrophes)