<p>Actually, the Damerau–Levenshtein distance <em>is</em> a metric. (See, for example, §11.1 of <em>Encyclopedia of Distances</em>, by Deza &amp; Deza, Springer, 2009.) That is, it <em>does</em> 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).</p>

<p>The problem is that actually <em>computing</em> the Damerau–Levenshtein distances is tricky, and you may see algorithms that compute something <em>similar</em> (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 <a href="http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance" rel="nofollow">Wikipedia</a>), 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 <em>not</em> obey the triangle inequality, but that is because they don't really find the true Damerau–Levenshtein distance.)</p>

<p>If you want the <em>unrestricted</em> 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 <a href="http://www.lemoda.net/text-fuzzy/lowrance-wagner/lowrance-wagner.pdf" rel="nofollow">Lowrance &amp; Wagner</a>, for example.</p>

<p>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.</p>

CC BY-SA 3.0
2013-08-04T06:53:12.357Z
2013-08-04T06:53:12.357Z
Magnus Lie Hetland
<p>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?</p>

<ds.algorithms><tree><edit-distance>
Spell Checker with BK tree and edit distance that accounts for transpositions
Anonymous
# Spell Checker with BK tree and edit distance that accounts for transpositions

(Asked by: username_0 on 2013-08-02)

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?

**Tags:** ds.algorithms, tree, edit-distance


---

## 1 answers

### Answer by username_1 on 2013-08-04. Score: 3 | Accepted answer

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](http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance)), 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](http://www.lemoda.net/text-fuzzy/lowrance-wagner/lowrance-wagner.pdf), 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.


---

