Три

Три
Три
Тип	Дерево
Изобретенный	1960
Изобретён	Эдвард Фредкин , Аксель Туэ и Рене де ла Брианде
Операция
Временная сложность в обозначении большого О
Операция	Средний
Поиск	На )
Вставлять	На )
Удалить	На )
Пространственная сложность
Космос	На )

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

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

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

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

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

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

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

Обзор

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

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

Операции

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

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

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

Базовый тип структуры узлов в дереве следующий: ${\text{Node}}$ может содержать необязательный ${\text{Value}}$ , который связан с каждым ключом, хранящимся в последнем символе строки или терминальном узле.

structure Node
    Children Node[Alphabet-Size]
    Is-Terminal Boolean
    Value Data-Type
end structure

Идет поиск

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

Следующий псевдокод реализует процедуру поиска по заданной строке. ключ в корневом дереве х . ^{[ 15 ]}^: 135

Trie-Find(x, key)
    for 0 ≤ i < key.length do
        if x.Children[key[i]] = nil then
            return false
        end if
        x := x.Children[key[i]]
    repeat
    return x.Value

В приведенном выше псевдокоде х и key соответствуют указателю корневого узла trie и строковому ключу соответственно. Операция поиска в стандартном дереве занимает $O({\text{dm}})$ время, где ${\text{m}}$ размер строкового параметра ${\text{key}}$ , и ${\text{d}}$ соответствует размеру алфавита . ^{[ 16 ]}^: 754 двоичные деревья поиска принимают С другой стороны, $O(m\log n)$ в худшем случае, так как поиск зависит от высоты дерева ( $\log n$ ) BST (в случае сбалансированных деревьев ), где ${\text{n}}$ и ${\text{m}}$ количество ключей и длина ключей. ^{[ 12 ]}^: 358

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

Вставка

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

Trie-Insert(x, key, value)
    for 0 ≤ i < key.length do
        if x.Children[key[i]] = nil then
            x.Children[key[i]] := Node()
        end if
        x := x.Children[key[i]]
    repeat
    x.Value := value
    x.Is-Terminal := True

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

Удаление

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

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

Trie-Delete(x, key)
    if key = nil then
        if x.Is-Terminal = True then
            x.Is-Terminal := False
            x.Value := nil
        end if
        for 0 ≤ i < x.Children.length
            if x.Children[i] != nil
                return x
            end if
        repeat
        return nil
    end if
    x.Children[key[0]] := Trie-Delete(x.Children[key[0]], key[1:])
    return x

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Деревья Патрисии

Древовидное представление набора строк Патрисии {in, целое число, интервал, строка, структура} .

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

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

Приложения

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

Сортировка

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

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

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

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

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

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

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

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

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

См. также

Ссылки

^ Jump up to: ^а ^б Маабар, Маха (17 ноября 2014 г.). «Три структуры данных» . CVR, Университет Глазго . Архивировано из оригинала 27 января 2021 года . Проверено 17 апреля 2022 г.
^ Туэ, Аксель (1912). «О взаимном положении равных частей некоторых рядов знаков» . Скрифтер Удгивне Аф Виденскабс-Сельскабет и Христиания . 1912 (1): 1–67. Цитируется Кнутом.
^ Jump up to: ^а ^б ^с ^д Кнут, Дональд (1997). «6.3: Цифровой поиск». Искусство компьютерного программирования. Том 3: Сортировка и поиск (2-е изд.). Аддисон-Уэсли. п. 492. ИСБН 0-201-89685-0 .
^ де ла Брианде, Рене (1959). Поиск файлов с использованием ключей переменной длины (PDF) . Учеб. Western J. Computer Conf. стр. 295–298. дои : 10.1145/1457838.1457895 . S2CID 10963780 . Архивировано из оригинала (PDF) 11 февраля 2020 г. Цитируется Брассом и Кнутом.
^ Jump up to: ^а ^б ^с ^д Брасс, Питер (8 сентября 2008 г.). Расширенные структуры данных . Великобритания : Издательство Кембриджского университета . дои : 10.1017/CBO9780511800191 . ISBN 978-0521880374 .
^ Jump up to: ^а ^б Эдвард Фредкин (1960). «Три памяти» . Коммуникации АКМ . 3 (9): 490–499. дои : 10.1145/367390.367400 . S2CID 15384533 .
^ Jump up to: ^а ^б Блэк, Пол Э. (16 ноября 2009 г.). "попробуй" . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий . Архивировано из оригинала 29 апреля 2011 г.
^ Jump up to: ^а ^б ^с ^д ^и Франклин Марк Лян (1983). Word Hyphen-a-ation с помощью компьютера (PDF) (докторская диссертация). Стэнфордский университет. Архивировано (PDF) из оригинала 11 ноября 2005 г. Проверено 28 марта 2010 г.
^ «Три» . Школа искусств и наук Университета Рутгерса . 2022. Архивировано из оригинала 17 апреля 2022 года . Проверено 17 апреля 2022 г.
^ Коннелли, Ричард Х.; Моррис, Ф. Локвуд (1993). «Обобщение структуры данных дерева» . Математические структуры в информатике . 5 (3). Сиракузский университет : 381–418. дои : 10.1017/S0960129500000803 . S2CID 18747244 .
^ Jump up to: ^а ^б Ахо, Альфред В.; Корасик, Маргарет Дж. (июнь 1975 г.). «Эффективное сопоставление строк: помощь в библиографическом поиске» . Коммуникации АКМ . 18 (6): 333–340. дои : 10.1145/360825.360855 . S2CID 207735784 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж Тареджа, Рима (13 октября 2018 г.). «Хеширование и столкновение». Структуры данных с использованием C (2-е изд.). Издательство Оксфордского университета . ISBN 9780198099307 .
^ Дацюк, Ян (24 июня 2003 г.). Сравнение алгоритмов построения минимальных, ациклических, детерминированных конечных автоматов из наборов строк . Международная конференция по внедрению и применению автоматов. Издательство Спрингер . стр. 255–261. дои : 10.1007/3-540-44977-9_26 . ISBN 978-3-540-40391-3 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г Седжвик, Роберт ; Уэйн, Кевин (3 апреля 2011 г.). Алгоритмы (4-е изд.). Аддисон-Уэсли , Принстонский университет . ISBN 978-0321573513 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж Гонне, GH; Йейтс, Р. Баеза (январь 1991 г.). Справочник по алгоритмам и структурам данных: на языках Паскаль и Си (2-е изд.). Бостон , США : Аддисон-Уэсли . ISBN 978-0-201-41607-7 .
^ Патил, Варша Х. (10 мая 2012 г.). Структуры данных с использованием C++ . Издательство Оксфордского университета . ISBN 9780198066231 .
^ С. Орлей; Дж. Мэтьюз. «Формат IEEE 754» . Кафедра математики и информатики Университета Эмори . Архивировано из оригинала 28 марта 2022 года . Проверено 17 апреля 2022 г.
^ Беллекенс, Ксавье (2014). «Высокоэффективная схема сжатия памяти для систем обнаружения вторжений с ускорением на графическом процессоре». Материалы 7-й Международной конференции по безопасности информации и сетей-СИН '14 . Глазго, Шотландия, Великобритания: ACM. стр. 302:302–302:309. arXiv : 1704.02272 . дои : 10.1145/2659651.2659723 . ISBN 978-1-4503-3033-6 . S2CID 12943246 .
^ Jump up to: ^а ^б Уиллар, Дэн Э. (27 января 1983 г.). «Лог-логарифмические запросы диапазона наихудшего случая возможны в пространстве O(n)» . Письма об обработке информации . 17 (2): 81–84. дои : 10.1016/0020-0190(83)90075-3 .
^ Сартадж Сахни (2004). «Структуры данных, алгоритмы и приложения на C++: попытки» . Университет Флориды . Архивировано из оригинала 3 июля 2016 года . Проверено 17 апреля 2022 г.
^ Мехта, Динеш П.; Сахни, Сартадж (7 марта 2018 г.). "Пытается". Справочник по структурам данных и приложениям (2-е изд.). Чепмен и Холл , Университет Флориды . ISBN 978-1498701853 .
^ Ян Дацюк; Стоян Михов; Брюс В. Уотсон; Ричард Э. Уотсон (1 марта 2000 г.). «Инкрементное построение минимальных ациклических конечных автоматов» . Компьютерная лингвистика . 26 (1). Массачусетский технологический институт Пресс : 3–16. arXiv : cs/0007009 . Бибкод : 2000cs........7009D . дои : 10.1162/089120100561601 .
^ «Дерево Патрисии» . Национальный институт стандартов и технологий . Архивировано из оригинала 14 февраля 2022 года . Проверено 17 апреля 2022 г.
^ Jump up to: ^а ^б ^с Крошмор, Максим; Лекрок, Тьерри (2009). «Три». Энциклопедия систем баз данных . Бостон , США : Springer Publishing . Бибкод : 2009eds..book.....L . дои : 10.1007/978-0-387-39940-9 . ISBN 978-0-387-49616-0 — через HAL (открыть архив) .
^ Jump up to: ^а ^б ^с Мартинес-Прието, Мигель А.; Брисабоа, Ньевес; Кановас, Родриго; Клод, Франциско; Наварро, Гонсало (март 2016 г.). «Практические словари сжатых строк» . Информационные системы . 56 . Эльзевир : 73–108. дои : 10.1016/j.is.2015.08.008 . ISSN 0306-4379 .
^ Кярккяйнен, Юха. «Лекция 2» (PDF) . Университет Хельсинки . Предварительный порядок узлов в дереве такой же, как лексикографический порядок строк, которые они представляют, при условии, что дочерние элементы узла упорядочены по меткам ребер.
^ Каллис, Рафаэль (2018). «Адаптивное корневое дерево (отчет № 14-708-887)» (PDF) . Цюрихский университет: факультет информатики, исследовательские публикации .
^ Ранджан Синха, Джастин Зобель и Дэвид Ринг (февраль 2006 г.). «Эффективная сортировка строк с использованием копирования» (PDF) . Журнал экспериментальной алгоритмики ACM . 11 : 1–32. дои : 10.1145/1187436.1187439 . S2CID 3184411 .
^ Й. Кярккяйнен и Т. Рантала (2008). «Инженерная поразрядная сортировка строк». В А. Амире, А. Терпине и А. Моффате (ред.). Обработка строк и поиск информации, Учеб. ШПИЛЬ . Конспекты лекций по информатике. Том. 5280. Спрингер. стр. 3–14. дои : 10.1007/978-3-540-89097-3_3 . ISBN 978-3-540-89096-6 .
^ Джанкарло, Рафаэле (28 мая 1992 г.). «Обобщение суффиксного дерева на квадратные матрицы с приложениями» . SIAM Journal по вычислительной технике . 24 (3). Общество промышленной и прикладной математики : 520–562. дои : 10.1137/S0097539792231982 . ISSN 0097-5397 .
^ Ян, Лай; Сюй, Лида; Ши, Чжунчжи (23 марта 2012 г.). «Усовершенствованный алгоритм TRIE динамического хеширования для поиска по лексикону». Информационные системы предприятия . 6 (4): 419–432. Бибкод : 2012EntIS...6..419Y . дои : 10.1080/17517575.2012.665483 . S2CID 37884057 .
^ Транье, Фредерик; Сандерс, Питер (декабрь 2010 г.). «Разработка базовых алгоритмов системы текстового поиска в памяти» . Транзакции ACM в информационных системах . 29 (1). Ассоциация вычислительной техники : 1–37. дои : 10.1145/1877766.1877768 . S2CID 932749 .

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

Словарь алгоритмов и структур данных NIST: Trie

[cvr14-1] Jump up to: ^а ^б Маабар, Маха (17 ноября 2014 г.). «Три структуры данных» . CVR, Университет Глазго . Архивировано из оригинала 27 января 2021 года . Проверено 17 апреля 2022 г.

[thue-2] Туэ, Аксель (1912). «О взаимном положении равных частей некоторых рядов знаков» . Скрифтер Удгивне Аф Виденскабс-Сельскабет и Христиания . 1912 (1): 1–67. Цитируется Кнутом.

[KnuthVol3-3] Jump up to: ^а ^б ^с ^д Кнут, Дональд (1997). «6.3: Цифровой поиск». Искусство компьютерного программирования. Том 3: Сортировка и поиск (2-е изд.). Аддисон-Уэсли. п. 492. ИСБН 0-201-89685-0 .

[4] де ла Брианде, Рене (1959). Поиск файлов с использованием ключей переменной длины (PDF) . Учеб. Western J. Computer Conf. стр. 295–298. дои : 10.1145/1457838.1457895 . S2CID 10963780 . Архивировано из оригинала (PDF) 11 февраля 2020 г. Цитируется Брассом и Кнутом.

[brass-5] Jump up to: ^а ^б ^с ^д Брасс, Питер (8 сентября 2008 г.). Расширенные структуры данных . Великобритания : Издательство Кембриджского университета . дои : 10.1017/CBO9780511800191 . ISBN 978-0521880374 .

[triememory-6] Jump up to: ^а ^б Эдвард Фредкин (1960). «Три памяти» . Коммуникации АКМ . 3 (9): 490–499. дои : 10.1145/367390.367400 . S2CID 15384533 .

[DADS-7] Jump up to: ^а ^б Блэк, Пол Э. (16 ноября 2009 г.). "попробуй" . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий . Архивировано из оригинала 29 апреля 2011 г.

[Liang1983-8] Jump up to: ^а ^б ^с ^д ^и Франклин Марк Лян (1983). Word Hyphen-a-ation с помощью компьютера (PDF) (докторская диссертация). Стэнфордский университет. Архивировано (PDF) из оригинала 11 ноября 2005 г. Проверено 28 марта 2010 г.

[9] «Три» . Школа искусств и наук Университета Рутгерса . 2022. Архивировано из оригинала 17 апреля 2022 года . Проверено 17 апреля 2022 г.

[10] Коннелли, Ричард Х.; Моррис, Ф. Локвуд (1993). «Обобщение структуры данных дерева» . Математические структуры в информатике . 5 (3). Сиракузский университет : 381–418. дои : 10.1017/S0960129500000803 . S2CID 18747244 .

[aho75-11] Jump up to: ^а ^б Ахо, Альфред В.; Корасик, Маргарет Дж. (июнь 1975 г.). «Эффективное сопоставление строк: помощь в библиографическом поиске» . Коммуникации АКМ . 18 (6): 333–340. дои : 10.1145/360825.360855 . S2CID 207735784 .

[reema18-12] Jump up to: ^а ^б ^с ^д ^и ^ж Тареджа, Рима (13 октября 2018 г.). «Хеширование и столкновение». Структуры данных с использованием C (2-е изд.). Издательство Оксфордского университета . ISBN 9780198099307 .

[13] Дацюк, Ян (24 июня 2003 г.). Сравнение алгоритмов построения минимальных, ациклических, детерминированных конечных автоматов из наборов строк . Международная конференция по внедрению и применению автоматов. Издательство Спрингер . стр. 255–261. дои : 10.1007/3-540-44977-9_26 . ISBN 978-3-540-40391-3 .

[robert11-14] Jump up to: ^а ^б ^с ^д ^и ^ж ^г Седжвик, Роберт ; Уэйн, Кевин (3 апреля 2011 г.). Алгоритмы (4-е изд.). Аддисон-Уэсли , Принстонский университет . ISBN 978-0321573513 .

[gonnet91-15] Jump up to: ^а ^б ^с ^д ^и ^ж Гонне, GH; Йейтс, Р. Баеза (январь 1991 г.). Справочник по алгоритмам и структурам данных: на языках Паскаль и Си (2-е изд.). Бостон , США : Аддисон-Уэсли . ISBN 978-0-201-41607-7 .

[patil_12-16] Патил, Варша Х. (10 мая 2012 г.). Структуры данных с использованием C++ . Издательство Оксфордского университета . ISBN 9780198066231 .

[17] С. Орлей; Дж. Мэтьюз. «Формат IEEE 754» . Кафедра математики и информатики Университета Эмори . Архивировано из оригинала 28 марта 2022 года . Проверено 17 апреля 2022 г.

[18] Беллекенс, Ксавье (2014). «Высокоэффективная схема сжатия памяти для систем обнаружения вторжений с ускорением на графическом процессоре». Материалы 7-й Международной конференции по безопасности информации и сетей-СИН '14 . Глазго, Шотландия, Великобритания: ACM. стр. 302:302–302:309. arXiv : 1704.02272 . дои : 10.1145/2659651.2659723 . ISBN 978-1-4503-3033-6 . S2CID 12943246 .

[willar83-19] Jump up to: ^а ^б Уиллар, Дэн Э. (27 января 1983 г.). «Лог-логарифмические запросы диапазона наихудшего случая возможны в пространстве O(n)» . Письма об обработке информации . 17 (2): 81–84. дои : 10.1016/0020-0190(83)90075-3 .

[20] Сартадж Сахни (2004). «Структуры данных, алгоритмы и приложения на C++: попытки» . Университет Флориды . Архивировано из оригинала 3 июля 2016 года . Проверено 17 апреля 2022 г.

[21] Мехта, Динеш П.; Сахни, Сартадж (7 марта 2018 г.). "Пытается". Справочник по структурам данных и приложениям (2-е изд.). Чепмен и Холл , Университет Флориды . ISBN 978-1498701853 .

[22] Ян Дацюк; Стоян Михов; Брюс В. Уотсон; Ричард Э. Уотсон (1 марта 2000 г.). «Инкрементное построение минимальных ациклических конечных автоматов» . Компьютерная лингвистика . 26 (1). Массачусетский технологический институт Пресс : 3–16. arXiv : cs/0007009 . Бибкод : 2000cs........7009D . дои : 10.1162/089120100561601 .

[23] «Дерево Патрисии» . Национальный институт стандартов и технологий . Архивировано из оригинала 14 февраля 2022 года . Проверено 17 апреля 2022 г.

[maxime09-24] Jump up to: ^а ^б ^с Крошмор, Максим; Лекрок, Тьерри (2009). «Три». Энциклопедия систем баз данных . Бостон , США : Springer Publishing . Бибкод : 2009eds..book.....L . дои : 10.1007/978-0-387-39940-9 . ISBN 978-0-387-49616-0 — через HAL (открыть архив) .

[prieto16-25] Jump up to: ^а ^б ^с Мартинес-Прието, Мигель А.; Брисабоа, Ньевес; Кановас, Родриго; Клод, Франциско; Наварро, Гонсало (март 2016 г.). «Практические словари сжатых строк» . Информационные системы . 56 . Эльзевир : 73–108. дои : 10.1016/j.is.2015.08.008 . ISSN 0306-4379 .

[26] Кярккяйнен, Юха. «Лекция 2» (PDF) . Университет Хельсинки . Предварительный порядок узлов в дереве такой же, как лексикографический порядок строк, которые они представляют, при условии, что дочерние элементы узла упорядочены по меткам ребер.

[27] Каллис, Рафаэль (2018). «Адаптивное корневое дерево (отчет № 14-708-887)» (PDF) . Цюрихский университет: факультет информатики, исследовательские публикации .

[cachestringsort-28] Ранджан Синха, Джастин Зобель и Дэвид Ринг (февраль 2006 г.). «Эффективная сортировка строк с использованием копирования» (PDF) . Журнал экспериментальной алгоритмики ACM . 11 : 1–32. дои : 10.1145/1187436.1187439 . S2CID 3184411 .

[stringradix-29] Й. Кярккяйнен и Т. Рантала (2008). «Инженерная поразрядная сортировка строк». В А. Амире, А. Терпине и А. Моффате (ред.). Обработка строк и поиск информации, Учеб. ШПИЛЬ . Конспекты лекций по информатике. Том. 5280. Спрингер. стр. 3–14. дои : 10.1007/978-3-540-89097-3_3 . ISBN 978-3-540-89096-6 .

[30] Джанкарло, Рафаэле (28 мая 1992 г.). «Обобщение суффиксного дерева на квадратные матрицы с приложениями» . SIAM Journal по вычислительной технике . 24 (3). Общество промышленной и прикладной математики : 520–562. дои : 10.1137/S0097539792231982 . ISSN 0097-5397 .

[Xu12-31] Ян, Лай; Сюй, Лида; Ши, Чжунчжи (23 марта 2012 г.). «Усовершенствованный алгоритм TRIE динамического хеширования для поиска по лексикону». Информационные системы предприятия . 6 (4): 419–432. Бибкод : 2012EntIS...6..419Y . дои : 10.1080/17517575.2012.665483 . S2CID 37884057 .

[32] Транье, Фредерик; Сандерс, Питер (декабрь 2010 г.). «Разработка базовых алгоритмов системы текстового поиска в памяти» . Транзакции ACM в информационных системах . 29 (1). Ассоциация вычислительной техники : 1–37. дои : 10.1145/1877766.1877768 . S2CID 932749 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

v т и Древовидные структуры данных
Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic Palindrome (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal d-ary Fibonacci Leftist Pairing Skew binomial Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree PH Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

v т и Структуры данных
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

v т и Струны
Строковая метрика	Approximate string matching Bitap algorithm Damerau–Levenshtein distance Изменить расстояние Сопоставление гештальт-образцов Расстояние Хэмминга Расстояние Яро – Винклера Расстояние Ли Автомат Левенштейна Расстояние Левенштейна Алгоритм Вагнера-Фишера
Алгоритм поиска строк	Алгоритм Апостола – Джанкарло Алгоритм поиска строк Бойера – Мура Алгоритм Бойера – Мура – Хорспула Алгоритм Кнута – Морриса – Пратта Алгоритм Рабина – Карпа Алгоритм Райта Триграммный поиск Алгоритм двустороннего сопоставления строк Алгоритм сопоставления строк Чжу – Такаока
Поиск нескольких строк	Ахо – Корасик Алгоритм Комментца-Вальтера
Регулярное выражение	Сравнение механизмов регулярных выражений Регулярная грамматика Конструкция Томпсона Недетерминированный конечный автомат
Выравнивание последовательности	ВЗРЫВ Алгоритм Хиршберга Алгоритм Нидлмана – Вунша Алгоритм Смита – Уотермана
Структура данных	ДАФСА Суффиксный массив Суффиксный автомат Суффиксное дерево Обобщенное суффиксное дерево Веревка Тернарное дерево поиска Три
Другой	Разбор Сопоставление с образцом Сопоставление сжатого шаблона Самая длинная общая подпоследовательность Самая длинная общая подстрока Последовательный анализ шаблонов Сортировка Системы перезаписи строк Строковые операции