Module org.cicirello.jpt
Package org.cicirello.sequences.distance

Class EditDistanceDouble

java.lang.Object
org.cicirello.sequences.distance.EditDistanceDouble
All Implemented Interfaces:
SequenceDistanceMeasurerDouble
Direct Known Subclasses:
EditDistance
public class EditDistanceDouble extends Object implements SequenceDistanceMeasurerDouble
EditDistanceDouble is an implementation of Wagner and Fischer's dynamic programming algorithm for computing string edit distance. This class supports double-valued costs, while the EditDistance class supports int-valued costs. If your costs are int-valued, the EditDistance class may be slightly faster, but not asymptotically faster.

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 N-1.

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 string-to-string correction problem," Journal of the ACM, vol. 21, no. 1, pp. 168–173, January 1974.

  • Constructor Summary

    Constructors
    Constructor
    Description
    EditDistanceDouble(double insertCost, double deleteCost, double changeCost)
    Constructs an edit distance measure with the specified edit operation costs.

  • Method Summary

    Modifier and Type
    Method
    Description
    final 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
    distancef(Object[] s1, Object[] s2)
    Measures the distance between two arrays of objects.
    final double
    distancef(String s1, String s2)
    Measures the distance between two Strings.
    final <T> double
    distancef(List<T> s1, List<T> s2)
    Measures the distance between two lists of objects.

    Methods inherited from class java.lang.Object

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

  • 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 non-negative.
      deleteCost - Cost of an deletion operation. Must be non-negative.
      changeCost - Cost of an change operation. Must be non-negative.
      Throws:
      IllegalArgumentException - if any of the costs are negative.

  • Method Details