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