Префиксное дерево (trie): как телефон угадывает слово по трём буквам

Чтобы быстро находить слова по их началу, удобно хранить не сами слова, а их буквы в виде ветвящегося дерева.

В trie общая приставка нескольких слов хранится ровно один раз — поэтому подсказки появляются мгновенно, ещё до того как вы дописали слово.

Задача автодополнения

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

Нужна структура, которая организована по буквам, чтобы по приставке сразу прыгнуть к нужной ветке. Это и есть префиксное дерево, оно же trie (от слова retrieval — «извлечение»).

Как устроено дерево букв

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

Например, слова «код», «кодер» и «кошка» начинаются на «ко». В trie это значит, что буквы «к» и «о» хранятся один раз, а дальше дерево ветвится: на «д» (к «код» и «кодер») и на «ш» (к «кошка»). Чем больше у слов общих начал, тем компактнее и быстрее дерево.

Где кончается слово

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

Почему это быстро

Чтобы найти все подсказки для приставки «ко», мы делаем всего два шага вниз по дереву — по букве «к», потом «о» — и оказываемся в узле, от которого растут все слова с этим началом. Дальше остаётся собрать всё поддерево. Главное: время поиска зависит только от длины введённого слова, а не от размера словаря. Хоть миллион слов в trie — приставку из четырёх букв мы найдём за четыре шага.

Trie на практике

Узел дерева — это словарь «буква → следующий узел» плюс флажок конца слова. Вот компактная реализация автодополнения:

class Trie:
    def __init__(self):
        self.children = {}
        self.is_word = False

    def add(self, word):
        node = self
        for ch in word:
            node = node.children.setdefault(ch, Trie())
        node.is_word = True

    def find_node(self, prefix):
        node = self
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def suggest(self, prefix):
        node = self.find_node(prefix)
        results = []
        def walk(n, path):
            if n.is_word:
                results.append(path)
            for ch, child in n.children.items():
                walk(child, path + ch)
        if node:
            walk(node, prefix)
        return results

t = Trie()
for w in ["код", "кодер", "кошка", "корень"]:
    t.add(w)
print(t.suggest("ко"))   # все слова на «ко»
print(t.suggest("код"))  # код и кодер

Метод find_node спускается по приставке, а suggest обходит найденное поддерево и собирает все настоящие слова. Заметьте, как suggest("код") выдаёт и «код», и «кодер» — потому что второе растёт из первого.

Где встречаются trie

Кроме автодополнения, префиксные деревья проверяют орфографию, ищут по справочникам, помогают маршрутизаторам выбирать сетевой путь по началу IP-адреса. Везде, где нужно работать с «началами» строк, trie оказывается на удивление кстати.

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