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

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

Бор, содержащий ключи «A», «to», «tea», «ted», «ten», «i», «in», «inn»

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

Операции над префиксным деревом

Выделяют три основные операции над префиксным деревом: проверка наличия ключа в дереве, удаление ключа из дерева и вставка нового ключа (возможно, с какой-то дополнительной связанной информацией). Каждая из этих операций реализуется с помощью спуска по дереву из корня, но эффективность такой операции напрямую зависит от организации навигации по узлам. Для последующего анализа различных подходов к этой проблеме обозначим через ${\displaystyle n}$ длину строки, которую запрашивают/удаляют/вставляют, а через ${\displaystyle \sigma }$ обозначим размер алфавита, то есть количество различных символов на рёбрах данного префиксного дерева. Пусть данный узел ${\displaystyle x}$ имеет ${\displaystyle k}$ сыновей (при этом ${\displaystyle k\leq \sigma }$). Обозначим через ${\displaystyle x_{1},x_{2},\ldots ,x_{k}}$ ссылки на этих сыновей, а через ${\displaystyle a_{1},a_{2},\ldots ,a_{k}}$ — символы, которые помечают рёбра, соединяющие ${\displaystyle x}$ с соответствующими сыновьями.

1. Наиболее простой способ организовать навигацию в ${\displaystyle x}$ — хранить динамический массив пар ${\displaystyle (a_{i},x_{i})}$. При таком подходе все три операции выполняются за ${\displaystyle O(n\sigma )}$. Если же вставка и удаление не используются, то лучше отсортировать пары по ключу ${\displaystyle a_{i}}$ и тогда операцию проверки наличия ключа в префиксном дереве можно будет выполнять за ${\displaystyle O(n\log \sigma )}$ с помощью бинарного поиска в узлах.
2. Можно добиться времени выполнения ${\displaystyle O(n\log \sigma )}$ для всех трёх операций, если хранить пары ${\displaystyle (a_{i},x_{i})}$ отсортированными по ключу ${\displaystyle a_{i}}$ в каком-либо сбалансированном бинарном дереве поиска, например, в красно-чёрном дереве или АВЛ-дереве. В большинстве языков программирования реализация какого-то сбалансированного дерева поиска входит в стандартную библиотеку в виде ассоциативного массива.
3. Другой популярный способ организации навигации в ${\displaystyle x}$ — хранить пары ${\displaystyle (a_{i},x_{i})}$ по ключу ${\displaystyle a_{i}}$ в хеш-таблице. При таком подходе все три операции выполняются за ожидаемое время ${\displaystyle O(n)}$ (в то время как два предыдущих варианта имеют гарантированное время выполнения). Во многих языках программирования хеш-таблицы входят в стандартную библиотеку. Можно ещё улучшить временные гарантии, заменив хеш-таблицу хешированием кукушки или другой аналогичной структурой: такой хеш позволяет выполнять запрос и удаление ключей за гарантированное время ${\displaystyle O(n)}$ и только лишь вставка выполняется за ожидаемое время ${\displaystyle O(n)}$.

Сжатое префиксное дерево

Рассмотрим префиксное дерево, содержащее все суффиксы строки ${\textstyle \underbrace {aa\cdots a} _{k{\text{ раз}}}b\underbrace {aa\cdots a} _{k{\text{ раз}}}b}$, имеющей длину ${\displaystyle n=2k+2}$. Это дерево имеет не менее ${\displaystyle k^{2}=\Theta (n^{2})}$ узлов и занимает, таким образом, ${\displaystyle \Theta (n^{2})}$ памяти. В данном примере такое расточительное потребление памяти вызвано наличием большого числа узлов, обладающих лишь одним сыном. Для борьбы с этой проблемой Дональдом Моррисоном^[5] была разработана модификация префиксного дерева, называемая сжатое префиксное дерево (также встречаются варианты компактное префиксное дерево, базисное дерево, сжатый бор, компактный бор, сжатый луч, сжатое нагруженное дерево; сам Моррисон^[5] называл свою структуру «PATRICIA tree» и это название до сих пор иногда встречается).

Определение и способы хранения

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

Сжатое префиксное дерево, содержащее заданные строки ${\displaystyle s_{1},s_{2},\ldots ,s_{k}}$, — это минимальное по числу узлов дерево, каждое ребро которого помечено непустой строкой (а не символом, как в обычном префиксном дереве) так, что любая строка ${\displaystyle s_{i}}$ может быть прочитана на пути из корня до какого-то (выделенного) узла, и для любого узла первые символы на всех метках на рёбрах узел-сын различны. Например, изображённое на рисунке сжатое префиксное дерево содержит восемь слов русского языка и выделенными узлами в нём являются только листья.

Сжатое префиксное дерево получается из обычного префиксного дерева, содержащего ключи ${\displaystyle s_{1},s_{2},\ldots ,s_{k}}$, путём последовательного удаления каждого узла (кроме корня), который имеет лишь одного сына и не является выделенным, при этом отец и сын удаляемого узла соединяются и образовавшееся ребро помечается строкой, полученной соединением меток на рёбрах отец-узел и узел-сын (хотя такой метод построения сжатого префиксного дерева не рекомендуется^[кем?]).

Эффективность сжатого префиксного дерева проистекает из способа представления меток на рёбрах. Поскольку каждая метка ${\displaystyle t}$ является подстрокой какой-то строки ${\displaystyle s_{h}}$, можно представить ${\displaystyle t}$ с помощью тройки чисел ${\displaystyle (h,i,j)}$, где ${\displaystyle s_{h}[i..j]=t}$ (здесь ${\displaystyle s_{h}[i..j]}$ обозначает подстроку строки ${\displaystyle s_{h}}$, начинающуюся в позиции ${\displaystyle i}$ и заканчивающуюся в позиции ${\displaystyle j}$). Если все строки ${\displaystyle s_{h}}$ являются подстроками какой-то одной заданной строки ${\displaystyle s}$, то метки можно представлять парами чисел ${\displaystyle (i,j)}$, соответствующими подстрокам ${\displaystyle s[i..j]}$. Навигация в узлах организуется теми же способами, что и в обычном префиксном дереве, но символами-ссылками служат первые символы в метках на рёбрах узел-сын: например, в сжатом префиксном дереве на рисунке узел, соответствующий строке «вест», имеет трёх сыновей и символами-ссылками в данном узле служат «и», «н», «ь», которые являются первыми символами в метках «иб», «ник», «ь» на рёбрах узел-сын. Можно показать, что сжатое префиксное дерево для набора строк ${\displaystyle s_{1},s_{2},\ldots ,s_{k}}$ имеет всего не более ${\displaystyle 2k}$ узлов и, таким образом, занимает ${\displaystyle O(k)}$ памяти, если не считать память необходимую для хранения самих строк ${\displaystyle s_{1},s_{2},\ldots ,s_{k}}$.

Операции над сжатым префиксным деревом

Операции запроса, удаления и вставки в сжатом префиксном дереве можно выполнять так же, как и в обычном префиксном дереве, при помощи спуска из корня. При этом алгоритм становится несколько более сложным из-за необходимости при спуске по рёбрам, помеченным строками длины два и более, читать содержимое метки из соответствующей подстроки одной из строк ${\displaystyle s_{1},s_{2},\ldots ,s_{k}}$. Теоретически время работы такого алгоритма можно оценить так же, как и для обычного префиксного дерева (то есть как ${\displaystyle O(n\sigma )}$, ${\displaystyle O(n\log \sigma )}$, ${\displaystyle O(n)}$ в зависимости от организации навигации в узлах), но на практике операции над сжатым префиксным деревом нередко оказываются быстрее из-за того, что большая часть пути от корня до узла проходит по рёбрам и нет необходимости часто обращаться к структурам данных в узлах.

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

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

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. Morrison, 1968.
6. Pymorphy 2 https://habrahabr.ru/post/176575/ Архивная копия от 24 августа 2017 на Wayback Machine
7. Robert Love. Linux Kernel Development. Third Edition. 2010.

Литература

• Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007. — Т. 3. — 832 с. — ISBN 5-8459-0082-1.
• Ахо А. В., Хопкрофт Дж. Э., Ульман Дж. Д. Структуры данных и алгоритмы = Data Structures and Algorithms / под ред. С. Н. Тригуба; пер. с англ. А. А. Минько. — М.: Вильямс, 2003. — 384 с. — ISBN 5-8459-0122-7.
• Crochemore M., Rytter W. Jewels of Stringology. — Singapore: World Publishing Scientific Co. Pte. Ltd., 2002. — 306 с. — ISBN 981-02-4782-6.
• Fredkin E. Trie Memory // Communications of the ACM. — 1960. — Т. 3, № 9. — С. 490–499. — doi:10.1145/367390.367400.
• Morrison D. R. Practical Algorithm to Retrieve Information Coded in Alphanumeric // Journal of the ACM. — 1968. — Т. 15, № 4. — С. 514–534. — doi:10.1145/321479.321481.

Ссылки

• Bentley, Jon; Sedgewick, Robert (1998-04-01). «Ternary Search Trees». Dr. Dobb’s Journal (Dr Dobb’s). Archived from the original on 2008-06-23.
• Algorithms and Data Structures Research & Reference Material: Tries Архивная копия от 6 марта 2013 на Wayback Machine, by Lloyd Allison, Monash University.
• Algorithms and Data Structures Research & Reference Material: PATRICIA Архивная копия от 22 мая 2018 на Wayback Machine, by Lloyd Allison, Monash University.
• Patricia Tree Архивная копия от 30 декабря 2017 на Wayback Machine, NIST Dictionary of Algorithms and Data Structures.
• Crit-bit trees Архивная копия от 31 декабря 2007 на Wayback Machine, by Daniel J. Bernstein.
• Radix Tree API in the Linux Kernel Архивная копия от 8 ноября 2020 на Wayback Machine, by Jonathan Corbet.
• Kart (key alteration radix tree) Архивная копия от 7 августа 2008 на Wayback Machine, by Paul Jarc.