Compute edit distance between two scalar sequences. This class uses Levenshtein (or Damerau-Levenshtein) to compute the edit distance between two inputs. The inputs are arrays containing any scalars (not just strings) so it can be used with, e.g., utf8 sequences.

$matrix = id(new PhutilEditDistanceMatrix())

->setSequences(str_split('ran'), str_split('rat'));

$cost = $matrix->getEditDistance();

Edit distance computation is slow and requires a large amount of memory; both are roughly O(N * M) in the length of the strings.

You can customize the cost of insertions, deletions and replacements. By default, each has a cost of 1.

$matrix->setReplaceCost(1);

By default, transpositions are not evaluated (i.e., the algorithm is Levenshtein). You can cause transpositions to be evaluated by setting a transpose cost (which will change the algorithm to Damerau-Levenshtein):

$matrix->setTransposeCost(1);

You can also provide a cost to alter the type of operation being applied. Many strings have several equivalently expensive edit sequences, but one some sequences are more readable to humans than others. Providing a small cost to alter operation type tends to smooth out the sequence and produce long runs of a single operation, which are generally more readable. For example, these strings:

(x)
((x))

...have edit strings "issis" and "isssi", which describe edit operations with the same cost, but the latter string is more comprehensible to human viewers.

If you set an alter cost, you must call setComputeString() to enable type computation. The alter cost should generally be smaller than c / N, where c is the smallest operational cost and N is the length of the longest string. For example, if you are using the default costs (insert = 1, delete = 1, replace = 1) and computing edit distances for strings of fewer than 1,000 characters, you might set the alter cost to 0.001.