Префиксное дерево

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

История

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

Основные свойства

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

Основные характеристики:

• Сложность поиска, вставки и удаления: O(L), где L — длина строки. Это не зависит от общего количества строк в словаре.
• Память: В наивной реализации каждый узел хранит массив ссылок на все возможные символы алфавита (например, 26 для латиницы, 33 для кириллицы). Это приводит к высокому расходу памяти, особенно при разреженном словаре. Существуют оптимизированные варианты (например, с использованием сжатых массивов или хеш-таблиц для дочерних узлов).
• Алфавит: Размер алфавита напрямую влияет на количество указателей в каждом узле.

Классификация и разновидности

### Стандартный бор (naive trie)

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

### Сжатый бор (radix tree, Patricia trie)

Вместо хранения одного символа в узле, сжатый бор хранит целые подстроки (префиксы) в одном узле. Это позволяет объединять узлы, из которых выходит только одна ветвь. Такая структура значительно уменьшает количество узлов и экономит память. Алгоритм PATRICIA (Practical Algorithm To Retrieve Information Coded In Alphanumeric) был предложен Дональдом Моррисоном в 1968 году.

### Бор с бинарным представлением (binary trie)

Используется для хранения бинарных строк (например, IP-адресов). Каждый узел имеет только два дочерних элемента (0 и 1). Широко применяется в маршрутизаторах для реализации алгоритмов поиска по таблицам маршрутизации (Longest Prefix Matching).

### Суффиксное дерево

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

Применение

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

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

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

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

Маршрутизация в компьютерных сетях

В IP-маршрутизации используется бинарный бор для хранения префиксов сетей (например, 192.168.0.0/16). При поиске маршрута для пакета алгоритм находит самый длинный совпадающий префикс (Longest Prefix Match), что позволяет определить, через какой интерфейс отправить пакет.

Компрессия данных

Некоторые алгоритмы сжатия (например, алгоритм Лемпеля — Зива — Велча, LZW) используют префиксные деревья для построения словаря повторяющихся последовательностей символов.

Биоинформатика

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

Пример реализации на Python

Ниже приведён простой пример реализации префиксного дерева для латинского алфавита (26 букв) с операциями вставки и поиска.

```python class TrieNode: def __init__(self): self.children = [None] * 26 self.is_end_of_word = False

class Trie: def __init__(self): self.root = TrieNode()

def _char_to_index(self, ch): return ord(ch) - ord('a')

def insert(self, word): node = self.root for ch in word: index = self._char_to_index(ch) if not node.children[index]: node.children[index] = TrieNode() node = node.children[index] node.is_end_of_word = True

def search(self, word): node = self.root for ch in word: index = self._char_to_index(ch) if not node.children[index]: return False node = node.children[index] return node.is_end_of_word ```

Преимущества и недостатки

Преимущества:

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

Недостатки:

• Высокое потребление памяти: В наивной реализации каждый узел хранит массив указателей размером с алфавит, что может быть расточительно для больших алфавитов (например, Юникод).
• Сложность реализации: Оптимизированные версии (сжатые боры, боры с динамическим выделением) требуют более сложного кода.
• Неэффективность для коротких строк: Если словарь состоит из коротких строк, накладные расходы на хранение узлов могут превышать выгоду от общего префикса.

Критика и альтернативы

Несмотря на широкое распространение, префиксное дерево не является универсальным решением. В ситуациях, где требуется минимальное потребление памяти, предпочтительнее использовать хеш-таблицы или сбалансированные деревья поиска (например, красно-чёрные деревья). Однако хеш-таблицы не поддерживают префиксный поиск и не гарантируют порядок обхода. Для задач, где важна сортировка ключей, часто используют B-деревья или их варианты (например, в файловых системах и базах данных). В современных системах автодополнения часто применяют комбинацию префиксного дерева с вероятностными моделями (например, на основе частотности слов) или с использованием суффиксных автоматов.

Интересные факты

• Префиксное дерево лежит в основе алгоритма сортировки строк за линейное время (поразрядная сортировка с использованием бора).
• В некоторых реализациях операционной системы Linux (например, в подсистеме работы с файловыми системами) используется структура, похожая на сжатый бор, для хранения путей к файлам.
• В 2019 году группа исследователей из Массачусетского технологического института (MIT) предложила вариант префиксного дерева, оптимизированный для работы на графических процессорах (GPU), что позволило ускорить обработку больших словарей в задачах машинного перевода.

Источники

• Кнут Д. Искусство программирования. Том 3. Сортировка и поиск. — Вильямс, 2007.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — Вильямс, 2013.
• Fredkin E. Trie Memory. Communications of the ACM, 1960.
• Morrison D. R. PATRICIA — Practical Algorithm To Retrieve Information Coded In Alphanumeric. Journal of the ACM, 1968.
• de la Briandais R. File Searching Using Variable Length Keys. Proceedings of the Western Joint Computer Conference, 1959.