БК-дерево

Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Март 2019 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

Пример [ править ]

Пример BK-дерева

На этом рисунке изображено BK-дерево для полученного набора слов {"книга", "книги", "торт", "бу", "благо", "повар", "торт", "накидка", "тележка"}. с помощью расстояния Левенштейна${\ displaystyle W}$

• каждый узел помечен строкой из ;${\ displaystyle u}$${\ displaystyle w_ {u} \ in W}$
• каждая дуга помечена где обозначает слово, которому присвоено .${\ Displaystyle (и, v)}$${\ displaystyle d_ {uv} = d (w_ {u}, w_ {v})}$${\ displaystyle w_ {u}}$${\ displaystyle u}$

BK-дерево построено так, чтобы:

• для всех узлов BK-дерева веса, присвоенные его выходным дугам, различны;${\ displaystyle u}$
• для всех дуги , помеченной , каждый потомок из удовлетворяет следующему уравнению: :${\ Displaystyle е = (и, v)}$${\ displaystyle k}$${\ displaystyle v '}$${\ displaystyle v}$${\ displaystyle d (w_ {u}, w_ {v '}) = k}$
  • Пример 1: Рассмотрим дугу от «книги» к «книгам». Расстояние между словом "book" и любым словом в {"books", "boo", "boon", "cook"} равно 1;
  • Пример 2: Рассмотрим дугу от «книги» до «бу». Расстояние между словом "книги" и любым словом в {"бу", "благо", "повар"} равно 2.

Вставка [ править ]

Примитив вставки используется для заполнения BK-дерева в соответствии с дискретной метрикой .${\ displaystyle t}$${\ displaystyle d}$

Вход:

• ${\ displaystyle t}$: БК-дерево;
  • ${\ displaystyle d_ {uv}}$обозначает вес, присвоенный дуге ;${\ Displaystyle (и, v)}$
  • ${\ displaystyle w_ {u}}$обозначает слово, присвоенное узлу );${\ displaystyle u}$
• ${\ displaystyle d}$: дискретная метрика, используемая (например, расстояние Левенштейна );${\ displaystyle t}$
• ${\ displaystyle w}$: элемент, в который нужно вставить ;${\ displaystyle t}$

Выход:

• Узел, соответствующий${\ displaystyle t}$${\ displaystyle w}$

Алгоритм:

• Если пуст:${\ displaystyle t}$
  • Создайте корневой узел в${\displaystyle r}$${\displaystyle t}$
  • ${\displaystyle w_{r}\leftarrow w}$
  • Возвращаться ${\displaystyle r}$
• Установить в корень${\displaystyle u}$${\displaystyle t}$
• Пока существует:${\displaystyle u}$
  • ${\displaystyle k\leftarrow d(w_{u},w)}$
  • Если :${\displaystyle k=0}$
    • Возвращаться ${\displaystyle u}$
  • Найдите ребенка такого, что${\displaystyle v}$${\displaystyle u}$${\displaystyle d_{uv}=k}$
  • Если не найдено:${\displaystyle v}$
    • Создать узел ${\displaystyle v}$
    • ${\displaystyle w_{v}\leftarrow w}$
    • Создайте дугу ${\displaystyle (u,v)}$
    • ${\displaystyle d_{uv}\leftarrow k}$
    • Возвращаться ${\displaystyle v}$
  • ${\displaystyle u\leftarrow v}$

Поиск [ править ]

Для найденного элемента поисковый примитив просматривает BK-дерево, чтобы найти ближайший элемент . Ключевая идея состоит в том, чтобы ограничить исследование узлами, которые могут улучшить только лучшего кандидата, найденного на данный момент, за счет использования структуры BK-дерева и неравенства треугольника (критерий отсечения).${\displaystyle w}$${\displaystyle w}$${\displaystyle t}$

Вход:

• ${\displaystyle t}$: БК-дерево;
• ${\displaystyle d}$: соответствующая дискретная метрика (например, расстояние Левенштейна );
• ${\displaystyle w}$: искомый элемент;
• ${\displaystyle d_{max}}$: максимально допустимое расстояние между лучшим совпадением и , по умолчанию ;${\displaystyle w}$${\displaystyle +\infty }$

Выход:

• ${\displaystyle w_{best}}$: элемент, ближайший к хранящемуся, согласно или если не найден;${\displaystyle w}$${\displaystyle t}$${\displaystyle d}$${\displaystyle \perp }$

Алгоритм:

• Если пусто:${\displaystyle t}$
  • Возвращаться ${\displaystyle \perp }$
• Создание набора узлов в процессе, и вставить корень в .${\displaystyle S}$${\displaystyle t}$${\displaystyle S}$
• ${\displaystyle (w_{best},d_{best})\leftarrow (\perp ,d_{max})}$
• Пока :${\displaystyle S\neq \emptyset }$
  • Извлечь произвольный узел из${\displaystyle u}$${\displaystyle S}$
  • ${\displaystyle d_{u}\leftarrow d(w,w_{u})}$
  • Если :${\displaystyle d_{u}<d_{best}}$
    • ${\displaystyle (w_{best},d_{best})\leftarrow (w_{u},d_{u})}$
  • Для каждой исходящей дуги :${\displaystyle (u,v)}$
    • Если : (критерий отсечения)${\displaystyle |d_{uv}-d_{u}|<d_{best}}$
      • Вставить в .${\displaystyle v}$${\displaystyle S}$
• Возвращаться ${\displaystyle w_{best}}$

См. Также [ править ]

• Расстояние Левенштейна - метрика расстояния, обычно используемая при построении 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]