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