MAXimal

добавлено: 6 Sep 2011 1:03
редактировано: 11 Feb 2012 15:03

Поиск всех тандемных повторов в строке. Алгоритм Мейна-Лоренца

Дана строка $s$ длины $n$ .

Тандемным повтором (tandem repeat) в ней называются два вхождения какой-либо подстроки подряд. Иными словами, тандемный повтор описывается парой индексов $i < j$ такими, что подстрока $s[i \ldots j]$ — это две одинаковые строки, записанные подряд.

Задача заключается в том, чтобы найти все тандемные повторы. Упрощённые варианты этой задачи: найти любой тандемный повтор или найти длиннейший тандемный повтор.

Примечание. Во избежание путаницы все строки в статье мы будем считать 0-индексированными, т.е. первый символ строки имеет индекс 0.

Описываемый здесь алгоритм был опубликован в 1982 г. Мейном и Лоренцем (см. список литературы).

Пример

Рассмотрим тандемные повторы на примере какой-нибудь простой строки, например:

$\text{[math]}$

В этой строке присутствуют следующие тандемные повторы:

$[2;5] =$
$[3;6] =$
$[7;8] =$

Другой пример:

$\text{[math]}$

Здесь есть только два тандемных повтора:

$[0;5] =$
$[2;3] =$

Число тандемных повторов

Вообще говоря, тандемных повторов в строке длины $n$ может быть порядка $O(n^2)$ .

Очевидным примером является строка, составленная из $n$ одинаковых букв — в такой строке тандемным повтором является любая подстрока чётной длины, которых примерно $n^2 / 4$ . Вообще, любая периодичная строка с коротким периодом будет содержать очень много тандемных повторов

С другой стороны, сам по себе этот факт никак не препятствует существованию алгоритма с асимптотикой $O (n \log n)$ , поскольку алгоритм может выдавать тандемные повторы в том или ином сжатом виде, группами по несколько штук сразу.

Более того, существует понятие серий — четвёрок чисел, которые описывают целую группу периодических подстрок. Было доказано, что число серий в любой строке линейно по отношению к длине строки.

Впрочем, описываемый ниже алгоритм не использует понятие серий, поэтому не будем детализировать это понятие.

Приведём здесь и другие интересные результаты, относящиеся к количеству тандемных повторов:

Известно, что если рассматривать только примитивные тандемные повторы (т.е. такие, половинки которых не являются кратными строками), то их количество в любой строке — $O (n \log n)$ .
Если кодировать тандемные повторы тройками чисел (называемыми тройками Крочемора (Crochemore)) $(i,p,r)$ (где $i$ — позиция начала, $p$ — длина повторяющейся подстроки, $r$ — количество повторов), то все тандемные повторы любой строки можно вывести с помощью $O (n \log n)$ таких троек. (Именно такой результат получается на выходе алгоритма Крочемора нахождения всех тандемных повторов.)
Строки Фибоначчи, определяемые следующим образом:
$t_0 = b,$
$t_1 = a,$
$t_i = t_{i-1} + t_{i-2},$
являются "сильно" периодичными.
Число тандемных повторов в $i$ -ой строке Фибоначчи длины $f_i$ , даже сжатых с помощью троек Крочемора, составляет $O (f_n \log f_n)$ .
Число примитивных тандемных повторов в строках Фибоначчи — также имеет порядок $O (f_n \log f_n)$ .

Алгоритм Мейна-Лоренца

Идея алгоритма Мейна-Лоренца довольно стандартна: это алгоритм "разделяй-и-властвуй".

Кратко он заключается в том, что исходная строка разбивается пополам, решение запускается от каждой из двух половинок по отдельности (тем самым мы найдём все тандемные повторы, располагающиеся только в первой или только во второй половинке). Дальше идёт самая сложная часть — это нахождение тандемных повторов, начинающихся в первой половине и заканчивающихся во второй (назовём такие тандемные повторы для удобства пересекающими). Как именно это делается — и есть сама суть алгоритма Мейна-Лоренца; это мы подробно опишем ниже.

Асимптотика алгоритма "разделяй-и-властвуй" хорошо исследована. В частности, для нас важно, что если мы научимся искать пересекающие тандемные повторы в строке длины $n$ за $O(n)$ , то итоговая асимптотика всего алгоритма получится $O (n \log n)$ .

Поиск пересекающих тандемных повторов

Итак, алгоритм Мейна-Лоренца свёлся к тому, чтобы по заданной строке $s$ научиться искать все пересекающие тандемные повторы, т.е. такие, которые начинаются в первой половине строки, а заканчиваются — во второй.

Обозначим через $u$ и $v$ две половинки строки $s$ :

$s = u + v$

(их длины примерно равны длине строки $s$ , делённой пополам).

Правые и левые тандемные повторы

Рассмотрим произвольный тандемный повтор и посмотрим на его средний символ (точнее, на тот символ, с которого начинается вторая половинка тандема; т.е. если тандемный повтор — это подстрока $s[i \ldots j]$ , то средним символом будет $(i+j+1)/2$ .

Тогда назовём тандемный повтор левым или правым в зависимости от того, где находится этот символ — в строке $u$ или в строке $v$ . (Можно сказать и так: тандемный повтор называется левым, если большая его часть лежит в левой половине строки $s$ ; иначе — тандемный повтор называется правым.)

Научимся искать все левые тандемные повторы; для правых всё будет аналогично.

Центральная позиция $cntr$ тандемного повтора

Обозначим длину искомого левого тандемного повтора через $2k$ (т.е. длина каждой половинки тандемного повтора — это $k$ ). Рассмотрим первый символ тандемного повтора, попадающий в строку $v$ (он стоит в строке $s$ в позиции $length(u)$ ). Он совпадает с символом, стоящим на $k$ позиций раньше него; обозначим эту позицию через $cntr$ .

Искать все тандемные повторы мы будем, перебирая эту позицию $cntr$ : т.е. найдём сначала все тандемные повторы с одним значением $cntr$ , затем с другим значением, и т.д. — перебирая все возможные значения $cntr$ от $0$ до $length(u)-1$ .

Например, рассмотрим такую строку:

$s =$

(символ вертикальной черты разделяет две половинки $u$ и $v$ )

Тандемный повтор $\text{[math]}$ , содержащийся в этой строке, будет обнаружен, когда мы будем просматривать значение $cntr = 1$ — потому что именно в позиции $1$ стоит символ 'a', совпадающий с первым символом тандемного повтора, попавшим в половинку $v$ .

Критерий наличия тандемного повтора с заданным центром $cntr$

Итак, мы должны научиться для зафиксированного значения $cntr$ быстро искать все тандемные повторы, соответствующие ему.

Получаем такую схему (для абстрактной строки, в которой содержится тандемный повтор $\text{[math]}$ ):

$\setlength{\unitlength}{2mm} \begin{picture}([...]$

Здесь через $l_1$ и $l_2$ мы обозначили длины двух кусочков тандемного повтора: $l_1$ — это длина части тандемного повтора до позиции $cntr-1$ , а $l_2$ — это длина части тандемного повтора от $cntr$ до конца половинки тандемного повтора. Таким образом, $l_1+l_2+l_1+l_2$ — это длина тандемного повтора.

Взглянув на эту картинку, можно понять, что необходимое и достаточное условие того, что с центром в позиции $cntr$ находится тандемный повтор длины $2 l = 2 (l_1 + l_2) = 2 (length(u) - cntr)$ , является следующее условие:

Пусть $k_1$ — это наибольшее число такое, что $k_1$ символов перед позицией $cntr$ совпадают с последними $k_1$ символами строки $u$ :
$u[ cntr-k_1 \ldots cntr-1 ] == u[ length(u)-k_1 \[...]$
Пусть $k_2$ — это наибольшее число такое, что $k_2$ символов, начиная с позиции $cntr$ , совпадают с первыми $k_2$ символами строки $v$ :
$u[ cntr \ldots cntr+k_2-1] == v[ 0 \ldots k_2-1 ][...]$
Тогда должно выполняться:
$\cases{ l_1 \le k_1, \cr l_2 \le k_2. }$

Этот критерий можно переформулировать таким образом. Зафиксируем конкретное значение $cntr$ , тогда:

Все тандемные повторы, которые мы будем сейчас обнаруживать, будут иметь длину $2 l = 2 (length(u) - cntr)$ .
Однако таких тандемных повторов может быть несколько: всё зависит от выбора длин кусочков $l_1$ и $l_2 = l - l_1$ .
Найдём $k_1$ и $k_2$ , как было описано выше.
Тогда подходящими будут являться тандемные повторы, для которых длины кусочков $l_1$ и $l_2$ удовлетворяют условиям:
$\cases{ l_1 + l_2 = l = length(u) - cntr, \cr l[...]$

Алгоритм нахождения длин $k_1$ и $k_2$

Итак, вся задача сводится к быстрому вычислению длин $k_1$ и $k_2$ для каждого значения $cntr$ .

Напомним их определения:

$k_1$ — максимальное неотрицательное число, для которого выполнено:
$u[ cntr-k_1 \ldots cntr-1 ] == u[ length(u)-k_1 \[...]$
$k_2$ — максимальное неотрицательное число, для которого выполнено:
$u[ cntr \ldots cntr+k_2-1] == v[ 0 \ldots k_2-1 ][...]$

На оба этих запроса можно отвечать за $O(1)$ , используя алгоритм нахождения Z-функции:

Для быстрого нахождения значений $k_1$ заранее посчитаем Z-функцию для строки $\overline{u}$ (т.е. строки $u$ , выписанной в обратном порядке).
Тогда значение $k_1$ для конкретного $cntr$ будет просто равно соответствующему значению массива Z-функции.
Для быстрого нахождения значений $k_2$ заранее посчитаем Z-функцию для строки $v+\#+u$ (т.е. строки $u$ , приписанной к строке $v$ через символ-разделитель).
Опять же, значение $k_2$ для конкретного $cntr$ надо будет просто взять из соответствующего элемента Z-функции.

Поиск правых тандемных повторов

До этого момента мы работали только с левыми тандемными повторами.

Чтобы искать правые тандемные повторы, надо действовать аналогично: мы определяем центр $cntr$ как символ, соответствующий последнему символу тандемного повтора, попавшему в первую строку.

Тогда длина $k_1$ будет определяться как наибольшее число символов до позиции $cntr$ включительно, совпадающих с последними символами строки $u$ . Длина $k_2$ будет определяться как максимальное число символов, начиная с $cntr+1$ , совпадающих с первыми символами строки $v$ .

Таким образом, для быстрого нахождения $k_1$ и $k_2$ надо будет посчитать заранее Z-функцию для строк $\overline{u} + \# + \overline{v}$ и $v$ соответственно. После этого, перебирая конкретное значение $cntr$ , мы по тому же самому критерию будем находить все правые тандемные повторы.

Асимптотика

Асмиптотика алгоритма Мейна-Лоренца составит, таким образом, $O (n \log n)$ : поскольку этот алгоритм представляет собой алгоритм "разделяй-и-властвуй", каждый рекурсивный запуск которого работает за время, линейное относительно длины строки: для четырёх строк за линейное время ищется их Z-функция, а затем перебирается значение $cntr$ и выводятся все группы обнаруженных тандемных повторов.

Тандемные повторы обнаруживаются алгоритмом Мейна-Лоренца в виде своеобразных групп: таких четвёрок $(cntr, l, k_1, k_2)$ , каждая из которых обозначает группу тандемных повторов с длиной $l$ , центром $cntr$ и с всевозможными длинами кусочков $l_1$ и $l_2$ , удовлетворяющими условиям:

$\cases{ l_1 + l_2 = l, \cr l_1 \le k_1, \cr l_[...]$

Реализация

Приведём реализацию алгоритма Мейна-Лоренца, которая за время $O (n \log n)$ находит все тандемные повторы данной строки в сжатом виде (в виде групп, описываемых четвёрками чисел).

В целях демонстрации обнаруженные тандемные повторы за время $O (n^2)$ "разжимаются" и выводятся по отдельности. Этот вывод при решении реальных задач легко будет заменить на какие-то другие, более эффективные, действия, например, на поиск наидлиннейшего тандемного повтора или подсчёт количества тандемных повторов.

vector<int> z_function (const string & s) {
	int n = (int) s.length();
	vector<int> z (n);
	for (int i=1, l=0, r=0; i<n; ++i) {
		if (i <= r)
			z[i] = min (r-i+1, z[i-l]);
		while (i+z[i] < n && s[z[i]] == s[i+z[i]])
			++z[i];
		if (i+z[i]-1 > r)
			l = i,  r = i+z[i]-1;
	}
	return z;
}
 
void output_tandem (const string & s, int shift, bool left, int cntr, int l, int l1, int l2) {
	int pos;
	if (left)
		pos = cntr-l1;
	else
		pos = cntr-l1-l2-l1+1;
	cout << "[" << shift + pos << ".." << shift + pos+2*l-1 << "] = " << s.substr (pos, 2*l) << endl;
}
 
void output_tandems (const string & s, int shift, bool left, int cntr, int l, int k1, int k2) {
	for (int l1=1; l1<=l; ++l1) {
		if (left && l1 == l)  break;
		if (l1 <= k1 && l-l1 <= k2)
			output_tandem (s, shift, left, cntr, l, l1, l-l1);
	}
}
 
inline int get_z (const vector<int> & z, int i) {
	return 0<=i && i<(int)z.size() ? z[i] : 0;
}
 
void find_tandems (string s, int shift = 0) {
	int n = (int) s.length();
	if (n == 1)  return;
 
	int nu = n/2,  nv = n-nu;
	string u = s.substr (0, nu),
		v = s.substr (nu);
	string ru = string (u.rbegin(), u.rend()),
		rv = string (v.rbegin(), v.rend());
 
	find_tandems (u, shift);
	find_tandems (v, shift + nu);
 
	vector<int> z1 = z_function (ru),
		z2 = z_function (v + '#' + u),
		z3 = z_function (ru + '#' + rv),
		z4 = z_function (v);
	for (int cntr=0; cntr<n; ++cntr) {
		int l, k1, k2;
		if (cntr < nu) {
			l = nu - cntr;
			k1 = get_z (z1, nu-cntr);
			k2 = get_z (z2, nv+1+cntr);
		}
		else {
			l = cntr - nu + 1;
			k1 = get_z (z3, nu+1 + nv-1-(cntr-nu));
			k2 = get_z (z4, (cntr-nu)+1);
		}
		if (k1 + k2 >= l)
			output_tandems (s, shift, cntr<nu, cntr, l, k1, k2);
	}
}

Литература

Michael Main, Richard J. Lorentz. An O (n log n) Algorithm for Finding All Repetitions in a String [1982]
Bill Smyth. Computing Patterns in Strings [2003]
Билл Смит. Методы и алгоритмы вычислений на строках [2006]