Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Presumably none from the list at en.wikipedia.org/wiki/String_metric apply, nor is it in sourceforge.net/projects/simmetrics ? –  András Salamon Feb 22 '13 at 17:16
    
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 Feb 25 '13 at 9:38
1  
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 Feb 28 '13 at 13:55
2  
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.) –  JɛffE Feb 28 '13 at 17:44
2  
You added the operation "cut a word in two"; do you mean the operation which maps $ww$ to $w$? –  argentpepper Feb 28 '13 at 20:09
show 4 more comments

4 Answers 4

I don't know whether this exact problem has been studied, but Chaudhuri et al. 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.

share|improve this answer
    
Thank, I will have a look at their work. I can see the relationship between the two problems. –  cz3rk Feb 28 '13 at 13:52
add comment

As has been pointed out, this problem is similar to the more commonly known edit distance problem (underlying the Levenshtein distance). It also has commonalities with, for example, Dynamic Time Warping distance (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 (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.

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.

share|improve this answer
add comment

Some related, well defined problem would be problem of 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.

share|improve this answer
    
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 Feb 22 '13 at 16:34
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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