Trie

Trie (от англ. retrieval — «поиск», также «префиксное дерево», «бор», «луч») — это структура данных, представляющая собой упорядоченное дерево, используемое для хранения множества строк (или других последовательностей, например, чисел в двоичной записи). Ключевой особенностью Trie является то, что все строки, имеющие общий префикс, разделяют в дереве соответствующий путь от корня до узла, где префикс заканчивается. Это обеспечивает высокую скорость операций поиска, вставки и удаления, зависящую от длины строки, а не от общего количества строк в хранилище.

История

Концепция префиксного дерева была впервые предложена в 1959 году французским математиком Рене де ла Брианде (René de la Briandais) в его диссертации, посвящённой эффективному поиску в словарях. Однако широкое распространение и название «trie» (от retrieval) структура получила благодаря Эдварду Фредкину (Edward Fredkin), который в 1960 году описал её в контексте компьютерных наук. В 1968 году Дональд Кнут (Donald Knuth) в своём фундаментальном труде «Искусство программирования» закрепил термин, отметив, что произносится он как «tree» (дерево), чтобы избежать путаницы с «tree» в общем смысле (в русскоязычной традиции чаще используется произношение «трай» или «три»).

Первоначально Trie применялись в основном для реализации словарей и автодополнения в системах обработки текста. С развитием вычислительных мощностей и ростом объёмов данных область применения значительно расширилась.

Определение и основные свойства

Trie — это корневое дерево, в котором каждый узел, кроме корневого, ассоциирован с одним символом (или битом) алфавита. Путь от корня до конечного узла (терминального) соответствует строке. Ключевые свойства:

• Совместное использование префиксов: Строки с одинаковым началом («префиксом») идут по одному пути. Например, строки «кот» и «кошка» будут разделять путь «к» → «о».
• Эффективность поиска: Время поиска строки длиной m составляет O(m), независимо от количества строк n в дереве. Это значительно быстрее, чем в хеш-таблицах (O(1) в среднем, но с возможными коллизиями) или сбалансированных деревьях поиска (O(log n)).
• Память: Основной недостаток — потенциально высокое потребление памяти, так как каждый узел может хранить множество указателей на дочерние узлы (по одному на каждый возможный символ алфавита). Для английского алфавита это 26 указателей, для русского — 33, для Unicode — тысячи.

Устройство и реализация

Структура узла

Каждый узел Trie обычно содержит два компонента:

1. Массив указателей (или словарь) на дочерние узлы. Размер массива равен мощности алфавита. Если символ алфавита отсутствует среди дочерних узлов, соответствующий указатель равен null.
2. Флаг (или счётчик) конца строки. Отмечает, является ли данный узел концом какой-либо строки. В некоторых реализациях вместо флага может храниться значение (например, для реализации ассоциативного массива).

Операции

• Вставка: Начиная с корня, для каждого символа строки проверяется, существует ли соответствующий дочерний узел. Если нет — создаётся новый. После обработки последнего символа устанавливается флаг конца строки.
• Поиск: Аналогично вставке, но если на каком-то шаге дочерний узел отсутствует, строка не найдена. Если строка найдена, проверяется флаг конца строки (чтобы отличить «кот» от «котик»).
• Удаление: Рекурсивно удаляются узлы, при условии, что они не являются частью других строк и не имеют других дочерних узлов.

Оптимизации памяти

Для борьбы с избыточным потреблением памяти применяются различные техники:

• Сжатое префиксное дерево (Radix tree / Patricia trie): Узлы, имеющие только одного потомка, сливаются в один узел, который хранит не один символ, а целую подстроку. Это значительно уменьшает количество узлов.
• Троичное дерево поиска (Ternary search tree): Каждый узел хранит один символ и три указателя: на узел с меньшим символом, с равным символом и с большим символом. Это аналог бинарного дерева поиска, но для строк. Экономит память, но немного медленнее классического Trie.
• Использование хеш-таблиц для дочерних узлов: Вместо массива фиксированного размера используется динамическая хеш-таблица, хранящая только существующие дочерние узлы.

Виды и классификации

Стандартное префиксное дерево

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

Сжатое префиксное дерево (Radix Tree)

Оптимизированная версия, где узлы с единственным потомком объединяются. Широко используется в сетевых протоколах (например, для хранения маршрутов в IP-таблицах) и в базах данных (LSM-деревья).

Троичное дерево поиска (Ternary Search Tree)

Компромисс между скоростью и памятью. Особенно эффективно для алфавитов с большим количеством символов (например, Unicode).

Двоичное префиксное дерево (Binary Trie)

Частный случай, где алфавит состоит из двух символов (0 и 1). Используется для хранения двоичных чисел, IP-адресов и в криптографии (например, в структуре Merkle Tree).

Применение

Автодополнение и проверка орфографии

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

Словари и тезаурусы

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

Сетевые протоколы

В маршрутизации IP-пакетов (CIDR) используется сжатое префиксное дерево (Patricia trie) для хранения таблиц маршрутизации и выполнения longest prefix match (поиск по самому длинному совпадающему префиксу).

Базы данных

Trie используется в некоторых NoSQL-базах данных (например, в Tokyo Cabinet) и в качестве внутренней структуры для индексов в LSM-деревьях (LevelDB, RocksDB).

Компиляторы и обработка естественного языка

Применяется для построения лексического анализатора (lexer) и для хранения ключевых слов языка программирования. В NLP используется для поиска по словарю и для стемминга (поиска основы слова).

Криптография

В криптографии используется двоичное префиксное дерево (Merkle Tree) для проверки целостности данных и в блокчейн-технологиях.

Примеры

Пример 1: Словарь английских слов

Рассмотрим Trie, содержащий слова: «cat», «cap», «car», «card». Дерево будет выглядеть так:

`` (root) └── c └── a ├── t (конец слова) ├── p (конец слова) └── r (конец слова) └── d (конец слова) ``

Пример 2: Автодополнение в поисковой строке

При вводе пользователем префикса «ca» система может найти все слова, начинающиеся с «ca», например: «cat», «cap», «car», «card», «cable» и т.д.

Критика

Основным недостатком Trie является высокое потребление памяти, особенно при работе с большими алфавитами (например, Unicode). Для алфавита из 256 символов каждый узел будет хранить 256 указателей, что может быть неэффективно для разреженных данных. Кроме того, Trie неэффективен для хранения строк, которые имеют мало общих префиксов (например, случайные строки).

Альтернативой Trie являются хеш-таблицы (быстрее, но не поддерживают префиксный поиск) и сбалансированные деревья поиска (экономят память, но медленнее для префиксного поиска). Сжатые префиксные деревья и троичные деревья поиска частично решают проблему памяти, но вносят дополнительные накладные расходы на операции.

Источники

1. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley.
2. Fredkin, E. (1960). "Trie memory". Communications of the ACM, 3(9), 490-499.
3. de la Briandais, R. (1959). "File searching using variable length keys". Proceedings of the Western Joint Computer Conference, 295-298.
4. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.