STR Строки и тексты Алгоритм
Алгоритм Ахо — Корасик
Также: Aho–Corasick algorithm · Aho-Corasick · автомат Ахо — Корасик · поиск по словарю · multi-pattern string matching · fgrep
Тысячи слов ищутся в тексте за один проход. Из слов строят бор, а каждому его узлу добавляют ссылку отказа — куда отступить, если следующая буква не продолжает ни одно слово. Получается автомат, который читает текст по букве, никогда не возвращается назад и сообщает обо всех вхождениях всех слов, включая вложенные друг в друга. Время работы почти не зависит от того, сколько слов в словаре.
Кто и где появляется в первой части «Войны и мира»? У двадцати шести героев 135 форм имён: «Пьер», «Пьера», «Пьеру», «Анной Павловной», «маленькой княгини», французские «Pierre» и «Lise». Искать каждую форму отдельно — 135 проходов по тексту. Автомат Ахо — Корасик складывает все формы в один бор и проходит 244 500 букв части один раз. Каждая строка ниже — герой, каждая отметка — упоминание. Нажмите на любую, чтобы прочитать фразу вокруг.
На картинке видно, как устроена часть. Главы I–VI — Петербург: салон Анны Павловны, где впервые появляются Пьер и князь Андрей, и ночная пирушка у Анатоля с Долоховым. Главы VII–XVII — Москва, именины у Ростовых: Наташа, Соня, Борис, Вера, Марья Дмитриевна и Шиншин, а между ними — первый визит Анны Михайловны с Борисом к умирающему графу Безухову. В главах XVIII–XXI граф умирает, и вокруг его наследства — князь Василий, Анна Михайловна и Катишь. Последние четыре главы — Лысые Горы: старый князь, княжна Марья, мадемуазель Бурьен, маленькая княгиня и снова князь Андрей. Пьер упомянут 251 раз, чаще всех.
Автомат нашёл 1373 совпадения, из них 1184 — целые слова. Остальные 189 — формы внутри других слов: «Пьер» внутри «Пьера», «Берг» внутри «Бергом». Автомат ищет подстроки, а не слова, и это важно, — к этому вернёмся в разделе о ловушках. На 244 500 прочитанных букв пришлось 25 956 шагов по ссылкам отказа, примерно один на десять букв.
Идея
Сложим все слова в бор и будем идти по нему, читая текст. Пока буквы продолжают какой-нибудь путь, идём вниз. Когда следующая буква не продолжает ни одного слова, не начинаем сначала, а переходим в узел, который соответствует самому длинному концу прочитанного, ещё лежащему в боре, — это ссылка отказа. Её, как префикс-функцию, считают заранее. Слово найдено, когда мы стоим в узле, где оно кончается, или в узле, из которого до такого узла ведут ссылки отказа.
У автомата три части. Переходы — рёбра бора: узел — это начало какого-то слова, переход по букве продлевает его. Ссылка отказа узла ведёт в узел самого длинного собственного конца его строки, который тоже есть в боре. Словарная ссылка ведёт по цепочке отказов к ближайшему узлу, где кончается какое-нибудь слово: по ним перечисляются слова, вложенные в конец текущего.
Автомат по шагам
Ниже — пример из статьи Альфреда Ахо и Маргарет Корасик 1975 года: словарь he, she, his, hers и текст ushers. Узлы пронумерованы в порядке вставки слов, как в статье: he — узлы 1 и 2, she — 3, 4 и 5, his — 6 и 7, hers — 8 и 9. Пунктир — ссылки отказа, оранжевые кружки — узлы, где кончается слово. Впишите свои слова и текст или выберите пример с вложенными словами.
Прочитав «ush», автомат стоит в узле 4 — это «sh», начало she. Буква e ведёт в узел 5, и там кончаются сразу два слова: she и, по словарной ссылке, he. Дальше r: из узла 5 перехода по r нет, и автомат отступает по ссылке отказа в узел 2 — «he», самый длинный конец «she», который ещё есть в боре. Из узла 2 буква r ведёт в 8, s — в 9, и найдено hers. Ни одна буква текста не прочитана дважды. Листинг ниже печатает ту же таблицу ссылок отказа, что и в статье 1975 года: для узлов с первого по девятый — 0 0 0 1 2 0 3 0 3.
После чтения букв t[0..i] автомат стоит в узле, строка которого — самый длинный конец прочитанного, лежащий в боре. Поэтому он сообщает о каждом вхождении каждого слова ровно один раз, в позиции его последней буквы.
Индукция по i. Пусть перед буквой c = t[i] автомат стоит в узле u — самом длинном конце t[0..i − 1] в боре. Любой конец t[0..i], лежащий в боре, — это некоторый конец t[0..i − 1], лежащий в боре, продлённый буквой c. Все концы t[0..i − 1], лежащие в боре, — это u, его ссылка отказа, её ссылка отказа и так далее до корня: как в лемме о гранях из статьи о КМП, конец конца — тоже конец, а самый длинный следующий конец и задаёт ссылка. Автомат перебирает их от длинного к короткому и останавливается на первом, который продлевается буквой c, — это и есть самый длинный конец t[0..i] в боре. Если не продлевается ни один, ответ — пустая строка, корень.
Слово w кончается в позиции i, когда w — конец t[0..i]. Слово лежит в боре, значит, w — один из концов текущего узла, то есть сам узел или узел на цепочке его ссылок отказа. Словарные ссылки проходят ровно по тем узлам этой цепочки, где кончаются слова, поэтому каждое такое w сообщается один раз.
Как построить ссылки отказа
Ссылка отказа узла v = u + c (узел u, продлённый буквой c) получается так же, как следующее значение префикс-функции. Берём ссылку отказа родителя u и пробуем продлить её буквой c; не продлевается — берём ссылку ссылки, и так далее. Первый узел, из которого есть переход по c, даёт ответ; если не нашлось ни одного, ссылка ведёт в корень. Все узлы на этом пути мельче v, поэтому узлы обходят в ширину, по уровням: к тому времени, как очередь дойдёт до v, ссылки всех более мелких узлов уже готовы. Словарная ссылка считается заодно: если в узле ссылки отказа кончается слово, это он, иначе — его собственная словарная ссылка.
Ссылки можно не хранить, а превратить автомат в полностью детерминированный: для каждого узла и каждой буквы заранее записать, куда попадёт поиск со всеми откатами. Так предложено в шестом разделе той же статьи 1975 года. Автомат тогда делает ровно один переход на букву, но таблица переходов занимает узлы × размер алфавита: для ДНК это пустяк, для Юникода — нет.
Код
Переходы бора хранятся словарём на каждый узел, ссылки отказа и словарные ссылки — массивами. search выдаёт пары «где кончилось, какое слово» по мере чтения текста, поэтому текст можно подавать потоком. В демо — пример из статьи 1975 года, все герои первой части романа и фильтр слов из раздела о ловушках.
Сколько это стоит
На тексте длины n автомат делает меньше 2n переходов: n переходов по буквам и меньше n по ссылкам отказа. Построение бора и всех ссылок занимает O(Σ|wi|) переходов, а перечисление найденного — O(z), где z — число вхождений.
Каждая буква текста — ровно один переход по букве, и он увеличивает глубину текущего узла не больше чем на единицу. Каждый переход по ссылке отказа уменьшает глубину хотя бы на единицу. Глубина не бывает отрицательной, поэтому уменьшений не больше, чем увеличений, — меньше n. Это то же рассуждение, что для КМП, и оно дословно повторяет теорему 2 из статьи Ахо и Корасик. Для построения тот же счёт применяют к пути каждого слова отдельно: ссылки отказа узлов одного слова вычисляются как поиск этого слова в самом боре, и шагов на слово меньше удвоенной длины. Словарные ссылки ведут только в узлы, где кончаются слова, поэтому каждый шаг по ним — найденное вхождение.
Слагаемое z бывает огромным, и оно честное: если в словаре слова a, aa, aaa, … , a446, то в тексте из ста тысяч букв a каждая позиция — конец сотен слов, и вхождений около 45 миллионов. Если нужно не перечислить вхождения, а только сосчитать их для каждого слова, перечислять не обязательно: в каждом узле считают, сколько раз автомат в нём стоял, и складывают эти числа вверх по ссылкам отказа, от глубоких узлов к мелким. Так устроена задача ниже.
Сам проход почти не зависит от числа слов. Замер: пятьдесят тысяч букв первой части романа и словарь из 10, 100, … , 10 000 слов «Войны и мира». Рядом — то, что пишут чаще всего: регулярное выражение из всех слов через «или».
В Python регулярное выражение из десяти слов быстрее самодельного автомата: его движок написан на C. Но время регулярки растёт вместе со словарём — на каждой позиции она пробует слова по очереди, — и при десяти тысячах слов она работает в 24 раза дольше автомата. Автомат за это время замедлился в полтора раза — от лишних шагов по ссылкам отказа и лишних найденных слов. В Go движок регулярных выражений при разборе выносит общие начала слов за скобки и тем самым сам строит что-то похожее на бор, поэтому растёт медленно, но при десяти тысячах слов всё равно отстаёт от автомата в 22 раза. Сравнение не совсем равное: регулярное выражение находит вхождения без перекрытий, а автомат — все.
Где ломается: подстрока — не слово
Автомат ищет подстроки, и фильтр запрещённых слов, построенный на нём напрямую, ловит невинные слова. В апреле 1996 года фильтр сервиса AOL не давал жителям города Скунторп заводить учётные записи: в названии города спрятано непристойное слово. С тех пор такую ошибку называют проблемой Скунторпа. Попробуйте на словаре «Войны и мира»: запретите «яд», «вор», «бес» и «лох».
«Яд» сидит в 97 словах романа из 14 871 — в «беспорядке» и во «взгляде». «Вор» — в 162, в том числе во «выговорил» и в «говоре». «Бес» прячется в «небесном» и в «собеседнике», а фильтр на «лох» не пропустил бы ни одного упоминания Долохова. Переключите на «целым словом»: фильтр проверяет, что перед найденным и после него нет букв, и все ложные срабатывания исчезают. Так же размечены герои в первой сцене. Но и это не конец: «лохи» и «воры» целым словом уже не совпадают с «лох» и «вор». Настоящие фильтры добавляют формы слов, нормализацию букв, похожих на буквы, и белые списки, а автомат остаётся внутри как быстрый поиск по всему этому словарю.
Где работает
- fgrep. Альфред Ахо сам реализовал свои алгоритмы поиска в первых версиях утилит Unix egrep и fgrep. fgrep ищет сразу по списку фиксированных строк, и его алгоритм — это и есть Ахо — Корасик.
- Антивирусы. В ClamAV сигнатуры с подстановочными знаками режутся на неподвижные куски, и все куски ищет один автомат Ахо — Корасик; простые сигнатуры ищет вариант Бойера — Мура.
- Сетевая безопасность. Snort, система обнаружения вторжений, ищет тысячи шаблонов в каждом пакете автоматом Ахо — Корасик; настройка
search-methodвыбирает между вариантами, которые по-разному меняют память на скорость. - Тексты и данные. Разметка по словарю — имена, термины, названия лекарств, — поиск праймеров и зондов в ДНК, подсветка ключевых слов в редакторах.
История
Альфред Ахо и Маргарет Корасик работали в Bell Laboratories. Технические библиотеки Bell Labs раз в две недели выпускали бюллетень «Current Technical Papers» со ссылками на статьи из журналов, и к лету 1973 года накопилось около 150 000 ссылок — около 10⁷ знаков. Библиограф задавал запрос — логическую формулу из ключевых слов, — и программа на Фортране искала заголовки, которые ей удовлетворяют, сравнивая с каждым заголовком каждое слово по очереди. Ахо и Корасик заменили этот поиск автоматом. На машине Honeywell 6070 запрос из 15 слов стал занимать 0,18 часа процессорного времени вместо 0,79, а запрос из 24 слов — 0,21 вместо 1,27. Чем больше слов, тем больше выигрыш: время автомата почти не зависит от их числа.
В статье «Efficient string matching: an aid to bibliographic search» (Communications of the ACM, июнь 1975) авторы прямо пишут, что их алгоритм построен по образцу алгоритма Кнута — Морриса — Пратта и что похожую схему для поиска первого вхождения предлагали Джон Хопкрофт и Ричард Карп, не опубликовав её. Позже Маргарет Корасик перешла в корпорацию MITRE, а Альфред Ахо вместе с Джеффри Ульманом получил премию Тьюринга за 2020 год — за алгоритмы и теорию, на которых держатся компиляторы.
Задачи
Нужно сосчитать, сколько раз каждое слово словаря встречается в тексте, и среди тестов есть такой, где вхождений десятки миллионов: перечислять их по одному нельзя.
Сколько раз каждое словоДанные: «Война и мир», Л. Н. Толстой, общественное достояние