Bk tree
Encyclopedia
A BK-tree is a metric tree suggested by Walter Austin Burkhard and Robert M. Keller specifically adapted to discrete metric space
s.
For simplicity, let us consider integer discrete metric
. 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
. BK-trees can be used for approximate string matching in a dictionary .
Metric space
In mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...
s.
For simplicity, let us consider integer discrete metric
. 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. BK-trees can be used for approximate string matching in a dictionary .External links
- A BK-tree implementation in Common Lisp with test results and performance graphs.
- BK-tree implementation written in Python and its port to Haskell.
- A good explanation of BK-Trees and their relationship to metric spaces http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees