WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте
Бор, содержащий ключи «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];
}

Приложения

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

Примечания

  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.

Литература

Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии