Смартфон как музыкальный центр: почему онлайн-стриминг — это будущее звукового мира
В современном мире музыка стала неотъемлемой частью повседневной жизни миллионов людей. С развитием технологий и

Какие причины инсульта?
Инсульт – это серьезное заболевание, которое может привести к различным нарушениям в функционировании мозга. Оно

В чем опасность нарушения ритма сердца?
Чем опасны нарушения ритма сердца? Профилактика осложнений при нарушениях ритма сердца.

Создание летней кухни: материалы, варианты оформления и рекомендации
Летняя кухня - это не только место для приготовления пищи на свежем воздухе, но и уютное пространство, где можно

Аренда фрезы для снятия асфальта в Москве: быстрое решение для ремонта дорожных покрытий
Необходимость ремонтных работ на дорожных покрытиях возникает регулярно. Полное восстановление изношенного

Исследование особенностей и преимуществ монолитного поликарбоната в современном строительстве
Монолитный поликарбонат – это материал, который набирает все большую популярность в сфере строительства благодаря

Как правильно выбрать квартиру в жилом комплексе "Малая Финляндия" в Выборге: идеальное сочетание комфорта и уюта
Перед тем как купить квартиру в Выборге, одним из ключевых факторов, на которые стоит обратить внимание, является

Изготовление световых объемных букв для эффективной рекламы
В мире современной рекламы одним из самых востребованных и эффективных видов наружной рекламы являются cветовые

ВИДЕОГАЛЕРЕЯ

Фрезерные станки Zenitech DF для обработки изделий из древесины

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

Статьи

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

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

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

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

Наиболее простой способ организовать навигацию в x {displaystyle x} — хранить динамический массив пар ( a i , x i ) {displaystyle (a_{i},x_{i})} . При таком подходе все три операции выполняются за O ( n σ ) {displaystyle O(nsigma )} . Если же вставка и удаление не используются, то лучше отсортировать пары по ключу a i {displaystyle a_{i}} и тогда операцию проверки наличия ключа в префиксном дереве можно будет выполнять за O ( n log ⁡ σ ) {displaystyle O(nlog sigma )} с помощью бинарного поиска в узлах.

Можно добиться времени выполнения O ( n log ⁡ σ ) {displaystyle O(nlog sigma )} для всех трёх операций, если хранить пары ( a i , x i ) {displaystyle (a_{i},x_{i})} отсортированными по ключу a i {displaystyle a_{i}} в каком-либо сбалансированном бинарном дереве поиска, например, в красно-чёрном дереве или АВЛ-дереве. В большинстве языков программирования реализация какого-то сбалансированного дерева поиска входит в стандартную библиотеку в виде ассоциативного массива.

Другой популярный способ организации навигации в x {displaystyle x} — хранить пары ( a i , x i ) {displaystyle (a_{i},x_{i})} по ключу a i {displaystyle a_{i}} в хеш-таблице. При таком подходе все три операции выполняются за ожидаемое время O ( n ) {displaystyle O(n)} (в то время как два предыдущих варианта имеют гарантированное время выполнения). Во многих языках программирования хеш-таблицы входят в стандартную библиотеку. Можно ещё улучшить временные гарантии, заменив хеш-таблицу хешированием кукушки или другой аналогичной структурой: такой хеш позволяет выполнять запрос и удаление ключей за гарантированное время O ( n ) {displaystyle O(n)} и только лишь вставка выполняется за ожидаемое время O ( n ) {displaystyle O(n)} .

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

Рассмотрим префиксное дерево, содержащее все суффиксы строки a a ⋯ a ⏟ k раз b a a ⋯ a ⏟ k раз b { extstyle underbrace {aacdots a} _{k{ ext{ раз}}}bunderbrace {aacdots a} _{k{ ext{ раз}}}b} , имеющей длину n = 2 k + 2 {displaystyle n=2k+2} . Это дерево имеет не менее k 2 = Θ ( n 2 ) {displaystyle k^{2}=Theta (n^{2})} узлов и занимает, таким образом, Θ ( n 2 ) {displaystyle Theta (n^{2})} памяти. В данном примере такое расточительное потребление памяти вызвано наличием большого числа узлов, обладающих лишь одним сыном. Для борьбы с этой проблемой Дональдом Моррисоном была разработана модификация префиксного дерева, называемая сжатое префиксное дерево (также встречаются варианты компактное префиксное дерево, базисное дерево, сжатый бор, компактный бор, сжатый луч, сжатое нагруженное дерево; сам Моррисон называл свою структуру «PATRICIA tree» и это название до сих пор иногда встречается).

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

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

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

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

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

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

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

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

Приложения

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

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