Алгоритм Крочемора

Алгоритм Крочемора (англ. Crochemore algorithm) — алгоритм на строках, позволяющий найти все тандемные повторы в строке [math]s[1..n][/math] за [math]O(n \log n)[/math]

Алгоритм

Разобьем описание алгоритма на две части: сначала покажем упрощенный алгоритм, работающий за [math]O(n^2)[/math], а затем попытаемся его оптимизировать до [math]O(n \log n)[/math]

Упрощенный алгоритм

Прежде чем перейти к объяснению алгоритма Крочемора, вначале опишем простой алгоритм, который на каждом этапе достигает такого же результата, что и алгоритм Крочемора, а именно: в строке [math] S [/math] он вычисляет все повторяющиеся подстроки длиной [math] l [/math], где [math] l = 1,2,...,n - 1[/math].

Рассмотрим следующую строку Фиббоначи:

[math] 1[/math]

[math] 2[/math]

[math] 3[/math]

[math] 4[/math]

[math] 5[/math]

[math] 6 [/math]

[math] 7[/math]

[math] 8[/math]

[math] 9 [/math]

[math] 10 [/math]

[math] 11 [/math]

[math] 12[/math]

[math] 13 [/math]

[math] 14 [/math]

[math]f_6 [/math]

a

b

a

a

b

a

b

a

a

b

a

a

b

$

Будем вычислять все повторяющиеся подстроки длины [math]l[/math] для всех [math]l[/math], таких что [math]1 \leqslant l \leqslant n-1[/math]. Зная эти данные, мы автоматически находим все тандемные повторы.

Предположим, что в строке [math]f_6[/math] вычислены последовательности позиций, в которых встречаются одинаковые символы:

[math]l = 1[/math]	[math] \langle 1, 3, 4, 6, 8, 9, 11, 12 \rangle[/math]	[math] \langle 2, 5, 7, 10, 13 \rangle[/math]	[math] \langle 14 \rangle[/math]
	a	b	$

Если нам заранее известен алфавит, и он индексирован, то мы можем выполнить данное вычисление за [math]O(n)[/math].

Далее для [math]l = 2[/math] мы хотим найти все повторяющиеся подстроки длины [math]2[/math]. Поскольку повторяющиеся подстроки длины [math]l \geqslant 2[/math] будут иметь общий префикс длиной [math]l - 1[/math], то вычисления уровня [math]l[/math] должны привести к последовательностям, которые будут подпоследовательностями последовательностей, вычисленных на уровне [math]l - 1[/math]. Другими словами, разбиение на уровне [math]l \geqslant 2[/math] — декомпозиция разбиения на уровне [math]l - 1[/math]:

Последовательная декомпозиция строки [math]f_6 = abaababaabaab\$[/math]
[math]l = 2[/math]	[math] \langle 1, 4, 6, 9, 12 \rangle[/math]	[math] \langle 3, 8, 11 \rangle[/math]	[math] \langle 2, 5, 7, 10 \rangle[/math]	[math] \langle 13 \rangle[/math]
	ab	aa	ba	b$
[math]l = 3[/math]	[math] \langle 1, 4, 6, 9 \rangle[/math]	[math] \langle 12 \rangle[/math]	[math] \langle 3, 8, 11 \rangle[/math]	[math] \langle 2, 7, 10 \rangle[/math]	[math] \langle 5 \rangle[/math]
	aba	ab$	aab	baa	bab
[math]l = 4[/math]	[math] \langle 1, 6, 9 \rangle[/math]	[math] \langle 4 \rangle[/math]	[math] \langle 3, 8 \rangle[/math]	[math] \langle 11 \rangle[/math]	[math] \langle 2, 7, 10 \rangle[/math]
	abaa	abab	aaba	aab$	baab
[math]l = 5[/math]	[math] \langle 1, 6, 9 \rangle[/math]	[math] \langle 3 \rangle[/math]	[math] \langle 8 \rangle[/math]	[math] \langle 2, 7 \rangle[/math]	[math] \langle 10 \rangle[/math]
	abaab	aabab	aabaa	baaba	baab$
[math]l = 6[/math]	[math] \langle 1, 6 \rangle[/math]	[math] \langle 9 \rangle[/math]	[math] \langle 2 \rangle[/math]	[math] \langle 7 \rangle[/math]
	abaaba	abaab$	baabab	baabaa
[math]l = 7[/math]	[math] \langle 1 \rangle[/math]	[math] \langle 6 \rangle[/math]
	abaabab	abaabaa

Если реализовывать процесс декомпозиции "наивно", то получаем сложность [math]O(n^2)[/math]

Заметим также, что приведенная выше декомпозиция дает сразу же понять, где существуют тандемные повторы.

Оптимизация

Декомпозицию каждой последовательности можно получить косвенным путем, а не путем прямых вычислений. Идея такого подхода состоит в следующем: на каждом уровне [math]l[/math] выполняется непосредственная декомпозиция каждой последовательности [math]c^{l}_j[/math]. Более точно, если [math]c^{l}_j = \langle p_1, p_2, \ldots , p_r \rangle[/math], то необходимо проверить совпадение букв [math]s[p_1 + l], s[p_2 + l], \ldots, s[p_r + l][/math], и, если какие-либо пары букв [math]s[p_i + l][/math] и [math]s[p_j + l][/math] равны, то [math]p_i[/math] и [math]p_j[/math] помещаются в одну и ту же последовательность на уровне [math]l + 1[/math].

Заметим, что декомпозицию можно выполнить, основываясь не на разбиваемой последовательности, а на последовательностях, относительно которых будут разбиваться другие последовательности.

Для каждой позиции [math]p_i \gt 1[/math] известно, что подстрока [math]s[p_i - 1 \ldots p_i + l - 1][/math] (длиной [math]l + 1[/math]) относится к некоторой последовательности [math]c^{l + 1}_{j'}[/math] на уровне [math]l + 1[/math]. Поскольку последовательность [math]c^{l}_{j}[/math] соответствует уникальной подстроке строки [math]s[/math], то каждая такая последовательность [math]c^{l + 1}_{j'}[/math] должна формироваться из тех же позиций [math]p_{i_1}, p_{i_2}, \ldots , p_{i_k}[/math] последовательности [math]c^{l}_{j}[/math], которые определяют класс эквивалентности [math]s[p_{i_1} - 1] = s[p_{i_2} - 1] = \ldots = s[p_{i_k} - 1][/math].

Таким образом, декомпозицию на уровне [math]l + 1[/math] можно выполнить косвенным путем, рассматривая каждую последовательность уровня [math]l[/math] с позиции, находящейся на [math]1[/math] левее от начальной позиции этой последовательности.

Лемма:

В каждом наборе последовательностей, порожденных одной последовательностью уровня [math]l - 1[/math], всегда можно исключить использование одной из них для декомпозиции последовательностей на уровне [math]l[/math]

При использовании хеш-таблицы, где ключом является подстрока, а значением — список позиций, где эта строка входит в [math]s[/math], декомпозицию на уровне [math]l[/math] найдем за время, в среднем пропорциональное количеству позиций на уровне [math]l - 1[/math].

Определение:

В декомпозиции последовательности [math]c^l_j[/math] на последовательности [math](c^{l+1}_1, c^{l+1}_2, \ldots, c^{l+1}_q), q \geqslant 1 [/math] назовем одну последовательность с наибольшим количеством элементов большой, а остальные [math]q - 1[/math] последовательности — малыми. Для [math]l = 1[/math] все последовательности будем считать малыми.

Лемма:

Предположим, что декомпозиция последовательностей, соответствующих произвольной строке [math]s[1..n][/math], выполняется для уровней [math]l = 1, 2, \ldots, l^*[/math], где [math]l^*[/math] — наименьший уровень, на котором каждая последовательность содержит единственную позицию. Тогда каждая позиция [math]i[/math] строки [math]s[/math] входит в малые последовательности [math]O(\log n)[/math] раз

Доказательство:

[math]\triangleright[/math]

Заметим, что если последовательность [math]c^l_j[/math] разбивается на подпоследовательности [math](c^{l+1}_1, c^{l+1}_2, \ldots, c^{l+1}_q)[/math], то каждая малая последовательность [math]c^{l+1}_{j'}[/math] удовлетворяет условию [math]c^{l+1}_{j'} \leqslant {c^{l}_{j} \over 2}[/math]. Другими словами, при [math]l \geqslant 2[/math] каждая малая последовательность не превышает половины размера своей исходной последовательности. Поскольку для [math]l - 1[/math] начальная малая последовательность может содержать не более [math]n[/math] позиций, то из этого следует, что ни одна из позиций не может входить в больше, чем [math]\log_2(n+1)[/math] малых последовательностей.

[math]\triangleleft[/math]

Поскольку строка [math]s[/math] содержит [math]n[/math] позиций, то из предыдущей леммы следует, что всего в малых последовательностях на всех уровнях содержится [math]O(n \log n)[/math] позиций. Таким образом, если время обработки последовательностей на каждом уровне [math]l[/math] пропорционально количеству элементов в малых последовательностях этого уровня, то полный процесс декомпозиции будет выполнен за [math]O(n \log n)[/math], что мы и хотели получить.

Псевдокод

  function crochemore(s: string): string
     [math]l[/math] [math]\gets[/math] 1
     Вычислим все последовательности на уровне 1 и пометим их как малые
     while [math]\exists[/math] малая последовательность на уровне [math]l[/math]:
        out [math]\gets[/math] кратные строки с периодом l
        Вычислим декомпозицию последовательностей уровня [math]l[/math], используя только малые последовательности
        l++
        Найдем малые последовательности на уровне [math]l[/math]

См. также

• Алгоритм Ландау-Шмидта

Источники информации

• Билл Смит Методы и алгоритмы вычислений на строках. Пер. с англ.— М.:Издательский дом "Вильямс", 2006. ISBN 5-8459-1081-1