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

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Тандемным повтором (tandem repeat) в строке называются два вхождения какой-либо подстроки подряд. Иными словами, тандемный повтор описывается парой индексов [math]i \lt j[/math] такими, что подстрока [math]s[i \ldots j][/math] — это две одинаковые строки, записанные подряд.


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

Идея

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

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13
[math]f_6 = [/math] a b a a b a b a a b a a b


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

[math]l = 1[/math] <1, 3, 4, 6, 8, 9, 11, 12> <2, 5, 7, 10, 13>
a b

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

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

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

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

Оптимизация

Декомпозицию каждой последовательности можно получить косвенным путем, а не путем прямых вычислений. Идея такого подхода состоит в следующем: на каждом уровне [math]l[/math] выполняется непосредственная декомпозиция каждой последовательности [math]c^{(l)}_j[/math]. Более точно, если [math]c^{(l)}_j = \lt p_1, p_2, \ldots , p_r\gt [/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]f_6[/math] последовательность [math]\lt 1, 4, 6, 9\gt [/math] на уровне [math]3[/math] разбивается на уровне [math]4[/math] на последовательности [math]\lt 1, 6, 9\gt [/math] и [math]\lt 4\gt [/math], поскольку [math]f_6[1 + 3] = f_6[6 + 3] = f_6[9 + 3] \neq f_6[4 + 3][/math].


Но декомпозицию можно выполнить, основываясь не на разбиваемой последовательности, а на последовательностях, относительно которых будут разбиваться другие последовательности. Снова рассмотрим уровень [math]l = [/math] и последовательность [math]c^{(3)}_1 = \lt p_1, p_2, p_3, p_4\gt = \lt 1, 4, 6, 9\gt [/math], относящуюся к подстроке [math]aba[/math].

Псевдокод

Реализация

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

Сложность

Источники