✖


Jump to content

Три

Это хорошая статья. Нажмите здесь для получения дополнительной информации.

Три
Тип Дерево
Изобретенный 1960
Изобретён Эдвард Фредкин , Аксель Туэ и Рене де ла Брианде
Временная сложность в обозначении большого О
Операция Средний Худший случай
Поиск На ​ ) На ​ )
Вставлять На ​ ) На ​ )
Удалить На ​ ) На ​ )
Пространственная сложность
Космос На ​ ) На ​ )
Изображение дерева. Один пустой кружок, представляющий корневой узел, указывает на трех дочерних узлов. Стрелка, указывающая на каждого ребенка, отмечена отдельной буквой. Сами дочерние элементы имеют аналогичный набор стрелок и дочерних узлов, причем узлы соответствуют полным словам, имеющим синие целочисленные значения.
Набор ключей «A», «to», «tea», «ted», «ten», «i», «in» и «inn». С каждым полным английским словом связано произвольное целочисленное значение.

В информатике дерево ) ( / ˈ 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 

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

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

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 и строковому ключу соответственно. Операция поиска в стандартном дереве занимает время, где размер строкового параметра , и соответствует размеру алфавита . [16] : 754  двоичные деревья поиска принимают С другой стороны, в худшем случае, так как поиск зависит от высоты дерева ( ) BST (в случае сбалансированных деревьев ), где и количество ключей и длина ключей. [12] : 358 

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

Вставка [ править ]

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

1
2
3
4
5
6
7
8
9

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 

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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 

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

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

Стратегии реализации [ править ]

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

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

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

Побитовые попытки [ править ]

См. также: x-fast trie и побитовое дерево с растровым изображением.

Побитовые попытки используются для удовлетворения огромных требований к пространству для узлов дерева в наивных простых реализациях векторов указателей. Каждый символ в наборе строковых ключей представлен отдельными битами, которые используются для перемещения по дереву по строковому ключу. Реализации этих типов дерева используют векторизованные инструкции ЦП для поиска первого установленного бита во вводе ключа фиксированной длины (например 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, где самый левый бит отличается в наборе ключей. . [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 

См. также [ править ]

Ссылки [ править ]

  1. ^ Jump up to: Перейти обратно: а б Маабар, Маха (17 ноября 2014 г.). «Три структуры данных» . CVR, Университет Глазго . Архивировано из оригинала 27 января 2021 года . Проверено 17 апреля 2022 г.
  2. ^ Туэ, Аксель (1912). «О взаимном положении равных частей некоторых рядов знаков» . Скрифтер Удгивне Аф Виденскабс-Сельскабет и Христиания . 1912 (1): 1–67. Цитируется Кнутом.
  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 г. Цитируется Брассом и Кнутом.
  5. ^ Jump up to: Перейти обратно: а б с д Брасс, Питер (8 сентября 2008 г.). Расширенные структуры данных . Великобритания : Издательство Кембриджского университета . дои : 10.1017/CBO9780511800191 . ISBN  978-0521880374 .
  6. ^ Jump up to: Перейти обратно: а б Эдвард Фредкин (1960). «Три памяти» . Коммуникации АКМ . 3 (9): 490–499. дои : 10.1145/367390.367400 . S2CID   15384533 .
  7. ^ Jump up to: Перейти обратно: а б Блэк, Пол Э. (16 ноября 2009 г.). "попробуй" . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий . Архивировано из оригинала 29 апреля 2011 г.
  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 .
  11. ^ Jump up to: Перейти обратно: а б Ахо, Альфред В.; Корасик, Маргарет Дж. (июнь 1975 г.). «Эффективное сопоставление строк: помощь в библиографическом поиске» . Коммуникации АКМ . 18 (6): 333–340. дои : 10.1145/360825.360855 . S2CID   207735784 .
  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 .
  14. ^ Jump up to: Перейти обратно: а б с д и ж г Седжвик, Роберт ; Уэйн, Кевин (3 апреля 2011 г.). Алгоритмы (4-е изд.). Аддисон-Уэсли , Принстонский университет . ISBN  978-0321573513 .
  15. ^ Jump up to: Перейти обратно: а б с д и ж Гонне, GH; Йейтс, Р. Баеза (январь 1991 г.). Справочник по алгоритмам и структурам данных: на языках Паскаль и Си (2-е изд.). Бостон , США : Аддисон-Уэсли . ISBN  978-0-201-41607-7 .
  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 .
  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 г.
  24. ^ Jump up to: Перейти обратно: а б с Крошмор, Максим; Лекрок, Тьерри (2009). «Три». Энциклопедия систем баз данных . Бостон , США : Springer Publishing . Бибкод : 2009eds..book.....L . дои : 10.1007/978-0-387-39940-9 . ISBN  978-0-387-49616-0 — через HAL (открыть архив) .
  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) . Цюрихский университет: факультет информатики, исследовательские публикации .
  28. ^ Ранджан Синха, Джастин Зобель и Дэвид Ринг (февраль 2006 г.). «Эффективная сортировка строк с использованием копирования» (PDF) . Журнал экспериментальной алгоритмики ACM . 11 : 1–32. дои : 10.1145/1187436.1187439 . S2CID   3184411 .
  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 .
  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 .

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теме Три .
Поищите слово в Викисловаре, бесплатном словаре.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Trie&oldid=1225266189"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 982a011df3e97518007f6cb93326e048__1716453000
URL1:https://arc.ask3.ru/arc/aa/98/48/982a011df3e97518007f6cb93326e048.html
Заголовок, (Title) документа по адресу, URL1:
Trie - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)