com.ninecode.email.util
Class Levenshtein

java.lang.Object
  |
  +--com.ninecode.email.util.Levenshtein

public class Levenshtein

extends Object

Computes the Levenshtein distance (string-to-string edit). From: Finding String Distances by Ray Valdes Dr. Dobbs Journal, April 1992

Author:

Derrick Oswald

Field Summary

protected static int	DEL Indicates the character is deleted.
protected static int	INS Indicates the character is inserted.
protected static int	MATCH Indicates the characters match.
protected com.ninecode.email.util.Levenshtein.MatrixCell[][]	mMatrix This is the matrix.
protected com.ninecode.email.util.Levenshtein.Operation[]	mOperationTable Costs defined on a per-op basis.
protected String	mString1 One string.
protected int	mString1Length One string length.
protected char[]	mString1Shadow One string as characters.
protected String	mString2 The other string.
protected int	mString2Length The other string length.
protected char[]	mString2Shadow The other string as characters.
protected static int	SUB Indicates one character is substituted for another.
protected static boolean	verbose_mode Debugging flag.

Constructor Summary

Levenshtein()
Create a Levenshtein distance calculation object.

Levenshtein(int size)
Create a Levenshtein distance calculation object.

Method Summary

protected void	calculateMatrix() Calculate the Levenshtein distance.
int	getDistance() Get the Levenshtein distance.
protected int	getDistance(int i, int j) Get the cost at a particular element in the matrix.
String	getString1() Get the current string being used.
String	getString2() Get the current string being used.
protected void	initialize(int size) Create memory structures.
void	setString1(String string) Setup one string value.
void	setString2(String string) Setup the other string value.

Methods inherited from class java.lang.Object

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

Field Detail

mOperationTable

protected com.ninecode.email.util.Levenshtein.Operation[] mOperationTable

Costs defined on a per-op basis.

MATCH

protected static final int MATCH

Indicates the characters match.

See Also:

Constant Field Values

INS

protected static final int INS

Indicates the character is inserted.

See Also:

Constant Field Values

DEL

protected static final int DEL

Indicates the character is deleted.

See Also:

Constant Field Values

SUB

protected static final int SUB

Indicates one character is substituted for another.

See Also:

Constant Field Values

mMatrix

protected com.ninecode.email.util.Levenshtein.MatrixCell[][] mMatrix

This is the matrix.

mString1

protected String mString1

One string.

mString2

protected String mString2

The other string.

mString1Length

protected int mString1Length

One string length.

mString2Length

protected int mString2Length

The other string length.

mString1Shadow

protected char[] mString1Shadow

One string as characters.

mString2Shadow

protected char[] mString2Shadow

The other string as characters.

verbose_mode

protected static final boolean verbose_mode

Debugging flag.

See Also:

Constant Field Values

Constructor Detail

Levenshtein

public Levenshtein()

Create a Levenshtein distance calculation object. The initial maximum string size is 64.

Levenshtein

public Levenshtein(int size)

Create a Levenshtein distance calculation object.

Parameters:

size - The initial maximum string size.

Method Detail

initialize

protected void initialize(int size)

Create memory structures.

Parameters:

size - The size of the matrix/character arrays to make.

setString1

public void setString1(String string)

Setup one string value. Resizes memory as appropriate.

Parameters:

string - The string to calculate with.

getString1

public String getString1()

Get the current string being used.

Returns:

One string.

setString2

public void setString2(String string)

Setup the other string value. Resizes memory as appropriate.

Parameters:

string - The string to calculate with.

getString2

public String getString2()

Get the current string being used.

Returns:

The other string.

calculateMatrix

protected void calculateMatrix()

Calculate the Levenshtein distance.

getDistance

protected int getDistance(int i,
                          int j)

Get the cost at a particular element in the matrix.

Parameters:

i - The row to get the distance for.

j - The column to get the distance for.

Returns:

The cost at that point, which measures the number of insertions, deletions and substitutions required to transform the string to that point.

getDistance

public int getDistance()

Get the Levenshtein distance.

Returns:

The Levenshtein distance, which measures the minimum number of insertions, deletions and substitutions required to transform one string into another.