STR Строки и тексты Алгоритм
Z-функция
Также: Z-function · Z-algorithm · Z-алгоритм · Z-массив · Z-array · алгоритм Мейна — Лоренца · Main–Lorentz algorithm
Для каждой позиции строки — сколько букв отсюда совпадает с началом той же строки. Все эти числа считаются за линейное время одним приёмом: внутри уже найденного совпадения ответ копируется из начала строки. Из Z-функции получаются поиск образца, все периоды строки и, в алгоритме Мейна и Лоренца, все повторы подряд — вплоть до опечатки в электронном тексте «Войны и мира».
Электронный текст «Войны и мира», с которым работают все статьи этого каталога, — два миллиона девятьсот тысяч знаков. Программа нашла в нём 28 093 места, где кусок текста сразу же повторяется. Почти все они короткие и скучные: «нн», «ее», многоточия. Самый длинный — 125 знаков в речи Ланжерона на военном совете накануне сражения в первом томе: «…такую диспозицию, где положение неприятеля предполагается известным, тогда как положение неприятеля предполагается известным, тогда как положение это может быть нам неизвестно». В других изданиях романа и в английском переводе эти 57 знаков стоят один раз. Значит, это не Толстой, а ошибка в самом файле, и она есть на сайте, откуда текст взят. Читатель легко примет её за оговорку персонажа. Ниже все повторы подряд из романа; под текстом — Z-функция, которая доказывает каждый из них.
Следующие по длине — уже сам Толстой: «Ваше превосходительство! Ваше превосходительство!», берейтор, который будит Пьера утром перед сражением, — «ваше сиятельство, ваше сиятельство, ваше сиятельство», умирающий старый князь Болконский — «прости... спасибо... прости... спасибо», сумасшедший на улице опустевшего города — «воскресну... воскресну... воскресну». Сдвиньте ползунок к восьми знакам: чаще всего, 97 раз, повторяется « друг» — это «друг друга», «друг другу», где повтор подряд встроен в сам язык. В переводе на этом месте случайность: «hand and», «husband and» — 130 раз подряд повторяется «and ».
Как программа убедилась, что 125 знаков — повтор? Под текстом столбики: для каждой позиции i от начала найденного куска — сколько знаков отсюда совпадает с началом куска. Столбик на позиции 57 поднимается до 68. Это значит, что текст с 57-го знака повторяет начало куска на 68 знаков, а раз 68 ≥ 57, то первые 114 знаков — один и тот же кусок, записанный дважды. Этот массив столбиков и называется Z-функцией.
Идея
Z-функция строки s длины n — массив z, где z[i] — сколько букв, начиная с позиции i, совпадает с началом строки. Для z[0] договоримся считать всю длину n. У слова «колокол» начало «кол» повторяется в конце:
к о л о к о л 7 0 0 0 3 0 0
По определению каждое z[i] считается сравнением букв, пока они совпадают. Для обычного текста это быстро: первая же буква обычно не совпадает. Но на строке из одних «а» каждая позиция сравнивается до самого конца, и всего выходит n²/2 сравнений.
Пусть уже известно, что кусок s[l..r) совпадает с началом строки s[0..r − l). Тогда любая позиция i внутри этого куска смотрит на те же буквы, что и позиция k = i − l в начале строки, а для неё ответ уже посчитан. Значит, z[i] не меньше min(z[k], r − i), и сравнивать надо только буквы правее r. Каждое удачное сравнение сдвигает r вправо, а назад r не ходит. Поэтому сравнений меньше 2n.
Кусок [l, r) — самый правый из найденных отрезков, совпадающих с началом строки, — называют Z-блоком. Буква z и слово «Z-блок» (Z-box) — из книги Дэна Гасфилда 1997 года; сам массив на русском обычно зовут Z-функцией.
Z-блок по шагам
Для очередной позиции i бывает три случая.
- i правее Z-блока (i ≥ r). Про буквы отсюда ничего не известно — сравниваем с начала строки, как в определении.
- i внутри блока, и z[k] < r − i. Совпадение у копии в начале строки обрывается раньше края блока. Значит, и здесь оно обрывается на той же букве: z[i] = z[k]. Сравнивать нечего; код ниже ради краткости всё же делает одно сравнение, и оно заведомо не совпадает.
- i внутри блока, и z[k] ≥ r − i. До края блока совпадение гарантировано, а за краем блок ничего не знает. Начинаем с z[i] = r − i и сравниваем буквы правее r.
Если совпадение у позиции i ушло правее r, блок становится [i, i + z[i]). Пройдите по шагам строку Гасфилда «aabcaabxaaz» и строку из одних «a»: на ней блок сразу растягивается на всю строку, и все следующие позиции получают ответ копированием.
На «aabcaabxaaz» Z-алгоритм делает 16 сравнений, а сравнение по определению — 18: в обычной строке экономить почти не на чем. На двенадцати «a» — 11 сравнений против 66. Разница растёт как n против n²: на двух тысячах «a» это 1999 сравнений против 1 999 000.
Почему копировать можно
Пусть s[l..r) = s[0..r − l), позиция i лежит внутри, l < i < r, и k = i − l. Если z[k] < r − i, то z[i] = z[k]. Если z[k] ≥ r − i, то z[i] ≥ r − i.
Из равенства блока и начала строки следует, что буквы от i до r те же, что от k до r − l: s[i + t] = s[k + t] при t < r − i.
Пусть z[k] = m < r − i. Первые m букв от k совпадают с началом строки, а буква s[k + m] не равна s[m]. Все эти буквы, вместе с несовпавшей, лежат внутри копии, поэтому от i стоят те же самые: первые m букв совпадают с началом, а s[i + m] = s[k + m] ≠ s[m]. Это и значит z[i] = m.
Если z[k] ≥ r − i, то все r − i букв от k до края копии совпадают с началом строки, а значит, и r − i букв от i до края блока. Про s[r] равенство блока ничего не говорит, и дальше алгоритм сравнивает честно.
Ограничение r − i не лишнее. Пусть z[k] больше r − i: у позиции k совпадение с началом идёт и за край копии, через букву s[r − l]. Но блок [l, r) кончился именно потому, что s[r] ≠ s[r − l]. Значит, у позиции i совпадение обрывается ровно на краю блока, z[i] = r − i, и взять z[k] целиком было бы ошибкой. Сравнивать за краем по-настоящему нужно только при z[k] = r − i.
Код
Z-функция, наивный способ для сравнения, поиск образца и все периоды строки. Обе функции заодно считают сравнения букв, чтобы было видно, где Z-алгоритм выигрывает. В Go функция обобщённая: одна и та же работает с байтами и с рунами, а «колокол» надо сравнивать по буквам, а не по байтам UTF-8.
Последняя таблица — четыре строки по две тысячи букв. На случайной ДНК наивный способ делает на 5 % больше сравнений: 2682 против 2554. На строке Фибоначчи разрыв уже почти впятеро, на теломере (TTAGGG подряд) — в 91 раз, на одной букве — в тысячу раз. Чем больше в строке повторов, тем больше наивный способ сравнивает одно и то же заново.
Сколько это стоит
Z-алгоритм на строке длины n делает меньше 2n сравнений букв и работает за время O(n); память — массив из n чисел.
Каждое сравнение либо не совпадает, либо совпадает. Несовпадение заканчивает работу с позицией i, поэтому несовпадений не больше n − 1. Совпадение всегда сравнивает букву s[i + z[i]], стоящую не левее r: в первом случае i ≥ r, в третьем сравнение начинается ровно с r, а во втором совпадений нет. После позиции с q совпадениями правый край блока сдвигается на q вправо, а дальше n он уйти не может. Поэтому совпадений за всю работу не больше n − 1, а всего сравнений не больше 2n − 2.
Это та же амортизированная оценка, что у КМП: отдельная позиция может потребовать сотни сравнений, но они оплачены продвижением r, которое не повторяется. Замер — строка растёт, теломера против случайной ДНК:
Наклон наивной линии на теломере — 2: строка вдвое длиннее, работы вчетверо больше. При восьми тысячах букв наивный способ на Python медленнее Z-алгоритма примерно в 250 раз. А на случайной ДНК наивный способ в полтора раза быстрее: сравнивать там почти нечего, а Z-алгоритм тратит время на проверки блока. Если повторов в данных не бывает, определение работает не хуже алгоритма; Z-алгоритм нужен как гарантия на любых данных.
Z-функция и префикс-функция
Обе описывают, как строка совпадает сама с собой, но смотрят в разные стороны. Префикс-функция π[i] смотрит назад: какое самое длинное начало строки заканчивается в позиции i. Z-функция смотрит вперёд: какое начало строки начинается в позиции i. Одно переводится в другое за линейное время: если z[i] = m, то начало длины m заканчивается в позиции i + m − 1, и π там не меньше m. Задачи, которые решает одна, решает и другая.
Разница в том, когда нужны буквы. КМП читает текст по одной букве и ни разу не возвращается, поэтому работает на потоке, который нельзя перемотать. Z-функция заглядывает вперёд: z[i] не узнать, пока не прочитаны буквы правее i, и строку нужно держать целиком. Зато вопрос «сколько букв отсюда совпадает с началом» часто ближе к задаче, а в коде нет цикла откатов по таблице — только один указатель r, который идёт вправо.
Поиск и периоды
Поиск. Склейте образец, разделитель, которого нет ни в одной строке, и текст: p + «#» + t. Ни одно совпадение с началом не перешагнёт через «#», поэтому z склейки не больше m = |p| и равно m ровно там, где в тексте начинается вхождение. Это find_all из листинга; вхождения могут перекрываться: «aba» в «abacabadabacaba» начинается в позициях 0, 4, 8 и 12. Гасфилд называет этот поиск самым простым линейным алгоритмом, какой он знает. Склейка занимает n + m памяти; если это много, Z-функцию считают только для образца, а по тексту ведут такой же Z-блок, не храня значения.
Периоды. Число p — период строки, если каждая буква повторяет ту, что на p левее. Это то же самое, что «хвост с позиции p совпадает с началом до самого конца строки», то есть p + z[p] = n. Один проход по массиву даёт все периоды сразу:
periods of abaababaab: [5, 8, 10]; made of copies: abaab x 2 periods of TTAGGGTTAGGGTTA: [6, 12, 15]; made of copies: no periods of abcabcabc: [3, 6, 9]; made of copies: abc x 3
Если длина делится на наименьший период, строка собрана из его копий и сжимается в «кусок × число». Кусок теломеры с периодом 6 и длиной 15 не делится: он оборвался посреди звена, и задача о таких кусках есть в статье о КМП.
Таблица для Бойера — Мура. Правило хорошего суффикса в алгоритме Бойера — Мура спрашивает, где ещё в образце встречается его конец. Это Z-функция наоборот: в книге Гасфилда таблицу считают Z-функцией перевёрнутого образца.
Все повторы подряд: Мейн и Лоренц
Вернёмся к первой сцене. Квадратом называют кусок вида ww — одно и то же дважды подряд. Повтор подряд — кусок с периодом p, в котором помещаются хотя бы две полные копии и который нельзя продлить ни влево, ни вправо. Первая сцена показывает повторы подряд, и в каждом сидят квадраты. В тройном «…аше сиятельство, ваше сиятельство, ваше сиятельство» 51 знак, и квадрат длины 36 начинается с любой из первых 16 позиций.
Искать в лоб — перебрать все периоды p и для каждого пройти по строке, сравнивая s[i] с s[i + p]: серия из p и больше равенств подряд — повтор. Это около 3n²/8 сравнений, для романа — 3,2 триллиона. Майкл Мейн и Ричард Лоренц в 1984 году нашли способ за O(n log n), и держится он на Z-функции.
Делим строку пополам, s = u | v. Квадраты целиком внутри u или внутри v найдёт рекурсия. Остаются квадраты, которые пересекают середину. Возьмём такой квадрат с половиной длины l, у которого вторая половина начинается левее середины (другой случай зеркален). Квадрат — это равенство s[x] = s[x + l] для всех x из первой половины. Точка q = mid − l лежит в первой половине, и q + l — ровно середина. Равенство вокруг q распадается на два вопроса:
- сколько букв перед q совпадает с буквами перед серединой — обозначим k₁;
- сколько букв от q совпадает с буквами от середины — k₂.
Квадрат с половиной l, пересекающий середину, есть, когда k₁ + k₂ ≥ l и k₂ > 0 (при k₂ = 0 он кончается ровно на середине и целиком лежит в u). Его начала тогда заполняют отрезок, который считается из k₁ и k₂. Ответы на оба вопроса сразу для всех l дают Z-функции: k₁ — Z-функция перевёрнутой u, k₂ — Z-функция склейки v + «#» + u. Ещё две Z-функции нужны для зеркального случая. На каждом уровне рекурсии это O(n) работы, уровней log₂ n.
На главе XII третьей части первого тома — 12 913 знаков — алгоритм сделал 534 724 сравнения, а перебор всех периодов сделал бы 62 523 132, в 117 раз больше. На всём романе разница — в 16 тысяч раз: 193 миллиона сравнений против 3,2 триллиона. Квадратов в главе 144, а повторов подряд 125: длинные повторы содержат по нескольку квадратов. Квадратов в строке может быть порядка n² — в строке из одних «а» квадрат начинается почти с каждой позиции и почти любой чётной длины, — поэтому алгоритм выдаёт их отрезками начал, а не по одному.
Повторов подряд в романе 28 093 — меньше, чем знаков. Это не случайность. Роман Колпаков и Григорий Кучеров в 1999 году показали, что в строке длины n повторов подряд O(n) и все их можно найти за линейное время, и предположили, что их всегда меньше n. Доказали это Хидео Баннаи и соавторы — статья «The “Runs” Theorem» вышла в 2017 году.
Где ломается: точное равенство
Z-функция отвечает на вопрос о точном совпадении, буква в букву, и одна несовпавшая буква обрывает ответ. Переключите первую сцену на перевод Мод. Там самый длинный повтор — 134 знака молитвы Платона Каратаева: «Lord Jesus Christ, holy Saint Nicholas, Frola and Lavra! Lord Jesus Christ, holy Saint Nicholas, Frola and Lavra!» В нашем тексте оригинала та же молитва повтором не считается: «Господи Иисус Христос, Никола угодник, Фрола и Лавра, Господи Иисус Христос, Никола угодник! Фрола и Лавра…» — после второго «угодник» стоит восклицательный знак, а не запятая, и копия рвётся на одном знаке.
В ДНК так почти всегда. Центромера X-хромосомы человека — место, за которое хромосому растаскивают при делении клетки, — это около 3,1 миллиона букв, примерно 1400 копий одного звена длиной 2057 букв. Ниже кусок из 12 000 букв из её середины по первой полной сборке генома человека, T2T-CHM13. Выберите любую букву, и сцена посчитает Z-функцию от неё.
Пики стоят точно на линиях через каждые 2057 букв: звено видно сразу. И при каждом сдвиге на 2057 букв одинаковы 99 % букв. Но пики низкие: от буквы 501 копия совпадает с началом на 258, 396, 258, 405 и 405 букв, а не на две тысячи. Одна несовпадающая буква на сотню-две рвёт совпадение, и самый длинный точный кусок, общий у соседних копий во всём фрагменте, — 536 букв. Алгоритм Мейна и Лоренца на этих 12 000 буквах находит самый длинный повтор подряд в 12 букв. Для него центромеры нет.
Поэтому биологи ищут повторы иначе. Программа Tandem Repeats Finder Гэри Бенсона (1999) не требует точных копий: она моделирует повтор долей совпадающих букв и частотой вставок и выпадений между соседними копиями. Кандидатов она находит по коротким совпадающим словам на одинаковом расстоянии друг от друга, а потом выравнивает копии с допуском ошибок, как в статье о редакционном расстоянии. Точные алгоритмы вроде Мейна — Лоренца годятся там, где ошибка и есть предмет поиска: удвоенная фраза в наборе, «the the» в рукописи, задвоенная строка в журнале.
История
В 1984 году в Journal of Algorithms вышла статья Майкла Мейна и Ричарда Лоренца «An O(n log n) algorithm for finding all repetitions in a string». В ней был способ, описанный выше: разделить строку пополам и найти повторы через середину за линейное время. До этого повторы подряд изучали в комбинаторике слов с начала XX века, когда Аксель Туэ построил бесконечные строки без квадратов.
Имя Z-функции дал Дэн Гасфилд. В книге «Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology» (1997) он обозначил числа буквой Z, а отрезки — Z-блоками, и сделал их общей подготовкой для всех классических линейных алгоритмов поиска: КМП и Бойера — Мура он выводит из Z-значений, а не из их исходных таблиц. Сам способ посчитать Z-значения за линейное время, пишет Гасфилд, был придуман раньше и для другой цели; по распространённой версии, речь о работе Мейна и Лоренца. В олимпиадном программировании Z-функция стала стандартным инструментом наравне с префикс-функцией.
Задачи
В первой задаче надо найти, с какой длины начало гена перестаёт встречаться где-либо ещё, — на обеих нитях ДНК. Во второй — самый длинный кусок, записанный дважды подряд, в тексте до пятидесяти тысяч знаков; перебор периодов здесь не успевает, и нужен Мейн — Лоренц.
Праймер без двойников Фраза дваждыДанные: «Война и мир», Л. Н. Толстой, общественное достояние «Война и мир» в переводе Луизы и Эйлмера Мод, Project Gutenberg, общественное достояние Центромера X-хромосомы человека: сборка T2T-CHM13v2.0 (NCBI RefSeq NC_060947.1)