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