# Spell Checker with BK tree and edit distance that accounts for transpositions

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?

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.