 All Implemented Interfaces:
SequenceDistanceMeasurerDouble
 Direct Known Subclasses:
EditDistance
EditDistance
class supports both doublevalued as well as intvalued costs. If your costs are
intvalued, the EditDistance
class may be slightly faster, but not asymptotically faster.
If your costs are doublevalued, there should be no difference (one is a subclass of the other).
Edit distance is the minimum cost to transform one string (or sequence) into the other, which is the sum of the costs of the edit operations necessary to do so. This edit distance considers 3 edit operations: Inserts which insert a new element into the sequence, Deletes which remove an element from the sequence, and Changes which replace an element with a different element.
The edit distance is parameterized by costs for the edit operations. The constructor enables you to specify 3 costs as values of type double, 1 for each type of edit operation.
This class supports computing edit distance for Java String objects or arrays of any of the primitive types, or arrays of objects. It makes no assumptions about the contents of the Strings or arrays, and they can contain duplicates, or can be such that some elements only appear in one or the other of the sequences, or can be of different lengths.
Another class, EditDistance
, is available if you
need to compute distance specifically between permutations, rather than general sequences. That
class computes distance between permutations of the integers from 0 to N1.
Runtime: O(n*m), where n and m are the lengths of the two sequences (i.e., Strings or arrays).
Wagner and Fischer's String Edit Distance was introduced in:
R. A. Wagner and M. J. Fischer, "The stringtostring correction problem," Journal of the ACM,
vol. 21, no. 1, pp. 168–173, January 1974.

Constructor Summary
ConstructorDescriptionEditDistanceDouble
(double insertCost, double deleteCost, double changeCost) Constructs an edit distance measure with the specified edit operation costs. 
Method Summary
Modifier and TypeMethodDescriptionfinal double
distancef
(boolean[] s1, boolean[] s2) Measures the distance between two arrays.final double
distancef
(byte[] s1, byte[] s2) Measures the distance between two arrays.final double
distancef
(char[] s1, char[] s2) Measures the distance between two arrays.final double
distancef
(double[] s1, double[] s2) Measures the distance between two arrays.final double
distancef
(float[] s1, float[] s2) Measures the distance between two arrays.final double
distancef
(int[] s1, int[] s2) Measures the distance between two arrays.final double
distancef
(long[] s1, long[] s2) Measures the distance between two arrays.final double
distancef
(short[] s1, short[] s2) Measures the distance between two arrays.final double
Measures the distance between two arrays of objects.final double
Measures the distance between two Strings.final <T> double
Measures the distance between two lists of objects.

Constructor Details

EditDistanceDouble
public EditDistanceDouble(double insertCost, double deleteCost, double changeCost) Constructs an edit distance measure with the specified edit operation costs. Parameters:
insertCost
 Cost of an insertion operation. Must be nonnegative.deleteCost
 Cost of an deletion operation. Must be nonnegative.changeCost
 Cost of an change operation. Must be nonnegative. Throws:
IllegalArgumentException
 if any of the costs are negative.


Method Details

distancef
public final double distancef(int[] s1, int[] s2) Description copied from interface:SequenceDistanceMeasurerDouble
Measures the distance between two arrays. Specified by:
distancef
in interfaceSequenceDistanceMeasurerDouble
 Parameters:
s1
 First array.s2
 Second array. Returns:
 distance between s1 and s2

distancef
public final double distancef(long[] s1, long[] s2) Description copied from interface:SequenceDistanceMeasurerDouble
Measures the distance between two arrays. Specified by:
distancef
in interfaceSequenceDistanceMeasurerDouble
 Parameters:
s1
 First array.s2
 Second array. Returns:
 distance between s1 and s2

distancef
public final double distancef(short[] s1, short[] s2) Description copied from interface:SequenceDistanceMeasurerDouble
Measures the distance between two arrays. Specified by:
distancef
in interfaceSequenceDistanceMeasurerDouble
 Parameters:
s1
 First array.s2
 Second array. Returns:
 distance between s1 and s2

distancef
public final double distancef(byte[] s1, byte[] s2) Description copied from interface:SequenceDistanceMeasurerDouble
Measures the distance between two arrays. Specified by:
distancef
in interfaceSequenceDistanceMeasurerDouble
 Parameters:
s1
 First array.s2
 Second array. Returns:
 distance between s1 and s2

distancef
public final double distancef(char[] s1, char[] s2) Description copied from interface:SequenceDistanceMeasurerDouble
Measures the distance between two arrays. Specified by:
distancef
in interfaceSequenceDistanceMeasurerDouble
 Parameters:
s1
 First array.s2
 Second array. Returns:
 distance between s1 and s2

distancef
public final double distancef(boolean[] s1, boolean[] s2) Description copied from interface:SequenceDistanceMeasurerDouble
Measures the distance between two arrays. Specified by:
distancef
in interfaceSequenceDistanceMeasurerDouble
 Parameters:
s1
 First array.s2
 Second array. Returns:
 distance between s1 and s2

distancef
public final double distancef(double[] s1, double[] s2) Description copied from interface:SequenceDistanceMeasurerDouble
Measures the distance between two arrays. Specified by:
distancef
in interfaceSequenceDistanceMeasurerDouble
 Parameters:
s1
 First array.s2
 Second array. Returns:
 distance between s1 and s2

distancef
public final double distancef(float[] s1, float[] s2) Description copied from interface:SequenceDistanceMeasurerDouble
Measures the distance between two arrays. Specified by:
distancef
in interfaceSequenceDistanceMeasurerDouble
 Parameters:
s1
 First array.s2
 Second array. Returns:
 distance between s1 and s2

distancef
Description copied from interface:SequenceDistanceMeasurerDouble
Measures the distance between two Strings. Specified by:
distancef
in interfaceSequenceDistanceMeasurerDouble
 Parameters:
s1
 First String.s2
 Second String. Returns:
 distance between s1 and s2

distancef
Description copied from interface:SequenceDistanceMeasurerDouble
Measures the distance between two arrays of objects. The objects in the arrays must be of a class that has overridden the Object.equals method. Specified by:
distancef
in interfaceSequenceDistanceMeasurerDouble
 Parameters:
s1
 First array.s2
 Second array. Returns:
 distance between s1 and s2

distancef
Description copied from interface:SequenceDistanceMeasurerDouble
Measures the distance between two lists of objects. The objects in the lists must be of a class that has overridden the Object.equals method. Specified by:
distancef
in interfaceSequenceDistanceMeasurerDouble
 Type Parameters:
T
 Type of List elements. Parameters:
s1
 First list.s2
 Second list. Returns:
 distance between s1 and s2
