Префиксное дерево

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Бор, содержащий ключи «A», «to», «tea», «ted», «ten», «i», «in», «inn».

Префиксное дерево (также бор[1], луч[2], нагруженное дерево[3], англ. trie[4]) — структура данных, позволяющая хранить ассоциативный массив, ключами которого являются строки. Представляет собой корневое дерево, каждое ребро которого помечено каким-то символом так, что для любого узла все рёбра, соединяющие этот узел с сыновьями, помечены разными символами. Некоторые узлы префиксного дерева выделены (на рисунке выделенные узлы подписаны цифрами): префиксное дерево содержит данную строку-ключ тогда и только тогда, когда эту строку можно прочитать на пути из корня до какого-то выделенного узла (заметим, что такой узел единственный). В некоторых приложениях удобно считать все узлы выделенными.

Таким образом, в отличие от бинарных деревьев поиска, ключ, идентифицирующий конкретный узел дерева, не хранится в данном узле, а определяется положением данного узла в дереве. Значение ключа можно получить соединением символов, написанных на рёбрах на пути от корня до данного узла. Корень дерева связан с пустой строкой. Часто выделенные узлы хранят какую-то дополнительную информацию, связанную с ключом, и обычно выделенными являются только листья и, возможно, некоторые внутренние узлы.

Операции над префиксным деревом[править | править вики-текст]

Выделяют три основные операции над префиксным деревом: проверка наличия ключа в дереве, удаление ключа из дерева и вставка нового ключа (возможно, с какой-то дополнительной связанной информацией). Каждая из этих операций очевидным образом реализуется с помощью спуска по дереву из корня, но эффективность такой реализации напрямую зависит от организации навигации по узлам. Для последующего анализа различных подходов к этой проблеме обозначим через длину строки, которую запрашивают/удаляют/вставляют, а через обозначим размер алфавита, то есть количество различных символов на рёбрах данного префиксного дерева. Пусть данный узел имеет сыновей (при этом, очевидно, ). Обозначим через ссылки на этих сыновей, а через — символы, которые помечают рёбра, соединяющие с соответствующими сыновьями.

  1. Наиболее простой способ организовать навигацию в — хранить динамический массив пар . При таком подходе все три операции выполняются за . Если же вставка и удаление не используются, то лучше отсортировать пары по ключу и тогда операцию проверки наличия ключа в префиксном дереве можно будет выполнять за с помощью бинарного поиска в узлах.
  2. Можно добиться времени выполнения для всех трёх операций, если хранить пары отсортированными по ключу в каком-либо сбалансированном бинарном дереве поиска, например, в красно-чёрном дереве или АВЛ-дереве. В большинстве языков программирования реализация какого-то сбалансированного дерева поиска входит в стандартную библиотеку в виде ассоциативного массива.
  3. Другой популярный способ организации навигации в — хранить пары по ключу в хеш-таблице. При таком подходе все три операции выполняются за ожидаемое время (в то время как два предыдущих варианта имеют гарантированное время выполнения). Во многих языках программирования хеш-таблицы входят в стандартную библиотеку. Можно ещё улучшить временные гарантии, заменив хеш-таблицу хешированием кукушки или другой аналогичной структурой: такой хеш позволяет выполнять запрос и удаление ключей за гарантированное время и только лишь вставка выполняется за ожидаемое время .

Сжатое префиксное дерево[править | править вики-текст]

Рассмотрим префиксное дерево, содержащее все суффиксы строки , имеющей длину . Нетрудно видеть, что это дерево имеет не менее узлов и занимает, таким образом, памяти. В данном примере такое расточительное потребление памяти вызвано наличием большого числа узлов, обладающих лишь одним сыном. Для борьбы с этой проблемой Дональдом Моррисоном[5] была разработана модификация префиксного дерева, называемая сжатое префиксное дерево (также встречаются варианты компактное префиксное дерево, базисное дерево, сжатый бор, компактный бор, сжатый луч, сжатое нагруженное дерево; сам Моррисон[5] называл свою структуру «PATRICIA tree» и это название до сих пор иногда встречается).

Определение и способы хранения[править | править вики-текст]

Пример сжатого префиксного дерева для русского языка.

Сжатое префиксное дерево, содержащее заданные строки , — это минимальное по числу узлов дерево, каждое ребро которого помечено непустой строкой (а не символом, как в обычном префиксном дереве) так, что любая строка может быть прочитана на пути из корня до какого-то (выделенного) узла, и для любого узла первые символы на всех метках на рёбрах узел-сын различны. Например, изображённое на рисунке сжатое префиксное дерево содержит восемь слов русского языка и выделенными узлами в нём являются только листья.

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

Эффективность сжатого префиксного дерева проистекает из способа представления меток на рёбрах. Поскольку каждая метка является подстрокой какой-то строки , можно представить с помощью тройки чисел , где (здесь обозначает подстроку строки , начинающуюся в позиции и заканчивающуюся в позиции ). Отметим, что если все строки являются подстроками какой-то одной заданной строки , то метки можно представлять парами чисел , соответствующими подстрокам . Навигация в узлах организуется теми же способами, что и в обычном префиксном дереве, но символами-ссылками служат первые символы в метках на рёбрах узел-сын: например, в сжатом префиксном дереве на рисунке узел, соответствующий строке «вест», имеет трёх сыновей и символами-ссылками в данном узле служат «и», «н», «ь», которые являются первыми символами в метках «иб», «ник», «ь» на рёбрах узел-сын. Можно показать, что сжатое префиксное дерево для набора строк имеет всего не более узлов и, таким образом, занимает памяти, если не считать память необходимую для хранения самих строк .

Операции над сжатым префиксным деревом[править | править вики-текст]

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

Если длины всех строк сравнительно невелики (например, в пределах длины одной кэш линии, которая на многих современных процессорах составляет 64 байта), то кэш промахов, вызванных частыми перескоками между различными метками, можно избежать с помощью другого метода спуска по дереву (заметим, что как раз этот метод был описан в статье Моррисона[5]). Для примера рассмотрим алгоритм поиска длиннейшего префикса заданной строки , который можно прочитать на пути из корня до какого-то узла в данном сжатом префиксном дереве; остальные операции можно реализовать по аналогии.

Алгоритм заключается в том, чтобы первым проходом опросить только узлы дерева, пропуская рёбра, и, таким образом, спустившись как можно ниже в дереве, найти строку из множества , имеющую самый длинный общий префикс со строкой . Затем нужно вычислить общий префикс и обычным наивным алгоритмом и вернуть результат. В представленном ниже C-подобном псевдокоде s[i] обозначает строку , root обозначает корень дерева, и каждый узел x содержит следующие поля/методы: x->len — длина метки на ребре от x к отцу x; x->child(c) — ссылка на сына узла x, соединённого с x ребром с меткой, начинающейся с символа c, или nullptr, если такого сына нет; x->src — число, такое что строка на пути от корня к x является префиксом строки .

size_t find_longest_prefix(string t) {
  struct node_t *x = root;
  for (size_t i = 0; i < t.length(); i += x->len)
    if (x->child(t[i]) != nullptr) x = x->child(t[i]);
    else break;
  return длина общего префикса t и s[x->src];
}

Приложения[править | править вики-текст]

Структура широко применяется в алгоритмах поиска и других приложениях.

  • Префиксное дерево используется в алгоритме Ахо — Корасик для поиска нескольких строк в заданной строке.
  • Также префиксное дерево используется в алгоритме Лемпеля — Зива — Велча.
  • Сжатое префиксное дерево, содержащее все суффиксы заданной строки, называется суффиксным деревом и играет важнейшую роль в алгоритмах поиска.
  • Сжатое префиксное дерево используется, в частности, для синтаксического анализа естественных языков[6].
  • Сжатое префиксное дерево является одной из структур данных ядра Linux[7].

Примечания[править | править вики-текст]

  1. В первом переводе монографии Кнута.
  2. В последующих переводах монографии Кнута.
  3. Ахо, Хопкрофт, Ульман, 2003, с. 152.
  4. Fredkin, 1960.
  5. 1 2 3 Morrison, 1968.
  6. Pymorphy 2 https://habrahabr.ru/post/176575/
  7. Robert Love. Linux Kernel Development. Third Edition. 2010.

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]