Бор — различия между версиями
(→Алгоритм) |
(→Другие модификации) |
||
Строка 26: | Строка 26: | ||
Поскольку на каждую вершину приходится <tex>O(1)</tex> памяти, то использование памяти есть <tex>O(n)</tex>. | Поскольку на каждую вершину приходится <tex>O(1)</tex> памяти, то использование памяти есть <tex>O(n)</tex>. | ||
− | === | + | ===Суффиксный бор=== |
{{main|Суффиксный бор}} | {{main|Суффиксный бор}} | ||
− | |||
Бор позволяет решать задачу [[Наивный алгоритм поиска подстроки в строке | поиска подстроки в строке]], если построить его на множестве суффиксов исходной строки. | Бор позволяет решать задачу [[Наивный алгоритм поиска подстроки в строке | поиска подстроки в строке]], если построить его на множестве суффиксов исходной строки. | ||
− | + | ===Цифровой бор=== | |
+ | {{main|Сверхбыстрый цифровой бор}} | ||
==Использование бора== | ==Использование бора== |
Версия 21:18, 13 апреля 2016
Бор (англ. trie, луч, нагруженное дерево) — структура данных для хранения набора строк, представляющая из себя подвешенное дерево с символами на рёбрах. Строки получаются последовательной записью всех символов, хранящихся на рёбрах между корнем бора и терминальной вершиной. Размер бора линейно зависит от суммы длин всех строк, а поиск в бору занимает время, пропорциональное длине образца.
Содержание
Пример
:Построение
Обозначения
Введем следующие обозначения:
- — набор строк, называемый словарем;
- — сумма длин строк.
Бор храним как дерево, в котором на ребрах хранятся символы, а в вершинах указатели на конец строки или её продолжение.
Алгоритм
Непосредственно построение:
- Начало.
- Шаг 1. Создадим дерево из одной вершины (в нашем случае корня).
- Шаг 2. Добавление элементов в дерево.
- Конец.
Это занимает, очевидно,
времени, так как поиск буквы, по которой нужно переходить, происходит за (в вершине есть указатели на буквы).Поскольку на каждую вершину приходится
памяти, то использование памяти есть .Суффиксный бор
Бор позволяет решать задачу поиска подстроки в строке, если построить его на множестве суффиксов исходной строки.
Цифровой бор
Использование бора
Поиск строки в бору
Задача: |
Требуется найти слово в словаре. |
При решении этой задачи, обход бора совершается из его корня по рёбрам, отмеченным символами , пока возможно. Если с последним символом мы приходим в вершину с сохраненным идентификатором, то — слово из словаря. Если в какой-то момент ребра, отмеченного нужным символом, не находится, то строки в словаре нет. Ясно, что это занимает времени. Таким образом, бор — это эффективный способ хранить словарь и искать в нем слова.
Использование бора в качестве ассоциативного массива
Благодаря тому, что бор позволяет решать задачу, описанную выше, он может выступать в качестве ассоциативного массива. Обычно, когда требуется такая структура, то используют двоичное дерево поиска или хеш-таблицу.
Достоинства
Бор объединяет некоторые преимущества этих структур данных и позволяет одновременно делать следующие операции, которые каждая из структур не может делать по отдельности.
- Добавление элемента в ассоциативный массив за (дерево выполняет данную операцию за ).
- Получение всех ключей в отсортированном порядке за (хеш-таблица выполняет данную операцию за ).
Обозначения:
- — длина строки
- — число ключей
Недостатки
Несмотря на данные достоинства у реализации ассоциативного массива в виде бора есть следующие недостатки:
- Бор хранит строки или символы, а это значит, что у значения ключа будет ограничение на тип (строки, символы, либо числа, представленные как строки). Чтобы это исправить, научимся приводить любой тип данных к строке. Тогда сможем хранить любой вид данных в качестве ключа.
- Если реализовывать ассоциативный массив на обычном боре, а ключами будут являться строки, то будет использоваться слишком много памяти (возможен, например, вариант, когда у слов нет пересечений по префиксу, тогда бор будет использовать памяти).
См. также
Источники информации
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — ISBN 5-8489-0857-4
- Бор. Построение бора