1632
правки
Изменения
Бор
,rollbackEdits.php mass rollback
'''Бор''' (англ. ''trie'', ''луч'', ''нагруженное дерево'') — {{---}} структура данных для хранения набора строк, представляющая из себя [[Дерево, эквивалентные определения | подвешенное дерево]] с символами на [[Основные определения теории графов | рёбрах]]. Строки получаются прохождением из корня по последовательной записью всех символов, хранящихся на [[Основные определения теории графов | рёбрамрёбрах]], записывая соответствующие им символы, до между корнем бора и терминальной вершинывершиной. Размер бора линейно
зависит от суммы длин всех строк, а поиск в бору занимает время, пропорциональное длине образца.
==Построение==
'''struct''' vertex:
'''vertex''' next[<tex>| \Sigma |</tex>]
'''bool''' isTerminal
===Алгоритм===
Непосредственно построение:
==Использование бора=====Поиск строки в бору===
{{Задача
|definition =
Требуется найти слово <tex>S</tex> в словаре.
}}
Если в какой-то момент [[Основные определения теории графов | ребра]], отмеченного нужным символом, не находится, то строки <tex>S</tex> в словаре нет.
Ясно, что это занимает <tex>O (|S|)</tex> времени. Таким образом, бор — это эффективный способ хранить словарь и искать в нем слова.
===Использование бора в качестве ассоциативного массива===Благодаря тому, что бор позволяет решать задачу, описанную выше, он может выступать в качестве ассоциативного массива. Обычно, когда требуется такая структура, то используют [[Дерево поиска, наивная реализация | двоичное дерево поиска]] или [[Хеш-таблица | хеш-таблицу]]. ====Достоинства====Мы можем ввести для каждой вершины поле Бор объединяет некоторые преимущества этих структур данных и позволяет одновременно делать следующие операции, которые каждая из структур не может делать по отдельности. {| class="wikitable" style="width:10cm" border=1|+| || '''Бор''' || '''Дерево''' || '''Хеш-таблица'''|-|-align="center" bgcolor=#FFFFFF| ''Добавление элемента'' | align="center" style="background: #ddffdd;" | <tex>\mathtt{value} \O(|S|)</tex>. Например, мы имеем | align="center" style="background: #ffdddd;" |<tex>O(|S|\mathtt{map}log k)</tex>| align="center" style="background: #ddffdd;" | <tex><O(|S|)</tex>|-align="center" bgcolor=#FFFFFF| ''Получение всех ключей в отсортированном порядке'' | align="center" style="background: #ddffdd;" | <tex>\mathtt{string}\ , \mathtt{type}\ O(k)</tex>| align="center" style="background: #ddffdd;" | <tex>>O(k)</tex>. Будем искать ключ, спускаясь по бору. Соответственно, если на какой-то вершине нет пометки, что вершина является концом слова, то объекта в | align="center" style="background: #ffdddd;" | <tex>O(k\mathtt{map}log k)</tex> нет|} ====Недостатки====Несмотря на данные достоинства у реализации ассоциативного массива в виде бора есть следующие недостатки:# Бор хранит строки или символы, а это значит, что у значения ключа будет ограничение на тип (строки, символы, либо числа, представленные как строки). Если хотим добавить егоЧтобы это исправить, то ставим научимся приводить любой тип данных к строке. Тогда сможем хранить любой вид данных в вершину флаг конца слова и заносим значениекачестве ключа.Работать такой алгоритм #Если реализовывать ассоциативный массив на обычном боре, а ключами будут являться строки, то будет за использоваться слишком много памяти (возможен, например, вариант, когда у слов нет пересечений по префиксу, тогда бор будет использовать <tex>O(kn| \Sigma |)</tex>, где <tex>k</tex> {{---}} максимальная длина словапамяти).
==См. также==
* [[Сжатое суффиксное дерево]]
* [[Алгоритм Ахо-Корасик]]
== Источники информации ==
*[http://e-maxx.ru/algo/aho_corasick Бор. Построение бора]
[[Категория: Алгоритмы и структуры данных]]