I want to try and write code for a BK tree using a certain edit distance that accounts for transpositions for a spell corrector. I've looked into Damerau-Levenshtein distance, but the triangle inequality required for a BK tree does not hold. Any suggestions?


Actually, the Damerau–Levenshtein distance is a metric. (See, for example, §11.1 of Encyclopedia of Distances, by Deza & Deza, Springer, 2009.) That is, it does obey the triangle inequality. This can be seen quite easily if you view every possible string as a node, with the edit operations and transpositions between them as edges. The Damerau–Levenshtein distance is then a shortest-path distance between the two strings in question, and such distances (graph geodesics) are always metric (i.e., triangular): You can't take a shortcut (breaking the triangle inequality) without simultaneously discovering a shorter path (a contradiction).

The problem is that actually computing the Damerau–Levenshtein distances is tricky, and you may see algorithms that compute something similar (optimal string alignment, for example), but that don't actually find the minimal number of steps. If Damerau–Levenshtein with adjacent transpositions is OK for your application, you can use that. You'll find algorithms for computing it online (even in Wikipedia), and as long as your code computes the minimum number of steps, the triangle inequality is obeyed. (But note that, as stated, algorithms based on finding the Damerau–Levenshtein distance through optimal alignment will not obey the triangle inequality, but that is because they don't really find the true Damerau–Levenshtein distance.)

If you want the unrestricted Damerau–Levenshtein distance (without necessarily using adjacent transpositions): Fear not, there are ways of computing that as well! You could have a look at the work of Lowrance & Wagner, for example.

If you don't want to get into the details of that, you could simply use a heuristic algorithm such as $A^*$ to compute the distance, with plain Levenshtein distance as the lower-bounding heuristic, for example. Should be efficient enough for reasonably-sized strings, and will give you the corret Damerau–Levenshtein distance. And it will work with your BK-trees.


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.