Class EditDistance

  • All Implemented Interfaces:

    public final class EditDistance
    extends Object
    implements PermutationDistanceMeasurerDouble
    Edit Distance:

    This is an implementation of Wagner and Fischer's dynamic programming algorithm for computing string edit distance, but adapted to permutations rather than general strings.

    Edit distance is the minimum cost to transform one permutation 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 permutation, Deletes which remove an element from the permutation, and Changes which replace an element with a different element.

    The edit distance is parameterized by costs for the edit operations. We provide one constructor which enables you to specify 3 costs, 1 for each type of edit operation.

    And we also provide a default constructor, which assigns a cost of 0.5 for insert, 0.5 for delete, and which assigns an infinite cost to changes, essentially disallowing that 3rd type of edit operation. We chose this as the default as it is equivalent to counting the number of reinsertion operations necessary to transform one permutation into the other, known as Reinsertion Distance. A reinsertion operation removes an element and reinserts it in a different position, and is treated as a single composite operation.

    Runtime: O(n2), where n is the permutation length.

    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.

    Its application as a means of computing Reinsertion Distance is first described in:
    V. A. Cicirello and R. Cernera, "Profiling the distance characteristics of mutation operators for permutation-based genetic algorithms," in Proceedings of the 26th FLAIRS Conference. AAAI Press, May 2013, pp. 46–51.

    • Constructor Detail

      • EditDistance

        public EditDistance​(double insertCost,
                            double deleteCost,
                            double changeCost)
        Constructs an EditDistance function.
        insertCost - Cost of an insertion operation.
        deleteCost - Cost of a deletion operation.
        changeCost - Cost of a change operation.
      • EditDistance

        public EditDistance()
        Default edit distance computes number of remove and reinsert operations to transform one permutation into the other. And does not use change operations.