Дерево BK: Алгоритм приближенного поиска строк

Введение

Дерево BK — это метрическое дерево, предложенное Уолтером Остином Беркхардом и Робертом М. Келлером, специально адаптированное для дискретных метрических пространств. Для простоты рассмотрим дискретную метрику целых чисел. Тогда дерево BK определяется следующим образом. Произвольный элемент *a* выбирается в качестве корневого узла. Корневой узел может иметь ноль или более поддеревьев. *k*-ое поддерево строится рекурсивно из всех элементов *b*, таких что... Деревья BK могут использоваться для приближенного поиска строк в словаре.

Пример алгоритма поиска

Рассмотрим пример B K Tree с 8 узлами, показанный выше, и установим "cool". Инициализируется для хранения корня дерева, который впоследствии извлекается как первое значение с = "book". Далее, поскольку расстояние от "book" до "cool" равно 2, и поскольку это наилучшее (т.е. наименьшее) расстояние, найденное на данный момент. Затем каждая исходящая дуга от корня рассматривается по очереди: дуга от "book" к "books" имеет вес 1, и поскольку меньше , узел, содержащий "books", вставляется для дальнейшей обработки. Следующая дуга, от "book" к "cake", имеет вес 4, и поскольку не меньше , узел, содержащий "cake", не вставляется в . Следовательно, поддерево, укорененное в "cake", будет отсечено от поиска, поскольку ближайшее к "cool" слово не может находиться в этом поддереве. Чтобы понять, почему это отсечение корректно, заметим, что кандидатское слово, находящееся в поддереве "cake" на расстоянии менее 2 от "cool", нарушило бы неравенство треугольника: неравенство треугольника требует, чтобы для этого набора из трех чисел (как сторон треугольника) сумма любых двух не была меньше третьего, но здесь расстояние от "cool" до "book" (равное 2) плюс расстояние от "cool" до (которое меньше 2) не может достичь или превысить расстояние от "book" до "cake" (равное 4). Поэтому безопасно игнорировать все поддерево, укорененное в "cake". Далее узел, содержащий "books", извлекается из , и теперь – расстояние от "cool" до "books". Поскольку , остается равным 2, и рассматривается единственная исходящая дуга от узла, содержащего "books". Далее узел, содержащий "boo", извлекается из , и – расстояние от "cool" до "boo". Это снова не улучшает . Каждая исходящая дуга от "boo" теперь рассматривается; дуга от "boo" к "boon" имеет вес 1, и поскольку , "boon" добавляется в . Аналогично, поскольку , "cook" также добавляется в . Наконец, каждый из двух последних элементов в рассматривается в произвольном порядке: предположим, что узел, содержащий "cook", извлекается первым, улучшая до расстояния 1, затем узел, содержащий "boon", извлекается последним, который находится на расстоянии 2 от "cool" и, следовательно, не улучшает наилучший результат. Наконец, "cook" возвращается в качестве ответа с .

Consider the example 8 node B K Tree shown above and set "cool". is initialized to contain the root of the tree, which is subsequently popped as the first value of with ="book". Further since the distance from "book" to "cool" is 2, and 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 is less than , the node containing "books" is inserted into for further processing. The next arc, from "book" to "cake," has weight 4, and since is not less than , the node containing "cake" is not inserted into 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 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 (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 and now , the distance from "cool" to "books." As , remains set at 2 and the single outgoing arc from the node containing "books" is considered. Next, the node containing "boo" is popped from and , the distance from "cool" to "boo." This again does not improve upon Each outgoing arc from "boo" is now considered; the arc from "boo" to "boon" has weight 1, and since , "boon" is added to Similarly, since , "cook" is also added to
Finally each of the two last elements in are considered in arbitrary order: suppose the node containing "cook" is popped first, improving 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 with .