1632
правки
Изменения
м
{{Определение|definition ='''Тандемным повтором''' (англ. 'tandem repeat') в строке называются два вхождения какой-либо подстроки подряд. Иными словами, тандемный повтор описывается парой индексов <tex>i < j</tex> такими, что подстрока <tex>s[i \ldots j]</tex> {{---}} это две одинаковые строки, записанные подряд}} '''Алгоритм Крочемора''' (англ. 'crochemore 'Crochemore algorithm'') {{---}} алгоритм на строках, позволяющий найти все тандемные повторы в строке <tex>s[1..n]</tex> за <tex>O(n \log n)</tex>
|proof=TBA
* [http://e-maxx.ru/algo/string_tandems E-maxx {{---}} Поиск всех тандемных повторов в строке. Алгоритм Мейна-Лоренца]
[[Категория: Поиск тандемных повторов]]
rollbackEdits.php mass rollback
== Алгоритм ==
=== Упрощенный алгоритм ===
Прежде чем перейти к объяснению алгоритма Крочемора, вначале опишем простой алгоритм, который на каждом этапе достигает такого же результата, что и алгоритм Крочемора, а именно: в строке <tex> S </tex> он вычисляет все повторяющиеся подстроки длиной <tex> l </tex>, где <tex> l = 1,2,...,n - 1</tex>.
Рассмотрим следующую строку Фиббоначи:
{|class="wikitable" style="text-align:center"
|-
|| || <tex> 1 </tex> || <tex> 2 </tex> || <tex> 3 </tex> || <tex> 4 </tex> || <tex> 5 </tex> || <tex> 6 </tex>|| <tex> 7 </tex> || <tex> 8 </tex> || <tex> 9 </tex>|| <tex> 10 </tex>|| <tex> 11 </tex>|| <tex> 12 </tex> || <tex> 13 </tex>|| <tex> 14</tex>
|-
|<tex>f_6 = </tex> || a || b || a || a || b || a || b || a || a || b || a || a || b || $
|}
Будем вычислять все повторяющиеся подстроки длины <tex>l</tex> для всех <tex>l</tex>, таких что <tex>1 \leqslant l \leqslant n-1</tex>. Зная эти данные, мы автоматически находим все тандемные повторы.
{|class="wikitable" style="text-align:center"
|-
|rowspan="2"| <tex>l = 1</tex> || <tex> \langle 1, 3, 4, 6, 8, 9, 11, 12\rangle</tex> || <tex> \langle 2, 5, 7, 10, 13\rangle</tex> || <tex> \langle 14\rangle</tex>
|-
|| a || b || $
{|class="wikitable" style="text-align:center"
!colspan=6|Последовательная декомпозиция строки <tex>f_6 = abaababaabaab\$</tex>
|-
| rowspan="2" | <tex>l = 2</tex> || <tex> \langle 1, 4, 6, 9, 12\rangle</tex> || <tex> \langle 3, 8, 11\rangle</tex> || <tex> \langle 2, 5, 7, 10\rangle</tex> || <tex> \langle 13\rangle</tex> ||
|-
|| ab || aa || ba || b$ ||
|-
| rowspan="2" | <tex>l = 3</tex> || <tex> \langle 1, 4, 6, 9\rangle</tex> || <tex> \langle 12\rangle</tex> || <tex> \langle 3, 8, 11\rangle</tex> || <tex> \langle 2, 7, 10\rangle</tex> || <tex> \langle 5\rangle</tex>
|-
|| aba || aaab$ || aab || baa || bab
|-
| rowspan="2" | <tex>l = 4</tex> || <tex> \langle 1, 6, 9\rangle</tex> || <tex> \langle 4\rangle</tex> || <tex> \langle 3, 8\rangle</tex> || <tex> \langle 11\rangle</tex> || <tex> \langle 2, 7, 10\rangle</tex>
|-
|| abaa || abab || aaba || aab$ || baab
|-
| rowspan="2" | <tex>l = 5</tex> || <tex> \langle 1, 6, 9\rangle</tex> || <tex> \langle 3\rangle</tex> || <tex> \langle 8\rangle</tex> || <tex> \langle 2, 7\rangle</tex> || <tex> \langle 10\rangle</tex>
|-
|| abaab || aabab || aabaa || baaba || baab$
|-
| rowspan="2" | <tex>l = 6</tex> || <tex> \langle 1, 6\rangle</tex> || <tex> \langle 9\rangle</tex> || <tex> \langle 2\rangle</tex> || <tex> \langle 7\rangle</tex> ||
|-
|| abaaba || abaab$ || baabab || baabaa ||
|-
| rowspan="2" | <tex>l = 7</tex> || <tex> \langle 1\rangle</tex> || <tex> \langle 6\rangle</tex> || || ||
|-
|| abaabab || abaabaa || || ||
|}
Если реализовывать процесс декомпозиции "наивно", то поучаем получаем сложность <tex>O(n^2)</tex> Заметим также, что приведенная выше декомпозиция дает сразу же понять, где существуют тандемные повторы.
=== Оптимизация ===
Декомпозицию каждой последовательности можно получить косвенным путем, а не путем прямых вычислений. Идея такого подхода состоит в следующем:
на каждом уровне <tex>l</tex> выполняется непосредственная декомпозиция каждой последовательности <tex>c^{l}_j</tex>. Более точно, если <tex>c^{l}_j = \langle p_1, p_2, \ldots , p_r \rangle</tex>, то необходимо проверить совпадение букв <tex>s[p_1 + l], s[p_2 + l], \ldots, s[p_r + l]</tex>, и, если какие-либо пары букв <tex>s[p_i + l]</tex> и <tex>s[p_j + l]</tex> равны, то <tex>p_i</tex> и <tex>p_j</tex> помещаются в одну и ту же последовательность на уровне <tex>l + 1</tex>.
Заметим, что декомпозицию можно выполнить, основываясь не на разбиваемой последовательности, а на последовательностях, относительно которых будут разбиваться другие последовательности.
Для каждой позиции <tex>p_i > 1</tex> известно, что подстрока <tex>s[p_i - 1 \ldots p_i + l - 1]</tex> (длиной <tex>l + 1</tex>) относится к некоторой последовательности <tex>c^{l + 1}_{j'}</tex> на уровне <tex>l + 1</tex>. Поскольку последовательность <tex>c^{l}_{j}</tex> соответствует уникальной подстроке строки <tex>s</tex>, то каждая такая последовательность <tex>c^{l + 1}_{j'}</tex> должна формироваться из тех же позиций <tex>p_{i_1}, p_{i_2}, \ldots , p_{i_k}</tex> последовательности <tex>c^{l}_{j}</tex>, которые определяют класс эквивалентности
<tex>s[p_{i_1} - 1] = s[p_{i_2} - 1] = \ldots = s[p_{i_k} - 1]</tex>.
Таким образом, декомпозицию на уровне <tex>l + 1</tex> можно выполнить косвенным путем, рассматривая каждую последовательность уровня <tex>l</tex> с позиции, находящейся на <tex>1</tex> левее от начальной позиции этой последовательности.
{{Лемма
|statement=В каждом наборе последовательностей, порожденных одной последовательностью уровня <tex>l - 1</tex>, всегда можно исключить использование одной из них для декомпозиции последовательностей на уровне <tex>l</tex>
}}
При использовании [[Хеш-таблица|хеш-таблицы]], где ключом является подстрока, а значением {{---}} список позиций, где эта строка входит в <tex>s</tex>, декомпозицию на уровне <tex>l</tex> найдем за время, в среднем пропорциональное количеству позиций на уровне <tex>l - 1</tex>.
{{Определение
|definition =
В декомпозиции последовательности <tex>c^l_j</tex> на последовательности <tex>(c^{l+1}_1, c^{l+1}_2, \ldots, c^{l+1}_q), q \geqslant 1 </tex> назовем одну последовательность с наибольшим количеством элементов '''большой''', а остальные <tex>q - 1</tex> последовательности {{- --}} '''малыми'''. Для <tex>l = 1</tex> все последовательности будем считать '''малыми'''.
}}
|statement=Предположим, что декомпозиция последовательностей, соответствующих произвольной строке <tex>s[1..n]</tex>, выполняется для уровней <tex>l = 1, 2, \ldots, l^*</tex>, где <tex>l^*</tex> {{---}} наименьший уровень, на котором каждая последовательность содержит единственную позицию. Тогда каждая позиция <tex>i</tex> строки <tex>s</tex> входит в малые последовательности <tex>O(\log n)</tex> раз
|proof=
Заметим, что если последовательность <tex>c^l_j</tex> разбивается на подпоследовательности <tex>(c^{l+1}_1, c^{l+1}_2, \ldots, c^{l+1}_q)</tex>, то каждая малая последовательность <tex>c^{l+1}_{j'}</tex> удовлетворяет условию <tex>c^{l+1}_{j'} \leqslant {c^{l}_{j} \over 2}</tex>. Другими словами, при <tex>l \geqslant 2</tex> каждая малая последовательность не превышает половины размера своей исходной последовательности. Поскольку для <tex>l - 1</tex> начальная малая последовательность может содержать не более <tex>n </tex> позиций, то из этого следует, что ни одна из позиций не может входить в больше, чем <tex>\log_2(n+1)</tex> малых последовательностей.
}}
Поскольку строка <tex>s</tex> содержит <tex>n</tex> позиций, то из предыдущей леммы следует, что всего в малых последовательностях на всех уровнях содержится <tex>O(n \log n)</tex> позиций. Таким образом, если время обработки последовательностей на каждом уровне <tex>l</tex> пропорционально количеству элементов в малых последовательностях этого уровня, то полный процесс декомпозиции будет выполнен за <tex>O(n \log n)</tex>, чего что мы и хотели получить.
== Псевдокод ==
'''function''' crochemore(s: '''string'''): '''string'''
<tex>l</tex> <tex>\gets</tex> 1
Вычислим все последовательности на уровне 1 и пометим их как малые
l++
Найдем малые последовательности на уровне <tex>l</tex>
== См. также ==
* [[Алгоритм Ландау-Шмидта]]
== Источники информации ==
* ''Билл Смит'' '''Методы и алгоритмы вычислений на строках'''. Пер. с англ.{{---}} М.:Издательский дом "Вильямс", 2006. ISBN 5-8459-1081-1
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Дискретная математика и алгоритмыОсновные определения. Простые комбинаторные свойства слов]]
