БК-дерево

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

Пример

Пример БК-дерева

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

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

БК-дерево строится так, что:

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

Вставка

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

Вход:

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

Выход:

• Узел $t$ соответствующий $w$

Алгоритм:

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

Поиск

Учитывая искомый элемент $w$, примитив поиска обходит BK-дерево, чтобы найти ближайший элемент $w$. Основная идея – ограничить исследование $t$ к узлам, которые могут улучшить только лучшего кандидата, найденного на данный момент, используя преимущества организации BK-дерева и неравенства треугольника (критерий отсечения).

Вход:

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

Выход:

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

Алгоритм:

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

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

Рассмотрим пример 8-узлового дерева BK, показанный выше, и установите $w=$"прохладный". $S$ инициализируется как содержащий корень дерева, который впоследствии извлекается как первое значение $u$ с $w_{u}$= «книга». Дальше $d_{u}=2$ так как расстояние от «книги» до «круто» равно 2, а $d_{best}=2$поскольку это лучшее (то есть наименьшее) расстояние, найденное на данный момент. Далее поочередно рассматривается каждая исходящая от корня дуга: дуга от «книги» к «книгам» имеет вес 1, и так как $|1-2|=1$ меньше чем $d_{best}=2$, узел, содержащий «книги», вставляется в $S$для дальнейшей обработки. Следующая дуга, от «книги» до «торта», имеет вес 4, и поскольку $|4-2|=2$ не меньше, чем $d_{best}=2$, узел, содержащий "торт", не вставляется в $S$. Таким образом, поддерево с корнем «торт» будет исключено из поиска, поскольку слово, наиболее близкое к «крутому», не может появиться в этом поддереве. Чтобы понять, почему такая обрезка правильна, обратите внимание, что слово-кандидат $c$ появление в поддереве «торта» с расстоянием менее 2 до «крутого» нарушит неравенство треугольника: неравенство треугольника требует, чтобы для этого набора из трех чисел (как сторон треугольника) никакие два не могли в сумме давать меньше третьего , но здесь расстояние от "крутого" до "книжного" (а это 2) плюс расстояние от "крутого" до "книжного" $c$(которое меньше 2) не может достичь или превысить расстояние от «книги» до «торта» (которое равно 4). Поэтому можно смело игнорировать все поддерево, основанное на «торте».

Затем извлекается узел, содержащий «книги». $S$ и сейчас $d_{u}=3$, расстояние от «крутого» до «книги». Как $d_{u}>d_{best}$, $d_{best}$остается установленным на 2, и рассматривается единственная исходящая дуга из узла, содержащего «книги». Затем узел, содержащий «boo», извлекается из $S$ и $d_{u}=2$, расстояние от «круто» до «бу». Это опять же не улучшает $d_{best}=2$. Теперь учитывается каждая исходящая дуга от «бу»; дуга от «бу» до «благо» имеет вес 1, и поскольку $|2-1|=1<d_{best}=2$, к слову добавляется «благо» $S$. Аналогично, поскольку $|2-2|=0<d_{best}$, к слову "повар" также добавляется $S$.

Наконец, каждый из двух последних элементов в $S$ рассматриваются в произвольном порядке: предположим, что узел, содержащий слово «cook», извлекается первым, что улучшает $d_{best}$на расстояние 1, то последним извлекается узел, содержащий «благо», который находится на расстоянии 2 от «крутого» и, следовательно, не улучшает лучший результат. Наконец, в качестве ответа возвращается «повар». $w_{best}$ с $d_{best}=1$.

См. также

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

Ссылки

• ^ В. Буркхард и Р. Келлер. Некоторые подходы к поиску файлов наилучшего соответствия, CACM, 1973 г.
• ^ Р. Баеза-Йейтс, В. Кунто, У. Манбер и С. Ву. Сопоставление по близости с использованием фиксированных деревьев запросов. В М. Крочеморе и Д. Гасфилде, редакторах, 5-е комбинаторное сопоставление с образцом, LNCS 807, страницы 198–212, Асиломар, Калифорния, июнь 1994 г.
• ^ Рикардо Баэса-Йейтс и Гонсало Наварро. Быстрое приближенное сопоставление строк в словаре. Учеб. ШПИЛЬ'98

Внешние ссылки

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