Войти
Дерево для ключей «A», «to», «tea», «ted» "," десять "," я "," в "и" трактир ". Обратите внимание, что в этом примере не все дочерние элементы отсортированы в алфавитном порядке слева направо, как должно быть (корень и узел 't'). В информатике, trie, также называемое цифровым деревом или префиксным деревом, представляет собой разновидность дерева поиска - упорядоченного дерева структуры данных используется для хранения динамического набора или ассоциативного массива, где ключами обычно являются строки. В отличие от двоичного дерева поиска, ни один узел в дереве не хранит ключ, связанный с этим узлом; вместо этого его позиция в дереве определяет ключ, с которым он связан; т.е. значение ключа распределяется по структуре. Все потомки узла имеют общий префикс строки, связанной с этим узлом, а корень связан с пустой строкой . Ключи обычно связаны с листьями, хотя некоторые внутренние узлы могут соответствовать интересующим ключам. Следовательно, ключи не обязательно связаны с каждым узлом. Для оптимизированного по пространству представления дерева префиксов см. компактное дерево префиксов.
В показанном примере ключи перечислены в узлах и значениях под ними. С каждым полным английским словом связано произвольное целочисленное значение. Дерево можно рассматривать как древовидный детерминированный конечный автомат. Каждый конечный язык генерируется trie-автоматом, и каждое trie-дерево может быть сжато в детерминированный ациклический конечный автомат.
Хотя попытки могут быть снабжены ключами с помощью символьных строк, это не обязательно. Одни и те же алгоритмы могут быть адаптированы для выполнения аналогичных функций в упорядоченных списках любой конструкции; например, перестановки в списке цифр или фигур. В частности, побитовое дерево привязано к отдельным битам, составляющим любые двоичные данные фиксированной длины, например целое число или адрес памяти.
Попытки были впервые описаны Рене де ла Брианэ в 1959 году. Термин «trie» был придуман двумя годами позже Эдвардом Фредкином, который произносит его (как «дерево») после среднего слога поиска. Однако другие авторы произносят это слово (как «попробовать»), пытаясь словесно отличить его от «дерева».
Как описано ниже, дерево имеет ряд преимуществ перед деревьями двоичного поиска.
Дерево также может использоваться для замены хеш-таблицы, по сравнению с которым он имеет следующие преимущества:
Однако у trie есть и некоторые недостатки по сравнению с хеш-таблицей:
Обычное применение дерева - это сохранение прогнозируемого текста или автозаполнения словарь, например, найденный в мобильном телефоне. Такие приложения используют возможности дерева для быстрого поиска, вставки и удаления записей; однако, если все, что требуется - это хранить слова из словаря (т.е. хранение дополнительной информации для каждого слова не требуется), минимальный детерминированный ациклический конечный автомат (DAFSA) будет использовать меньше места, чем дерево. Это связано с тем, что DAFSA может сжимать идентичные ветви из дерева, которые соответствуют одним и тем же суффиксам (или частям) разных сохраняемых слов.
Попытки также хорошо подходят для реализации алгоритмов приблизительного сопоставления, в том числе используемых в программном обеспечении проверки орфографии и расстановки переносов.
A индекс термина хранит свою информацию в структуре данных trie.
Дерево представляет собой дерево узлов, которое поддерживает поиск и вставку операции. Find возвращает значение для ключевой строки, а Insert вставляет строку (ключ) и значение в дерево. И Insert, и Find выполняются за время O (m), где m - длина ключа.
Простой класс Node может использоваться для представления узлов в trie:
class Node: def __init __ (self) ->None: # Обратите внимание, что использование словаря для детей (как в этой реализации) # по умолчанию не будет лексикографически сортировать дочерние элементы, что # требуется лексикографической сортировкой в разделе Сортировка. # Для лексикографической сортировки мы можем вместо этого использовать массив узлов. self.children: Dict [str, Node] = {} # отображение символа на узел self.value: Необязательно [Any] = NoneОбратите внимание, что children- это словарь символов для дочерних узлов узла ; и говорят, что "конечный" узел - это узел, который представляет собой полную строку.. Значение trie можно найти следующим образом:
def find (node: Node, key: str) ->Optional [Any ]: "" "Найти значение по ключу в узле." "" For char in key: if char in node.children: node = node.children [char] else: return None return node.value
Небольшие изменения эту процедуру можно использовать
Вставка продолжается путем обхода дерева в соответствии со строкой, которая должна быть вставлена, а затем добавления новых узлов для суффикса строки, которая не содержится в дереве:
def insert (node: Node, key: str, value: Any) ->None: "" "Вставить пару ключ / значение в узел." "" Для char в ключе: если char нет в node.children: node.children [char] = Node () node = node.children [char] node.value = value
Удаление ключа может быть d один лениво (очищая только значение в узле, соответствующем ключу), или нетерпеливо очищая все родительские узлы, которые больше не нужны. Неторопливое удаление описано в псевдокоде здесь:
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 node.children и _delete (node.children [c], key, d + 1): del node.children [c] # Возвращает, является ли поддрие с корнем в `node` полностью пустым return node.value равно None и len (node.children) == 0 return _delete (root, key, 0)
Попытки могут использоваться для возврата списка ключей с заданным префиксом. Это также можно изменить, чтобы разрешить использование подстановочных знаков в поиске по префиксу.
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: список символов "" ", если x равно None: вернуть, если x.value не равно None: prefix_str = ''.join (prefix) results.append (prefix_str) for c in x.children: prefix.append (c) _collect (x.children [c], prefix, results) del prefix [-1] # удалить последний символ def _get_node (node: Node, key: str) ->Необязательно [Node] : "" "Найти узел по ключу. Это то же самое, что и функция` find`, определенная выше, но возвращает сам найденный узел, а не значение найденного узла. "" "Для char в ключе: if char в node.children: node = node.children [char] else: return None return node
Лексикографическая сортировка набора ключей может быть выполнено путем создания из них дерева с лексикографической сортировкой дочерних узлов каждого узла и обхода его в предварительном порядке, распечатывая только значения листьев. Этот алгоритм представляет собой форму Radix sort.
A trie - фундаментальная структура данных для Burstsort, который (в 2007 году) был самым быстрым из известных алгоритмов сортировки строк благодаря эффективному кешу . использовать. Теперь есть более быстрые.
Специальный вид дерева, называемый суффиксным деревом, может использоваться для индексации всех суффиксов в тексте в для быстрого полнотекстового поиска.
Дерево, реализованное как двоичное дерево с левым потомком и правым братом : вертикальные стрелки - дочерние указатели, пунктирные горизонтальные стрелки - следующие указатели. В этом дереве хранится набор строк: {ребенок, плохой, банк, ящик, папа, танец}. Списки отсортированы, чтобы обеспечить возможность обхода в лексикографическом порядке. Есть несколько способов представления попыток, соответствующих различным компромиссам между использованием памяти и скоростью операций. Основная форма - это форма связанного набора узлов, где каждый узел содержит массив дочерних указателей, по одному на каждый символ в алфавите (так что для английского алфавита можно было бы хранить 26 дочерних указателей и 256 указателей для алфавита байтов). Это просто, но расточительно с точки зрения памяти: при использовании алфавита байтов (размер 256) и четырехбайтовых указателей каждому узлу требуется килобайт памяти, а при небольшом перекрытии префиксов строк - количество требуемых узлов. это примерно общая длина хранимых строк. Другими словами, узлы в нижней части дерева, как правило, имеют мало дочерних элементов, а их много, поэтому структура тратит пространство на хранение нулевых указателей.
Проблема с хранением может быть решена с помощью метода реализации, называемого сокращение алфавита, в результате чего исходные строки интерпретируются как более длинные строки по меньшему алфавиту. Например, строку из n байтов можно альтернативно рассматривать как строку из 2n четырехбитовых единиц и сохранять в дереве с шестнадцатью указателями на узел. Поисковые запросы должны посещать в два раза больше узлов в худшем случае, но требования к хранилищу снижаются в восемь раз.
Альтернативная реализация представляет узел в виде тройки (символ, потомок, следующий) и связывает дочерние элементы узла вместе как односвязный список : дочерний элемент указывает на первого дочернего элемента узла, рядом со следующим дочерним элементом родительского узла. Набор дочерних элементов также можно представить как двоичное дерево поиска ; Одним из примеров этой идеи является троичное дерево поиска, разработанное Bentley и Sedgewick.
Другой альтернативой, позволяющей избежать использования массива из 256 указателей (ASCII), как предлагалось ранее, состоит в том, чтобы сохранить массив алфавита как битовую карту из 256 бит, представляющих алфавит ASCII, резко уменьшая размер узлов.
Побитовые попытки во многом аналогичны как обычное символьное дерево, за исключением того, что отдельные биты используются для обхода того, что фактически становится формой двоичного дерева. Как правило, реализации используют специальную инструкцию ЦП, чтобы очень быстро найти первый установленный бит в ключе фиксированной длины (например, в GCC __builtin_clz ()встроенный). Это значение затем используется для индексации таблицы с 32 или 64 записями, которая указывает на первый элемент в поразрядном дереве с таким количеством начальных нулевых битов. Затем поиск продолжается путем проверки каждого последующего бита в ключе и выбора child [0]или child [1]соответственно, пока элемент не будет найден.
Хотя этот процесс может показаться медленным, он очень локален в кэше и хорошо распараллеливается из-за отсутствия зависимостей регистров и, следовательно, фактически имеет отличную производительность при современном выполнении вне очереди ЦП. красно-черное дерево, например, намного лучше работает на бумаге, но очень недружелюбно к кешированию и вызывает остановку нескольких конвейеров и TLB на современных ЦП, что делает этот алгоритм скорее связанным с задержкой памяти. чем скорость процессора. Для сравнения, побитовое дерево редко обращается к памяти, а когда и делает, то только для чтения, что позволяет избежать накладных расходов на когерентность кэша SMP. Следовательно, он все чаще становится предпочтительным алгоритмом для кода, который выполняет множество быстрых вставок и удалений, таких как распределители памяти (например, недавние версии знаменитого распределителя памяти Дуга Ли (dlmalloc) и его потомков ). Наихудший случай шагов для поиска такой же, как и биты, используемые для индексации бункеров в дереве.
В качестве альтернативы, термин «побитовое дерево» может в более общем смысле относиться к структуре двоичного дерева, содержащей целочисленные значения, сортируя их по их двоичный префикс. Примером может служить x-fast trie.
Сжатие дерева и объединение общих ветвей иногда может привести к значительному увеличению производительности. Это лучше всего работает при следующих условиях:
Например, его можно использовать для представления разреженных битовых наборов ; то есть подмножества гораздо большего фиксированного перечислимого множества. В таком случае дерево задается позицией битового элемента в полном наборе. Ключ создается из строки битов, необходимых для кодирования целой позиции каждого элемента. Такие попытки имеют очень вырожденную форму с отсутствием многих ветвей. После обнаружения повторения общих шаблонов или заполнения неиспользуемых промежутков уникальные листовые узлы (битовые строки) могут быть легко сохранены и сжаты, уменьшая общий размер дерева.
Такое сжатие также используется при реализации различных таблиц быстрого поиска для получения свойств символа Unicode. Сюда могут входить таблицы преобразования регистра (например, для греческой буквы пи, от Π до π) или таблицы поиска, нормализующие комбинацию базовых и комбинированных символов (например, a- умлаут в немецком, ä, или далет - патах - дагеш - оле в библейском иврите, דַּ֫). Для таких приложений представление аналогично преобразованию очень большой, одномерной, разреженной таблицы (например, кодовых точек Unicode) в многомерную матрицу их комбинаций с последующим использованием координат в гиперматрице в качестве строкового ключа несжатого файла. trie, чтобы представить получившийся символ. Затем сжатие будет состоять из обнаружения и объединения общих столбцов в гиперматрице для сжатия последнего измерения в ключе. Например, чтобы избежать сохранения полной многобайтовой кодовой точки Unicode для каждого элемента, образующего столбец матрицы, можно использовать группировки похожих кодовых точек. Каждое измерение гиперматрицы хранит начальную позицию следующего измерения, так что необходимо сохранить только смещение (обычно один байт). Результирующий вектор сам сжимается, когда он также разрежен, поэтому каждое измерение (связанное с уровнем слоя в дереве) может быть сжато отдельно.
Некоторые реализации действительно поддерживают такое сжатие данных в динамических разреженных попытках и позволяют вставки и удаления в сжатых попытках. Однако обычно это требует значительных затрат, когда сжатые сегменты необходимо разделить или объединить. Необходимо найти компромисс между сжатием данных и скоростью обновления. Типичная стратегия - ограничить диапазон глобальных поисков для сравнения общих ветвей в разреженном дереве.
Результат такого сжатия может быть похож на попытку преобразования дерева в направленный ациклический граф (DAG), потому что обратное преобразование из DAG в дерево очевидно и всегда возможно. Однако форма группы DAG определяется формой ключа, выбранного для индексации узлов, что, в свою очередь, ограничивает возможное сжатие.
Другая стратегия сжатия - «распутать» структуру данных в однобайтовый массив. Такой подход устраняет необходимость в указателях узлов, существенно снижая требования к памяти. Это, в свою очередь, позволяет отображать память и использовать виртуальную память для эффективной загрузки данных с диска.
Еще один подход - «упаковать» дерево. Лян описывает компактную реализацию разреженного упакованного дерева, применяемого для автоматического переноса, в котором потомки каждого узла могут чередоваться в памяти.
Несколько вариантов дерева подходят для хранения наборов строк во внешней памяти , включая деревья суффиксов. Для этой задачи также была предложена комбинация дерева и B-дерева, называемого B-деревом; по сравнению с суффиксными деревьями, они ограничены в поддерживаемых операциях, но также более компактны, выполняя операции обновления быстрее.
 | На Wikimedia Commons есть материалы, связанные с Trie. |
 | Найдите trie в Wiktionary, бесплатном словаре. |
