13
$\begingroup$

Motivation: A coauthor edits a manuscript and I would like to see a clear summary of the edits. All "diff"-like tools tend to be useless if you are both moving text around (e.g., re-organising the structure) and doing local edits. Is it really so hard to get it right?


Definitions: I would like to find the minimum edit distance, where the permitted operations are:

  • "cheap" operations: add/change/delete a single character (the usual Levenshtein operations),

  • "expensive": operations: move a substring to a new location ($abcd \mapsto acbd$ for any strings $a$, $b$, $c$, $d$).

Given two strings $x$ and $y$ and integers $k$ and $K$, I would like to solve the following problem:

  • can you transform $x$ into $y$ using at most $k$ cheap operations and at most $K$ expensive operations?

Questions:

  1. Does this problem have a name? (It sounds like a very standard question in the context of sequence alignment.)

  2. Is it hard?

  3. If it is hard, is it fixed-parameter tractable with $K$ as the parameter?

  4. Are there efficient approximation algorithms? (E.g., find a solution with at most $2k$ cheap and $2K$ expensive operations if a solution with $k$ cheap and $K$ expensive operations exist.)

I tried to have a look at the string metrics listed in Wikipedia, but none of them looked right.

$\endgroup$
  • 3
    $\begingroup$ For $k=0$, the problem is Sorting by Transpositions. See, e.g. web.cs.dal.ca/~whidden/HThesis07.pdf I have not encountered your problem, but it seems very well motivated. $\endgroup$ – Serge Gaspers Mar 10 '13 at 14:39
  • 4
    $\begingroup$ The NP-hardness of the Sorting by Transpositions problem has been proved in 2010, see Sorting by transpositions is difficult. $\endgroup$ – Marzio De Biasi Mar 10 '13 at 16:33
  • 3
    $\begingroup$ Transpositions are hard, but insertions and deletions are not. If you allow an expensive operation to be either the deletion of an arbitrary substring or the insertion of any substring of the other string, the problem should become quite easy. The resulting distance would not be symmetric, though. $\endgroup$ – Jouni Sirén Mar 11 '13 at 2:56
  • $\begingroup$ I'm more curious about the fixed-parameter tractability. Is there any new discovery? $\endgroup$ – Yixin Cao Apr 5 '13 at 13:55
5
$\begingroup$

As commented by Serge Gaspers, for $k=0$ the problem is Sorting by Transpositions, and was introduced by Bafna and Pevzner in 1995. Its NP-hardness has been proved only in 2010; see Laurent Bulteau, Guillaume Fertin, and Irena Rusu, "Sorting by Transpositions is Difficult".

$\endgroup$
4
$\begingroup$

The problem becomes easier, if we consider long deletions and substring copying instead of transpositions. Assume that we are using the standard dynamic programming algorithm for edit distance computation, and that an expensive operation of length $k$ increases the distance by $ak+b$, for some constants $a,b \ge 0$. These constants may be different for long deletions and substring copying.

A long deletion is the deletion of an arbitrary substring from $x$. Supporting them is easy, if we break them down into two kinds of simple operations: deleting the first character (cost $a+b$) and extending the deletion by one character (cost $a$). In addition to the standard array $A$, where $A[i,j]$ is the edit distance between prefixes $x[1 \dots i]$ and $y[1 \dots j]$, we use another array $A_{d}$ to store the edit distance, when the last operation used was a long deletion. With this array, we only have to look at $A[i-1,j]$, $A[i-1,j-1]$, $A[i,j-1]$ and $A_{d}[i-1,j]$ when computing $A[i,j]$ and $A_{d}[i,j]$, allowing us to do it in $O(1)$ time.

Substring copying means the insertion of an arbitrary substring of $x$ into the edited string. As with long deletions, we break the operation down into two simple operations: inserting the first character and extending the insertion by one character. We also use array $A_{s}$ to store the edit distance between prefixes, provided that the last operation used was substring copying.

Doing this efficiently is more complicated than with long deletions, and I am not sure whether we can get to amortized $O(1)$ time per cell. We build a suffix tree for $x$, which takes $O(|x|)$ time, assuming a constant-size alphabet. We store a pointer to the current suffix tree node in $A_{s}[i,j-1]$, allowing us to check in constant time, whether we can extend the insertion by character $y[j]$. If that is true, we can compute $A[i,j]$ and $A_{s}[i,j]$ in constant time.

Otherwise $zy[j]$, where $z$ is the inserted substring that was used to compute $A_{s}[i,j-1]$, is not a substring of $x$. We use the suffix tree to find the longest suffix $z'$ of $z$, for which $z'y[j]$ is a substring of $x$, in $O(|z|-|z'|)$ time. To compute $A_{s}[i,j]$, we now need to look at cells $A[i, j-|z'|-1]$ to $A[i,j-1]$. Finding suffix $z'$ requires just amortized $O(1)$ time per cell, but computing $A_{s}[i,j]$ with a brute-force approach takes $O(|z'|)$ time. There is probably some way to do this more efficiently, but I cannot find it right now.

In the worst case, the algorithm takes $O(\min(|x| \cdot |y|^{2}, |x|^{2} \cdot |y|))$ time, but a better analysis should be possible. The resulting edit distance with long deletions and substring copying is not symmetric, but that should not be a problem. After all, it is usually easier to reach the empty string from a nonempty one than the other way around.

$\endgroup$

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.