Префиксные деревья: автодополнение и поиск самого длинного префикса

Что это такое

Словарь NIST определяет trie как дерево для хранения строк с узлом для каждого общего префикса. Каждое ребро несёт один символ — байт, символ текста или бит, — а конечная метка или лист отмечает сохранённые ключи. Поиск проходит одно ребро на символ, поэтому стоимость зависит от длины ключа, а не от количества сохранённых ключей. Все ключи с общим префиксом находятся в поддереве под узлом этого префикса. Radix tree, или Patricia/сжатое префиксное дерево, объединяет цепочки узлов с единственным потомком в одно подписанное ребро для экономии памяти. Таблица маршрутизации IPv4 ядра Linux использует LC-trie; согласно документации, её поиск возвращается назад по дереву, чтобы найти самый длинный префикс, совпадающий с адресом назначения.

Почему это важно

С хеш-таблицами неудобны две операции: «все ключи, начинающиеся с X» и «самый длинный сохранённый ключ, являющийся префиксом X». Префиксное дерево превращает первую в обход поддерева, а вторую — в один спуск с запоминанием последнего пройденного конечного узла. Автодополнение, маршрутизаторы путей HTTP, поиск самого длинного IP-префикса, токенизаторы и списки блокировки сводятся к одной из них.

Как применять

• Сначала зафиксируйте алфавит. Проще всего байты; для текста одинаково нормализуйте вставку и поиск — Unicode NFC, свёртка регистра — и решите, представляют ли узлы кодовые точки или байты UTF-8.
• Выбирайте устройство узла по плотности алфавита: массив потомков для небольшого плотного алфавита, небольшой отсортированный массив или хеш-таблицу для разреженного, сжатие radix при длинных общих участках ключей.
• Автодополнение: спуститесь к узлу префикса, затем обходите с ограничением числа результатов. Храните счётчики узлов или кешированный top-k, чтобы выдавать «самые частые дополнения» без обхода всего поддерева.
• Самый длинный префикс: идите по запросу, запоминая самый глубокий встреченный конечный узел, и верните его при завершении или неудаче прохода.
• Прежде чем строить дерево, попробуйте отсортированный массив: bisect_left по префиксу, затем просмотр, пока элементы с него начинаются, обеспечивает автодополнение статических данных с гораздо меньшей памятью. Дерево окупается при частых обновлениях, запросах самого длинного префикса или очень длинных общих префиксах.

Подводные камни

Наивные узлы с 256 указателями занимают килобайты каждый; обычно проблема в памяти, а не скорости. При удалении нужно обрезать неконечные узлы, оставшиеся без потомков. Несовпадение нормализации делает ключи невидимыми. Рекурсивный обход длинных ключей упирается в ограничения стека. Префиксные деревья не отвечают на инфиксные, суффиксные или нечёткие запросы: для них нужны другие индексы.