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

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

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

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

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

История, этимология и произношение [ править ]

Идея дерева для представления набора строк была впервые абстрактно описана Акселем Туэ в 1912 году. [1] [2] Попытки были впервые описаны в компьютерном контексте Рене де ла Бриандэ в 1959 году [3] [4] [ 2] идея была независимо описана в 1960 году Эдвард Фредкин , [5] , который ввел термин синтаксического дерева , произнесения его / т г я / (как «дерево»), после того, как средний слог поиска . [6] [7] Однако другие авторы произносить его / т г aɪ/ (как «попробовать»), пытаясь словесно отличить его от «дерева». [6] [7] [2]

Приложения [ править ]

Представление словаря [ править ]

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

Замена других структур данных [ править ]

Замена хеш-таблиц [ править ]

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

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

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

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

Представительство DFSA [ править ]

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

Алгоритмы [ править ]

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

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

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

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

def  find ( node :  Node ,  key :  str )  ->  Необязательно [ Any ]:  "" "Найти значение по ключу в узле." ""  для  char  в  ключе :  если  char  в  node . дети :  узел  =  узел . children [ char ]  else :  return  None  узел возврата  . ценить

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

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

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

def  insert ( node :  Node ,  key :  str ,  value :  Any )  ->  None :  "" "Вставить пару ключ / значение в узел." ""  for  char  in  key :  if  char  not  in  node . дети :  узел . children [ char ]  =  Node ()  node  =  node . дети [ символ ]  узел . ценить =  значение

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

def  delete ( root :  Node ,  key :  str )  ->  bool :  "" "Без промедления удалите ключ из дерева с корнем в` root`.  Верните, пусто ли дерево с корнем в `root`.  " ""  def  _delete ( node :  Node ,  key :  str ,  d :  int )  ->  bool :  "" "Очистить узел, соответствующий ключу [d], и удалить дочерний ключ [d + 1],  если это поддерево полностью пусто, и вернуть, был ли очищен `node`  .  " ""  if  d  ==  len ( key ):  node . value  =  None  else :  c  =  key [ d ]  if  c  in узел . children  и  _delete ( node . children [ c ],  key ,  d + 1 ):  del  node . children [ c ]  # Возвращает, является ли поддрие с корнем в `node` полностью пустым  возвращаемым  узлом . Значение  не является  None  и  LEN ( узел . детей )  ==  0 return  _delete ( корень ,  ключ ,  0 )

Автозаполнение [ править ]

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

def  keys_with_prefix ( root :  Node ,  prefix :  str )  ->  List [ str ]:  results :  List [ str ]  =  []  x  =  _get_node ( root ,  prefix )  _collect ( x ,  list ( prefix ),  results )  возвращает  результатыdef  _collect ( x :  Необязательный [ узел ],  префикс :  List [ str ],  results :  List [ str ])  ->  None :  "" "  Добавить ключи в узле` x`, соответствующие заданному префиксу, к `results`.  prefix: list символов  "" ",  если  x  равно  None :  вернуть,  если  x . значение  не равно  None : prefix_str = '' . присоединиться (    префикс )  результаты . добавить ( prefix_str )  для  c  в  x . дети :  префикс . append ( c )  _collect ( x . children [ c ],  prefix ,  results )  del  prefix [ - 1 ]  # удалить последний символ def  _get_node ( node :  Node ,  key :  str )  ->  Необязательно [ Node ]:  "" "  Найти узел по ключу. Это то же самое, что и функция` find`, определенная выше,  но возвращает сам найденный узел, а не найденный узел значение.  "" "  для  символа  в  ключе :  если  символ  в  узле . дети :  узел  =  узел . children [ char ]  else :  return  None  узел возврата

Сортировка [ править ]

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

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

Полнотекстовый поиск [ править ]

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

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

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

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

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

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

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

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

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

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

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

Попытки сжатия [ править ]

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

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

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

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

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

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

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

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

Внешняя память пытается [ править ]

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

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

  • Суффиксное дерево
  • Основное дерево
  • Направленный ациклический граф слов (он же DAWG)
  • Ациклические детерминированные конечные автоматы
  • Хеш-три
  • Детерминированные конечные автоматы
  • Джуди Массив
  • Алгоритм поиска
  • Расширяемое хеширование
  • Отображенное дерево хеш-массива
  • Префиксное хеш-дерево
  • Burstsort
  • Алгоритм Лулео
  • Кодирование Хаффмана
  • Ctrie
  • HAT-trie

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

  1. ^ Туэ, Аксель (1912). "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen" . Скриптер удгивне аф Виденскабс-Сельскабет и Христиания . 1912 (1): 1–67. Цитируется Кнутом.
  2. ^ a b c Кнут, Дональд (1997). «6.3: Цифровой поиск». Искусство программирования Том 3: Сортировка и поиск (2-е изд.). Эддисон-Уэсли. п. 492. ISBN. 0-201-89685-0.
  3. ^ де ла Бриандаис, Рене (1959). Поиск файлов с использованием ключей переменной длины (PDF) . Proc. Western J. Computer Conf. С. 295–298. Цитируется Брассом и Кнутом.
  4. ^ a b c d Брасс, Питер (2008). Расширенные структуры данных . Издательство Кембриджского университета. п. 336.
  5. ^ a b Эдвард Фредкин (1960). "Трие Память". Коммуникации ACM . 3 (9): 490–499. DOI : 10.1145 / 367390.367400 .
  6. ^ a b Блэк, Пол Э. (16 ноября 2009 г.). "трие" . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий . Архивировано 29 апреля 2011 года.
  7. ^ а б в г Франклин Марк Лян (1983). Слово Hy-phen-a -tion By Com-put-er (PDF) (докторская диссертация). Стэндфордский Университет. Архивации (PDF) с оригинала на 2005-11-11 . Проверено 28 марта 2010 .
  8. ^ Ахо, Альфред V .; Корасик, Маргарет Дж. (Июнь 1975 г.). «Эффективное сопоставление строк: помощь в библиографическом поиске» (PDF) . Коммуникации ACM . 18 (6): 333–340. DOI : 10.1145 / 360825.360855 .
  9. ^ a b Седжвик, Роберт; Уэйн, Кевин (12 июня 2020 г.). «Пытается» . algs4.cs.princeton.edu . Проверено 11 августа 2020 .
  10. ^ Kärkkäinen, Юха. «Лекция 2» (PDF) . Университет Хельсинки . Предварительный порядок узлов в дереве такой же, как лексикографический порядок строк, которые они представляют, при условии, что дочерние элементы узла упорядочены по меткам ребер.
  11. ^ Каллис, Рафаэль (2018). «Адаптивное основание Radix Tree (Отчет № 14-708-887)» (PDF) . Цюрихский университет: факультет информатики, исследовательские публикации .
  12. ^ Ranjan Синха и Джастин Зобель и Дэвид Ring (февраль 2006). «Эффективная кеш-сортировка строк с помощью копирования» (PDF) . ACM Journal of Experimental Algorithmics . 11 : 1–32. DOI : 10.1145 / 1187436.1187439 .
  13. ^ J. Kärkkäinen и Т. Рантала (2008). «Инженерная сортировка строк». В А. Амир, А. Турпин и А. Моффат (ред.). Обработка строк и поиск информации, Proc. SPIRE . Конспект лекций по информатике. 5280 . Springer. С. 3–14. DOI : 10.1007 / 978-3-540-89097-3_3 .
  14. ^ а б Эллисон, Ллойд. «Пытается» . Проверено 18 февраля 2014 .
  15. ^ Сахни, Сартадж. «Пытается» . Структуры данных, алгоритмы и приложения в Java . Университет Флориды . Проверено 18 февраля 2014 .
  16. ^ Bellekens, Xavier (2014). «Высокоэффективная схема сжатия памяти для систем обнаружения вторжений с ускорением на GPU». Материалы 7-й Международной конференции по безопасности информации и сетей - SIN '14 . Глазго, Шотландия, Великобритания: ACM. С. 302: 302–302: 309. arXiv : 1704.02272 . DOI : 10.1145 / 2659651.2659723 . ISBN 978-1-4503-3033-6.
  17. ^ Ли, Дуг. «Распределитель памяти» . Дата обращения 1 декабря 2019 . HTTP для исходного кода . Двоичное Trie описано в Версии 2.8.6, Раздел «Наложенные структуры данных», Структура «malloc_tree_chunk».
  18. ^ Jan Daciuk; Стоян Михов; Брюс У. Ватсон; Ричард Э. Уотсон (2000). "Инкрементальное построение минимальных ациклических конечных автоматов" . Компьютерная лингвистика . Ассоциация компьютерной лингвистики. 26 : 3–16. arXiv : cs / 0007009 . DOI : 10.1162 / 089120100561601 . Архивировано из оригинала на 2011-09-30 . Проверено 28 мая 2009 .В данной статье представлен метод прямого построения минимального ациклического автомата с конечными состояниями, который распознает заданный конечный список слов в лексикографическом порядке. Наш подход состоит в том, чтобы построить минимальный автомат за одну фазу, добавляя новые строки одну за другой и минимизируя результирующий автомат на лету. Альтернативный URL
  19. ^ Ульрих Германн; Эрик Джоанис; Сэмюэл Ларкин (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. В то же время их можно быстро отобразить в памяти и искать непосредственно во времени, линейном по длине ключа, без необходимости распаковывать весь файл. Накладные расходы на локальную декомпрессию во время поиска незначительны.
  20. ^ Аскитис, Николай; Зобель, Джастин (2008). «B-попытки для управления строками на диске» (PDF) . Журнал VLDB : 1–26. ISSN 1066-8888 .  

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

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