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!



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.