Изменения

'''Бор''' (англ. ''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|}\limits</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>.

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

Бор позволяет решать задачу поиска подстроки в строке, если построить его на множестве суффиксов исходной строки. Такой ===Цифровой бор называется [[Суффиксный ==={{main|Сверхбыстрый цифровой бор | суффиксным бором]], который позволяет найти количество различных подстрок данной строки и решить другие задачи за линейное время, если его оптимизировать. Такая оптимизация называется [[Сжатое суффиксное дерево | сжатым суффиксным деревом]].}}

==Использование бора=====Поиск строки в бору===

'''Поиск строки Требуется найти слово <tex>S</tex> в бору'''словаре.

Поиск строки <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>[[Основные определения теории графов | ребро]] с более чем одним символом.}

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