Trie, или нагруженное дерево

Здравствуй, Хабрахабр. Сегодня я хочу рассказать о такой замечательной структуре данных как словарь на нагруженном дереве, известной также как префиксное дерево, или trie.

Что это ?


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

Как это работает ?


Нагруженное дерево отличается от обычных n-арных деревьев тем, что в его узлах не хранятся ключи. Вместо них в узлах хранятся односимвольные метки, а ключем, который соответствует некоему узлу является путь от корня дерева до этого узла, а точнее строка составленная из меток узлов, повстречавшихся на этом пути. В таком случае корень дерева, очевидно, соответствует пустому ключу.

На рисунке вы можете наблюдать пример нагруженного дерева с ключами c, cap, car, cdr, go, if, is, it.
Типичное нагруженное дерево

И то же самое дерево с выделенным на нем ключем car.
Типичное нагруженное дерево

Сразу видно, что наше дерево содержит «лишние» ключи, ведь любому узлу дерева соответствует единственный путь до него от корня, а значит и некоторый ключ. Чтобы избежать проблемы с «лишними» ключами, каждому узлу дерева добавляется булева характеристика, указывающая, является ли узел реально существующим либо промежуточным по дороге в какой-либо другой.

Основные операции


Так как нагруженное дерево реализует интерфейс ассоциативного массива, в нем можно выделить три основные операции, а именно вставку, удаление и поиск ключа. Как и многие деревья, нагруженное дерево обладает свойством самоподобия, то есть любое его поддерево также является полноценным нагруженным деревом. Легко заметить, что все ключи в таком поддереве имеют общий префикс, (откуда и пошло название «префиксное дерево») а значит можно выделить специфичную для этого дерева операцию — получение всех ключей дерева с заданным префиксом за время O(|Prefix|).

Поиск ключа

Как уже было сказано, ключ, соответствующий узлу — конкатенация меток узлов, содержащихся в пути от корня к данному узлу. Из этого свойства естественным образом следует алгоритм поиска ключа (как, впрочем, и алгоритмы добавления и удаления).

Пусть дан ключ Key, который необходимо найти в дереве. Будем спускаться из корня дерева на нижние уровни, каждый раз переходя в узел, чья метка совпадает с очередным символом ключа. После того как обработаны все символы ключа, узел, в котором остановился спуск и будет искомым узлом. Если в процессе спуска не нашлось узла с меткой, соответствующей очередному символу ключа, или спуск остановился на промежуточной вершине (вершине, не имеющей значения), то искомый ключ отсутствует в дереве.

Временная сложность этого алгоритма, очевидно, равна О(|Key|).

Более подробно алгоритм показан на блок-схеме:

Алгоритм поиска ключа


Вставка

Алгоритм добавления ключа в дерево очень похож на алгоритм поиска.

Пусть дана пара из ключа Key и значения Value, которую нужно добавить. Как и в алгоритме поиска ключа, будем спускаться из корня дерева на нижние уровни, каждый раз переходя в узел, чья метка совпадает с очередным символом ключа. После того как обработаны все символы ключа, узел, в котором остановился спуск и будет узлом, которому должно быть присвоено значение Value (также, разумеется, узел должен быть помечен как имеющий значение). Если в процессе спуска отсутствует узел с меткой, соответствующей очередному символу ключа, то следует создать новый промежуточный узел с нужной меткой и назначить его потомком текущего.

Временная сложность добавления ключа — О(|Key|).

Иллюстрация алгоритма на блок-схеме:

Алгоритм вставки ключа


Удаление

Удаление ключа также реализуется очень легко.

Пусть дан ключ Key, который необходимо удалить из дерева. Проведем поиск этого ключа. Если ключ существует в словаре, то зная узел, которому он соответствует, можно просто пометить его как промежуточный, сделав его «невидимым» для последующих поисков.
После этого можно подняться от «отключенного» узла к корню, попутно удаляя все узлы которые являются листьями, однако экономия памяти в данном случае не существенна, а для эффективного определения того, является ли узел листом потребуется вводить дополнительную характеристику узла.

Временная оценка алгоритма удаления — знакомое уже О(|Key|).

Требовательность к ресурсам


Нагруженное дерево по показателям потребления памяти/процессорного времени не уступает хэш-таблицам и сбалансированным деревьям, а иногда и превосходит их по этим параметрам.

Процессорное время

Сложность операций вставки, удаления и поиска — O(|Key|). Хотя сбалансированные деревья и выполняют эти операции за O(ln(n)) но в этой асимптотике скрыто время, необходимое для сравнения ключей, которое, в общем случае, составляет O(|Key|). С хэш-таблицами ситуация аналогична — хоть время доступа и составляет О(1+a), но взятие хэша (если он не предвычислен заранее, разумеется) занимает O(|Key|).

Графики со сравнением производительности нагруженных деревьев, хэш-таблиц и красно-черных деревьев можно посмотреть в английской википедии.

Память

По потреблению памяти нагруженное дерево часто выигрывает у хэш-таблиц и сбалансированных деревьев. Это связано с тем что у множества ключей в нагруженном дереве совпадают префиксы, и вместе с ними память которую они используют. Также, в отличии от сбалансированных деревьев, в нагруженном дереве нет необходимости хранить ключ в каждом узле.

Оптимизации


Существует 2 основных типа оптимизации нагруженного дерева:
  • Сжатие. Сжатое нагруженное дерево получается из обычного удалением промежуточных узлов, которые ведут к единственному не промежуточному узлу. Например, цепочка промежуточных узлов с метками a, b, c заменяется на один узел с меткой abc.
  • Patricia. Patricia нагруженное дерево получается из сжатого (или обычного) удалением промежуточных узлов, которые имеют одного ребенка.

Зачем все это нужно?


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

Вот собственно и все. Надеюсь, читателю было интересно узнать об этой замечательной структуре данных, незаслуженно редко упоминаемой на Хабре.
Поделиться публикацией
Похожие публикации
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 29
  • +25
    Читаем мы теги, читаем.
    • 0
      Хорошая статья, спасибо!

      Все-таки слабым местом trie является память — если никак не сжимать, то оно может разрастись до впечатляющих размеров.
      • 0
        Забыл спросить. Откуда термин «нагруженное дерево»? Раньше просто встречал только «префиксное дерево».
        • +2
          Вообще у этой структуры великое множество названий — trie, нагруженное дерево, префиксное дерево, бор, луч, и наверняка еще парочка о которых я не знаю. Помню у Ахо и Ульмана пояснялось происхождение большинства названий.

          В первой прочитанной мною статье эта структура называлась нагруженным деревом, с тех пор и употребляю это название.
          • 0
            Добавьте хоть в теги альтернативные названия.
            А ещё лучше и в начале статьи список названий.
            А то до самого конца преследовала мысль «Чем это отличается от бора?»
        • 0
          По сравнение с хеш таблицами, как и написано в статье, будет занимать меньше места, если у нескольких ключей префиксы одинаковы.

          Да и специфика налицо: поддеревья по префиксу далеко не любая структура выдаст быстро. Так что использование памяти компенсируется.
        • +1
          Спасибо большое за статью, а теги мы и читаем (ну иногда точно читаем :))))
          • +1
            На Хабре появился последователь Skiminok'а? :) Поддерживаю.
            • +1
              Спасибо, спасибо.

              Самому очень нравятся его статьи про DSU и декартовы деревья.
              • +3
                Спасибо :)
                Эта статья, в свою очередь, тоже замечательна.

                Стоит упомянуть здесь одну из лучших книг по строковым алгоритмам и структурам данных, связанным с ними:
                Дэн Гасфилд, «Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология»
                • 0
                  Префиксные деревья — это вычислительная ботаника? =)
                  • +1
                    Огромное количество эффективных алгоритмов на строках и структур данных для быстрых операций с ними (в том числе бор) были разработаны, когда биологам потребовалось анализировать цепочки ДНК колоссальной длины.
            • 0
              Стоило бы раздел «Зачем все это нужно» поставит сразу после «Что это ?» и раскрыть пошире область применения. Почему то не хочется читать как удалять/добавлять/делать что-то, если не понятно зачем вообще все это надо.
              • +2
                Иненно так я поисковые подсказки реализовывал на одном из проектов. Там, правда, добавил такую характеристику узлам, как частота, чтобы показывать наиболее популярные запросы первыми.
              • 0
                а вот, кстати, неплохая реализация trie на C99: hg.atheme.org/libmowgli/libmowgli/file/tip/src/libmowgli/mowgli_patricia.c
                • 0
                  *Сглатываю слюну*, мне казалось, что реализация не доходит и до 100 строк, а тут целоая 1000.

                  Так как комменты могу писать раз в 5 минут, объясните пожалуйста, как алгоритм поиска работатет за O(|Key|)? Разве мы у каждого родителя не должны проверить всех его потомков? В худшем случае это работает O(число потомков), или есть более быстрый способ поиска «нужного» потомка? Или O(|Key|) подразумевает проход по всем потомкам и данного родителя?
                  • +1
                    Ложная тревога. Мощность алфавита — константа, извиняюсь.
                    • 0
                      Там по ссылке гораздо усложнённый вариант.
                      Я когда бор пишу, он у меня от силы несколько десятков строк занимает.
                      • –1
                        Извините, не я автор, я сам этот код увидел три дня назад, когда отлаживал Audacious :) Тогда же узнал, что это такое и как работает, хотя код до конца покамест не понимаю.
                    • 0
                      Я вот когда был в ЛКШ, попал в параллеь В', и самое зубодробительное что там было — скорее всего геометрия. На пол параллели выше (из параллели В) люди ходили и разбирались с этими деревьями, искали ключи, я стоял как дурак и думал, что за… Какие ключи??!!!
                      Вывод: После небольшого экскурса автора в деревья я больше не буду стоять деревом при их виде.
                      И еще вопросик, где можно найти материал почитать про различные алгоритмы и структуры, чтобы было написано понятным языком, примерно как у вас.
                    • 0
                      Иллюстрации красивые. В чем вы их рисовали?
                      • 0
                        В Microsoft Visio 2010.
                      • 0
                        После этого можно подняться от «отключенного» узла к корню, попутно удаляя все узлы которые являются листьями, однако экономия памяти в данном случае не существенна, а для эффективного определения того, является ли узел листом потребуется вводить дополнительную характеристику узла.

                        Думается, можно не вводить дополнительную характеристику, а просто удалять при подъёме пустые узлы до первого непустого.
                        • 0
                          Можно, однако я написал
                          для эффективного определения того, является ли узел листом

                          Если не хранить в узле количество его потомков, то для определения того является ли узел листом нужно будет проверить существование каждого из n его возможных потомков, где n — мощность алфавита.
                      • 0
                        Спасибо, почитал перед ГОСАМИ))

                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.