BK-дерево
-
Определение BK-дерева
- BK-дерево — метрическое дерево, предложенное Уолтером Остином Буркхардом и Робертом М. Келлером.
- Адаптировано для дискретных метрических пространств.
- Используется для приблизительного сопоставления строк в словаре.
-
Пример BK-дерева
- Пример BK-дерева для набора слов {«книга», «books», «торт», «boo», «благо», «повар», «торт», «накидка», «тележка»}.
- Каждый узел помечен строкой из набора слов.
- Дуги помечены расстоянием между словами.
-
Вставка в BK-дерево
- Примитив вставки используется для заполнения BK-дерева.
- Ввод: вес дуги, слово, метрика, элемент для вставки.
- Выход: узел, соответствующий элементу.
-
Поиск в BK-дереве
- Примитив поиска обходит BK-дерево для нахождения ближайшего элемента.
- Ограничение изучения к узлам, улучшающим наилучший кандидат.
- Ввод: BK-дерево, метрика, элемент, максимальное расстояние.
- Выход: ближайший элемент или ⊥, если не найден.
-
Пример алгоритма поиска
- Пример для 8-узлового дерева с w = «круто».
- Ввод: корень дерева, метрика, w, максимальное расстояние.
- Вывод: «готовить» как ближайший элемент с d = 1.