БК-дерево - BK-tree

А БК-дерево это метрическое дерево предложен Уолтером Остином Буркхардом и Роберт М. Келлер^[1] специально адаптирован для дискретных метрические пространства.Для простоты рассмотрим целое число дискретная метрика ${\displaystyle d(x,y)}$. Тогда BK-дерево определяется следующим образом. Произвольный элемент а выбран как корневой узел. Корневой узел может иметь ноль или более поддеревьев. В k-й поддерево рекурсивно строится из всех элементов б такой, что ${\displaystyle d(a,b)=k}$. BK-деревья можно использовать для приблизительное соответствие строк в словаре.^{[2][пример необходим ]}

Смотрите также

• Расстояние Левенштейна - метрика расстояния, обычно используемая при построении BK-дерева
• Расстояние Дамерау – Левенштейна - модифицированная форма расстояния Левенштейна, допускающая транспозиции

Рекомендации

• ^ В. Буркхард и Р. Келлер. Некоторые подходы к поиску наиболее подходящего файла, CACM, 1973
• ^ Р. Баеза-Йейтс, В. Кунто, У. Манбер и С. Ву. Близкое сопоставление с использованием фиксированных деревьев запросов. В M. Crochemore и D. Gusfield, редакторах, 5th Combinatorial Pattern Matching, LNCS 807, pages 198–212, Asilomar, CA, июнь 1994.
• ^ Рикардо Баеза-Йейтс и Гонсало Наварро. Быстрое приближенное сопоставление строк в словаре. Proc. SPIRE'98

внешняя ссылка

• Реализация BK-дерева в Common Lisp с результатами тестов и графиками производительности.
• Объяснение BK-деревьев и их отношения к метрическим пространствам [3]
• Объяснение BK-Trees с реализацией на C #[4]
• Реализация BK-дерева в Lua [5]
• Реализация BK-дерева в Python [6]