Trie - Trie

Эта статья посвящена древовидной структуре данных. Для французской коммуны см. Три-сюр-Баиз.
Три для ключей «A», «to», «tea», «ted», «ten», «i», «in» и «inn». Обратите внимание, что в этом примере не все дочерние элементы отсортированы в алфавитном порядке слева направо, как должно быть (корень и узел 't').

В Информатика, а три, также называемый цифровое дерево или же префиксное дерево, это своего рода дерево поиска - приказано дерево структура данных используется для хранения динамический набор или же ассоциативный массив где ключи обычно струны. В отличие от двоичное дерево поиска, ни один узел в дереве не хранит ключ, связанный с этим узлом; вместо этого его позиция в дереве определяет ключ, с которым он связан; т.е. значение ключа распределяется по структуре. Все потомки узла имеют общий префикс строки, связанной с этим узлом, а корень связан с пустой строкой. Ключи обычно связаны с листьями, хотя некоторые внутренние узлы могут соответствовать интересующим ключам. Следовательно, ключи не обязательно связаны с каждым узлом. Для оптимизированного по пространству представления дерева префиксов см. компактное префиксное дерево.

В показанном примере ключи перечислены в узлах и значениях под ними. С каждым полным английским словом связано произвольное целочисленное значение. Дерево можно рассматривать как дерево в форме детерминированный конечный автомат. Каждый конечный язык генерируется trie-автоматом, и каждое дерево может быть сжато в детерминированный ациклический конечный автомат.

Хотя попытки можно вводить с помощью символьных строк, это не обязательно. Одни и те же алгоритмы могут быть адаптированы для выполнения аналогичных функций в упорядоченных списках любой конструкции; например, перестановки в списке цифр или фигур. В частности, побитовое дерево задается отдельными битами, составляющими любые двоичные данные фиксированной длины, например целое число или адрес памяти.

История, этимология и произношение

Впервые попытки были описаны Рене де ла Брианэ в 1959 году.[1][2]:336 Период, термин три был придуман два года спустя Эдвард Фредкин, кто произносит это /ˈтря/ (как «дерево»), после среднего слога поиск.[3][4] Однако другие авторы произносят это /ˈтраɪ/ (как «попробовать»), пытаясь словесно отличить это от «дерева».[3][4][5]

Приложения

В качестве замены других структур данных

Как обсуждается ниже,[куда? ] дерево имеет ряд преимуществ перед деревьями двоичного поиска.[6][нужны примеры ]

Дерево также можно использовать для замены хеш-таблица, перед которым имеет следующие преимущества:

  • Поиск данных в дереве выполняется быстрее в худшем случае, за время O (m) (где m - длина строки поиска), по сравнению с несовершенной хеш-таблицей. Несовершенная хеш-таблица может иметь конфликты ключей. Конфликт ключей - это отображение хэш-функцией различных ключей в одну и ту же позицию в хеш-таблице. Наихудшая скорость поиска в несовершенной хеш-таблице равна НА) время, но гораздо чаще O (1), с O (m) временем, потраченным на оценку хэша.
  • В дереве нет коллизий разных ключей.
  • Сегменты в дереве, аналогичные сегментам хэш-таблицы, в которых хранятся конфликты ключей, необходимы только в том случае, если один ключ связан с более чем одним значением.
  • Нет необходимости предоставлять хеш-функцию или изменять хеш-функции по мере добавления большего количества ключей в дерево.
  • Trie может обеспечить алфавитный порядок записей по ключам.

Однако у дерева есть и недостатки по сравнению с хеш-таблицей:

  • Поиск в Trie может быть медленнее, чем поиск в хэш-таблице, особенно если доступ к данным осуществляется напрямую на жестком диске или другом вторичном запоминающем устройстве, где время произвольного доступа больше по сравнению с основной памятью.[7]
  • Некоторые ключи, такие как числа с плавающей запятой, могут приводить к длинным цепочкам и префиксам, которые не имеют особого смысла. Тем не менее, побитовое дерево может работать со стандартными числами с плавающей запятой в стандартном формате IEEE с плавающей запятой в одном и двух форматах.[нужна цитата ]
  • Для некоторых попыток может потребоваться больше места, чем для хэш-таблицы, поскольку память может быть выделена для каждого символа в строке поиска, а не для отдельного фрагмента памяти для всей записи, как в большинстве хеш-таблиц.

Представление словаря

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

Попытки также хорошо подходят для реализации алгоритмов приблизительного сопоставления,[8] включая те, которые используются в проверка орфографии и перенос[4] программного обеспечения.

Индексация срока

А дерево дискриминации указатель срока хранит свою информацию в trie-структуре данных.[9]

Алгоритмы

Trie - это дерево узлов, поддерживающее операции поиска и вставки. Find возвращает значение для ключевой строки, а Insert вставляет строку (ключ) и значение в дерево. И Insert, и Find выполняются O (м) время, где m - длина ключа.

Для представления узлов в дереве можно использовать простой класс Node:

учебный класс Узел:    def __в этом__(себя) -> Никто:        # Обратите внимание, что использование словаря для детей (как в этой реализации)        # по умолчанию не будет лексикографически сортировать дочерние элементы, что является        # требуется лексикографической сортировкой в ​​разделе Сортировка.        # Для лексикографической сортировки мы можем вместо этого использовать массив узлов.        себя.дети: Диктовать[ул., Узел] = {}  # отображение персонажа на узел        себя.ценить: Необязательный[Любой] = Никто

Обратите внимание, что дети словарь символов для потомков узла; и говорят, что «конечный» узел - это тот, который представляет собой полную строку.
Значение trie можно посмотреть следующим образом:

def найти(узел: Узел, ключ: ул.) -> Необязательный[Любой]:    "" "Найти значение по ключу в узле." ""    за char в ключ:        если char в узел.дети:            узел = узел.дети[char]        еще:            возвращаться Никто    возвращаться узел.ценить

Можно использовать небольшие модификации этой процедуры.

  • чтобы проверить, есть ли в дереве какое-либо слово, которое начинается с заданного префикса (см. § Автозаполнение ), и
  • чтобы вернуть самый глубокий узел, соответствующий некоторому префиксу данной строки.

Вставка продолжается путем обхода дерева в соответствии со строкой, которую нужно вставить, а затем добавления новых узлов для суффикса строки, не содержащейся в дереве:

def вставлять(узел: Узел, ключ: ул., ценить: Любой) -> Никто:    "" "Вставить пару ключ / значение в узел." ""    за char в ключ:        если char нет в узел.дети:            узел.дети[char] = Узел()        узел = узел.дети[char]    узел.ценить = ценить

Удаление ключа может быть выполнено лениво (очищая только значение в узле, соответствующем ключу), или быстро, очищая все родительские узлы, которые больше не нужны. Нетерпеливое удаление описано здесь в псевдокоде:[10]

def Удалить(корень: Узел, ключ: ул.) -> bool:    "" "Быстро удалите ключ из дерева с корнем` root`.    Вернуть, пусто ли теперь дерево с корнем в `root`.    """        def _Удалить(узел: Узел, ключ: ул., d: int) -> bool:        "" "Очистить узел, соответствующий ключу [d], и удалить дочерний ключ [d + 1]        если это поддерево полностью пусто, и вернуть, был ли узел        очищено.        """        если d == len(ключ):            узел.ценить = Никто        еще:            c = ключ[d]            если c в узел.дети и _Удалить(узел.дети[c], ключ, d+1):                дель узел.дети[c]        # Возвращает, является ли поддрие с корнем в `node` полностью пустым        возвращаться узел.ценить является Никто и len(узел.дети) == 0    возвращаться _Удалить(корень, ключ, 0)

Автозаполнение

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

def keys_with_prefix(корень: Узел, префикс: ул.) -> Список[ул.]:    полученные результаты: Список[ул.] = []    Икс = _get_node(корень, префикс)    _собирать(Икс, список(префикс), полученные результаты)    возвращаться полученные результатыdef _собирать(Икс: Необязательный[Узел], префикс: Список[ул.], полученные результаты: Список[ул.]) -> Никто:    """    Добавить ключи под узлом `x`, соответствующие заданному префиксу` results`.    префикс: список символов    """    если Икс является Никто:        возвращаться    если Икс.ценить является нет Никто:        prefix_str = ''.присоединиться(префикс)        полученные результаты.добавить(prefix_str)    за c в Икс.дети:        префикс.добавить(c)        _собирать(Икс.дети[c], префикс, полученные результаты)        дель префикс[-1]  # удалить последний символ        def _get_node(узел: Узел, ключ: ул.) -> Необязательный[Узел]:    """    Найдите узел по ключу. Это то же самое, что и функция `find`, определенная выше,    но возвращает сам найденный узел, а не значение найденного узла.    """    за char в ключ:        если char в узел.дети:            узел = узел.дети[char]        еще:            возвращаться Никто    возвращаться узел

Сортировка

Лексикографическая сортировка набора ключей может быть выполнена путем построения из них дерева, с лексикографической сортировкой дочерних узлов каждого узла и обходом его в Предварительный заказ, распечатывая любые значения либо во внутренних узлах, либо в листовых узлах.[11] Этот алгоритм представляет собой форму радиальная сортировка.[12]

A trie - это фундаментальная структура данных Burstsort, который (в 2007 г.) был самым быстрым из известных алгоритмов сортировки строк благодаря своей эффективной тайник использовать.[13] Теперь есть более быстрые.[14]

Полнотекстовый поиск

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

Стратегии реализации

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

Существует несколько способов представления попыток, соответствующих различным компромиссам между использованием памяти и скоростью операций. Основная форма - это форма связанного набора узлов, где каждый узел содержит массив дочерних указателей, по одному на каждый символ в алфавит (так что для английский алфавит, можно было бы хранить 26 дочерних указателей, а для алфавита байтов - 256 указателей). Это просто, но расточительно с точки зрения памяти: при использовании алфавита байтов (размер 256) и четырехбайтовых указателей каждому узлу требуется килобайт памяти, а при небольшом перекрытии префиксов строк - количество требуемых узлов. это примерно общая длина хранимых строк.[2]:341 Другими словами, узлы в нижней части дерева, как правило, имеют несколько дочерних элементов, и их много, поэтому структура тратит пространство на хранение нулевых указателей.[15]

Проблему хранения можно решить с помощью метода реализации, называемого сокращение алфавита, в результате чего исходные строки интерпретируются как более длинные строки меньшего алфавита. Например, строка п байты можно также рассматривать как строку 2п четырехбитные блоки и хранится в дереве с шестнадцатью указателями на узел. В худшем случае поисковые запросы должны посещать в два раза больше узлов, но требования к хранилищу снижаются в восемь раз.[2]:347–352

Альтернативная реализация представляет узел в виде тройки (символ, ребенок, следующий) и связывает потомков узла вместе как односвязный список: ребенок указывает на первого ребенка узла, следующий следующему дочернему элементу родительского узла.[15][16] Набор детей также можно представить в виде двоичное дерево поиска; одним из примеров этой идеи является троичное дерево поиска разработан Bentley и Sedgewick.[2]:353

Другой альтернативой, позволяющей избежать использования массива из 256 указателей (ASCII), как предлагалось ранее, является сохранение массива алфавита в виде 256-битного битового массива, представляющего алфавит ASCII, резко уменьшая размер узлов.[17]

Побитовые попытки

Побитовые попытки во многом такие же, как и обычное символьное дерево, за исключением того, что отдельные биты используются для обхода того, что фактически становится формой двоичного дерева. Как правило, реализации используют специальную инструкцию ЦП, чтобы очень быстро найти первый установленный бит в ключе фиксированной длины (например, GCC __builtin_clz () внутренняя). Это значение затем используется для индексации таблицы с 32 или 64 записями, которая указывает на первый элемент в поразрядном дереве с таким количеством начальных нулевых битов. Затем поиск продолжается путем проверки каждого последующего бита в ключе и выбора ребенок [0] или же ребенок [1] соответствующим образом, пока элемент не будет найден.

Хотя этот процесс может показаться медленным, он очень локален в кэше и хорошо распараллеливается из-за отсутствия зависимостей регистров и, следовательно, имеет отличную производительность на современных внеочередное исполнение ЦП. А красно-черное дерево например, работает намного лучше на бумаге, но очень недружелюбен к кешу и вызывает несколько конвейеров и TLB останавливается на современных процессорах, что ограничивает этот алгоритм задержкой памяти, а не скоростью процессора. Для сравнения, побитовое дерево редко обращается к памяти, а когда и делает, то только для чтения, что позволяет избежать накладных расходов на когерентность кэша SMP. Следовательно, он все чаще становится предпочтительным алгоритмом для кода, который выполняет множество быстрых вставок и удалений, таких как распределители памяти (например, последние версии знаменитого Распределитель Дуга Ли (dlmalloc) и его потомки ). Наихудший случай шагов поиска - это то же самое, что и биты, используемые для индексации бункеров в дереве.[18]

В качестве альтернативы, термин «поразрядное дерево» может в более общем смысле относиться к структуре двоичного дерева, содержащей целочисленные значения, сортируя их по их двоичному префиксу. Примером может служить x-fast trie.

Сжатие пытается

Сжатие дерева и объединение общих ветвей иногда может привести к значительному увеличению производительности. Лучше всего это работает при следующих условиях:

  • Дерево (в основном) статическое, поэтому вставка или удаление ключей не требуется (например, после массового создания дерева).
  • Нужны только поиски.
  • Узлы trie не привязаны к данным, зависящим от узла, или данные узлов являются общими.[19]
  • Общий набор хранимых ключей очень разрежен в пределах их пространства представления (поэтому сжатие окупается).

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

Такое сжатие также используется при реализации различных таблиц быстрого поиска для получения Unicode свойства персонажа. Они могут включать таблицы сопоставления случаев (например, для Греческий письмо число Пи, от Π до π), или таблицы поиска, нормализующие комбинацию базовых и комбинированных символов (например, a-умляут в Немецкий, ä, или далет -патах -дагеш -оле в Библейский иврит, דַּ֫). Для таких приложений представление аналогично преобразованию очень большой, одномерной, разреженной таблицы (например, кодовых точек Unicode) в многомерную матрицу их комбинаций с последующим использованием координат в гиперматрице в качестве строкового ключа несжатого файла. trie, чтобы представить получившийся символ. Затем сжатие будет состоять из обнаружения и объединения общих столбцов в гиперматрице для сжатия последнего измерения в ключе. Например, чтобы избежать сохранения полной многобайтовой кодовой точки Unicode для каждого элемента, образующего столбец матрицы, можно использовать группировки похожих кодовых точек. Каждое измерение гиперматрицы хранит начальную позицию следующего измерения, так что необходимо сохранить только смещение (обычно один байт). Результирующий вектор сам сжимается, когда он также является разреженным, поэтому каждое измерение (связанное с уровнем слоя в дереве) может быть сжато отдельно.

Некоторые реализации действительно поддерживают такое сжатие данных в динамических разреженных попытках и позволяют вставки и удаления в сжатых попытках. Однако обычно это требует значительных затрат, когда сжатые сегменты необходимо разделить или объединить. Необходимо найти компромисс между сжатием данных и скоростью обновления. Типичная стратегия - ограничить диапазон глобальных поисков для сравнения общих ветвей в разреженном дереве.[нужна цитата ]

Результат такого сжатия может выглядеть как попытка преобразовать дерево в ориентированный ациклический граф (DAG), потому что обратное преобразование из DAG в дерево очевидно и всегда возможно. Однако форма группы DAG определяется формой ключа, выбранного для индексации узлов, что, в свою очередь, ограничивает возможное сжатие.

Другая стратегия сжатия - «распутать» структуру данных в однобайтовый массив.[20]Такой подход устраняет необходимость в указателях узлов, существенно снижая требования к памяти. Это, в свою очередь, позволяет отображать память и использовать виртуальную память для эффективной загрузки данных с диска.

Еще один подход - «упаковать» дерево.[4] Лян описывает компактную реализацию разреженного упакованного дерева, применяемую к автоматическим перенос, в котором потомки каждого узла могут чередоваться в памяти.

Внешняя память пытается

Несколько вариантов trie подходят для поддержки наборов строк в внешняя память, включая суффиксные деревья. Сочетание дерева и B-дерево, называется B-trie также был предложен для этой задачи; по сравнению с деревьями суффиксов, они ограничены в поддерживаемых операциях, но также более компактны и быстрее выполняют операции обновления.[21]

Смотрите также

Рекомендации

  1. ^ де ла Бриандаис, Рене (1959). Поиск файлов с использованием ключей переменной длины. Proc. Western J. Computer Conf. С. 295–298. Цитируется Брассом.
  2. ^ а б c d Брасс, Питер (2008). Расширенные структуры данных. Издательство Кембриджского университета.
  3. ^ а б Блэк, Пол Э. (16 ноября 2009 г.). "trie". Словарь алгоритмов и структур данных. Национальный институт стандартов и технологий. В архиве из оригинала от 29.04.2011.
  4. ^ а б c d Франклин Марк Лян (1983). Слово Hy-phen-a -tion с помощью компьютера (PDF) (Докторская диссертация). Стэндфордский Университет. В архиве (PDF) из оригинала 11.11.2005. Получено 2010-03-28.
  5. ^ Кнут, Дональд (1997). «6.3: Цифровой поиск». Искусство программирования, том 3: Сортировка и поиск (2-е изд.). Эддисон-Уэсли. п. 492. ISBN  0-201-89685-0.
  6. ^ Бентли, Джон; Седжвик, Роберт (1998-04-01). "Деревья троичного поиска". Журнал доктора Добба. Доктора Добба. Архивировано из оригинал 23 июня 2008 г.
  7. ^ Эдвард Фредкин (1960). "Три памяти". Коммуникации ACM. 3 (9): 490–499. Дои:10.1145/367390.367400.
  8. ^ Ахо, Альфред V .; Корасик, Маргарет Дж. (Июнь 1975 г.). «Эффективное сопоставление строк: помощь в библиографическом поиске» (PDF). Коммуникации ACM. 18 (6): 333–340. Дои:10.1145/360825.360855.
  9. ^ Джон У. Уиллер; Guarionex Jordan.«Эмпирическое исследование индексации терминов в дарвиновской реализации модели эволюционного исчисления».2004.p. 5.
  10. ^ а б Седжвик, Роберт; Уэйн, Кевин (12 июня 2020 г.). "Пытается". algs4.cs.princeton.edu. Получено 2020-08-11.
  11. ^ Кярккяйнен, Юха. «Лекция 2» (PDF). Университет Хельсинки. Предварительный порядок узлов в дереве такой же, как лексикографический порядок строк, которые они представляют, при условии, что дочерние элементы узла упорядочены по меткам ребер.
  12. ^ Каллис, Рафаэль (2018). "Адаптивное основание системы корней" (отчет № 14-708-887) " (PDF). Цюрихский университет: Департамент информатики, исследовательские публикации.
  13. ^ Ранджан Синха, Джастин Зобель и Дэвид Ринг (февраль 2006 г.). «Эффективная кеш-сортировка строк с помощью копирования» (PDF). ACM Журнал экспериментальной алгоритмики. 11: 1–32. Дои:10.1145/1187436.1187439.
  14. ^ Я. Кярккяйнен и Т. Рантала (2008). «Инженерная сортировка строк». В А. Амир, А. Турпин и А. Моффат (ред.). Обработка строк и поиск информации, Proc. ШПИЛЬ. Конспект лекций по информатике. 5280. Springer. С. 3–14. Дои:10.1007/978-3-540-89097-3_3.
  15. ^ а б Эллисон, Ллойд. "Пытается". Получено 18 февраля 2014.
  16. ^ Сахни, Сартадж. "Пытается". Структуры данных, алгоритмы и приложения в Java. Университет Флориды. Получено 18 февраля 2014.
  17. ^ Беллекенс, Ксавье (2014). «Высокоэффективная схема сжатия памяти для систем обнаружения вторжений с ускорением на GPU». Материалы 7-й Международной конференции по безопасности информации и сетей - SIN '14. Глазго, Шотландия, Великобритания: ACM. С. 302: 302–302: 309. arXiv:1704.02272. Дои:10.1145/2659651.2659723. ISBN  978-1-4503-3033-6.
  18. ^ Ли, Дуг. "Распределитель памяти". Получено 1 декабря 2019. HTTP для исходного кода. Двоичное Trie описано в Версии 2.8.6, Раздел «Наложенные структуры данных», Структура «malloc_tree_chunk».
  19. ^ Ян Дачюк; Стоян Михов; Брюс В. Ватсон; Ричард Э. Уотсон (2000). «Инкрементальное построение минимальных ациклических конечных автоматов». Компьютерная лингвистика. Ассоциация компьютерной лингвистики. 26: 3–16. arXiv:cs / 0007009. Дои:10.1162/089120100561601. Архивировано из оригинал на 2011-09-30. Получено 2009-05-28. В данной статье представлен метод прямого построения минимального ациклического автомата с конечными состояниями, который распознает заданный конечный список слов в лексикографическом порядке. Наш подход состоит в том, чтобы построить минимальный автомат за одну фазу, добавляя новые строки одну за другой и минимизируя результирующий автомат на лету. Альтернативный URL
  20. ^ Ульрих Германн; Эрик Джоанис; Сэмюэл Ларкин (2009). «Плотно упакованные попытки: как уместить большие модели в память и заставить их загружаться быстро» (PDF). ACL Workshops: Proceedings of the Workshop on Software Engineering, Testing, and Quality Assurance for Natural Language Processing. Ассоциация компьютерной лингвистики. С. 31–39. Мы представляем Tightly Packed Tries (TPT), компактную реализацию сжатых структур Trie только для чтения с быстрой разбивкой на страницы по запросу и коротким временем загрузки. Мы демонстрируем преимущества TPT для хранения n-граммовых языковых моделей и таблиц фраз для статистический машинный перевод. Эти базы данных, закодированные как TPT, требуют меньше места, чем представления тех же данных в виде плоских текстовых файлов, сжатых с помощью утилиты gzip. В то же время их можно быстро отобразить в памяти и искать непосредственно во времени, линейном по длине ключа, без необходимости распаковывать весь файл. Накладные расходы на локальную декомпрессию во время поиска незначительны.
  21. ^ Аскитис, Николай; Зобель, Джастин (2008). «B-попытки для управления строками на диске» (PDF). Журнал VLDB: 1–26. ISSN  1066-8888.

внешняя ссылка