stringtranslate.com

Трие

Изображение trie. Один пустой круг, представляющий корневой узел, указывает на три дочерних узла. Стрелка к каждому дочернему узлу обозначена другой буквой. Сами дочерние узлы имеют похожий набор стрелок и дочерних узлов, причем узлы соответствуют полным словам, имеющим синие целые значения.
Trie для ключей "A", "to", "tea", "ted", "ten", "i", "in" и "inn". Каждое полное английское слово имеет произвольное целочисленное значение, связанное с ним.

В информатике trie ( / ˈ t r aɪ / , / ˈ t r iː / ), также называемый цифровым деревом или префиксным деревом , [1] является типом дерева поиска : в частности, k -арной древовидной структурой данных, используемой для поиска определенных ключей из набора. Эти ключи чаще всего являются строками , со связями между узлами, определяемыми не всем ключом, а отдельными символами . Чтобы получить доступ к ключу (восстановить его значение, изменить его или удалить), trie обходит в глубину , следуя связям между узлами, которые представляют каждый символ в ключе.

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

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

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

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

Идея trie-дерева для представления набора строк была впервые абстрактно описана Акселем Туэ в 1912 году. [2] [3] Trie-деревья были впервые описаны в компьютерном контексте Рене де ла Брианде в 1959 году. [4] [3] [5] : 336 

Идея была независимо описана в 1960 году Эдвардом Фредкиным , [6] который ввел термин trie , произнося его / ˈ t r iː / (как «дерево»), после среднего слога слова retrieval . [7] [8] Однако другие авторы произносят его / ˈ t r aɪ / (как «пытаться»), пытаясь отличить его словесно от «дерева». [7] [8] [3]

Обзор

Trie — это форма индексированной по строкам структуры данных поиска, которая используется для хранения списка слов в словаре, по которому можно осуществлять поиск таким образом, чтобы обеспечить эффективную генерацию списков завершения . [9] [10] : 1  Префиксное trie — это упорядоченная древовидная структура данных, используемая для представления набора строк в конечном алфавитном наборе, что позволяет эффективно хранить слова с общими префиксами. [1]

Trie могут быть эффективными в алгоритмах поиска строк , таких как предиктивный текст , приблизительное сопоставление строк и проверка орфографии по сравнению с бинарными деревьями поиска. [11] [8] [12] : 358  Trie можно рассматривать как древовидный детерминированный конечный автомат . [13]

Операции

Три представления наборов строк: море, продает и она.

Попытки поддерживают различные операции: вставку, удаление и поиск строкового ключа. Попытки состоят из узлов, содержащих ссылки, которые либо указывают на другие дочерние узлы суффикса, либо на null . Как и для каждого дерева, на каждый узел, кроме корня, указывает только один другой узел, называемый его родителем . Каждый узел содержит столько ссылок, сколько символов в применимом алфавите (хотя попытки, как правило, имеют значительное количество ссылок null). В некоторых случаях используемый алфавит — это просто алфавит кодировки символов , что приводит, например, к размеру 256 в случае (беззнакового) ASCII . [14] : 732 

Нулевые ссылки внутри дочерних узлов подчеркивают следующие характеристики: [14] : 734  [5] : 336 

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

Базовый тип структуры узлов в trie-дереве выглядит следующим образом: может содержать необязательный , который связан с каждым ключом, хранящимся в последнем символе строки, или терминальным узлом.

Идет поиск

Поиск значения в trie осуществляется на основе символов в ключе строки поиска, поскольку каждый узел в trie содержит соответствующую ссылку на каждый возможный символ в данной строке. Таким образом, следование строке в trie дает связанное значение для данного ключа строки. Нулевая ссылка во время поиска указывает на отсутствие ключа. [14] : 732-733 

Следующий псевдокод реализует процедуру поиска для заданного строкового ключа в корневом trie-дереве x . [15] : 135 

В приведенном выше псевдокоде x и key соответствуют указателю корневого узла trie и строке key соответственно. Операция поиска в стандартном trie занимает время, где — размер строкового параметра , а соответствует размеру алфавита . [16] : 754  Двоичные деревья поиска , с другой стороны, берут в худшем случае, поскольку поиск зависит от высоты дерева ( ) BST (в случае сбалансированных деревьев ), где и — количество ключей и длина ключей. [12] : 358 

Trie занимает меньше места по сравнению с BST в случае большого количества коротких строк, поскольку узлы разделяют общие начальные подпоследовательности строк и неявно хранят ключи. [12] : 358  Конечный узел дерева содержит ненулевое значение, и поиск считается успешным, если соответствующее значение найдено в trie, и неудачным , если нет. [14] : 733 

Вставка

Вставка в trie осуществляется с использованием наборов символов в качестве индексов для дочернего массива до тех пор, пока не будет достигнут последний символ строкового ключа. [14] : 733-734  Каждый узел в trie соответствует одному вызову процедуры радиксной сортировки , поскольку структура trie отражает выполнение шаблона радиксной сортировки сверху вниз. [15] : 135 

Если до достижения последнего символа строки key встречается нулевая ссылка, создается новый узел (строка 3). [14] : 745  Значение конечного узла присваивается входному значению; поэтому, если первое было ненулевым во время вставки, оно заменяется новым значением.

Удаление

Удаление пары ключ-значение из дерева включает в себя поиск конечного узла с соответствующим строковым ключом, маркировку конечного индикатора и значения как false и null соответственно. [14] : 740 

Ниже представлена ​​рекурсивная процедура удаления строкового ключа из корневого дерева ( x ).

Процедура начинается с проверки ключа ; null обозначает прибытие конечного узла или конца строки ключа. Если узел является конечным и не имеет потомков, он удаляется из trie (строка 14). Однако конец строки ключа без конечного узла указывает на то, что ключ не существует, поэтому процедура не изменяет trie. Рекурсия продолжается путем увеличения индекса ключа .

Замена других структур данных

Замена хэш-таблиц

Trie можно использовать вместо хэш-таблицы , по сравнению с которой он имеет следующие преимущества: [12] : 358 

Однако попытки менее эффективны, чем хэш-таблица, когда данные напрямую доступны на вторичном устройстве хранения, таком как жесткий диск, который имеет большее время случайного доступа , чем основная память . [6] Попытки также невыгодны, когда значение ключа не может быть легко представлено в виде строки, например, числа с плавающей точкой , где возможны множественные представления (например, 1 эквивалентно 1,0, +1,0, 1,00 и т. д.), [12] : 359  однако его можно однозначно представить как двоичное число в IEEE 754 , по сравнению с форматом дополнения до двух . [17]

Стратегии внедрения

Trie, реализованный как двоичное дерево left-child right-sibling : вертикальные стрелки — указатели потомков , пунктирные горизонтальные стрелки — указатели next . Набор строк, хранящихся в этом trie, — {baby, bad, bank, box, dad, dance }. Списки отсортированы для обеспечения обхода в лексикографическом порядке.

Попытки могут быть представлены несколькими способами, соответствующими различным компромиссам между использованием памяти и скоростью операций. [5] : 341  Использование вектора указателей для представления префикса потребляет огромное количество памяти; однако, объем памяти может быть уменьшен за счет времени выполнения, если для каждого вектора узлов используется односвязный список , поскольку большинство записей вектора содержат . [3] : 495 

Такие методы, как сокращение алфавита, могут облегчить высокую сложность пространства, переосмысливая исходную строку как длинную строку в меньшем алфавите, т. е. строку из n байтов можно альтернативно рассматривать как строку из 2 n четырехбитных единиц и хранить в trie с шестнадцатью указателями на узел. Однако в худшем случае для поиска необходимо посетить вдвое больше узлов, хотя требования к пространству снижаются в восемь раз. [5] : 347–352  Другие методы включают хранение вектора из 256 указателей ASCII в виде битовой карты из 256 бит, представляющей алфавит ASCII, что значительно уменьшает размер отдельных узлов. [18]

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

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

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

Сжатые попытки

Radix tree , также известное как сжатое trie , представляет собой оптимизированный по пространству вариант trie, в котором любой узел с одним потомком объединяется со своим родителем; устранение ветвей узлов с одним потомком приводит к лучшим метрикам как в пространстве, так и во времени. [20] [21] : 452  Это работает лучше всего, когда trie остается статичным, а набор хранимых ключей очень разрежен в их пространстве представления. [22] : 3–16 

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

Патриция деревья

Представление дерева Патрисии набора строк {in, integer, interval, string, structure} .

Деревья Patricia являются частной реализацией сжатого бинарного trie, которая использует двоичное кодирование строковых ключей в своем представлении. [23] [15] : 140  Каждый узел в дереве Patricia содержит индекс, известный как «пропускное число», который хранит индекс ветвления узла, чтобы избежать пустых поддеревьев во время обхода. [15] : 140-141  Наивная реализация trie потребляет огромное количество памяти из-за большего количества конечных узлов, вызванного разреженным распределением ключей; деревья Patricia могут быть эффективны в таких случаях. [15] : 142  [24] : 3 

Представление дерева Patricia показано справа. Каждое значение индекса, смежное с узлами, представляет собой «номер пропуска» — индекс бита, с которым должно быть решено ветвление. [24] : 3  Номер пропуска 1 в узле 0 соответствует позиции 1 в двоичном коде ASCII, где самый левый бит отличается в наборе ключей . [24] : 3-4  Номер пропуска имеет решающее значение для поиска, вставки и удаления узлов в дереве Patricia, и операция маскирования битов выполняется во время каждой итерации. [15] : 143 

Приложения

Структуры данных Trie обычно используются в предиктивных текстовых словарях или словарях автозаполнения , а также в алгоритмах приблизительного соответствия . [11] Trie обеспечивают более быстрый поиск, занимают меньше места, особенно когда набор содержит большое количество коротких строк, поэтому используются в проверке орфографии , приложениях для расстановки переносов и алгоритмах сопоставления самых длинных префиксов . [8] [12] : 358  Однако, если хранение слов словаря — это все, что требуется (т. е. нет необходимости хранить метаданные, связанные с каждым словом), минимальный детерминированный ациклический конечный автомат (DAFSA) или базисное дерево будут использовать меньше места для хранения, чем trie. Это связано с тем, что DAFSA и базисные деревья могут сжимать идентичные ветви из trie, которые соответствуют тем же суффиксам (или частям) разных сохраняемых слов. Строковые словари также используются в обработке естественного языка , например, для поиска лексикона текстового корпуса . [25] : 73 

Сортировка

Лексикографическая сортировка набора строковых ключей может быть реализована путем построения trie-дерева для заданных ключей и обхода дерева в прямом порядке ; [26] это также форма радиксной сортировки . [27] Trie также являются фундаментальными структурами данных для burstsort , которая примечательна тем, что является самым быстрым алгоритмом сортировки строк по состоянию на 2007 год, [28] что достигается за счет эффективного использования кэша ЦП . [29]

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

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

Поисковые системы в Интернете

Специализированный вид trie, называемый сжатым trie, используется в поисковых системах для хранения индексов — коллекции всех искомых слов. [31] Каждый конечный узел связан со списком URL-адресов — называемым списком вхождений — страниц, которые соответствуют ключевому слову. Trie хранится в основной памяти, тогда как вхождение хранится во внешнем хранилище, часто в больших кластерах , или индекс в памяти указывает на документы, хранящиеся во внешнем месте. [32]

Биоинформатика

Trie используются в биоинформатике , в частности, в программных приложениях для выравнивания последовательностей , таких как BLAST , которые индексируют все различные подстроки длины k (называемые k-мерами ) текста, сохраняя позиции их вхождений в сжатых базах данных последовательностей trie. [25] : 75 

Интернет-маршрутизация

Сжатые варианты попыток, такие как базы данных для управления базой данных пересылки (FIB), используются для хранения префиксов IP-адресов в маршрутизаторах и мостах для поиска на основе префиксов с целью разрешения операций на основе масок в IP-маршрутизации . [25] : 75 

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

Ссылки

  1. ^ ab Maabar, Maha (17 ноября 2014 г.). «Структура данных Trie». CVR, Университет Глазго . Архивировано из оригинала 27 января 2021 г. Получено 17 апреля 2022 г.
  2. ^ Туэ, Аксель (1912). «Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen». Скрифтер Удгивне Аф Виденскабс-Сельскабет и Христиания . 1912 (1): 1–67.Цитируется Кнутом.
  3. ^ abcd Кнут, Дональд (1997). "6.3: Цифровой поиск". Искусство программирования. Том 3: Сортировка и поиск (2-е изд.). Эддисон-Уэсли. стр. 492. ISBN 0-201-89685-0.
  4. ^ de la Briandais, René (1959). Поиск файлов с использованием ключей переменной длины (PDF) . Proc. Western J. Computer Conf. стр. 295–298. doi :10.1145/1457838.1457895. S2CID  10963780. Архивировано из оригинала (PDF) 2020-02-11.Цитируется Брассом и Кнутом.
  5. ^ abcd Брасс, Питер (8 сентября 2008 г.). Advanced Data Structures. Великобритания : Cambridge University Press . doi : 10.1017/CBO9780511800191. ISBN 978-0521880374.
  6. ^ ab Эдвард Фредкин (1960). "Trie Memory". Сообщения ACM . 3 (9): 490–499. doi : 10.1145/367390.367400 . S2CID  15384533.
  7. ^ ab Black, Paul E. (2009-11-16). "trie". Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий . Архивировано из оригинала 2011-04-29.
  8. ^ abcde Франклин Марк Лян (1983). Word Hy-phen-a-tion By Comp-um-er (PDF) (диссертация доктора философии). Стэнфордский университет. Архивировано (PDF) из оригинала 2005-11-11 . Получено 2010-03-28 .
  9. ^ "Trie". Школа искусств и наук, Ратгерский университет . 2022. Архивировано из оригинала 17 апреля 2022 года . Получено 17 апреля 2022 года .
  10. ^ Коннелли, Ричард Х.; Моррис, Ф. Локвуд (1993). «Обобщение структуры данных trie». Математические структуры в информатике . 5 (3). Сиракузский университет . : 381–418. doi :10.1017/S0960129500000803. S2CID  18747244.
  11. ^ ab Aho, Alfred V.; Corasick, Margaret J. (июнь 1975 г.). «Эффективное сопоставление строк: помощь в библиографическом поиске». Communications of the ACM . 18 (6): 333–340. doi : 10.1145/360825.360855 . S2CID  207735784.
  12. ^ abcdef Thareja, Reema (13 октября 2018 г.). «Хеширование и коллизия». Структуры данных с использованием C (2-е изд.). Oxford University Press . ISBN 9780198099307.
  13. ^ Дачук, Ян (24 июня 2003 г.). Сравнение алгоритмов построения минимальных, ациклических, детерминированных, конечных автоматов из наборов строк. Международная конференция по реализации и применению автоматов. Springer Publishing . С. 255–261. doi :10.1007/3-540-44977-9_26. ISBN 978-3-540-40391-3.
  14. ^ abcdefg Седжвик, Роберт ; Уэйн, Кевин (3 апреля 2011 г.). Алгоритмы (4-е изд.). Эддисон-Уэсли , Принстонский университет . ISBN 978-0321573513.
  15. ^ abcdef Gonnet, GH; Yates, R. Baeza (январь 1991). Справочник по алгоритмам и структурам данных: на языках Pascal и C (2-е изд.). Бостон , США : Addison-Wesley . ISBN 978-0-201-41607-7.
  16. ^ Патил, Варша Х. (10 мая 2012 г.). Структуры данных с использованием C++. Oxford University Press . ISBN 9780198066231.
  17. ^ S. Orley; J. Mathews. "Формат IEEE 754". Кафедра математики и компьютерных наук, Университет Эмори . Архивировано из оригинала 28 марта 2022 года . Получено 17 апреля 2022 года .
  18. ^ Беллекенс, Ксавье (2014). «Высокоэффективная схема сжатия памяти для систем обнаружения вторжений с ускорением на GPU». Труды 7-й Международной конференции по безопасности информации и сетей — SIN '14 . Глазго, Шотландия, Великобритания: ACM. стр. 302:302–302:309. arXiv : 1704.02272 . doi : 10.1145/2659651.2659723. ISBN 978-1-4503-3033-6. S2CID  12943246.
  19. ^ ab Willar, Dan E. (27 января 1983 г.). «Лог-логарифмические запросы в худшем случае возможны в пространстве O(n)». Information Processing Letters . 17 (2): 81–84. doi :10.1016/0020-0190(83)90075-3.
  20. ^ Сартадж Сахни (2004). «Структуры данных, алгоритмы и приложения на языке C++: Попытки». Университет Флориды . Архивировано из оригинала 3 июля 2016 года . Получено 17 апреля 2022 года .
  21. ^ Мехта, Динеш П.; Сахни, Сартадж (7 марта 2018 г.). «Попытки». Справочник по структурам данных и приложениям (2-е изд.). Chapman & Hall , Университет Флориды . ISBN 978-1498701853.
  22. ^ Ян Дачук; Стоян Михов; Брюс В. Уотсон; Ричард Э. Уотсон (1 марта 2000 г.). «Инкрементное построение минимальных ациклических конечных автоматов». Computational Linguistics . 26 (1). MIT Press : 3–16. arXiv : cs/0007009 . Bibcode : 2000cs........7009D. doi : 10.1162/089120100561601 .
  23. ^ "Patricia tree". Национальный институт стандартов и технологий . Архивировано из оригинала 14 февраля 2022 года . Получено 17 апреля 2022 года .
  24. ^ abc Crochemore, Maxime; Lecroq, Thierry (2009). "Trie". Энциклопедия систем баз данных. Бостон , США : Springer Publishing . Bibcode : 2009eds..book.....L. doi : 10.1007/978-0-387-39940-9. ISBN 978-0-387-49616-0– через HAL (открытый архив) .
  25. ^ abc Martinez-Prieto, Miguel A.; Brisaboa, Nieves; Canovas, Rodrigo; Claude, Francisco; Navarro, Gonzalo (март 2016 г.). «Практические сжатые строковые словари». Information Systems . 56. Elsevier : 73–108. doi :10.1016/j.is.2015.08.008. ISSN 0306-4379  .
  26. ^ Кярккяйнен, Юха. "Лекция 2" (PDF) . Университет Хельсинки . Предварительный порядок узлов в дереве совпадает с лексикографическим порядком строк, которые они представляют, предполагая, что потомки узла упорядочены по меткам ребер.
  27. ^ Каллис, Рафаэль (2018). "Адаптивное радиксное дерево (отчет № 14-708-887)" (PDF) . Университет Цюриха: Кафедра информатики, Научные публикации .
  28. ^ Ранджан Синха и Джастин Зобель и Дэвид Ринг (февраль 2006 г.). «Кэш-эффективная сортировка строк с использованием копирования» (PDF) . ACM Journal of Experimental Algorithmics . 11 : 1–32. doi :10.1145/1187436.1187439. S2CID  3184411.
  29. ^ J. Kärkkäinen и T. Rantala (2008). "Engineering Radix Sort for Strings". В A. Amir и A. Turpin и A. Moffat (ред.). String Processing and Information Retrieval, Proc. SPIRE . Lecture Notes in Computer Science. Vol. 5280. Springer. pp. 3–14. doi :10.1007/978-3-540-89097-3_3. ISBN 978-3-540-89096-6.
  30. ^ Джанкарло, Раффаэле (28 мая 1992 г.). «Обобщение суффиксного дерева для квадратных матриц с приложениями». Журнал SIAM по вычислениям . 24 (3). Общество промышленной и прикладной математики : 520–562. doi :10.1137/S0097539792231982. ISSN  0097-5397.
  31. ^ Ян, Лай; Сюй, Лида; Ши, Чжунчжи (23 марта 2012 г.). «Улучшенный динамический хэш-алгоритм TRIE для поиска в лексиконе». Enterprise Information Systems . 6 (4): 419–432. Bibcode :2012EntIS...6..419Y. doi :10.1080/17517575.2012.665483. S2CID  37884057.
  32. ^ Трансье, Фредерик; Сандерс, Питер (декабрь 2010 г.). «Разработка базовых алгоритмов поисковой системы текста в памяти». Труды ACM по информационным системам . 29 (1). Ассоциация вычислительной техники : 1–37. doi : 10.1145/1877766.1877768. S2CID  932749.

Внешние ссылки

На Викискладе есть медиафайлы по теме Трие .
Найдите слово trie в Викисловаре, бесплатном словаре.