1632
правки
Изменения
м
Метод нахождения всех тандемных повторой за время <tex>O( n \log n + z)</tex>, где <tex>z</tex> — число всех тандемных повторов в <tex>S</tex>. Метод разработали Ландау и Шмидт.Рещение Решение Ландау-Шмидта — это рекурсивный алгоритм типа "разделяй и властвуй", который основан на возможности вычислять запросы о наибольшем общем продолжении за константное время. Пусть <tex>h = [\lfloor n/2]\rfloor </tex>. В укрупненном масштабе метод Ландау-Шмидта делит задачу нахождения всех тандемных повторов на четыре подзадачи:
# * Найти все тандемные повторы, содержащиеся целиком в первой половине <tex>S</tex>( до позиции <tex>h</tex> включительно).# * Найти все тандемные повторы, содержащиеся целиком во второй половине <tex>S</tex> ( после позиции <tex>h</tex>).# * Найти все тандемные повторы, в которых первая копия покрывает позицию <tex>h</tex>.# * Найти все тандемные повторы, в которых вторая копия покрывает позицию <tex>h</tex>.
*===Алгоритм для задачи 3случая с перекрытием===Мы хотим найти все тандемные повторы, у которых первая копия покрывает позицию <tex>h</tex> ( но не обязательно начинается в ней). Идея алгоритма заключается в следующем. Для любого фиксированного <tex>l</tex> можно за константное время проверить, существует ли такой тандемный повтор длины <tex>2l</tex>, у которого первая копия покрывает позицию <tex>h</tex>. Применение этого теста ко всем допустимым значениям <tex>l</tex> означает, что за время <tex>O( n)</tex> мы можем найти все длины таких тандемных повторов. Более того, для каждой такой длины мы можем перечислить начальные точки этих тандемных повторов за время, пропорциональное их числу. Ниже описано, как проверить
== Теорема ==
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D1%80%D0%BE%D1%87%D0%B5%D0%BC%D0%BE%D1%80%D0%B0 Алгоритм-Крочемора]
* [http://e-maxx.ru/algo/string_tandems Алгоритм Мейна-Лоренца]
* [http://digitool.library.colostate.edu/webclient/DeliveryManager?pid=166681 Michael G. Main and Richard J. Lorentz An O( n log n) Algorithm for Finding All Repetitions in a String]
[[Категория: Дискретная математика и алгоритмы]]
rollbackEdits.php mass rollback
== Определения ==
{{Определение
|definition=Подстрока <tex>\alpha</tex>, содержащаяся в строке <tex>S</tex>, называется '''тандемным рядом'''(англ. ''tandem array'') строки <tex>\beta</tex> ( называемой основой), если а состоит из более чем одной последовательной копии <tex>\beta</tex>.
}}
Например, если <tex>S = xyzabcabcabcabcpq</tex>, то <tex>S = abcabcabcabc</tex> — тандемный ряд строки <tex>\beta = abc</tex>. Заметим, что <tex>S</tex> содержит также тандемный ряд строки <tex>abcabc</tex> ( т.е. то есть тандемный ряд с более длинной основой). Тандемный
ряд ''максимален'', если он не может быть продолжен ни влево, ни вправо. При фиксированной основе <tex>\beta</tex> тандемный ряд <tex>\beta</tex> в <tex>S</tex> может быть задан парой чисел <tex>( j, k)</tex>, определяющей его начальную позицию в <tex>S</tex> и число повторов <tex>\beta</tex>.
{{Определение
|definition='''Тандемный повтор''' (англ. ''tandem repeat'') <tex>\alpha</tex> — это строка, которая может быть записана как <tex>\beta\beta</tex>, где <tex>\beta</tex> — подстрока <tex>\alpha</tex>.
}}
Каждый тандемный повтор задается начальной позицией повтора и длиной подстроки <tex>\beta</tex>. Это определение не требует, чтобы <tex>\beta</tex> была максимальной длины. Например,в строке <tex>xababababy</tex> есть шесть тандемных повторов. Два из них начинаются в позиции два: <tex>abab</tex> и <tex>abababab</tex>. В первом случае <tex>\beta = ab</tex>, а во втором <tex>\beta = abab</tex>.
== Алгоритм ==
Ясно, что никакой тандемный повтор не может встретиться больше чем в одной из этих подзадач. Первые две подзадачи решаются рекурсивно применением того же алгоритма Ландау-Шмидта. Две последние подзадачи симметричны, поэтому мы рассмотрим только третью подзадачу, и алгоритм для нее определит весь алгоритм.
{|border="0" cellpadding="2" width=30% align=right
|[[Файл: tandemtandem1.png|thumb|400px|center| Любая позиция между <tex>A</tex> и <tex>B</tex> включительно может быть начальной точкой тандемного повтора длины <tex>2l</tex>. Как указывается в шаге 4, длины <tex>l_1</tex> и <tex>l_2</tex> обе положительны, поэтому подынтервал этих начальных точек определяет тандемные повторы, в которых первая копия покрывает <tex>h</tex>.]]
|}
число <tex>l</tex>.
# Положить <tex>q:=h + l</tex>.# Вычислить наибольшее общее продолжение ( в прямом направлении) из позиций <tex>h</tex> и <tex>q</tex>. Пусть <tex>l_1</tex> — длина этого продолжения.# Вычислить наибольшее общее продолжение ( в обратном направлении) из позиций <tex>h - 1</tex> и <tex>q - 1</tex>. Пусть <tex>l_2</tex> — длина этого продолжения.# Тандемный повтор длины <tex>2l</tex>, первая копия которого покрывает позицию <tex>h</tex>, существует в том и только том случае, если <tex>l_1 + l_2 \geqslant l</tex> и обе длины <tex>l_1</tex> и <tex>l_2</tex> положительны. Более того, если такой тандемный повтор длины <tex>2l</tex> существует, то он может начинаться в любой позиции от <tex>\max ( h - l_2, \ h — - l + 1)</tex> до <tex>\min ( h + l_1 — - l, \ h)</tex> включительно. Вторая копия повтора начинается в <tex>l</tex> позициях вправо. Вывести каждую из этих начальных позиций вместе с длиной <tex>2l</tex>.
=== Корректность ===
{{Лемма
|statement = Приведенный метод корректно решает подзадачу 3 для фиксированного <tex>h</tex> Это значит, что он находит все тандемные повторы, у которых первая копия покрывает позицию <tex>h</tex>. Для фиксированного <tex>h</tex> его время работы случай с перекрытием равно <tex>O( n/2) + z_h</tex>, где <tex>z_h</tex> — число таких тандемных повторов.
|proof =
Предположим сначала, что имеется тандемный повтор, у которого первая копия покрывает позицию h, и его длина равна, скажем, <tex>2l</tex>. Это означает, что позиция <tex>q = h + l</tex> во второй копии соответствует позиции <tex>h</tex> в первойx копии. Следовательно, для того чтобы обеспечить совпадение суффиксов в этих копиях, некоторая подстрока, начинающаяся в <tex>h</tex>, должна совпадать с подстрокой, начинающейся в <tex>q</tex>. Такая подстрока может иметь длину не более <tex>l_1</tex>. Аналогично, должна быть подстрока, кончающаяся в <tex>h - 1</tex>, которая совпадает с подстрокой, кончающейся в <tex>q-1</tex>, для того чтобы обеспечить совпадение префиксов. Длина этой подстроки не должна превосходить <tex>l_2</tex>. Так как все символы между <tex>h</tex> и <tex>q</tex> содержатся в одной из двух копий, то <tex>l_1 + l_2 \geqslant l</tex>. Обратно, рассуждая в основном так же, если <tex> l_1 + l_2 \leqslant l </tex> и <tex>l_1</tex> и <tex>l_2</tex> положительны, то можно найти тандемный повтор длины <tex>2l</tex>, у которого первая копия покрывает <tex>h</tex>. Необходимое и достаточное условие существования такого тандема теперь доказано.
Обратное доказательство, что все начальные позиции попадают в названный диапазон, аналогично доказывается.
Для подсчета времени сначала отметим, что при фиксированном <tex>h</tex> методу нужно константное время на один выбор <tex>l</tex> для того, чтобы выполнить общие запросы о продолжении, и, таким образом, время <tex>O( n/2)</tex> на все такие запросы. Для любого фиксированного <tex>l</tex> методу нужно константное время на обнаруживаемый тандем, и никакой тандем не обнаруживается дважды, так как у всех обнаруживаемых тандемов длины <tex>2l</tex> стартовые точки различны. Поскольку сообщение о каждом повторе состоит из начальной точки и длины, то алгоритм никогда не сообщает о тандемном повторе дважды. Следовательно, время, расходуемое на вывод информации о тандемных повторах, пропорционально <tex>z_h</tex> — числу повторов, у которых первая копия покрывает позицию <tex>h</tex>.}}
Приведенный метод корректно решает случай с перекрытием для фиксированного <tex>h</tex> Это значит, что он находит все тандемные повторы, у которых первая копия покрывает позицию <tex>h</tex>.
Теперь покажем что сам Алгоритм правильный.
{{Теорема
|statement = Каждый тандемный повтор в <tex>S</tex> находится решением подзадач 1-4 и при этом только единожды. Время работы алгоритма равно <tex>O( n \log n + z)</tex>, где <tex>z</tex> — число всех тандемных повторов в <tex>S</tex>.
|proof=
То, что алгоритм находит все тандемные повторы, прямо следует из факта, что каждый тандем имеет форму, предусмотренную одной из подзадач 1 —4для всех случаев. Чтобы показать, что никакой тандемный повтор не выводится дважды, вспомним, что для <tex>h = n/2</tex> никакой из тандемов не принимает формы, предусмотренной более чем одной из четырех подзадач. Рекурсивно это выполняется для подзадач 1 и 2первых двух случаев. Далее, при доказательстве Леммы леммы мы установили, что решение подзадачи 3( а также 4) покрытиями никогда не получает один и тот же тандем дважды. Следовательно, при полном решении четырех подзадач никакой тандемный повтор не выводится дважды. Отсюда следует, что время вывода всех тандемных повторов равно <tex>O( z)</tex>. Чтобы завершить анализ, рассмотрим время, расходуемое на запросы о продолжении. Это время пропорционально числу выполняемых запросов. Пусть <tex>T( n)</tex> — число запросов при длине строки <tex>n</tex>. Тогда <tex>T( n) = 2T( n/2) + O( n)</tex> и <tex>T( n) = O( n \log n)</tex>, как и утверждалось.}} ==См. также==* [[Алгоритм Бойера-Мура]]* [[Алгоритм Кнута-Морриса-Пратта]]* [[Алгоритм Крочемора]]* [[Алгоритм Ландау-Вишкина (k несовпадений)]]
== Источники информации ==
* Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — 2-е изд.
* ''Билл Смит'' '''Методы и алгоритмы вычислений на строках'''. Пер. с англ.{{---}} М.:Издательский дом "Вильямс", 2006. ISBN 5-8459-1081-1
* [http://cs.haifa.ac.il/LANDAU/gadi/LSS.pdf Landau, G.M., J.P. Schmidt and D. Sokol. An algorithm for approximate tandem repeats]
[[Категория: Поиск тандемных повторовОсновные определения. Простые комбинаторные свойства слов]]
[[Категория: Алгоритмы и структуры данных]]
