2
$\begingroup$

The best known algorithm for computing the exact edit distance between two strings is I believe an algorithm by Masek and Paterson that runs in time $O(n^2/\log^2 n)$, for binary alphabets.

Is there any algorithm that possibly by taking advantage of larger alphabet sizes (and potentially the possibility of few matches to explore) can run in time that might be strictly better than the above bound for large (i.e non-constant sized) alphabets ? Or is there some easy reason why this would be as hard as the case for a binary alphabet ?

$\endgroup$
  • 1
    $\begingroup$ IIRC the Masek and Paterson algorithm has $O(n^2/\log n)$ time complexity. $\endgroup$ – Gianluca Della Vedova Sep 7 '12 at 7:54
  • 1
    $\begingroup$ Even if the alphabet is bigger, the input strings might have only two unique characters. $\endgroup$ – Jeffε Sep 7 '12 at 12:14
  • $\begingroup$ I guess I was thinking of the "induced" alphabet i.e the union of the characters in the two strings. My thought was that edit distance calculation should be easier if there is little overlap between the two strings. $\endgroup$ – Suresh Venkat Sep 7 '12 at 15:36
5
$\begingroup$

The answer is certainly yes. Assume for simplicity that the two strings are of equal length $n$. If the "induced" alphabet of each string is also of size $n$, then both strings are permutations, and the problem degenerates to the classical longest increasing subsequence (LIS) problem: it is easy to see that the edit distance between a given permutation $\pi$ and the sorted permutation $1,2,\ldots,n$ is $n-LIS(\pi)$. The LIS problem was studied as early as 1930s by Erdos and Szekeres, and by Robinson. The best algorithms for LIS run in time $O(n \log n)$ or $O(n \log\log n)$, depending on the computation model. Such algorithms were (re)discovered dozens of times (or perhaps hundreds of thousands, considering that the problem makes a good programming exercise), often with various twists. It is easy to find the relevant papers, since most of them cite previous work. The most recent result I am aware of, and a good point to start exploring the references, is the $O(n \log\log LIS(\pi))$ algorithm by Crochemore and Porat:

M. Crochemore and E. Porat. Fast computation of a longest increasing subsequence and application. Information and Computation, 208(9):1054--1059, 2010. http://dx.doi.org/10.1016/j.ic.2010.04.003

The same paper also describes how to interpolate between this extreme case and the general edit distance problem, taking the total number of character matches as a parameter. This is relevant when your "induced" alphabet size is large, but not exactly equal to $n$. For smaller "induced" alphabet sizes (say $n/2$), it is easy to construct examples that are essentially binary over a significant part (say, one half) of each input string, so a large "induced" alphabet over the whole string won't help more than by a constant factor.

$\endgroup$
  • $\begingroup$ Excellent. That's very helpful. $\endgroup$ – Suresh Venkat Sep 13 '12 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.