Просмотр кода страницы Префиксное дерево

[[Файл:Trie_example.svg|thumb|
Бор, содержащий ключи «A», «to», «tea», «ted», «ten», «i», «in», «inn»
]]
'''Префиксное дерево''' (также ''бор''<ref>В первом переводе монографии Кнута.</ref>, ''луч''<ref>В последующих переводах монографии Кнута.</ref>, ''нагруженное дерево''{{sfn|Ахо, Хопкрофт, Ульман|2003|с=152}}, {{lang-en|trie}}{{sfn|Fredkin|1960}}) — [[структура данных]], позволяющая хранить [[ассоциативный массив]], ключами которого чаще всего являются строки. Представляет собой [[Корневой_граф#Корневое_дерево|корневое дерево]], каждое ребро которого помечено каким-то символом так, что для любого узла все рёбра, соединяющие этот узел с его сыновьями, помечены разными символами. Некоторые узлы префиксного дерева выделены (на рисунке они подписаны цифрами) и считается, что префиксное дерево содержит данную строку-ключ [[тогда и только тогда]], когда эту строку можно прочитать на пути из корня до некоторого (единственного для этой строки) выделенного узла. В некоторых приложениях удобно считать все узлы дерева выделенными.

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

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

Выделяют три основные операции над префиксным деревом: проверка наличия ключа в дереве, удаление ключа из дерева и вставка нового ключа (возможно, с какой-то дополнительной связанной информацией). Каждая из этих операций реализуется с помощью спуска по дереву из корня, но эффективность такой операции напрямую зависит от организации навигации по узлам. Для последующего анализа различных подходов к этой проблеме обозначим через <math>n</math> длину строки, которую запрашивают/удаляют/вставляют, а через <math>\sigma</math> обозначим ''размер алфавита'', то есть количество различных символов на рёбрах данного префиксного дерева. Пусть данный узел <math>x</math> имеет <math>k</math> сыновей (при этом <math>k \le \sigma</math>). Обозначим через <math>x_1, x_2, \ldots, x_k</math> ссылки на этих сыновей, а через <math>a_1, a_2, \ldots, a_k</math> — символы, которые помечают рёбра, соединяющие <math>x</math> с соответствующими сыновьями.

# Наиболее простой способ организовать навигацию в <math>x</math> — хранить [[динамический массив]] пар <math>(a_i,x_i)</math>. При таком подходе все три операции выполняются [[О-символика|за <math>O(n\sigma)</math>]]. Если же вставка и удаление не используются, то лучше отсортировать пары по ключу <math>a_i</math> и тогда операцию проверки наличия ключа в префиксном дереве можно будет выполнять за <math>O(n\log\sigma)</math> с помощью [[Бинарный поиск|бинарного поиска]] в узлах.
# Можно добиться времени выполнения <math>O(n\log\sigma)</math> для всех трёх операций, если хранить пары <math>(a_i,x_i)</math> отсортированными по ключу <math>a_i</math> в каком-либо сбалансированном [[бинарное дерево поиска|бинарном дереве поиска]], например, в [[красно-чёрное дерево|красно-чёрном дереве]] или [[АВЛ-дерево|АВЛ-дереве]]. В большинстве языков программирования реализация какого-то сбалансированного дерева поиска входит в стандартную библиотеку в виде [[ассоциативный массив|ассоциативного массива]].
# Другой популярный способ организации навигации в <math>x</math> — хранить пары <math>(a_i,x_i)</math> по ключу <math>a_i</math> в [[хеш-таблица|хеш-таблице]]. При таком подходе все три операции выполняются за [[математическое ожидание|ожидаемое]] время <math>O(n)</math> (в то время как два предыдущих варианта имеют гарантированное время выполнения). Во многих языках программирования хеш-таблицы входят в стандартную библиотеку. Можно ещё улучшить временные гарантии, заменив хеш-таблицу [[Кукушкино хеширование|хешированием кукушки]] или другой аналогичной структурой: такой хеш позволяет выполнять запрос и удаление ключей за гарантированное время <math>O(n)</math> и только лишь вставка выполняется за ''ожидаемое'' время <math>O(n)</math>.

== Сжатое префиксное дерево ==
Рассмотрим префиксное дерево, содержащее все [[суффикс (информатика)|суффиксы]] строки <math display="inline">\underbrace{aa\cdots a}_{k\text{ раз}}b\underbrace{aa\cdots a}_{k\text{ раз}}b</math>, имеющей длину <math>n = 2k + 2</math>. Это дерево имеет не менее <math>k^2 = \Theta(n^2)</math> узлов и занимает, таким образом, <math>\Theta(n^2)</math> памяти. В данном примере такое расточительное потребление памяти вызвано наличием большого числа узлов, обладающих лишь одним сыном. Для борьбы с этой проблемой Дональдом Моррисоном{{sfn|Morrison|1968}} была разработана модификация префиксного дерева, называемая [[Базисное дерево|сжатое префиксное дерево]] (также встречаются варианты ''компактное префиксное дерево, базисное дерево'', ''сжатый бор'', ''компактный бор'', ''сжатый луч'', ''сжатое нагруженное дерево''; сам Моррисон{{sfn|Morrison|1968}} называл свою структуру «PATRICIA tree» и это название до сих пор иногда встречается). 

=== Определение и способы хранения ===
[[Файл:Radix-tree-ru.png|thumb|Пример сжатого префиксного дерева для русского языка.]]
Сжатое префиксное дерево, содержащее заданные строки <math>s_1, s_2, \ldots, s_k</math>, — это минимальное по числу узлов дерево, каждое ребро которого помечено непустой строкой (а не символом, как в обычном префиксном дереве) так, что любая строка <math>s_i</math> может быть прочитана на пути из корня до какого-то (выделенного) узла, и для любого узла первые символы на всех метках на рёбрах узел-сын различны. Например, изображённое на рисунке сжатое префиксное дерево содержит восемь слов русского языка и выделенными узлами в нём являются только листья.

Сжатое префиксное дерево получается из обычного префиксного дерева, содержащего ключи <math>s_1, s_2, \ldots, s_k</math>, путём последовательного удаления каждого узла (кроме корня), который имеет лишь одного сына и не является выделенным, при этом отец и сын удаляемого узла соединяются и образовавшееся ребро помечается строкой, полученной соединением меток на рёбрах отец-узел и узел-сын (хотя такой метод построения сжатого префиксного дерева не рекомендуется{{Кем}}). 

Эффективность сжатого префиксного дерева проистекает из способа представления меток на рёбрах. Поскольку каждая метка <math>t</math> является [[подстрока|подстрокой]] какой-то строки <math>s_h</math>, можно представить <math>t</math> с помощью тройки чисел <math>(h, i, j)</math>, где <math>s_h[i..j] = t</math> (здесь <math>s_h[i..j]</math> обозначает подстроку строки <math>s_h</math>, начинающуюся в позиции <math>i</math> и заканчивающуюся в позиции <math>j</math>). Если все строки <math>s_h</math> являются подстроками какой-то одной заданной строки <math>s</math>, то метки можно представлять парами чисел <math>(i,j)</math>, соответствующими подстрокам <math>s[i..j]</math>. Навигация в узлах организуется теми же способами, что и в обычном префиксном дереве, но символами-ссылками служат первые символы в метках на рёбрах узел-сын: например, в сжатом префиксном дереве на рисунке узел, соответствующий строке «вест», имеет трёх сыновей и символами-ссылками в данном узле служат «и», «н», «ь», которые являются первыми символами в метках «иб», «ник», «ь» на рёбрах узел-сын. Можно показать, что сжатое префиксное дерево для набора строк <math>s_1, s_2, \ldots, s_k</math> имеет всего не более <math>2k</math> узлов и, таким образом, занимает <math>O(k)</math> памяти, если не считать память необходимую для хранения самих строк <math>s_1, s_2, \ldots, s_k</math>.

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

Операции запроса, удаления и вставки в сжатом префиксном дереве можно выполнять так же, как и в обычном префиксном дереве, при помощи спуска из корня. При этом алгоритм становится несколько более сложным из-за необходимости при спуске по рёбрам, помеченным строками длины два и более, читать содержимое метки из соответствующей подстроки одной из строк <math>s_1, s_2, \ldots, s_k</math>. Теоретически время работы такого алгоритма можно оценить так же, как и для обычного префиксного дерева (то есть как <math>O(n\sigma)</math>, <math>O(n\log\sigma)</math>, <math>O(n)</math> в зависимости от организации навигации в узлах), но на практике операции над сжатым префиксным деревом нередко оказываются быстрее из-за того, что большая часть пути от корня до узла проходит по рёбрам и нет необходимости часто обращаться к структурам данных в узлах.

Если длины всех строк <math>s_i</math> сравнительно невелики (например, в пределах длины одной [[кэш процессора|кэш линии]], которая на многих современных процессорах составляет 64 байта), то [[кэш процессора#Виды_промахов|промахов кэша]], вызванных частыми перескоками между различными метками, можно избежать с помощью другого метода спуска по дереву (как раз этот метод был описан в статье Моррисона{{sfn|Morrison|1968}}). Для примера рассмотрим алгоритм поиска длиннейшего префикса заданной строки <math>t</math>, который можно прочитать на пути из корня до какого-то узла в данном сжатом префиксном дереве; остальные операции можно реализовать по аналогии.

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

<source lang="C">
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];
}
</source>

== Приложения ==

Структура широко применяется в алгоритмах поиска и других приложениях.
* Префиксное дерево используется в [[Алгоритм Ахо — Корасик|алгоритме Ахо — Корасик]] для поиска нескольких строк в заданной строке.
* Также префиксное дерево используется в [[алгоритм Лемпеля — Зива — Велча|алгоритме Лемпеля — Зива — Велча]].
* Сжатое префиксное дерево, содержащее все суффиксы заданной строки, называется [[суффиксное дерево|суффиксным деревом]] и играет важнейшую роль в алгоритмах поиска.
* Сжатое префиксное дерево используется, в частности, для [[Морфологический анализ|морфологического анализа]] естественных языков<ref>Pymorphy 2 https://habrahabr.ru/post/176575/ {{Wayback|url=https://habrahabr.ru/post/176575/ |date=20170824215412 }}</ref>.
* Сжатое префиксное дерево является одной из структур данных [[Ядро Linux|ядра Linux]]<ref>Robert Love. Linux Kernel Development. Third Edition. 2010.</ref>.

== Примечания ==
{{Примечания}}

== Литература ==
* {{Книга:Кнут|3}}
* {{книга|автор=[[Ахо, Альфред|Ахо А. В.]], [[Хопкрофт, Джон|Хопкрофт Дж. Э.]], [[Ульман, Джеффри|Ульман Дж. Д.]]|заглавие= Структуры данных и алгоритмы|оригинал=Data Structures and Algorithms|год=2003|страниц=384|место=М.|издательство= Вильямс|ref=Ахо, Хопкрофт, Ульман|isbn=5-8459-0122-7|ответственный=под ред. {{nobr|С. Н. Тригуба}}; пер. с англ. {{nobr|А. А. Минько}}}}
* {{книга|автор=[[:en:Maxime Crochemore|Crochemore M.]], [[:en:Wojciech Rytter|Rytter W.]]|заглавие= Jewels of Stringology|издательство= World Publishing Scientific Co. Pte. Ltd.|место=Singapore|год=2002|страниц=306|isbn=981-02-4782-6|ref=CrochemoreRytter}}
* {{статья|автор=[[:en:Edward Fredkin|Fredkin E.]]|заглавие= Trie Memory|издание= [[Communications of the ACM]]|номер=9|том=3|страницы=490–499|год=1960|ref=Fredkin|doi=10.1145/367390.367400}}
* {{статья|автор=Morrison D. R.|заглавие= Practical Algorithm to Retrieve Information Coded in Alphanumeric|издание= [[Journal of the ACM]]|номер=4|том=15|год=1968|ref=Morrison|страницы=514–534|doi=10.1145/321479.321481}}

== Ссылки ==
* Bentley, Jon; Sedgewick, Robert (1998-04-01). [https://web.archive.org/web/20080623071352/http://www.ddj.com/windows/184410528 «Ternary Search Trees»]. Dr. Dobb’s Journal (Dr Dobb’s). Archived from the [http://www.ddj.com/windows/184410528 original] on 2008-06-23.
* [http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Trie/ Algorithms and Data Structures Research & Reference Material: Tries] {{Wayback|url=http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Trie/ |date=20130306054143 }}, by Lloyd Allison, Monash University.
* [http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/ Algorithms and Data Structures Research & Reference Material: PATRICIA] {{Wayback|url=http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/ |date=20180522213057 }}, by Lloyd Allison, Monash University.
* [https://xlinux.nist.gov/dads/HTML/patriciatree.html Patricia Tree] {{Wayback|url=https://xlinux.nist.gov/dads/HTML/patriciatree.html |date=20171230113339 }}, NIST Dictionary of Algorithms and Data Structures.
* [http://cr.yp.to/critbit.html  Crit-bit trees] {{Wayback|url=http://cr.yp.to/critbit.html |date=20071231114136 }}, by Daniel J. Bernstein.
* [https://lwn.net/Articles/175432/ Radix Tree API in the Linux Kernel] {{Wayback|url=https://lwn.net/Articles/175432/ |date=20201108131647 }}, by Jonathan Corbet.
* [http://code.dogmap.org/kart/ Kart (key alteration radix tree)] {{Wayback|url=http://code.dogmap.org/kart/ |date=20080807173647 }}, by Paul Jarc.

{{Структуры данных}}
{{Деревья (структуры данных)}}
{{Строки}}

[[Категория:Строковые алгоритмы]]
[[Категория:Деревья (структуры данных)]]