Module org.cicirello.jpt

Package org.cicirello.permutations.distance

Class EditDistance

java.lang.Object

org.cicirello.permutations.distance.EditDistance

All Implemented Interfaces:

PermutationDistanceMeasurerDouble

public final class EditDistance
extends Object
implements PermutationDistanceMeasurerDouble

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. However, the ReinsertionDistance class provides an implementation of a specialized algorithm that is more efficient for this special case.

Runtime: O(n²), 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 Summary

Constructors

Constructor	Description
EditDistance()	Default edit distance computes number of remove and reinsert operations to transform one permutation into the other.
EditDistance(double insertCost, double deleteCost, double changeCost)	Constructs an EditDistance function.

Method Summary

Modifier and Type	Method	Description
double	distancef(Permutation p1, Permutation p2)	Measures the distance between two permutations.

Methods inherited from class java.lang.Object

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

Constructor Details

EditDistance

public EditDistance(double insertCost,
 double deleteCost,
 double changeCost)

Constructs an EditDistance function.

Parameters:

insertCost - Cost of an insertion operation.

deleteCost - Cost of a deletion operation.

changeCost - Cost of a change operation.

Throws:

IllegalArgumentException - if any of the costs are negative.

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.

Method Details

distancef

public double distancef(Permutation p1,
 Permutation p2)

Measures the distance between two permutations.

Specified by:

distancef in interface PermutationDistanceMeasurerDouble

Parameters:

p1 - first permutation

p2 - second permutation

Returns:

distance between p1 and p2