<p>I don't know whether this exact problem has been studied, but  <a href="http://cseweb.ucsd.edu/~kamalika/pubs/ccmr06.pdf" rel="nofollow">Chaudhuri et al.</a> studied the related <strong>tandem duplication-random loss</strong> problem: you are given a permutation, and you want to transform it into the identity permutation by 
 (1)  duplicating a segment of any length and appending the copy right after the original, then (2) deleting elements so that you obtain a new permutation instead of a string. Note that applying (1) then (2) accounts for one operation. </p>

<p>Different variants can be defined according to the weight given to each operation, which in their paper depends on the width of the duplicated segments. 
They also study a similar problem with the <strong>whole genome duplication</strong>, which is exactly the kind of duplication you allow. I don't remember reading about work on this problem in the context of strings, but I hope this can at least give you a starting point for your searches.</p>

CC BY-SA 3.0
2013-02-28T13:52:27.437Z
Thank, I will have a look at their work. I can see the relationship between the two problems.
cz3rk
CC BY-SA 3.0
2013-02-28T06:22:03.357Z
2013-02-28T06:22:03.357Z
Anthony Labarre
<p>As has been pointed out, this problem is similar to the more commonly known edit distance problem (underlying the <a href="http://en.wikipedia.org/wiki/Levenshtein_distance" rel="nofollow">Levenshtein distance</a>). It also has commonalities with, for example, <a href="http://en.wikipedia.org/wiki/Dynamic_time_warping" rel="nofollow">Dynamic Time Warping distance</a> (the duplication, or  “stuttering,” in your last requirement). </p>

<h3>Steps toward dynamic programming</h3>

<p>My first attempt at a recursive decomposition along the lines of Levenshtein distance and Dynamic Time Warping Distance was something like the following (for $x=x_1\ldots x_n$ and $y=y_1\ldots y_m$), with $d(x,y)$ being set to
$$
\min
\begin{cases}
d(x,y_1\ldots y_{m-1})+1 &amp; &amp;\text{▻ Add letter at end}\\
d(x,y_2\ldots y_m)+1 &amp; &amp; \text{▻ Add letter at beginning}\\
d(x,y_1\ldots y_{m/2})+1 &amp; \text{if $y=y_1\ldots y_{m/2}y_1\ldots y_{m/2}$}
    &amp; \text{▻ Doubling}\\
d(x_1\ldots x_{n/2},y)+1 &amp; \text{if $x=x_1\ldots x_{n/2}x_1\ldots x_{n/2}$}
    &amp; \text{▻ Halving}\\
d(x_1\ldots x_n,y) + 1 &amp;&amp; \text{▻ Deletion}\\
d(x_1\ldots x_{n-1},y_1\ldots y_{m-1}) &amp; \text{if $y_n = y_m$}
    &amp; \text{▻ Ignoring last elt.}\\
\end{cases}
$$</p>

<p>Here, the last option basically says that converting FOOX to BARX is equivalent to converting FOO to BAR. This means that you could use the “add letter at end” option to achieve the stuttering (duplication) effect, and the deletion at an point. The problem is that it automatically lets you add an <em>arbitrary</em> character in the middle of the string <em>as well</em>, something you probably don't want. (This “ignoring identical last elements” is the standard way to achieve deletion and stuttering in arbitrary positions. It does make prohibiting arbitrary insertions, while allowing additions at either end, a bit tricky, though…)</p>

<p>I've included this breakdown even though it doesn't do the job completely, in case someone else can “rescue” it, somehow—and because I use it in my heuristic solution, below.</p>

<p>(Of course, if you could get a breakdown like this that actually defined your distance, you'd only need to add memoization, and you'd have a solution. However, because you're not just working with prefixes, I don't think you could use just indexes for your memoization; you might have to store the actual, modified strings for each call, which would get huge if your strings are of substantial size.)</p>

<h3>Steps toward a heuristic solution</h3>

<p>Another approach, which might be easier to understand, and which could use quite a bit less space, is to search for the shortest “edit path” from your first string to your second, using the <a href="http://en.wikipedia.org/wiki/A%2a_search_algorithm" rel="nofollow">$A^\ast$ algorithm</a> (basically, best-first branch-and-bound). The search space would be defined directly by your edit operations. Now, for a large string, you <em>would</em> get a large neighborhood, as you could delete any character (giving you a neighbor for each potential deletion), or duplicate any character (again, giving you a linear number of neighbors), as well as adding any character at either end, which would give you a number of neighbors equal to twice the alphabet size. (Just hope you're not using full Unicode ;-) With such a large fanout, you might achieve quite a substantial speedup using a <a href="http://www.avglab.com/andrew/pub/alenex06.pdf" rel="nofollow"><em>bidirectional</em> $A^*$, or some relative</a>.</p>

<p>In order to make $A^*$ work, you'd need a lower bound for the remaining distance to your target. I'm not sure if there's an obvious choice here, but what you <em>could</em> do is implement a dynamic programming solution based on the recursive decomposition I gave above (again with possible space issues if your strings are very long). While that decomposition doesn't exactly compute your distance, it <em>is</em> guaranteed to be a lower bound (because it's more permissive), which means it'll work as a heuristic in $A^*$. (How tight it'll be, I don't know, but it would be correct.) Of course, the memoization of your bound function could be shared across all calculations of the bound during your $A^*$ run. (A time-/space-tradeoff there.)</p>

<h3>So…</h3>

<p>The efficiency of my proposed solution would seem to depent quite a bit on (1) the lengths of your strings, and (2) the size of your alphabet. If neither is huge, it might work. That is:</p>

<ul>
<li>Implement the lower bound to your distance using my recursive decomposition and dynamic programming (for example, using a memoized, recursive function).</li>
<li>Implement $A^*$ (or bidirectional $A^*$) with your edit operations as “moves” in the state-space, and the dynamic programming-based lower bound.</li>
</ul>

<p>I can't really give any guarantees for how efficient it'd be, but it <em>should</em> be correct, and it would probably be a lot better than a brute-force solution.</p>

<p>If nothing else, I hope this gives you some ideas for further investigations.</p>

CC BY-SA 3.0
2013-03-11T09:12:08.900Z
2013-03-11T09:12:08.900Z
Magnus Lie Hetland
<p>Some related, well defined problem would be problem of <a href="http://en.wikipedia.org/wiki/Sequence_alignment" rel="nofollow">sequence alignment</a>. It is different because it doesn't use operation of duplication. 
Defined operations are: insertion of character, deletion of character, transformation of character. Popular algorithm for solving this problem is <a href="http://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm" rel="nofollow">Needleman-Wunsch</a>.</p>

CC BY-SA 3.0
2013-02-22T16:34:11.350Z
I know this one but I really want to work with a set of defined moves. The only way that I have found to do it, is with a brute-force recursive algorithm. Not very nice and he could become computationaly intensive if the size of the words increased.
cz3rk
CC BY-SA 3.0
2013-02-22T15:42:00.073Z
2013-02-22T15:42:00.073Z
Martinsos
<p>Except for duplication, the Levenstein distance might be worth a look:
<a href="http://en.wikipedia.org/wiki/Levenshtein_distance" rel="nofollow">http://en.wikipedia.org/wiki/Levenshtein_distance</a></p>

CC BY-SA 3.0
2013-02-28T07:23:07.857Z
2013-02-28T07:23:07.857Z
user13407
<p>I am looking for a data structure and an algorithm to compute the minimum number of changes required to transform one word into another, given the two words as inputs, where the only allowed changes are</p>

<ul>
<li>add a letter at one of the extremities (for example, AB -> ABC),</li>
<li>duplicate and concatenate the whole word (for example, ABC -> ABCABC),</li>
<li>cut a word in two (the dual of the duplication move, ABCABC -> ABC + ABC),</li>
<li>delete one of the letters (for example, ABC -> AC), and</li>
<li>repeat one of the letters (for example, ABC -> ABBC).</li>
</ul>

<p>For example, a minimal sequence of moves from ABC to BCBC is ABC -> BC (delete A) -> BCBC (duplication).</p>

<p>I don't have a background in computer science. Perhaps this is a well-known problem, but my Google search gave me nothing.</p>

<p>Do you know some related, well-defined problem?</p>

<p><em>Edit</em>: As suggested in the answer by Anthony Labarre, I read some papers about the poset permutation/arrangement problem which is similar to the problem described above. Does anyone know more about this problem? Is this relevant?</p>

CC BY-SA 3.0
2013-02-22T17:16:03.320Z
Presumably none from the list at https://en.wikipedia.org/wiki/String_metric apply, nor is it in http://sourceforge.net/projects/simmetrics/ ?
András Salamon
CC BY-SA 3.0
2013-02-25T09:38:20.400Z
I don't know all of them but most of the goal of these methods is to align strings whit only single letter change allowed and don't allow more complex moves.
cz3rk
CC BY-SA 3.0
2013-02-28T12:05:35.237Z
Can duplication be applied in both directions?
reinierpost
CC BY-SA 3.0
2013-02-28T13:55:28.403Z
A duplication apply on the whole string ABC -> ABCABC so the direction doesn't matter. But the direction of the repetition can only be in the order left right, like a stammer.
cz3rk
CC BY-SA 3.0
2013-02-28T15:24:13.643Z
@cz3rk: Is the distance from `ABCABC` to `ABC` the same as the distance from `ABC` to `ABCABC`?  Is this an allowed editing sequence: `AAAAAAAA` -> `AAAA` -> `AA` -> `A` -> `B` -> `BB` -> `BBBB` -> `BBBBBBBB`?
reinierpost
CC BY-SA 3.0
2013-02-28T16:35:00.853Z
ABCABC to ABC and ABC to ABCABC is the same, I forget to mention a cut move separating a string in two. The AAAAAAAA->BBBBBBBB will not be relevant in my case because the two words don't share letters.
cz3rk
CC BY-SA 3.0
2013-02-28T17:44:42.887Z
Why does it matter if the input words don't share letters?  (There should be an empty string between `A` and `B` in @reinerpost's sequence.)
Jeffε
CC BY-SA 3.0
2013-02-28T19:28:43.877Z
it would probably be helpful if you sketched out the application at least somewhat... note there is some relation to [grammar based codes](http://en.wikipedia.org/wiki/Grammar-based_code)
vzn
CC BY-SA 3.0
2013-02-28T20:09:23.277Z
You added the operation "cut a word in two"; do you mean the operation which maps $ww$ to $w$?
argentpepper
<graph-algorithms><ds.data-structures><edit-distance>
Shortest number of editing move between two words
cz3rk
# Shortest number of editing move between two words

(Asked by: username_0 on 2013-02-22)

I am looking for a data structure and an algorithm to compute the minimum number of changes required to transform one word into another, given the two words as inputs, where the only allowed changes are

* add a letter at one of the extremities (for example, AB -> ABC),
* duplicate and concatenate the whole word (for example, ABC -> ABCABC),
* cut a word in two (the dual of the duplication move, ABCABC -> ABC + ABC),
* delete one of the letters (for example, ABC -> AC), and
* repeat one of the letters (for example, ABC -> ABBC).

For example, a minimal sequence of moves from ABC to BCBC is ABC -> BC (delete A) -> BCBC (duplication).

I don't have a background in computer science. Perhaps this is a well-known problem, but my Google search gave me nothing.

Do you know some related, well-defined problem?

*Edit*: As suggested in the answer by Anthony Labarre, I read some papers about the poset permutation/arrangement problem which is similar to the problem described above. Does anyone know more about this problem? Is this relevant?

**Tags:** graph-algorithms, ds.data-structures, edit-distance
> **Comments:**
> **username_1**: Presumably none from the list at https://en.wikipedia.org/wiki/String_metric apply, nor is it in http://sourceforge.net/projects/simmetrics/ ?  
> **username_0**: I don't know all of them but most of the goal of these methods is to align strings whit only single letter change allowed and don't allow more complex moves.  
> **username_2**: Can duplication be applied in both directions?  
> **username_0**: A duplication apply on the whole string ABC -> ABCABC so the direction doesn't matter. But the direction of the repetition can only be in the order left right, like a stammer.  
> **username_2**: @cz3rk: Is the distance from `ABCABC` to `ABC` the same as the distance from `ABC` to `ABCABC`?  Is this an allowed editing sequence: `AAAAAAAA` -> `AAAA` -> `AA` -> `A` -> `B` -> `BB` -> `BBBB` -> `BBBBBBBB`?  
> **username_0**: ABCABC to ABC and ABC to ABCABC is the same, I forget to mention a cut move separating a string in two. The AAAAAAAA->BBBBBBBB will not be relevant in my case because the two words don't share letters.  
> **username_3**: Why does it matter if the input words don't share letters?  (There should be an empty string between `A` and `B` in @reinerpost's sequence.)  
> **username_4**: it would probably be helpful if you sketched out the application at least somewhat... note there is some relation to [grammar based codes](http://en.wikipedia.org/wiki/Grammar-based_code)  
> **username_5**: You added the operation "cut a word in two"; do you mean the operation which maps $ww$ to $w$?  

---

## 4 answers

### Answer by username_6 on 2013-02-28. Score: 3

I don't know whether this exact problem has been studied, but [Chaudhuri et al.](http://cseweb.ucsd.edu/~kamalika/pubs/ccmr06.pdf) studied the related **tandem duplication-random loss** problem: you are given a permutation, and you want to transform it into the identity permutation by
(1) duplicating a segment of any length and appending the copy right after the original, then (2) deleting elements so that you obtain a new permutation instead of a string. Note that applying (1) then (2) accounts for one operation.

Different variants can be defined according to the weight given to each operation, which in their paper depends on the width of the duplicated segments.
They also study a similar problem with the **whole genome duplication**, which is exactly the kind of duplication you allow. I don't remember reading about work on this problem in the context of strings, but I hope this can at least give you a starting point for your searches.

> **Comments:**
> **username_0**: Thank, I will have a look at their work. I can see the relationship between the two problems.  

---

### Answer by username_7 on 2013-03-11. Score: 2

As has been pointed out, this problem is similar to the more commonly known edit distance problem (underlying the [Levenshtein distance](http://en.wikipedia.org/wiki/Levenshtein_distance)). It also has commonalities with, for example, [Dynamic Time Warping distance](http://en.wikipedia.org/wiki/Dynamic_time_warping) (the duplication, or “stuttering,” in your last requirement).

### Steps toward dynamic programming

My first attempt at a recursive decomposition along the lines of Levenshtein distance and Dynamic Time Warping Distance was something like the following (for $x=x\_1\ldots x\_n$ and $y=y\_1\ldots y\_m$), with $d(x,y)$ being set to
$$
\min
\begin{cases}
d(x,y\_1\ldots y\_{m-1})+1 & &\text{▻ Add letter at end}\\
d(x,y\_2\ldots y\_m)+1 & & \text{▻ Add letter at beginning}\\
d(x,y\_1\ldots y\_{m/2})+1 & \text{if $y=y\_1\ldots y\_{m/2}y\_1\ldots y\_{m/2}$}
& \text{▻ Doubling}\\
d(x\_1\ldots x\_{n/2},y)+1 & \text{if $x=x\_1\ldots x\_{n/2}x\_1\ldots x\_{n/2}$}
& \text{▻ Halving}\\
d(x\_1\ldots x\_n,y) + 1 && \text{▻ Deletion}\\
d(x\_1\ldots x\_{n-1},y\_1\ldots y\_{m-1}) & \text{if $y\_n = y\_m$}
& \text{▻ Ignoring last elt.}\\
\end{cases}
$$

Here, the last option basically says that converting FOOX to BARX is equivalent to converting FOO to BAR. This means that you could use the “add letter at end” option to achieve the stuttering (duplication) effect, and the deletion at an point. The problem is that it automatically lets you add an *arbitrary* character in the middle of the string *as well*, something you probably don't want. (This “ignoring identical last elements” is the standard way to achieve deletion and stuttering in arbitrary positions. It does make prohibiting arbitrary insertions, while allowing additions at either end, a bit tricky, though…)

I've included this breakdown even though it doesn't do the job completely, in case someone else can “rescue” it, somehow—and because I use it in my heuristic solution, below.

(Of course, if you could get a breakdown like this that actually defined your distance, you'd only need to add memoization, and you'd have a solution. However, because you're not just working with prefixes, I don't think you could use just indexes for your memoization; you might have to store the actual, modified strings for each call, which would get huge if your strings are of substantial size.)

### Steps toward a heuristic solution

Another approach, which might be easier to understand, and which could use quite a bit less space, is to search for the shortest “edit path” from your first string to your second, using the [$A^\ast$ algorithm](http://en.wikipedia.org/wiki/A%2a_search_algorithm) (basically, best-first branch-and-bound). The search space would be defined directly by your edit operations. Now, for a large string, you *would* get a large neighborhood, as you could delete any character (giving you a neighbor for each potential deletion), or duplicate any character (again, giving you a linear number of neighbors), as well as adding any character at either end, which would give you a number of neighbors equal to twice the alphabet size. (Just hope you're not using full Unicode ;-) With such a large fanout, you might achieve quite a substantial speedup using a [*bidirectional* $A^\*$, or some relative](http://www.avglab.com/andrew/pub/alenex06.pdf).

In order to make $A^\*$ work, you'd need a lower bound for the remaining distance to your target. I'm not sure if there's an obvious choice here, but what you *could* do is implement a dynamic programming solution based on the recursive decomposition I gave above (again with possible space issues if your strings are very long). While that decomposition doesn't exactly compute your distance, it *is* guaranteed to be a lower bound (because it's more permissive), which means it'll work as a heuristic in $A^\*$. (How tight it'll be, I don't know, but it would be correct.) Of course, the memoization of your bound function could be shared across all calculations of the bound during your $A^\*$ run. (A time-/space-tradeoff there.)

### So…

The efficiency of my proposed solution would seem to depent quite a bit on (1) the lengths of your strings, and (2) the size of your alphabet. If neither is huge, it might work. That is:

* Implement the lower bound to your distance using my recursive decomposition and dynamic programming (for example, using a memoized, recursive function).
* Implement $A^\*$ (or bidirectional $A^\*$) with your edit operations as “moves” in the state-space, and the dynamic programming-based lower bound.

I can't really give any guarantees for how efficient it'd be, but it *should* be correct, and it would probably be a lot better than a brute-force solution.

If nothing else, I hope this gives you some ideas for further investigations.


---

### Answer by username_8 on 2013-02-22. Score: 0

Some related, well defined problem would be problem of [sequence alignment](http://en.wikipedia.org/wiki/Sequence_alignment). It is different because it doesn't use operation of duplication.
Defined operations are: insertion of character, deletion of character, transformation of character. Popular algorithm for solving this problem is [Needleman-Wunsch](http://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm).

> **Comments:**
> **username_0**: I know this one but I really want to work with a set of defined moves. The only way that I have found to do it, is with a brute-force recursive algorithm. Not very nice and he could become computationaly intensive if the size of the words increased.  

---

### Answer by username_9 on 2013-02-28. Score: -2

Except for duplication, the Levenstein distance might be worth a look:
<http://en.wikipedia.org/wiki/Levenshtein_distance>


---

