5
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ @Kaveh, my point with "string-matching" tag was that a few questions about Levenshtein distance have this tag. But it's up to you. $\endgroup$ – Roman Yankovsky Jun 19 '12 at 22:14
  • $\begingroup$ IMHO that doesn't make the string-matching tag appropriate for this question but you can add it back if you want. $\endgroup$ – Kaveh Jun 21 '12 at 21:33
  • $\begingroup$ This is suspiciously like finding the minimum number of permutations to get from one element to another which, if I'm not mistaken, is NP-Hard. Maybe allowing all $\binom{n}{2}$ swaps simplifies it, I'm not sure. $\endgroup$ – user834 Jun 21 '12 at 22:06
  • $\begingroup$ I think this variant does not fulfill Bellman's optimality criterion anymore, so dynamic programming won't work. It smells similar to secondary structure prediction with pseudoknots, which is known to be NP-hard (as opposed to cubic time by DP without pseudoknots). $\endgroup$ – Raphael Jun 22 '12 at 8:39
  • $\begingroup$ If you ignore everything but the swapping, I think this is related to decomposing permutations. Because what you want to do is implement a permutation via swaps. First, decompose the permutation into cycles (fast and easy), and then get the necessary swaps from each cycle. Won't help with the other edit operations, though – and mixing the two ain't trivial, I think. $\endgroup$ – Magnus Lie Hetland Jun 22 '12 at 10:05
1
+50
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Not exactly what I need, but it is something to think about. Thank you! $\endgroup$ – Roman Yankovsky Jun 27 '12 at 11:34
-1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for this answer. It's not my downvote. I have updated my question, hope this will help. $\endgroup$ – Roman Yankovsky Jun 22 '12 at 11:12

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.