 All Implemented Interfaces:
SequenceDistanceMeasurer
,SequenceDistanceMeasurerDouble
 Direct Known Subclasses:
LongestCommonSubsequenceDistance
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 inserts a new element into the sequence, Deletes which removes 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 class provides a
constructor which enables you to specify 3 costs as ints, 1 for each type of edit operation. If
your application requires noninteger costs, then use the EditDistanceDouble
class which
defines the costs as doubles, but is otherwise an implementation of the same algorithm.
This class supports computing EditDistance 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 (with same name but in different package) is available if you need to compute
distance specifically between permutations, rather than general sequences. That class is the
EditDistance
class which 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
ConstructorDescriptionEditDistance
(double insertCost, double deleteCost, double changeCost) Deprecated.EditDistance
(int insertCost, int deleteCost, int changeCost) Constructs an edit distance measure with the specified edit operation costs. 
Method Summary
Modifier and TypeMethodDescriptionfinal int
distance
(boolean[] s1, boolean[] s2) Measures the distance between two arrays.final int
distance
(byte[] s1, byte[] s2) Measures the distance between two arrays.final int
distance
(char[] s1, char[] s2) Measures the distance between two arrays.final int
distance
(double[] s1, double[] s2) Measures the distance between two arrays.final int
distance
(float[] s1, float[] s2) Measures the distance between two arrays.final int
distance
(int[] s1, int[] s2) Measures the distance between two arrays.final int
distance
(long[] s1, long[] s2) Measures the distance between two arrays.final int
distance
(short[] s1, short[] s2) Measures the distance between two arrays.final int
Measures the distance between two arrays of objects.final int
Measures the distance between two Strings.final <T> int
Measures the distance between two lists of objects.Methods inherited from class org.cicirello.sequences.distance.EditDistanceDouble
distancef, distancef, distancef, distancef, distancef, distancef, distancef, distancef, distancef, distancef, distancef

Constructor Details

EditDistance
Deprecated.For doublevalued costs, use theEditDistanceDouble
class instead.Constructs an edit distance measure with the specified edit operation costs. With costs as doubles, all of the distancef methods that compute distance as double values are available. The distance methods that compute integervalued distances may or may not be available if this constructor is used with double valued costs. If the costs are equal to integer values if cast to type double, then the distance methods will also function. Otherwise, they will throw an exception. For safety, it is recommended to only use the distancef methods if you use this constructor to pass costs as type double. If you desire integer valued distances, then use the other constructor to pass costs as ints. 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.

EditDistance
public EditDistance(int insertCost, int deleteCost, int 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

distance
public final int distance(int[] s1, int[] s2) Measures the distance between two arrays. Specified by:
distance
in interfaceSequenceDistanceMeasurer
 Parameters:
s1
 First array.s2
 Second array. Returns:
 distance between s1 and s2
 Throws:
UnsupportedOperationException
 if costs were initialized with double values.

distance
public final int distance(long[] s1, long[] s2) Measures the distance between two arrays. Specified by:
distance
in interfaceSequenceDistanceMeasurer
 Parameters:
s1
 First array.s2
 Second array. Returns:
 distance between s1 and s2
 Throws:
UnsupportedOperationException
 if costs were initialized with double values.

distance
public final int distance(short[] s1, short[] s2) Measures the distance between two arrays. Specified by:
distance
in interfaceSequenceDistanceMeasurer
 Parameters:
s1
 First array.s2
 Second array. Returns:
 distance between s1 and s2
 Throws:
UnsupportedOperationException
 if costs were initialized with double values.

distance
public final int distance(byte[] s1, byte[] s2) Measures the distance between two arrays. Specified by:
distance
in interfaceSequenceDistanceMeasurer
 Parameters:
s1
 First array.s2
 Second array. Returns:
 distance between s1 and s2
 Throws:
UnsupportedOperationException
 if costs were initialized with double values.

distance
public final int distance(char[] s1, char[] s2) Measures the distance between two arrays. Specified by:
distance
in interfaceSequenceDistanceMeasurer
 Parameters:
s1
 First array.s2
 Second array. Returns:
 distance between s1 and s2
 Throws:
UnsupportedOperationException
 if costs were initialized with double values.

distance
public final int distance(boolean[] s1, boolean[] s2) Measures the distance between two arrays. Specified by:
distance
in interfaceSequenceDistanceMeasurer
 Parameters:
s1
 First array.s2
 Second array. Returns:
 distance between s1 and s2
 Throws:
UnsupportedOperationException
 if costs were initialized with double values.

distance
public final int distance(double[] s1, double[] s2) Measures the distance between two arrays. Specified by:
distance
in interfaceSequenceDistanceMeasurer
 Parameters:
s1
 First array.s2
 Second array. Returns:
 distance between s1 and s2
 Throws:
UnsupportedOperationException
 if costs were initialized with double values.

distance
public final int distance(float[] s1, float[] s2) Measures the distance between two arrays. Specified by:
distance
in interfaceSequenceDistanceMeasurer
 Parameters:
s1
 First array.s2
 Second array. Returns:
 distance between s1 and s2
 Throws:
UnsupportedOperationException
 if costs were initialized with double values.

distance
Measures the distance between two Strings. Specified by:
distance
in interfaceSequenceDistanceMeasurer
 Parameters:
s1
 First String.s2
 Second String. Returns:
 distance between s1 and s2
 Throws:
UnsupportedOperationException
 if costs were initialized with double values.

distance
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:
distance
in interfaceSequenceDistanceMeasurer
 Parameters:
s1
 First array.s2
 Second array. Returns:
 distance between s1 and s2
 Throws:
UnsupportedOperationException
 if costs were initialized with double values.

distance
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:
distance
in interfaceSequenceDistanceMeasurer
 Type Parameters:
T
 Type of List elements. Parameters:
s1
 First list.s2
 Second list. Returns:
 distance between s1 and s2
 Throws:
UnsupportedOperationException
 if costs were initialized with double values.

EditDistanceDouble
class instead.