Бор — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Использование)
(Использование бора в качестве ассоциативного массива)
Строка 41: Строка 41:
  
 
===Использование бора в качестве ассоциативного массива===
 
===Использование бора в качестве ассоциативного массива===
====Обозначения====
 
*<tex>k</tex> {{---}} длина строки
 
*<tex>m</tex> {{---}} число ключей
 
 
====Идея====
 
 
Благодаря тому, что бор позволяет решать задачу, описанную выше, он может выступать в качестве ассоциативного массива. Обычно, когда требуется такая структура, то используют [[Дерево поиска, наивная реализация | двоичное дерево поиска]] или [[Хеш-таблица | хеш-таблицу]].  
 
Благодаря тому, что бор позволяет решать задачу, описанную выше, он может выступать в качестве ассоциативного массива. Обычно, когда требуется такая структура, то используют [[Дерево поиска, наивная реализация | двоичное дерево поиска]] или [[Хеш-таблица | хеш-таблицу]].  
=====Плюсы=====
+
====Плюсы====
 
Бор объединяет некоторые преимущества этих структур данных и позволяет одновременно делать следующие операции, которые каждая из структур не может делать по отдельности.
 
Бор объединяет некоторые преимущества этих структур данных и позволяет одновременно делать следующие операции, которые каждая из структур не может делать по отдельности.
 
#Добавление элемента в ассоциативный массив за <tex>O(k)</tex> (а дерево может за <tex>O(k\log m)</tex>).
 
#Добавление элемента в ассоциативный массив за <tex>O(k)</tex> (а дерево может за <tex>O(k\log m)</tex>).
 
#Получение всех ключей в отсортированном порядке за <tex>O(m)</tex> (а хеш-таблица может только за <tex>O(m\log m)</tex>).
 
#Получение всех ключей в отсортированном порядке за <tex>O(m)</tex> (а хеш-таблица может только за <tex>O(m\log m)</tex>).
=====Минусы=====
+
Обозначения:
 +
*<tex>k</tex> {{---}} длина строки
 +
*<tex>m</tex> {{---}} число ключей
 +
 
 +
====Минусы====
 
Несмотря на данные достоинства у реализации ассоциативного массива в виде бора есть следующий недостаток:
 
Несмотря на данные достоинства у реализации ассоциативного массива в виде бора есть следующий недостаток:
 
# Бор хранит строки или символы, а это значит, что у значения ключа будет ограничение на тип (строки, символы, либо числа, представленные как строки). Чтобы это исправить, будем использовать любой тип данных, у которого прописаны операторы сравнения.
 
# Бор хранит строки или символы, а это значит, что у значения ключа будет ограничение на тип (строки, символы, либо числа, представленные как строки). Чтобы это исправить, будем использовать любой тип данных, у которого прописаны операторы сравнения.

Версия 19:41, 13 апреля 2016

Бор (англ. trie, луч, нагруженное дерево) — структура данных для хранения набора строк, представляющая из себя подвешенное дерево с символами на рёбрах. Строки получаются последовательной записью всех рёбер между корнем бора и терминальной вершиной. Размер бора линейно зависит от суммы длин всех строк, а поиск в бору занимает время, пропорциональное длине образца.

Пример

Бор для набора образцов [math] \{ \textbf{he}, \textbf{she}, \textbf{his}, \textbf{hers}\} [/math]:
Бор.jpg

Построение

Обозначения

Введем следующие обозначения:

  • [math]P = \{P_1,\ldots,P_k\} [/math] — набор строк, называемый словарем;
  • [math]n = \sum_{i=1}^{k}\limits |P_i|[/math] — сумма длин строк.

Бор храним как дерево, в котором на ребрах хранятся символы, а в вершинах указатели на конец строки или её продолжение.

Алгоритм

Непосредственно построение:

  • Начало.
  • Шаг 1. Создадим дерево из одной вершины (в нашем случае корня).
  • Шаг 2. Добавление элементов в дерево.
    • Добавляем шаблоны [math]P_i[/math] один за другим. Следуем из корня по рёбрам, отмеченным буквами из [math]P_i[/math], пока возможно.
    • Если [math]P_i[/math] заканчивается в [math]v[/math], сохраняем идентификатор [math]P_i[/math] (например, [math]i[/math]) в [math]v[/math] и отмечаем вершину [math]v[/math] как терминальную.
    • Если ребра, отмеченного очередной буквой [math]P_i[/math] нет, то создаем новое ребро и вершину для каждого оставшегося символа [math]P_i[/math].
  • Конец.

Это занимает, очевидно, [math]O(|P_1| + \ldots + |P_k|) = O(n)[/math] времени, так как поиск буквы, по которой нужно переходить, происходит за [math]O(1)[/math](в вершине есть указатели на буквы).

Поскольку на каждую вершину приходится [math]O(1)[/math] памяти, то использование памяти есть [math]O(n)[/math].

Другие модификации

Бор позволяет решать задачу поиска подстроки в строке, если построить его на множестве суффиксов исходной строки. Такая модификация называется суффиксным бором.

Использование бора

Поиск строки в бору

Задача:
Требуется найти слово в словаре.

Для того, чтобы решить эту задачу, мы начнем идти из корня бора по рёбрам, отмеченным символами [math]S[/math], пока возможно. Если с последним символом [math]S[/math] мы приходим в вершину с сохраненным идентификатором, то [math]S[/math] — слово из словаря. Если в какой-то момент ребра, отмеченного нужным символом, не находится, то строки [math]S[/math] в словаре нет. Ясно, что это занимает [math]O (|S|)[/math] времени. Таким образом, бор — это эффективный способ хранить словарь и искать в нем слова.

Использование бора в качестве ассоциативного массива

Благодаря тому, что бор позволяет решать задачу, описанную выше, он может выступать в качестве ассоциативного массива. Обычно, когда требуется такая структура, то используют двоичное дерево поиска или хеш-таблицу.

Плюсы

Бор объединяет некоторые преимущества этих структур данных и позволяет одновременно делать следующие операции, которые каждая из структур не может делать по отдельности.

  1. Добавление элемента в ассоциативный массив за [math]O(k)[/math] (а дерево может за [math]O(k\log m)[/math]).
  2. Получение всех ключей в отсортированном порядке за [math]O(m)[/math] (а хеш-таблица может только за [math]O(m\log m)[/math]).

Обозначения:

  • [math]k[/math] — длина строки
  • [math]m[/math] — число ключей

Минусы

Несмотря на данные достоинства у реализации ассоциативного массива в виде бора есть следующий недостаток:

  1. Бор хранит строки или символы, а это значит, что у значения ключа будет ограничение на тип (строки, символы, либо числа, представленные как строки). Чтобы это исправить, будем использовать любой тип данных, у которого прописаны операторы сравнения.

См. также

Источники информации

  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — ISBN 5-8489-0857-4
  • Бор. Построение бора