105
правок
Изменения
Бор
,ё
'''Бор''' (англ. ''trie'', ''луч'', ''нагруженное дерево'') {{---}} структура данных для хранения набора строк, представляющая из себя [[Дерево, эквивалентные определения | подвешенное дерево]] с символами на [[Основные определения теории графов | рёбрах]]. Строки получаются последовательной записью всех символов, хранящихся на [[Основные определения теории графов | рёберрёбрах]] между корнем бора и терминальной вершиной. Размер бора линейно
зависит от суммы длин всех строк, а поиск в бору занимает время, пропорциональное длине образца.
===Обозначения===
Введем следующие обозначения:
*<tex>\Sigma</tex> {{---}} используемый алфавит;*<tex>P = \{P_1,\ldots,P_k\} </tex> {{---}} набор строкнад <tex>\Sigma</tex>, называемый словаремсловарём;
*<tex>n = \sum_{i=1}^{k}\limits |P_i|</tex> {{---}} сумма длин строк.
Бор храним как список смежностинабор вершин, в котором храним список рёберу каждой из которых есть метка, которые соответствуют каждому символуобозначающая, а так же храним терминальные является ли вершина терминальной и указатели (рёбра) на другие вершиныили на ''NULL''. '''struct''' vertex: '''vertex''' next[<tex>| \Sigma |</tex>] '''bool''' isTerminal
===Алгоритм===
**Добавляем шаблоны <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(1| \Sigma |)</tex> памяти, то использование памяти есть <tex>O(n| \Sigma |)</tex>.
===Другие модификацииСуффиксный бор===
{{main|Суффиксный бор}}
Бор позволяет решать задачу [[Наивный алгоритм поиска подстроки в строке | поиска подстроки в строке]], если построить его на множестве суффиксов исходной строки.
===Цифровой бор===
{{main|Сверхбыстрый цифровой бор}}
==Использование бора==
{{Задача
|definition =
Требуется найти слово <tex>S</tex> в словаре.
}}
При решении этой задачи, обход бора совершается из его корня по [[Основные определения теории графов | рёбрам]], отмеченным символами строки <tex>S</tex>, пока возможно.Если с последним символом <tex>S</tex> мы приходим в терминальную вершину с сохраненным идентификатором, то <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>O(k|S|)</tex> (дерево выполняет данную операцию за | align="center" style="background: #ffdddd;" |<tex>O(k|S|\log mk)</tex>).| align="center" style="background: #Получение всех ключей в отсортированном порядке за ddffdd;" | <tex>O(m|S|)</tex> (хеш|-таблица выполняет данную операцию за align="center" bgcolor=#FFFFFF| ''Получение всех ключей в отсортированном порядке'' | align="center" style="background: #ddffdd;" | <tex>O(m\log mk)</tex>).Обозначения| align="center" style="background:*#ddffdd;" | <tex>O(k)</tex> {{---}} длина строки*| align="center" style="background: #ffdddd;" | <tex>mO(k\log k)</tex> {{---}|} число ключей
====Недостатки====
Несмотря на данные достоинства у реализации ассоциативного массива в виде бора есть следующий недостатокследующие недостатки:# Бор хранит строки или символы, а это значит, что у значения ключа будет ограничение на тип (строки, символы, либо числа, представленные как строки). Чтобы это исправить, будем использовать научимся приводить любой тип данныхк строке. Тогда сможем хранить любой вид данных в качестве ключа.#Если реализовывать ассоциативный массив на обычном боре, а ключами будут являться строки, то будет использоваться слишком много памяти (возможен, например, вариант, когда у которого прописаны операторы сравненияслов нет пересечений по префиксу, тогда бор будет использовать <tex>O(n| \Sigma |)</tex> памяти).
==См. также==
