STR Строки и тексты Структура данных
Суффиксный массив
Также: Suffix array · SA · LCP array · массив LCP · алгоритм Касаи · Kasai's algorithm · SA-IS · prefix doubling
Все хвосты текста, отсортированные по алфавиту, — и о тексте сразу видно всё: где встречается любое слово, какие куски повторяются, сколько в тексте разных подстрок. Строится удвоением за O(n log n) или за линейное время алгоритмом SA-IS, а массив общих начал соседей — за O(n) алгоритмом Касаи.
Самая длинная фраза, которая встречается в «Войне и мире» дважды, — 79 знаков из второй части эпилога: «…только настолько понятна нам, насколько мы знаем законы необходимости…». На втором месте, 78 знаков, — пункт диспозиции Наполеона к сражению в третьем томе: Толстой приводит её целиком, а потом разбирает по пунктам и цитирует снова. Чтобы найти такие повторы в 2,9 миллиона знаков, не нужно сравнивать каждое место с каждым — а это четыре триллиона пар. Достаточно отсортировать все хвосты текста: два хвоста с общим началом окажутся рядом. Ниже все повторы романа от тридцати знаков, найденные так; дуга соединяет два места с одной и той же фразой.
Узкие дуги у правого края — эпилог: во второй его части Толстой рассуждает о свободе и необходимости и повторяет собственные формулировки через страницу. Пучок в третьем томе — диспозиция и её разбор. Сдвиньте ползунок к сорока знакам и посмотрите на длинные дуги через полромана: «он испытывал чувство, подобное тому, которое…» — формула, к которой автор возвращается в разных томах, «Княжна Марья сидела одна в своей комнате», «как это всегда бывает с людьми, которые…». В переводе Мод самый длинный повтор — 115 знаков, и это опять диспозиция.
Идея
Суффиксный массив строки s длины n — номера всех её суффиксов, хвостов s[i..], в алфавитном порядке этих хвостов. Сами хвосты не хранятся: массив — это n чисел. Рядом с ним почти всегда держат массив LCP: lcp[j] — длина общего начала соседей, суффиксов номер j − 1 и j в этом порядке. Для «абракадабры»:
0 10 0 а 1 7 1 абра 2 0 4 абракадабра 3 5 1 адабра 4 3 1 акадабра 5 8 0 бра 6 1 3 бракадабра 7 6 0 дабра 8 4 0 кадабра 9 9 0 ра 10 2 2 ракадабра
Отсортированный список хвостов — указатель ко всему тексту сразу. Все места, где начинается образец, — это хвосты, которые начинаются с образца, а в отсортированном списке такие хвосты стоят подряд: их находят двоичным поиском. Повтор — это два хвоста с общим началом, а общее начало длиннее всего у соседей по списку: самый длинный повтор — максимум массива LCP. Всё остальное — следствия этих двух наблюдений.
В главе курса массив строится сортировкой с ключами-парами и находит повторы в геномах фагов; здесь — как построить его быстро, как посчитать LCP за линейное время и что ещё он умеет.
Удвоение
Сортировать хвосты, сравнивая их буква за буквой, дорого: соседние хвосты повторяющегося текста совпадают на длинных отрезках. Удвоение сортирует их по нарастающему началу. Сначала по первой букве: одинаковые буквы получают один номер — класс. Потом по первым двум буквам, по четырём, по восьми. Порядок по первым 2k буквам — это порядок пар «класс первых k букв, класс следующих k», а оба класса уже известны с прошлого раунда. Когда все классы стали разными, массив готов.
Пару можно отсортировать подсчётом, а не сравнениями. Вторые половины уже упорядочены прошлым раундом: хвост i по второй половине стоит там же, где хвост i + k по первой. Значит, порядок по второй половине получается одним проходом по старому массиву, а устойчивая сортировка подсчётом по первой половине его не портит. Раунд стоит O(n).
Раундов не больше log₂ n, но обычно гораздо меньше: удвоение останавливается, как только длина k превысит самое длинное общее начало двух хвостов. В «абракадабре» общее начало не длиннее четырёх букв, и хватает трёх раундов. В главе с диспозицией самый длинный повтор — 78 знаков, и раундов семь. На строке из одних «а» их будет столько, сколько удвоений нужно до длины строки.
Касаи: общие начала за линейное время
Массив LCP можно посчитать, сравнивая каждую пару соседей с первой буквы. На обычном тексте это быстро, но на повторах соседи совпадают почти целиком, и выходит n²/2 сравнений. Тору Касаи и его соавторы в 2001 году заметили, что, если идти не по массиву, а по тексту — хвост 0, хвост 1, хвост 2, — общее начало с соседом не может сильно уменьшиться.
Пусть у хвоста i общее начало с его соседом выше в массиве равно h > 0. Тогда у хвоста i + 1 общее начало с его соседом выше не меньше h − 1.
Пусть соседом хвоста i был хвост p, и их общее начало h > 0. Тогда первые буквы равны, s[p] = s[i], и хвост p меньше хвоста i. Отрежем у обоих по первой букве: хвост p + 1 меньше хвоста i + 1, и общее начало у них h − 1. Значит, в массиве хвост p + 1 стоит выше хвоста i + 1, а все хвосты между ними, по порядку сортировки, начинаются с тех же h − 1 букв. В том числе ближайший сосед хвоста i + 1 сверху.
Поэтому сравнение для хвоста i + 1 начинается не с нуля, а с h − 1. Значение h растёт на единицу при каждом удачном сравнении, при переходе к следующему хвосту падает не больше чем на единицу (и один раз, у первого хвоста массива, сбрасывается в ноль) и никогда не превышает n. Поэтому удачных сравнений за весь проход не больше 3n, неудачных — не больше n, и проход линеен. Вернитесь к сцене выше и пролистайте её до конца: после раундов удвоения идёт проход Касаи, синим отмечены буквы, которые он не сравнивает, потому что знает их совпадение заранее.
Указатель: поиск двоичным поиском
Хвосты, которые начинаются с образца p, стоят в массиве подряд. Первый из них — первый хвост, не меньший p; за последним — первый хвост, который больше всех, что начинаются с p. Обе границы находит двоичный поиск, и в каждом его шаге сравниваются не больше m букв. Ниже массив первой части романа, 244 500 хвостов, построенный прямо в браузере тем же удвоением, что в листинге.
Слева — весь массив сверху вниз: светлая полоса — отрезок, который поиск ещё не исключил, оранжевая — найденный блок. Справа — хвосты вокруг середины. На каждый образец уходит около 36 шагов, по 17–18 на каждую границу: log₂ 244 500 ≈ 17,9. «Князь» находится в 159 местах, и все они — один блок массива. Время поиска не зависит от того, сколько раз встречается образец: найдя границы блока, мы уже знаем число вхождений, а сами места выписываются по одному.
Манбер и Майерс в статье 1990 года показали, как ускорить поиск до O(m + log n): если хранить общие начала не только соседей, но и пар, которые встречаются в двоичном поиске, то каждое следующее сравнение можно начинать не с первой буквы. На практике обычно хватает простой версии.
Код
Удвоение с сортировкой подсчётом, Касаи, поиск двумя двоичными поисками. В Python поиск — это bisect с ключом, который вырезает у хвоста первые m букв, в Go — sort.Search. Демо печатает массив «абракадабры» и разбирает главу XXVII второй части третьего тома — ту самую, с диспозицией.
Повтор в выводе максимальный: его нельзя продлить ни вправо — это и есть длина общего начала соседей, — ни влево: буквы перед ним в двух местах разные. Без второго условия каждый повтор в 78 знаков потянул бы за собой ещё 77, 76, 75… — те же фразы без первой буквы. В главе пункты диспозиции повторяются почти дословно: «перейдет по своим трем мостам», «направятся к редуту и войдут в линию с прочими войсками», «по вступлении таким образом в бой будут даны приказания». И несколько раз, иногда с переставленными словами, — рефрен Толстого: «не было и не могло быть исполнено», «не могло быть и не было сделано».
Сколько это стоит
Удвоение — O(n) на раунд и не больше log₂ n раундов: O(n log n). Касаи — O(n). Поиск — O(m log n). Память — массив из n чисел, при 32-битных номерах 4n байт, и ещё столько же на LCP. Суффиксное дерево, которое умеет то же самое, в аккуратной реализации занимает около 20n байт; отчасти поэтому массив его и вытеснил.
Удвоение растёт чуть быстрее линейного. Касаи на теломере, где соседи совпадают почти целиком, остаётся линейным, а сравнение соседей с первой буквы — квадратично: при двух тысячах знаков на Python оно уже почти в четыреста раз медленнее.
Можно ли строить массив за линейное время? Да, и первые такие алгоритмы, не использующие суффиксное дерево, появились в 2003 году сразу в нескольких работах, среди них — Юхи Кярккяйнена и Петера Сандерса и Панга Ко и Шринивасы Алуру. Самый практичный из линейных — SA-IS Ге Нонга, Сен Чжана и Вай Хонг Чана (2009). Он делит хвосты на два типа: L — больше следующего за ним хвоста, S — меньше. Хвосты типа S, перед которыми стоит хвост типа L, сортируются рекурсивно, а все остальные выводятся из них двумя проходами, «наведённой» сортировкой: если хвост i + 1 уже на своём месте, то хвост i типа L встаёт в начало корзины своей первой буквы в том же порядке. Рекурсия получает строку не длиннее половины исходной, отсюда O(n).
Что ещё видно в массиве
Число разных подстрок. Каждая подстрока — начало какого-то хвоста. Хвост номер j приносит столько новых подстрок, сколько у него начал, которых не было у хвостов выше: его длина минус lcp[j]. Всего разных подстрок n(n + 1)/2 − Σ lcp. В главе с диспозицией — 22 337 829 из 22 374 705 возможных. У всего романа общие начала соседей в сумме — 24 848 933 знака, в среднем 8,6 знака на хвост: почти все подстроки романа уникальны. Это задача про ДНК ниже.
Кусок, который встречается k раз. Он общий у k хвостов подряд в массиве, и его длина — минимум из k − 1 значений LCP между ними. Самый длинный такой кусок — максимум этого минимума по всем окнам, и скользящее окно считает его за O(n). Это вторая задача.
Общий кусок двух текстов. Склейте их через разделитель, которого нет ни в одном, и постройте массив склейки. Самый длинный общий кусок — максимум LCP по парам соседей, из которых один хвост начинается в первом тексте, а другой во втором. Рабин — Карп решает ту же задачу хешами и двоичным поиском по длине.
Преобразование Барроуза — Уилера. Если выписать буквы, стоящие перед хвостами в порядке массива, s[sa[j] − 1], получится перестановка Барроуза — Уилера, на которой построен bzip2 и индексы для поиска ридов в геномах. Перед хвостами с одинаковым началом чаще всего стоят одинаковые буквы — поэтому она так хорошо сжимается.
Где работает
- Стандартная библиотека Go. Пакет
index/suffixarrayстроит массив алгоритмом SA-IS — в исходнике ссылка на статью Нонга, Чжана и Чана — и ищет по нему за O(m log n), в том числе все совпадения регулярного выражения. - Сжатие. Построитель словаря в zstd (
zdict.c) сортирует суффиксы обучающих данных библиотекой libdivsufsort Юты Мори и по соседям в массиве находит повторяющиеся куски, которые стоит положить в словарь. - Двоичные патчи. Утилита bsdiff строит суффиксный массив старой версии файла и для каждого места новой версии ищет в нём самое длинное совпадение; разница между версиями программы получается маленькой.
- Геномы. Программы, которые прикладывают миллионы коротких прочтений к геному, используют сжатого родственника массива — FM-индекс на основе перестановки Барроуза — Уилера. Строят его через суффиксный массив генома.
История
Уди Манбер и Джин Майерс предложили суффиксный массив в 1990 году как простую и экономную замену суффиксному дереву; журнальная версия статьи вышла в 1993-м. По имеющимся сведениям, Гастон Гонне независимо пришёл к той же структуре в 1987 году и назвал её PAT-массивом. Алгоритм Касаи для LCP опубликован в 2001 году, линейные построения — в 2003-м, SA-IS — в 2009-м. С тех пор суффиксный массив стал рабочей структурой: дерево умеет то же, но занимает в несколько раз больше памяти и сложнее в коде.
Задачи
В первой задаче надо сосчитать разные куски генома, не выписывая их. Во второй — найти самую длинную фразу, которая встречается в тексте не меньше k раз: суффиксный массив вместе со скользящим окном.
Сколько разных кусков Фраза k разДанные: «Война и мир», Л. Н. Толстой, общественное достояние «Война и мир» в переводе Луизы и Эйлмера Мод, Project Gutenberg, общественное достояние