Представьте себе проблему любимой поисковой системы. По мере того, как вы вводите текст в поле, всплывают предложения о том, что должно быть дальше. Как выполнить такую ​​сложную операцию - перебрать огромные объемы данных, чтобы найти все, что начинается с введенных вами символов.

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

Введите Trie

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

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

В нашем примере выше у нас есть дерево, содержащее три слова: копать, собака и выкопать.

Анатомия узла Trie

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

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

Если диаграмма выше представляет корневой узел, то этот массив показывает начало слов, начинающихся с aa, be, do. Это могло соответствовать словам трубкозуба, пчелы и осла. Каждое слово строится по мере того, как вы проходите по узлам дерева.

Это приводит ко второму, что понадобится нашим узлам - способу пометить последний символ в слове.

Чтобы обозначить это, последний узел имеет логическое значение, равное истине. Это называется «конечным узлом».

Давайте рассмотрим простой пример, используя слово «at».

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

У корневого узла есть массив, который представляет все символы в нашем алфавите.

Здесь корень показан с массивом с указателем в индексе 0. Этот указатель будет указывать на узел, содержащий следующий символ в слове.

Здесь вы можете видеть, что флаг «конец слова» указывает путь к родительскому узлу.

Контрольные точки

Поскольку слова, которые мы хотим найти, разбросаны по дереву, нам понадобится много узлов. К счастью, эта древовидная структура позволит очень быстро находить и вставлять наши слова. Надеюсь, вы заметили, что поиск и вставка в это дерево выполняется за O (n), где n - это размер нашего слова, а не размер нашего словаря.

Это колоссальное ускорение, когда у вас огромный словарь для поиска, а средний размер слова невелик.

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

На небольшом ноутбуке вставка системного словаря из 235 886 слов занимает целых 2,44 секунды.

С другой стороны, среднее время извлечения составило 0,000051 секунды (51 микросекунда), при этом извлечение замедлялось в зависимости от количества возвращенных совпадений.

При автозавершении всего лишь со значения «s», которое соответствует большому количеству слов, время поиска увеличивается до 0,048 секунды.

Вывод

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