Transposition of any characters in Damerau–Levenshtein edit distance computation

Question

Is it possible to modify the computation of Damerau–Levenshtein distance to take into account not only the transposition of adjacent characters, but the transposition of any characters?

Maybe some heuristic would help?

update

I will identify the application.

I have two sequences of characters. An "Old" one and a "New" one. I need to compute editorial prescription (is it a correct English term?) as a series of actions that could be applied to an "Old" sequence to make it equal to a "New" one.

There are not more than 10-20 characters in a sequence in most cases, thus O(n) is not so important.

The important part is... characters in that "Old" sequence have some metadata assigned to each other. That's why transposition is more welcome than remove/insert when it's possible.

My goal is to make an "Old" sequence equal to a "New" one preserving that metadata as much as possible.

Answer 1

Thanks for updating the question - here goes an answer tailored to your application:

Since we are dealing with realatively small instances we could define an optimal algorithm based on a backtracking branch and bound schema (Presentation on B&B - easy, Something more thorough with common application) by constructing a "path" of permutations with following assuptions:

• We want to promote swaps to preserve metadata - cost = 1
• We want to penilize other operations but allow them if nessesary - cost = 2
• Dissalow "stupid" moves ex. Inserting a letter that's not in the target sequence
• Innitial Upper Bound = Levensthein (plain version not the Damerau extension) x 2 (because of the costs)

• Lower Bound current path cost + how many letters (disregard positions) do not match in current and target sequences Example:

• i have ABCCDD

• i want CCWGZDD

the cost added to current path is (1 (W) + 1 (G) + 1 (Z) + 2 (D)) = 5 (probably there is room for a better Lower Bound but it's usually non-trivial to come up with one)

• Each time you get to target sequence and path cost is lower than Upper Bound - update it and backtrack.
• Each time your Lower Bound exeeds Upper Bound - backtrack

Please google backtracking algorithms and branch and bound for more information. Should you like the solution but have no idea how to go about implementing it please let me know (PW) I'll try to cook-up some pseudocode for you.

The algorithm in worst case is exponential but on real istances should perform very well.

Answer 2

I agree to user834 comment - this seems like exacly this kind of problem. It is not simplified because after each swap we can perform another and another ... so in each step of the algorithm we have O(n^2) possible swaps.

It would be helpful if you could identify the application of this question - perhaps the question itself is ill-posed.

I would also appreciate if you could elaborate on the cost-metric you would like to use for swaps other than adjectant - would it still be = 1?

If you a sure that this is exactly what you want I could propose a following metaheuristic based on local search (An accessible publication about local search and other metaheurestics):

Define following:

neighbourhood (possible move) | size:

• swap | O(n^2)
• letter change | O(n*alphabethSize)
• delete | O(n)
• insert | O(n*alphabethSize)

Steps:

1. Try each move and evaluate the D-L distance of the new sequence to target sequence.
2. Chose best move.
3. Go back to 1.

Stop if you have the target sequence or there are no more moves that get you closer to it (local minimum).

Possible execution optimisations:

• don't consider letters that are not in target seqence
• candidate moves (see the .pdf)
• you could use the greedy version of local search - choose the first move that betters the distance to target sequence (much faster but more likely to produce worse results). Also remember to evaluate the moves in random order in this version.

Optimality guarantee: none this is a heurestic.

Guys please justify downvoting if you can.