BK-tree

A BK-tree is a metric tree suggested by Walter Austin Burkhard and Robert M. Keller specifically adapted to discrete metric spaces. For simplicity, consider integer discrete metric ${\displaystyle d(x,y)}$. Then, BK-tree is defined in the following way. An arbitrary element a is selected as root node. The root node may have zero or more subtrees. The k-th subtree is recursively built of all elements b such that ${\displaystyle d(a,b)=k}$. BK-trees can be used for approximate string matching in a dictionary.

See also

• Levenshtein distance – the distance metric commonly used when building a BK-tree
• Damerau–Levenshtein distance – a modified form of Levenshtein distance that allows transpositions

References

• ^ W. Burkhard and R. Keller. Some approaches to best-match file searching, CACM, 1973
• ^ R. Baeza-Yates, W. Cunto, U. Manber, and S. Wu. Proximity matching using fixed queries trees. In M. Crochemore and D. Gusfield, editors, 5th Combinatorial Pattern Matching, LNCS 807, pages 198–212, Asilomar, CA, June 1994.
• ^ Ricardo Baeza-Yates and Gonzalo Navarro. Fast Approximate String Matching in a Dictionary. Proc. SPIRE'98

External links

• A BK-tree implementation in Common Lisp with test results and performance graphs.
• An explanation of BK-Trees and their relationship to metric spaces
• An explanation of BK-Trees with an implementation in C#
• A BK-tree implementation in Lua
• A BK-tree implementation in Python