Levenshtein-Distance edit distance between lists is a well studied problem. But I can't find much on possible improvements if it is known that no element does occurs more than once in each list.

Let's also assume that the elements are comparable/sortable (but the lists to compare are not sorted to begin with).

In particular I am interested if the uniqueness of elements makes it possible to improve upon Ukkonen's algorithm for edit distance which has time complexity $O(\min(m,n)s)$ and space complexity $O(\min(s,m,n)s)$, where $s$ is the minimum cost of the editing steps.

More formally,

how efficiently can we compute the edit distance between two given strings $s,t \in \Sigma^*$ with the promise that they don't have any repeated letters?

$\Sigma$ is a very large alphabet.

  • What is your question now; how to speed up pairwise edit distance, or how to speed up computing all pairwise distances of a list of strings? – Raphael Jul 27 '15 at 6:24
  • 2
    I suspect the question is: How to compute the edit distance between $s,t$, where $s,t \in \Sigma^*$ are strings over some very large alphabet $\Sigma$, and we're guaranteed that no letter appears twice in $s$ or in $t$ (the OP represents each string as a list of letters, i.e., a list of elements). But this needs confirmation. – D.W. Jul 27 '15 at 8:53
  • Yes, in this case the large alphabet is made up of database indexes and the "strings", s and t, are lists containing these indexes. – user362178 Jul 27 '15 at 10:06
  • For those wondering about the complexities: $m$ and $n$ are the lengths of the input strings and $s$ is the actual edit distance, so it is included in the complexity. The cost of each edit is considered 1 but is probably irrelevant for calculating this distance (the number of edits $s$). – Albert Hendriks Apr 14 at 0:03

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

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

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

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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