Изменения

'''Бор''' (англ. ''trie'', ''луч'', ''нагруженное дерево'') — {{---}} структура данных для хранения набора строк, представляющая из себя [[Дерево, эквивалентные определения | подвешенное дерево ]] с символами на ребрах[[Основные определения теории графов | рёбрах]]. Строки получаются прохождением из корня по рёбрампоследовательной записью всех символов, записывая соответствующие им символы, до хранящихся на [[Основные определения теории графов | рёбрах]] между корнем бора и терминальной вершинывершиной. Размер бора линейно

Бор для набора образцов <tex> \{ \textbf{he}, \textbf{she}, \textbf{his}, \textbf{hers}\} </tex>:<br />[[Файл:Aho-corasick1Бор.jpg‎]]

Пусть ===Обозначения===Введем следующие обозначения:*<tex>\Sigma</tex> {{---}} используемый алфавит;*<tex>P = \{P_1,...\ldots,P_k\} </tex> — {{---}} набор строкнад <tex>\Sigma</tex>, называемый словаремсловарём;*<tex>n = \sum_{i=1}^{k}\limits |P_i|</tex> {{---}} сумма длин строк.

Пусть <tex>n = \sum_{i=1}^k|P_i|</tex>Бор храним как набор вершин, у каждой из которых есть метка, обозначающая, является ли вершина терминальной и указатели (рёбра) на другие вершины или на ''NULL''.

Начинаем с дерева из одной вершины (корня); добавляем шаблоны <tex>P_i</tex> один за другим '''struct''' vertex:Следуем из корня по ребрам, отмеченным буквами из '''vertex''' next[<tex>P_i| \Sigma |</tex>, пока возможно.] '''bool''' isTerminal

===Алгоритм===Непосредственно построение:*Начало.*'''Шаг 1.''' Создадим [[Дерево, эквивалентные определения | дерево]] из одной вершины (в нашем случае корня).*'''Шаг 2.''' Добавление элементов в дерево.**Добавляем шаблоны <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>P_i</tex>.*Конец.Построение занимает, очевидно, <tex>O(|P_1| + \ldots + |P_k|) = O(n)</tex> времени, так как поиск буквы, по которой нужно переходить, происходит за <tex>O(1)</tex>.

Если ребра, отмеченного очередной буквой Поскольку на каждую вершину приходится <tex>P_iO(| \Sigma |)</tex> нетпамяти, то создаем новые ребра и вершины для всех оставшихся символов использование памяти есть <tex>P_iO(n| \Sigma |)</tex>.

Это занимает, очевидно, <tex>O (===Суффиксный бор==={{main|P_1Суффиксный бор}}Бор позволяет решать задачу [[Наивный алгоритм поиска подстроки в строке | + ... + |P_k|) = O (n)</tex> временипоиска подстроки в строке]], если построить его на множестве суффиксов исходной строки.

===Цифровой бор==={{main|Сверхбыстрый цифровой бор}} ==Использование бора=====Поиск строки в бору==={{Задача|definition =Поиск строки Требуется найти слово <tex>S</tex> в бору: начинаем в корнесловаре.}}При решении этой задачи, идем обход бора совершается из его корня по ребрам[[Основные определения теории графов | рёбрам]], отмеченным символами строки <tex>S</tex>, пока возможно.Если с последним символом <tex>S</tex> мы приходим в терминальную вершину с сохраненным идентификатором, то <tex>S</tex> — слово из словаря.Если в какой-то момент [[Основные определения теории графов | ребра]], отмеченного нужным символом, не находится, то строки <tex>S </tex> в словаре нет.

==Сжатый бор=Использование бора в качестве ассоциативного массива===Сжатый Благодаря тому, что бор — позволяет решать задачу, описанную выше, он может выступать в качестве ассоциативного массива. Обычно, когда требуется такая структура , то используют [[Дерево поиска, наивная реализация | двоичное дерево поиска]] или [[Хеш-таблица | хеш-таблицу]]. ====Достоинства====Бор объединяет некоторые преимущества этих структур данных для хранения набора строки позволяет одновременно делать следующие операции, отличающаяся от которые каждая из структур не может делать по отдельности. {| class="wikitable" style="width:10cm" border=1|+| || '''Бор''' || '''Дерево''' || '''Хеш-таблица'''|-|-align="center" bgcolor=#FFFFFF| ''Добавление элемента'' | align="center" style="background: #ddffdd;" | <tex>O(|S|)</tex>| align="center" style="background: #ffdddd;" |<tex>O(|S|\log k)</tex> | align="center" style="background: #ddffdd;" | <tex>O(|S|)</tex>|-align="center" bgcolor=#FFFFFF| ''Получение всех ключей в отсортированном порядке'' | align="center" style="background: #ddffdd;" | <tex>O(k)</tex>| align="center" style="background: #ddffdd;" | <tex>O(k)</tex> | align="center" style="background: #ffdddd;" | <tex>O(k\log k)</tex>|} ====Недостатки====Несмотря на данные достоинства у реализации ассоциативного массива в виде бораесть следующие недостатки:следующим улучшением: если # Бор хранит строки или символы, а это значит, что у некоторой вершины исходящая степень равна 1значения ключа будет ограничение на тип (строки, символы, либо числа, представленные как строки). Чтобы это исправить, научимся приводить любой тип данных к строке. Тогда сможем хранить любой вид данных в качестве ключа.#Если реализовывать ассоциативный массив на обычном боре, а ключами будут являться строки, то этубудет использоваться слишком много памяти (возможен, например, вариант, когда у слов нет пересечений по префиксу, тогда бор будет использовать <tex>O(n| \Sigma |)</tex> памяти). ==См. также==* [[Суффиксный массив]]* [[Суффиксный бор]]* [[Сжатое суффиксное дерево]]* [[Алгоритм Ахо-Корасик]] == Источники информации ==вершину* Томас Х. Кормен, реброЧарльз И. Лейзерсон, входящее в нееРональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и реброанализ — 2-е изд. — М.: «Вильямс», исходящее из нее, можно объединить 2007. — ISBN 5-8489-0857-4*[http://e-maxx.ru/algo/aho_corasick Бор. Построение бора]   [[Категория: Алгоритмы и структуры данных]] [[Категория: Поиск подстроки в одностроке]][[Категория: Точный поиск]]ребро с более чем одним символом.[[Категория: Структуры данных]]