Возможно, вы знали о дереве двоичного поиска (BST) - элегантной структуре данных для хранения значений (или пар ключ-значение), которая позволяет выполнять быстрый поиск, сортировку и все другие виды словарных операций. Для незнакомых: у каждого узла BST может быть не более двух дочерних узлов. Левый дочерний элемент меньше родителя, а правый ребенок больше. Данные ограничения приводят к созданию дерева, в котором значения хранятся в отсортированном порядке.

Зачем нужны попытки?

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

Чтобы получить представление, мы должны помнить, что деревья двоичного поиска поддерживают отсортированный список значений, и это достигается путем сравнения. Строки представляют собой последовательность символов, и сравнение двух строк включает последовательное сравнение их символов до тех пор, пока не будет обнаружено несоответствие. Предположим, что средняя длина строк равна L для строк N. Для операций поиска и вставки выполняется log N сравнений, которые равны высоте дерева, и для каждого сравнения мы можем иметь L сравнений символов в худшем случае. , что дает нам сложность O (L log N) для каждой операции. Это допустимо, если длина струн небольшая. Но ситуация будет ухудшаться по мере того, как длина строк увеличивается и становится порядка N.

Если бы мы могли как-то уменьшить количество ненужных сравнений символов, производительность значительно увеличилась бы. Структура данных Trie достигает той же цели.

Что такое ТРИ?

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

Так как же Trie предлагает нам преимущество перед BST? Сохраняя символы или части строки вместо всей строки. Это позволяет нам хранить префиксы, общие для двух или более строк в одном узле, и строка, которая должна быть вставлена ​​или найдена, не должна сравнивать свои символы с этим префиксом более одного раза.

Попытки - прекрасный пример компромиссов: они быстро и гибко выполняют строковые операции, но занимают много памяти.

Попытки можно представить разными способами. Я собираюсь поговорить о Radix Tries. Это символьное дерево, в котором узлы хранят ровно один символ.

Radix Tries

Каждый узел в Radix Trie (также известном как Standard Trie) имеет R разных узлов, где R представляет все возможные символы в алфавите (или Radix). Например, в английском алфавите всего 26 символов, а в греческом - всего 24 символа. Родительский узел Trie всегда равен нулю.

Путешествие по дереву

Теперь, когда структура Trie определена, как мы собираемся получить строки?

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

Нам нужно помнить еще одну вещь: хотя приведенное выше дерево показало только ссылки на узлы, в которых на самом деле присутствует символ, присутствуют и другие нулевые узлы. То есть все узлы, представленные в этом дереве, имеют ровно 26 узловых ссылок.

Вставка строки

Хорошо, у меня есть образец дерева выше, и я хочу вставить в него слово disc. Это легко сделать, выполнив следующие шаги:

  1. Начиная с корня, выберите первый символ c в строке. Если существует узел с символом c, связанный с ним, мы переходим к этому узлу, в противном случае мы создаем новый узел, связанный с этим символом.
  2. Мы выбираем следующий символ строки и снова проверяем его наличие в любом из связанных с ним узлов, перемещаясь вниз, если он найден, и создавая его, если нет.
  3. Мы повторяем вышеуказанные шаги до тех пор, пока из строки не перестанут выделяться символы. Здесь мы отмечаем узел или устанавливаем значение, которое позволит нам идентифицировать его как строку в будущем.

Удаление строки

Удалить строку так же просто, как вставить ее, если мы выполним следующие два шага:

  1. Мы проходим по дереву для поиска строки. Очевидно, что последний узел, в котором мы оказались, помечается, если строка существует, и, следовательно, мы снимаем отметку с него.
  2. Мы проверяем, все ли ссылки узла из него нулевые. Если это так, мы удаляем его и перемещаемся вверх по дереву, повторяя те же шаги, пока не получим отмеченный узел или не окажемся в корне.

Чем это полезно?

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

Представление

Что касается временной сложности, то наихудший сценарий операций поиска, вставки и удаления линейно пропорционален длине строки L. Это можно записать как O (L). Однако промах при поиске может быть быстрее в зависимости от древовидной структуры и самой строки.

Из-за размера дерева выполняется меньше работы, поскольку промежуточные узлы уже созданы.

Где это используется?

Мы закончили со всеми теоретическими концепциями, необходимыми до сих пор. Остается вопрос: Где мы собираемся его использовать?

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

Мы также можем использовать попытки в качестве структуры хранения словаря. Слова можно искать в словаре, и их соответствующие значения могут быть извлечены, если они существуют.

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