<p>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 <em>longest increasing subsequence (LIS) problem</em>: 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:</p>

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

<p>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.</p>

CC BY-SA 3.0
2012-09-13T21:10:45.440Z
Excellent. That's very helpful.
Suresh Venkat
CC BY-SA 3.0
2012-09-13T20:15:01.920Z
2012-09-13T20:20:18.263Z
2012-09-13T20:20:18.263Z
Alexander Tiskin
<p>The best known algorithm for computing the <strong>exact</strong> 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. </p>

<p>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 ? </p>

CC BY-SA 3.0
2012-09-07T07:54:51.500Z
IIRC the Masek and Paterson algorithm has $O(n^2/\log n)$ time complexity.
Gianluca Della Vedova
CC BY-SA 3.0
2012-09-07T12:14:30.367Z
Even if the alphabet is bigger, the input strings might have only two unique characters.
Jeffε
CC BY-SA 3.0
2012-09-07T15:36:35.153Z
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.
Suresh Venkat
<ds.algorithms><edit-distance>
Edit distance algorithms that depend on alphabet
Suresh Venkat
# Edit distance algorithms that depend on alphabet

(Asked by: username_0 on 2012-09-07)

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 ?

**Tags:** ds.algorithms, edit-distance

> **Comments:**
> **username_1**: IIRC the Masek and Paterson algorithm has $O(n^2/\log n)$ time complexity.  
> **username_2**: Even if the alphabet is bigger, the input strings might have only two unique characters.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_3 on 2012-09-13. Score: 5

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.

> **Comments:**
> **username_0**: Excellent. That's very helpful.  

---

