2
$\begingroup$

Wondering if it's possible to calculate Damerau–Levenshtein distance with transposition of non-adjacent characters (DL distance allows transposition of immediately adjacent characters only). I want this for an application where I am examining differences between sentences, and when whole words or substrings are transposed more than one character, they are doubly penalized (subtracted then added).

In my searching, I found this question, which recommended using backtracking branch and bound schema that I'm too dumb to implement well. However, I came up with a simple heuristic: calculate Levenshtein distance, keep track of lists of additions and subtractions separately, and remove instances of letters that appear in both lists (on the logic that any subtract-add pair could be better implemented as transposition).

Is this heuristic a) mathematically similar to what I am looking for above or b) close enough that the distances would be heavily correlated for a sample of similar sentences? Can provide test examples if needed. Thanks!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.