Алгоритм Ахо-Корасик: поиск сразу многих образцов в тексте

Коротко

Алгоритм находит вхождения всех образцов из словаря за один проход по тексту — независимо от того, сколько образцов в словаре.

Задача

Есть словарь из тысяч слов и большой текст. Нужно найти все вхождения всех слов.

Наивный подход — запустить KMP по разу на каждое слово: O(k · n), где k — число образцов. При 10 000 запрещённых слов и тексте в мегабайт это безнадёжно.

Ахо-Корасик делает один проход по тексту. Время не зависит от количества образцов.

Практические применения:

• фильтрация запрещённых слов в чатах;
• антивирусные сигнатуры;
• поиск по биологическим последовательностям;
• системы обнаружения вторжений (Snort использует именно этот алгоритм);
• подсветка терминов в тексте.

Идея: префиксное дерево плюс суффиксные ссылки

Алгоритм — это обобщение KMP на множество образцов, и строится из двух частей.

Первая часть — префиксное дерево (trie) из всех образцов. Оно позволяет идти по тексту, спускаясь по дереву, пока символы совпадают.

словарь: he, she, his, hers

        (корень)
        /      \
       h        s
      / \        \
     e*  i        h
     |   |         \
     r   s*         e*
     |
     s*

* — конец слова

Вторая часть — суффиксные ссылки. Проблема дерева: если на каком-то символе спуск невозможен, придётся начинать с корня и терять прогресс. Суффиксная ссылка отвечает на вопрос: «какой наибольший суффикс текущего пути является префиксом какого-то образца?»

Это ровно та же идея, что префикс-функция в KMP, только для дерева вместо строки.

Три вида ссылок

Суффиксная ссылка (fail) — куда перейти, если по текущему символу продолжить нельзя. Ведёт в вершину, соответствующую наибольшему собственному суффиксу.

Переход (goto) — куда идти по символу с учётом суффиксных ссылок. Именно он превращает дерево в автомат: из любого состояния по любому символу есть ровно один переход.

Выходная ссылка (output) — ближайшая вершина по цепочке суффиксных ссылок, которая является концом слова. Нужна, потому что при совпадении hers одновременно совпадает и hers, и he... точнее, суффикс s может быть отдельным словом. Без выходных ссылок часть совпадений теряется.

Реализация

from collections import deque


class AhoCorasick:
    def __init__(self, patterns: list[str]) -> None:
        # каждая вершина: переходы, суффиксная ссылка, выходная ссылка, слова
        self.goto = [{}]
        self.fail = [0]
        self.output = [0]
        self.words = [[]]

        for pattern in patterns:
            self._add(pattern)

        self._build_links()

    def _add(self, pattern: str) -> None:
        node = 0
        for ch in pattern:
            if ch not in self.goto[node]:
                self.goto.append({})
                self.fail.append(0)
                self.output.append(0)
                self.words.append([])
                self.goto[node][ch] = len(self.goto) - 1
            node = self.goto[node][ch]

        self.words[node].append(pattern)

    def _build_links(self) -> None:
        queue = deque()

        # дети корня: суффиксная ссылка ведёт в корень
        for ch, child in self.goto[0].items():
            self.fail[child] = 0
            queue.append(child)

        # обход в ширину: ссылки родителей уже готовы
        while queue:
            node = queue.popleft()

            for ch, child in self.goto[node].items():
                # ищем, куда ведёт суффиксная ссылка по этому символу
                f = self.fail[node]
                while f and ch not in self.goto[f]:
                    f = self.fail[f]

                self.fail[child] = self.goto[f].get(ch, 0)
                if self.fail[child] == child:
                    self.fail[child] = 0

                # выходная ссылка: ближайший конец слова по цепочке fail
                link = self.fail[child]
                self.output[child] = link if self.words[link] else self.output[link]

                queue.append(child)

    def _next_state(self, node: int, ch: str) -> int:
        while node and ch not in self.goto[node]:
            node = self.fail[node]
        return self.goto[node].get(ch, 0)

    def search(self, text: str) -> list[tuple[int, str]]:
        """Возвращает список (позиция начала, найденное слово)."""
        result = []
        node = 0

        for i, ch in enumerate(text):
            node = self._next_state(node, ch)

            # слова, заканчивающиеся здесь
            for word in self.words[node]:
                result.append((i - len(word) + 1, word))

            # слова из выходных ссылок — иначе потеряем вложенные совпадения
            out = self.output[node]
            while out:
                for word in self.words[out]:
                    result.append((i - len(word) + 1, word))
                out = self.output[out]

        return result


ac = AhoCorasick(['he', 'she', 'his', 'hers'])
for pos, word in ac.search('ushers'):
    print(f'позиция {pos}: {word}')
# позиция 1: she
# позиция 2: he
# позиция 2: hers

Обратите внимание на результат: в строке ushers найдены три вхождения, включая вложенное he внутри she. Именно это и обеспечивают выходные ссылки — наивный обход дерева нашёл бы только she.

Почему построение идёт в ширину

Суффиксная ссылка вершины вычисляется через ссылку её родителя. Значит родитель должен быть обработан раньше ребёнка.

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

Оптимизация: полный автомат

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

for ch in alphabet:
    if ch in goto[node]:
        transition[node][ch] = goto[node][ch]
    else:
        transition[node][ch] = transition[fail[node]][ch]

Тогда обработка каждого символа текста — одно обращение к массиву, честные O(1). Цена — память O(вершин × размер алфавита), что для больших алфавитов может быть накладно.

Компромисс типичный: словарь переходов экономит память, полный автомат экономит время.

Сравнение с другими подходами

Вывод: много образцов разной длины — Ахо-Корасик. Это единственный из трёх, чьё время поиска не зависит от размера словаря.

Практический пример: фильтр слов

def censor(text: str, banned: list[str], mask: str = '*') -> str:
    ac = AhoCorasick(banned)
    chars = list(text)

    for pos, word in ac.search(text.lower()):
        for i in range(pos, pos + len(word)):
            chars[i] = mask

    return ''.join(chars)


print(censor('это спам и реклама', ['спам', 'реклама']))
# это **** и *******

На реальном словаре из тысяч слов и потоке сообщений такой фильтр работает за один проход на сообщение.

Частые ошибки

Построение ссылок обходом в глубину. Ссылки родителей окажутся не готовы — алгоритм посчитает мусор.

Пропуск выходных ссылок. Теряются вложенные совпадения: найдётся she, но не he внутри него. Ошибка тихая и обнаруживается только на специфичных данных.

Самоссылка вершины. При неаккуратном вычислении fail вершина может сослаться сама на себя, и поиск зациклится. В коде выше есть явная проверка.

Суффиксная ссылка корня и его детей. Дети корня всегда ссылаются на корень — это база рекурсии, её нужно задать до начала обхода.

Что запомнить

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

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→