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 instance using the given 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>	getInsertions(java.lang.String s)
java.util.Set<java.lang.String>	getSubstitutions(java.lang.String s)

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 instance using the given Dictionary. Should throw an IllegalArgumentException if the dictionary provided is null.

Parameters:

dict -

Method Detail

getSubstitutions

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

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)

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)

Description copied from class: Corrector

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.

Any input that is *not* a valid word (i.e. only composed of letters and/or apostrophes) should throw an IllegalArgumentException.

Specified by:

getCorrections in class Corrector

Parameters:

wrong - the misspelled word

Returns:

a (potentially empty) set of proposed corrections