STR Строки и тексты Структура данных
Суффиксный автомат
Также: Suffix automaton · DAWG · directed acyclic word graph · граф подслов · endpos · суффиксные ссылки · suffix links · CDAWG
Граф, в котором из корня можно пройти ровно по подстрокам текста. Состояние — класс подстрок с одними и теми же концами вхождений; их меньше 2n, переходов меньше 3n, а строится всё онлайн, по букве, за линейное время.
«Все счастливые семьи похожи друг на друга» — первая фраза «Анны Карениной». Её можно склеить из кусков «Евгения Онегина»: «все с» взять из шестой строфы третьей главы, «частливые » — из семнадцатой строфы четвёртой, а «друг на друга» целиком найдётся в двенадцатой строфе шестой. На всю фразу уйдёт пятнадцать кусков, и меньше нельзя. Чтобы резать так, нужна структура, которая на каждую следующую букву за один шаг отвечает, есть ли в поэме такое продолжение. Это суффиксный автомат — граф, в котором из корня можно пройти ровно по подстрокам текста. Наберите свою фразу: она соберётся из «Онегина» наименьшим числом кусков, а у каждого куска видно, откуда он и сколько раз встречается.
«Я помню чудное мгновенье» Пушкина собирается из шестнадцати кусков его же романа: «я помню » — из тридцать третьей строфы первой главы, той, что начинается словами «Я помню море пред грозою», а «мгновенье» и «виденье, » — из письма Татьяны. Ищется всё без учёта регистра, буквы ё и вида тире и кавычек.
Идея
Сложим все суффиксы текста в бор: из корня можно пройти ровно по подстрокам. Но узел бора — это отдельная подстрока, а у «Онегина» их 9 648 463 959. Склеим узлы с одинаковым будущим. Для подстроки x обозначим endpos(x) — множество позиций, где кончаются её вхождения. В слове «колокол» у «л», «ол» и «кол» концы одни и те же — третья и седьмая буквы, а у «окол», «локол», «олокол» и «колокол» — только седьмая. Строки с общими концами продолжаются одинаково: что бы ни приписать справа, вхождения кончатся на одних и тех же местах. Поэтому их можно хранить одним состоянием.
Если у непустых строк u и w, |u| ≤ |w|, одинаковые концы, то u — суффикс w, и у любой строки, которая длиннее u, короче w и тоже суффикс w, концы те же.
В любом общем конце кончаются и u, и w, значит, короткая — суффикс длинной. Пусть x лежит между ними: u — суффикс x, x — суффикс w. Каждое вхождение w несёт вхождение x с тем же концом, каждое вхождение x — вхождение u: endpos(w) ⊆ endpos(x) ⊆ endpos(u) = endpos(w).
Значит, состояние автомата — это самая длинная строка класса и её суффиксы подряд, до какой-то длины. Длину самой длинной обозначим len. Следующий, более короткий суффикс встречается чаще и лежит в другом классе; на этот класс указывает суффиксная ссылка link. Ссылки образуют дерево с корнем в классе пустой строки: концы родителя включают концы детей, а у разных детей концы не пересекаются. Поэтому число вхождений любой подстроки — это число концов её класса, и все они сосчитываются одним проходом по дереву снизу вверх.
Состояние — класс подстрок с одним и тем же множеством концов. Переход по букве c ведёт из класса строк x в класс строк xc, суффиксная ссылка — в класс самого длинного суффикса с бóльшим числом концов. Такой граф строится онлайн, буква за буквой, и в нём меньше 2n состояний и 3n переходов.
Построение по букве
Пусть автомат текста T готов, и last — состояние всего T. Приписываем букву c.
- Новое состояние cur для строки Tc: len(cur) = len(last) + 1.
- Идём от last по суффиксным ссылкам. Пока у состояния p нет перехода по c, добавляем переход в cur: суффиксы T, за которыми c раньше не шла, теперь продолжаются только концом текста.
- Если дошли до корня и вышли за него, ссылка cur — корень. Иначе пусть переход по c из p ведёт в q. Если len(q) = len(p) + 1, строки q — суффиксы Tc, и ссылка cur — это q.
- Если len(q) больше, класс q раскалывается: его строки до длины len(p) + 1 получили новый конец, а длинные — нет. Заводим копию q с len(p) + 1, теми же переходами и той же ссылкой; переходы по c из p и дальше по ссылкам, пока они ведут в q, переводим в копию. Ссылки q и cur — копия.
Посмотрите, как это происходит на коротком слове. Пунктир — суффиксные ссылки, под графом — классы текущего автомата: строки и их концы. В «колоколе» копия появляется на четвёртой букве: класс {«о», «ко»} раскалывается, потому что «о» встретилась второй раз, а «ко» — нет. Можно ввести своё слово.
Почему состояний и переходов мало
У автомата строки длины n ≥ 2 не больше 2n − 1 состояний.
Начинаем с одного корня, каждая буква добавляет cur и, может быть, копию. На первой букве копии нет: у корня ещё нет переходов. На второй тоже: существуют только корень и состояние первой буквы с len = 1, переход по c может вести только в него из корня, а len(корня) + 1 = 1. Итого не больше 1 + 1 + 1 + 2(n − 2) = 2n − 1.
У автомата строки длины n ≥ 2 не больше 3n − 3 переходов.
Сначала заметим: префикс самой длинной строки класса — сам самая длинная строка своего класса. Иначе какая-то более длинная yp имеет те же концы, что и префикс p; значит, перед каждым вхождением p стоит y, и строка y·longest(v) имела бы те же концы, что longest(v), будучи длиннее.
Пометим в каждое состояние, кроме корня, один входящий переход — по последней букве его самой длинной строки. Помеченные переходы образуют дерево, путь по которому из корня в v читает longest(v); их не больше 2n − 2. Возьмём непомеченный переход a → b по букве c. Строку longest(a)·c можно продолжить вправо до конца текста — получится суффикс текста. Путь этого суффикса из корня идёт по помеченным переходам до a, а потом по нашему переходу: это первый непомеченный переход на пути. Поэтому разные непомеченные переходы дают разные суффиксы. Весь текст среди них не встречается: его путь — путь к last по помеченным переходам. Непустых суффиксов, кроме самого текста, n − 1, и всего переходов не больше 2n − 2 + n − 1.
Точные границы чуть меньше: 3n − 4 перехода при n ≥ 3. Обе достигаются: 2n − 1 состояний — у строки вида abb…b, 3n − 4 перехода — у abb…bc. У «Онегина» на 138 918 знаков 201 422 состояния и 306 788 переходов — 1,45n и 2,21n.
Построение по всей строке делает O(n) шагов, если переход по букве находится и добавляется за O(1).
Первый цикл на каждом шаге добавляет переход, копирование — тоже; переходы не исчезают, а их меньше 3n. Остаётся цикл перенаправления. Пусть d(v) — глубина v в дереве ссылок.
Если есть переход a → b по c, то d(b) ≤ d(a) + 1. Возьмём строку x из a: цепочка ссылок от b — это классы непустых суффиксов xc (более длинные суффиксы строк b лежат в самом b). Это строки yc, где y — суффикс x, включая пустой. Если y₁ и y₂ в одном классе, то и y₁c с y₂c в одном: их концы — концы y, за которыми идёт c. Классов среди y не больше d(a) + 1.
Пусть на шаге первый цикл прошёл k₁ ссылок от last до p, а второй ещё k₂ — до p′. Если ссылка cur — это q, то d(cur) = d(q) + 1 ≤ d(p) + 2 = d(last) − k₁ + 2. Если копия, то её ссылка — старая ссылка q, и в неё ведёт переход из p′: строка этой ссылки длины len(link q) — это zc, где z — суффикс строк p; состояния цепочки, строки которых длиннее z, по c ведут в q, а первое, где лежит z, — это p′. Тогда d(cur) = d(link q) + 2 ≤ d(p′) + 3 = d(last) − k₁ − k₂ + 3. Глубина нового last растёт за шаг не больше чем на 3 − k₁ − k₂ и не бывает отрицательной, поэтому сумма всех k₁ + k₂ за n шагов не больше 3n.
Склейка
Склейка в сцене — один проход фразы по автомату: идём по переходам, пока можем, и это самый длинный кусок, который есть в поэме; режем и начинаем от корня. Длина каждого куска выбирается жадно, и это не теряет ничего.
Если каждый раз брать самый длинный кусок, который есть в тексте, кусков получится не больше, чем в любой другой склейке той же фразы.
Пусть жадная склейка режет фразу в местах g₁ < g₂ < …, а другая — в o₁ < o₂ < …. Докажем, что oi ≤ gi. Для i = 0 оба разреза — начало фразы. Пусть oi ≤ gi. Если oi+1 ≤ gi, всё ясно. Иначе кусок от oi до oi+1 есть в тексте, а с ним и его хвост от gi: часть подстроки — тоже подстрока. Жадный кусок от gi — самый длинный из возможных, поэтому gi+1 ≥ oi+1. Раз жадные разрезы не отстают, жадная склейка доходит до конца фразы не позже.
Тот же проход, если не начинать от корня заново, а при неудаче отступать по суффиксной ссылке, даёт для каждой позиции второго текста длину самого длинного куска, который кончается в ней и есть в первом. Максимум этих длин — самая длинная общая подстрока двух текстов за O(n + m).
Код
Состояние — номер в параллельных списках: длина, ссылка, словарь переходов, конец первого вхождения и пометка «копия». Онлайн-шаг — функция add, ровно как в списке выше. Число вхождений сосчитано снизу вверх по дереву ссылок: каждое состояние, которое не копия, — один конец, состояния обходятся от длинных к коротким. Склейка выдаёт для каждого куска место первого вхождения (глава и строфа) и сколько раз кусок есть в поэме.
Сколько это стоит
| Структура | Размер | Построение | По букве |
|---|---|---|---|
| Бор всех суффиксов | O(n²) узлов — у «Онегина» 9,6 млрд | O(n²) | да |
| Суффиксное дерево | меньше 2n узлов, рёбра — отрезки текста | O(n), алгоритм Укконена | да |
| Суффиксный массив и LCP | n чисел и ещё n | O(n log n) или O(n) | нет |
| Суффиксный автомат | меньше 2n состояний и 3n переходов | O(n) | да |
Массив компактнее: на каждый знак — два числа. Зато автомат растёт вместе с текстом и отвечает «есть ли такое продолжение» за шаг, не зная длины куска заранее. Наивная склейка удлиняет кусок по букве и каждый раз ищет его в тексте; поиск подстроки сделан в языке на C и быстр, но проходит весь текст на каждой неудаче. Ниже склейка первых 3000 знаков «Онегина» из кусков начала «Войны и мира» длины n: автомат растёт онлайн, замер — после каждого удвоения.
Проход по автомату не зависит от длины текста: около 2 мс на Python и десятые доли миллисекунды на Go при любом n. Поиск растёт линейно, и на 131 тысяче знаков он медленнее в 70 раз на Python и почти в двести раз на Go.
Где легко ошибиться
- Без копии. Если в шаге 4 просто сделать ссылкой cur состояние q, автомат начнёт принимать лишнее. Самый короткий пример на двух буквах — «abba»: такой автомат принимает «aba», которой в слове нет.
- Общий словарь у копии. Копии нужен свой экземпляр переходов. В Python
nxt.append(nxt[q])вместоdict(nxt[q])оставляет один словарь на двоих, и перенаправление портит оба: «колокол» начинает принимать «кок» и «кокол». - Конец первого вхождения у копии — тот же, что у q, а не у cur: копия старше, её строки встречались раньше.
- Подсчёт вхождений рекурсией. Дерево ссылок у строки «aaa…a» — цепочка длины n. Обходить его лучше по убыванию len: у каждой ссылки len меньше.
- Память. Словарь на состояние — это сотни байт. Для «Онегина» хватает, для текста в сотни мегабайт переходы кладут в общие массивы, как в сцене, или переходят на суффиксный массив.
Где работает
Поиск образца справа налево: алгоритм Backward DAWG Matching читает окно текста с конца по автомату перевёрнутого образца и, как только кусок окна перестаёт быть подстрокой образца, сдвигает окно сразу за него; его битовую версию BNDM предложили Гонсало Наварро и Матьё Раффино в 1998 году. Самая длинная общая подстрока двух текстов и длины совпадений в каждой позиции — проходом, как в склейке. Подсчёты по растущему тексту: сколько разных подстрок после каждой буквы, какой кусок повторяется, — для онлайн-разбиения при сжатии. В олимпиадах автомат — универсальный индекс подстрок: число вхождений, k-я по алфавиту подстрока, кратчайшая строка, которой в тексте нет.
История
Ансельм Блюмер, Джанет Блюмер, Анджей Эренфойхт, Дэвид Хаусслер и Росс Макконнелл описали эту структуру в 1983 году и назвали её направленным ациклическим графом слов, DAWG. Они же построили его онлайн за линейное время и доказали границы в 2n − 1 состояний и 3n − 4 перехода. Подробная статья вместе с Му-Тянем Чэнем и Джоэлом Сейферасом вышла в 1985 году под названием «Наименьший автомат, распознающий подслова текста». Чэнь и Сейферас заметили, что построение суффиксного дерева Питера Вайнера 1973 года попутно строит автомат перевёрнутой строки. В 1987 году Блюмеры с соавторами сжали автомат так же, как сжимают суффиксное дерево, — получился компактный граф слов CDAWG.
Задачи
Склейка: для каждой фразы — наименьшее число кусков текста. И эхо: для каждой буквы — длина самого длинного куска, который на ней кончается и уже встречался раньше; на автомате это длина по суффиксной ссылке после очередного шага.
Склейка ЭхоДанные: «Евгений Онегин»: Викитека, по Полному собранию сочинений 1977 года, современная орфография; общественное достояние