Бор

Материал из Викиконспекты
Перейти к: навигация, поиск

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

Содержание

[править] Пример

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

[править] Построение

[править] Обозначения

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

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

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

struct vertex:
    vertex next[| \Sigma |] 
    bool isTerminal

[править] Алгоритм

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

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

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

Поскольку на каждую вершину приходится O(| \Sigma |) памяти, то использование памяти есть O(n| \Sigma |).

[править] Суффиксный бор

Основная статья: Суффиксный бор

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

[править] Цифровой бор

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

[править] Поиск строки в бору

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

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

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

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

[править] Достоинства

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

Бор Дерево Хеш-таблица
Добавление элемента O(|S|) O(|S|\log k) O(|S|)
Получение всех ключей в отсортированном порядке O(k) O(k) O(k\log k)

[править] Недостатки

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

  1. Бор хранит строки или символы, а это значит, что у значения ключа будет ограничение на тип (строки, символы, либо числа, представленные как строки). Чтобы это исправить, научимся приводить любой тип данных к строке. Тогда сможем хранить любой вид данных в качестве ключа.
  2. Если реализовывать ассоциативный массив на обычном боре, а ключами будут являться строки, то будет использоваться слишком много памяти (возможен, например, вариант, когда у слов нет пересечений по префиксу, тогда бор будет использовать O(n| \Sigma |) памяти).

[править] См. также

[править] Источники информации

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