Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Из Википедии — свободной энциклопедии

Бор, содержащий ключи «A», «to», «tea», «ted», «ten», «i», «in», «inn».
Бор, содержащий ключи «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/ Архивная копия от 24 августа 2017 на Wayback Machine
  7. Robert Love. Linux Kernel Development. Third Edition. 2010.

Литература

Ссылки

Эта страница в последний раз была отредактирована 12 апреля 2022 в 18:14.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).