Бор — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Построение)
Строка 12: Строка 12:
  
 
Непосредственно построение:
 
Непосредственно построение:
#Начинаем с дерева из одной вершины (корня).
+
#Начинаем с [[Дерево, эквивалентные определения | дерева]] из одной вершины (корня).
 
#Добавляем шаблоны <tex>P_i</tex> один за другим.
 
#Добавляем шаблоны <tex>P_i</tex> один за другим.
#Следуем из корня по ребрам, отмеченным буквами из <tex>P_i</tex>, пока возможно.
+
#Следуем из корня по [[Основные определения теории графов | ребрам]], отмеченным буквами из <tex>P_i</tex>, пока возможно.
 
#Если <tex>P_i</tex> заканчивается в <tex>v</tex>, сохраняем идентификатор <tex>P_i</tex> (например, <tex>i</tex>) в <tex>v</tex> и отмечаем вершину <tex>v</tex> как терминальную.
 
#Если <tex>P_i</tex> заканчивается в <tex>v</tex>, сохраняем идентификатор <tex>P_i</tex> (например, <tex>i</tex>) в <tex>v</tex> и отмечаем вершину <tex>v</tex> как терминальную.
#Если ребра, отмеченного очередной буквой <tex>P_i</tex> нет, то создаем новые ребра и вершины для всех оставшихся символов <tex>P_i</tex>.
+
#Если [[Основные определения теории графов | ребра]], отмеченного очередной буквой <tex>P_i</tex> нет, то создаем новые ребра и вершины для всех оставшихся символов <tex>P_i</tex>.
  
 
Это занимает, очевидно, <tex>O (|P_1| + ... + |P_k|) = O (n)</tex> времени.
 
Это занимает, очевидно, <tex>O (|P_1| + ... + |P_k|) = O (n)</tex> времени.

Версия 20:28, 26 марта 2016

Бор (trie, луч, нагруженное дерево) — структура данных для хранения набора строк, представляющая из себя подвешенное дерево с символами на рёбрах. Строки получаются прохождением из корня по рёбрам, записывая соответствующие им символы, до терминальной вершины. Размер бора линейно зависит от суммы длин всех строк, а поиск в бору занимает время, пропорциональное длине образца.

Пример

Бор для набора образцов {he, she, his, hers}:
Бор.jpg

Построение

Пусть [math]P = \{P_1,...,P_k\} [/math] — набор строк, называемый словарем.

Пусть [math]n = \sum_{i=1}^k|P_i|[/math].

Непосредственно построение:

  1. Начинаем с дерева из одной вершины (корня).
  2. Добавляем шаблоны [math]P_i[/math] один за другим.
  3. Следуем из корня по ребрам, отмеченным буквами из [math]P_i[/math], пока возможно.
  4. Если [math]P_i[/math] заканчивается в [math]v[/math], сохраняем идентификатор [math]P_i[/math] (например, [math]i[/math]) в [math]v[/math] и отмечаем вершину [math]v[/math] как терминальную.
  5. Если ребра, отмеченного очередной буквой [math]P_i[/math] нет, то создаем новые ребра и вершины для всех оставшихся символов [math]P_i[/math].

Это занимает, очевидно, [math]O (|P_1| + ... + |P_k|) = O (n)[/math] времени.

Поиск строки в бору

Поиск строки [math]S[/math] в бору: начинаем в корне, идем по ребрам, отмеченным символами [math]S[/math], пока возможно. Если с последним символом [math]S[/math] мы приходим в вершину с сохраненным идентификатором, то [math]S[/math] — слово из словаря. Если в какой-то момент ребра, отмеченного нужным символом, не находится, то строки [math]S[/math] в словаре нет. Ясно, что это занимает [math]O (|S|)[/math] времени. Таким образом, бор — это эффективный способ хранить словарь и искать в нем слова.

Сжатый бор

Сжатый бор — структура данных для хранения набора строк, отличающаяся от бора следующим улучшением: если у некоторой вершины исходящая степень равна 1, то эту вершину, ребро, входящее в нее, и ребро, исходящее из нее, можно объединить в одно ребро с более чем одним символом.

См. также

Источники информации

  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — ISBN 5-8489-0857-4
  • Алгоритм Ахо-Корасик