Skip to main content
Computer Science

Return to Answer

Bounty Ended with 50 reputation awarded by Stefan Haustein
Rename "restricted edit distance" to "insert/delete edit distance".
Source Link
j_random_hacker
j_random_hacker
  • 5.5k
  • 1
  • 16
  • 22

The reason for this detour is that there is a very efficient way to calculate the LCS (and thus the insert/delete edit distance) when at least one of the sequences contains only distinct characters: In this case, the LCS problem can be transformed into the problem of finding a longest increasing subsequence, which can be solved in time $O(n \log n)$. Suppose we are given two strings $A$ and $B$, and string $A$ has distinct characters. We can rename the first character in $A$ to 1, the second to 2 and so on, keeping track of what number we assigned to each character in a table. Then in $B$, we rename its characters using this table (i.e., every occurrence of whatever was the first character in A is changed to 1, etc.). Finally, we look for a longest increasing subsequence in B. This corresponds to a LCS between A and B, and from there we can immediately calculate the restrictedinsert/delete edit distance. The total time needed is just $O(n + m\log m)$ if $A$ and $B$ have lengths $n$ and $m$, respectively.

The insert/delete distance clearly provides an upper bound on the Levenshtein distance (since any valid sequence of edit operations under the restrictedinsert/delete distance is also a valid sequence of Levenshtein edit operations). Dividing the restrictedinsert/delete edit distance by 2 also gives a lower bound, since in the worst case any Levenshtein edit operation can be changed into 2 restrictedinsert/delete edit operations.

The reason for this detour is that there is a very efficient way to calculate the LCS (and thus the insert/delete edit distance) when at least one of the sequences contains only distinct characters: In this case, the LCS problem can be transformed into the problem of finding a longest increasing subsequence, which can be solved in time $O(n \log n)$. Suppose we are given two strings $A$ and $B$, and string $A$ has distinct characters. We can rename the first character in $A$ to 1, the second to 2 and so on, keeping track of what number we assigned to each character in a table. Then in $B$, we rename its characters using this table (i.e., every occurrence of whatever was the first character in A is changed to 1, etc.). Finally, we look for a longest increasing subsequence in B. This corresponds to a LCS between A and B, and from there we can immediately calculate the restricted edit distance. The total time needed is just $O(n + m\log m)$ if $A$ and $B$ have lengths $n$ and $m$, respectively.

The insert/delete distance clearly provides an upper bound on the Levenshtein distance (since any valid sequence of edit operations under the restricted distance is also a valid sequence of Levenshtein edit operations). Dividing the restricted edit distance by 2 also gives a lower bound, since in the worst case any Levenshtein edit operation can be changed into 2 restricted edit operations.

The reason for this detour is that there is a very efficient way to calculate the LCS (and thus the insert/delete edit distance) when at least one of the sequences contains only distinct characters: In this case, the LCS problem can be transformed into the problem of finding a longest increasing subsequence, which can be solved in time $O(n \log n)$. Suppose we are given two strings $A$ and $B$, and string $A$ has distinct characters. We can rename the first character in $A$ to 1, the second to 2 and so on, keeping track of what number we assigned to each character in a table. Then in $B$, we rename its characters using this table (i.e., every occurrence of whatever was the first character in A is changed to 1, etc.). Finally, we look for a longest increasing subsequence in B. This corresponds to a LCS between A and B, and from there we can immediately calculate the insert/delete edit distance. The total time needed is just $O(n + m\log m)$ if $A$ and $B$ have lengths $n$ and $m$, respectively.

The insert/delete distance clearly provides an upper bound on the Levenshtein distance (since any valid sequence of edit operations under the insert/delete distance is also a valid sequence of Levenshtein edit operations). Dividing the insert/delete edit distance by 2 also gives a lower bound, since in the worst case any Levenshtein edit operation can be changed into 2 insert/delete edit operations.

Source Link
j_random_hacker
j_random_hacker
  • 5.5k
  • 1
  • 16
  • 22

TL;DR: A slightly more restrictive kind of edit distance, in which we can only insert and delete individual characters, can be computed in linearithmic time when both (or even just one) of the strings have unique characters. This gives useful upper and lower bounds on the Levenshtein edit distance.

Insert/delete edit distance, and longest common subsequences

Levenshtein edit distance allows single-character insertions, deletions and substitutions, assigning each a cost of 1. If we restrict to just insertions and deletions, we get a similar distance measure that now causes substitutions to have a cost of 2 (since any substitution can be mimicked using an insertion and a deletion). I don't know a standard name for this more restrictive kind of edit distance, so I'll call it "insert/delete edit distance". It corresponds closely to the longest common subsequence (LCS) problem, in which we are given two strings, of length $m$ and $n$, respectively, and want to know the length of the longest subsequence that appears in both. If two strings have LCS $L$, then they have insert/delete edit distance $n+m-2L$: the easiest way to see this is to align the strings so that characters in the LCS appear stacked on top of each other, while characters not in the LCS appear opposite a - gap character. It will then be apparent that we can edit the first string into the second by making an insertion wherever there is a - in the top row, and a deletion wherever there is a - in the bottom row. For example:

-C-IRC-LE
T-RI-CKLE

Here the LCS of CIRCLE and TRICKLE, ICLE, has length 4, and the edit distance is indeed $6+7-2*4=5$.

Longest increasing subsequences

The reason for this detour is that there is a very efficient way to calculate the LCS (and thus the insert/delete edit distance) when at least one of the sequences contains only distinct characters: In this case, the LCS problem can be transformed into the problem of finding a longest increasing subsequence, which can be solved in time $O(n \log n)$. Suppose we are given two strings $A$ and $B$, and string $A$ has distinct characters. We can rename the first character in $A$ to 1, the second to 2 and so on, keeping track of what number we assigned to each character in a table. Then in $B$, we rename its characters using this table (i.e., every occurrence of whatever was the first character in A is changed to 1, etc.). Finally, we look for a longest increasing subsequence in B. This corresponds to a LCS between A and B, and from there we can immediately calculate the restricted edit distance. The total time needed is just $O(n + m\log m)$ if $A$ and $B$ have lengths $n$ and $m$, respectively.

Bounds on Levenshtein edit distance

The insert/delete distance clearly provides an upper bound on the Levenshtein distance (since any valid sequence of edit operations under the restricted distance is also a valid sequence of Levenshtein edit operations). Dividing the restricted edit distance by 2 also gives a lower bound, since in the worst case any Levenshtein edit operation can be changed into 2 restricted edit operations.

Generalisations

Already in 1977, Hunt and Szymanski came up with an algorithm that can be viewed as a generalisation of the longest increasing subsequence algorithm. It is efficient whenever the number of pairs of matching character positions between the two strings is small. If there are $r$ such pairs, their algorithm takes $O((r + n)\log n)$ time. (Notice that $r \le n$ if all characters in one string are distinct.) This algorithm was the basis of the original diff program, which treated entire lines of text as individual characters. diff later switched to using Myers's $O(nd)$-time algorithm, where $d$ is the insert/delete edit distance, as this performs better when overall differences are small but some "characters" (text lines) appear frequently (such as a line containing just an opening brace in C program code).

Hunt, J.; Szymanski, T. (1977), "A fast algorithm for computing longest common subsequences", Communications of the ACM, 20 (5): 350–353, doi:10.1145/359581.359603