Изменения

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

Бор для набора образцов <tex> \{ \textbf{'''he'''}, '''\textbf{she'''}, '''\textbf{his'''}, '''\textbf{hers'''}\} </tex>:<br />

Пусть ===Обозначения===Введем следующие обозначения:*<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''.

#Начинаем с *Начало.*'''Шаг 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>O(| \Sigma |)</tex> памяти, то использование памяти есть <tex>O(n| \Sigma |)</tex>. ===Суффиксный бор==={{main|Суффиксный бор}}Бор позволяет решать задачу [[Наивный алгоритм поиска подстроки в строке | поиска подстроки в строке]], если построить его на множестве суффиксов исходной строки.

Это занимает, очевидно, <tex>O (===Цифровой бор==={{main|P_1| + ... + |P_k|) = O (n)</tex> времени.Сверхбыстрый цифровой бор}}

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

==Сжатый бор=Использование бора в качестве ассоциативного массива===Сжатый Благодаря тому, что бор — позволяет решать задачу, описанную выше, он может выступать в качестве ассоциативного массива. Обычно, когда требуется такая структура данных для хранения набора строк, отличающаяся от бораследующим улучшением: если у некоторой вершины исходящая степень равна 1, то этувершину, используют [[Основные определения теории графов Дерево поиска, наивная реализация | ребродвоичное дерево поиска]], входящее в нее, и или [[Основные определения теории графов Хеш-таблица | реброхеш-таблицу]]. ====Достоинства====Бор объединяет некоторые преимущества этих структур данных и позволяет одновременно делать следующие операции, исходящее которые каждая из нее, можно объединить в одно[[Основные определения теории графов | ребро]] с более чем одним символомструктур не может делать по отдельности.

{| 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>| сжатым суффиксным деревом]].}

==Использование бора в качестве ''map''==Недостатки====Несмотря на данные достоинства у реализации ассоциативного массива в виде бора есть следующие недостатки:Мы можем ввести для каждой вершины поле <tex>value</tex># Бор хранит строки или символы, а это значит, что у значения ключа будет ограничение на тип (строки, символы, либо числа, представленные как строки). Например, мы имеем <tex>map<stringЧтобы это исправить, valueнаучимся приводить любой тип данных к строке.type></tex>Тогда сможем хранить любой вид данных в качестве ключа. Будем искать ключ#Если реализовывать ассоциативный массив на обычном боре, спускаясь по бору. Соответственноа ключами будут являться строки, если на какой-то вершине нет пометкибудет использоваться слишком много памяти (возможен, например, что вершина является концом словавариант, то объекта в <tex>map</tex> когда у слов нет. Если хотим добавить егопересечений по префиксу, то ставим в вершину флаг конца слова и заносим значение.Работать такой алгоритм тогда бор будет за использовать <tex>O(n| \Sigma |)</tex>, где <tex>n</tex> - количество добавленных словпамяти).

*[http://e-maxx.ru/algo/aho_corasick Алгоритм Ахо-КорасикБор. Построение бора] 

[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]