<p>As commented by Serge Gaspers, for $k=0$ the problem is <em>Sorting by Transpositions</em>, and was introduced by Bafna and Pevzner in 1995. Its NP-hardness has been proved only in 2010; see <a href="http://arxiv.org/abs/1011.1157">Laurent Bulteau, Guillaume Fertin, and Irena Rusu, "Sorting by Transpositions is Difficult"</a>.</p>

CC BY-SA 3.0
2013-03-10T18:25:56.627Z
2013-03-10T18:25:56.627Z
Marzio De Biasi
<p>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.</p>

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

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

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

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

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

CC BY-SA 3.0
2013-03-11T20:19:25.123Z
2013-03-11T20:19:25.123Z
Jouni Sirén
<p><strong>Motivation:</strong> 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 <em>both</em> moving text around (e.g., re-organising the structure) <em>and</em> doing local edits. Is it really so hard to get it right?</p>

<hr>

<p><strong>Definitions:</strong> I would like to find the minimum edit distance, where the permitted operations are:</p>

<ul>
<li><p>"cheap" operations: add/change/delete a single character (the usual Levenshtein operations),</p></li>
<li><p>"expensive": operations: move a substring to a new location ($abcd \mapsto acbd$ for any strings $a$, $b$, $c$, $d$).</p></li>
</ul>

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

<ul>
<li>can you transform $x$ into $y$ using at most $k$ cheap operations and at most $K$ expensive operations?</li>
</ul>

<hr>

<p><strong>Questions:</strong></p>

<ol>
<li><p>Does this problem have a name? (It sounds like a very standard question in the context of sequence alignment.)</p></li>
<li><p>Is it hard?</p></li>
<li><p>If it is hard, is it fixed-parameter tractable with $K$ as the parameter?</p></li>
<li><p>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.)</p></li>
</ol>

<p>I tried to have a look at the <a href="http://en.wikipedia.org/wiki/String_metric">string metrics listed in Wikipedia</a>, but none of them looked right.</p>

CC BY-SA 3.0
2013-03-10T14:39:38.297Z
For $k=0$, the problem is Sorting by Transpositions. See, e.g. http://web.cs.dal.ca/~whidden/HThesis07.pdf
I have not encountered your problem, but it seems very well motivated.
Serge Gaspers
CC BY-SA 3.0
2013-03-10T16:33:15.900Z
The NP-hardness of the Sorting by Transpositions problem has been proved in 2010, see [Sorting by transpositions is difficult](http://arxiv.org/abs/1011.1157).
Marzio De Biasi
CC BY-SA 3.0
2013-03-11T02:56:35.763Z
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.
Jouni Sirén
CC BY-SA 3.0
2013-04-05T13:55:57.170Z
I'm more curious about the fixed-parameter tractability.  Is there any new discovery?
Yixin Cao
<ds.algorithms><reference-request><parameterized-complexity><string-matching><edit-distance>
Edit distance with move operations
Jukka Suomela
# Edit distance with move operations

(Asked by: username_0 on 2013-03-10)

**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](http://en.wikipedia.org/wiki/String_metric), but none of them looked right.

**Tags:** ds.algorithms, reference-request, parameterized-complexity, string-matching, edit-distance

> **Comments:**
> **username_1**: For $k=0$, the problem is Sorting by Transpositions. See, e.g. http://web.cs.dal.ca/~whidden/HThesis07.pdf I have not encountered your problem, but it seems very well motivated.  
> **username_2**: The NP-hardness of the Sorting by Transpositions problem has been proved in 2010, see [Sorting by transpositions is difficult](http://arxiv.org/abs/1011.1157).  
> **username_3**: 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.  
> **username_4**: I'm more curious about the fixed-parameter tractability.  Is there any new discovery?  

---

## 2 answers

### Answer by username_2 on 2013-03-10. Score: 7 | Accepted answer

As commented by username_1, 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"](http://arxiv.org/abs/1011.1157).


---

### Answer by username_3 on 2013-03-11. Score: 6

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.


---

