BK-tree
≈ 8 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
A BK-tree (short for Burkhard-Keller tree) is a metric tree suggested by Walter Austin Burkhard and Robert M. Keller specifically adapted to discrete metric spaces. For simplicity, given a way to measure the distance between any two elements of a set, a BK-tree is built with a single root node and several subtrees, each connected to the root as a child. All nodes in a subtree have an equal distance to the root node, and the edge weight of the edge connecting the subtree to the root is equal to the distance. As shown in the picture. Also, each subtree of a BK-tree is a BK-tree. BK-trees can be used for approximate string matching in a dictionary . The problem is formulated as follows: Given a pattern string P = p_1p_2...p_m and a text string T = t_1t_2\dots t_n , we need to find a substring T_{j',j} = t_{j'}\dots t_j in T , which, of all substrings of T , has the smallest edit distance to the pattern P . An ordinary way using BK-tree is to insert all \Theta(n^2) substrings of T and the pattern string P into the BK-tree, and find the subtree containing nodes with the smallest distance from the root. This will lead to a time complexity of \Theta(n^2 \log n) . However, this algorithm is very accurate and can find every substrings with the smallest edit distance to P .
A BK-tree (short for Burkhard-Keller tree) is a metric tree suggested by Walter Austin Burkhard and Robert M. Keller specifically adapted to discrete metric spaces. For simplicity, given a way to measure the distance between any two elements of a set, a BK-tree is built with a single root node and several subtrees, each connected to the root as a child. All nodes in a subtree have an equal distance to the root node, and the edge weight of the edge connecting the subtree to the root is equal to the distance. As shown in the picture. Also, each subtree of a BK-tree is a BK-tree. BK-trees can be used for approximate string matching in a dictionary . The problem is formulated as follows: Given a pattern string P = p_1p_2...p_m and a text string T = t_1t_2\dots t_n , we need to find a substring T_{j',j} = t_{j'}\dots t_j in T , which, of all substrings of T , has the smallest edit distance to the pattern P . An ordinary way using BK-tree is to insert all \Theta(n^2) substrings of T and the pattern string P into the BK-tree, and find the subtree containing nodes with the smallest distance from the root. This will lead to a time complexity of \Theta(n^2 \log n) . However, this algorithm is very accurate and can find every substrings with the smallest edit distance to P .
Example
This picture depicts the BK-tree for the set W of words {"book", "books", "cake", "boo", "boon", "cook", "cape", "cart"} obtained by using the Levenshtein distance each node u is labeled by a string of w_u \in W ; each arc (u,v) is labeled by d_{uv} = d(w_u,w_v) where w_u denotes the word assigned to u . The BK-tree is built so that: for all node u of the BK-tree, the weight assigned to its egress arcs are distinct; for all arc e=(u,v) labeled by k , each descendant v' of v satisfies the following equation: d(w_u, w_{v'}) = k : Example 1: Consider the arc from "book" to "books". The distance between "book" and any word in {"books", "boo", "boon", "cook"} is equal to 1; Example 2: Consider the arc from "books" to "boo". The distance between "books" and any word in {"boo", "boon", "cook"} is equal to 2. If k = 0 : Return u Find v the child of u such that d_{uv} = k If v is not found: Create the node v w_v \leftarrow w Create the arc (u, v) d_{uv} \leftarrow k Return v u \leftarrow v Consider the example 8-node B-K Tree shown above and set w= "cool". S is initialized to contain the root of the tree, which is subsequently popped as the first value of u with w_u ="book". Further d_u=2 since the distance from "book" to "cool" is 2, and d_{best}=2 as this is the best (i.e. smallest) distance found thus far. Next each outgoing arc from the root is considered in turn: the arc from "book" to "books" has weight 1, and since |1-2|=1 is less than d_{best}=2 , the node containing "books" is inserted into S for further processing. The next arc, from "book" to "cake," has weight 4, and since |4-2|=2 is not less than d_{best}=2 , the node containing "cake" is not inserted into S . Therefore, the subtree rooted at "cake" will be pruned from the search, as the word closest to "cool" cannot appear in that subtree. To see why this pruning is correct, notice that a candidate word c appearing in "cake"s subtree having distance less than 2 to "cool" would violate the triangle inequality: the triangle inequality requires that for this set of three numbers (as sides of a triangle), no two can sum to less than the third, but here the distance from "cool" to "book" (which is 2) plus the distance from "cool" to c (which is less than 2) cannot reach or exceed the distance from "book" to "cake" (which is 4). Therefore, it is safe to disregard the entire subtree rooted at "cake". Next the node containing "books" is popped from S and now d_u=3 , the distance from "cool" to "books." As d_u > d_{best} , d_{best} remains set at 2 and the single outgoing arc from the node containing "books" is considered. Next, the node containing "boo" is popped from S and d_u=2 , the distance from "cool" to "boo." This again does not improve upon d_{best} = 2 . Each outgoing arc from "boo" is now considered; the arc from "boo" to "boon" has weight 1, and since |2-1|=1 , "boon" is added to S . Similarly, since |2-2|=0 , "cook" is also added to S . Finally each of the two last elements in S are considered in arbitrary order: suppose the node containing "cook" is popped first, improving d_{best} to distance 1, then the node containing "boon" is popped last, which has distance 2 from "cool" and therefore does not improve the best result. Finally, "cook" is returned as the answer w_{best} with d_{best}=1 .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1376355969 under CC BY-SA 4.0; modifications have been made.