Алгоритм Крочемора — различия между версиями

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

Текущая версия на 19:23, 4 сентября 2022

Алгоритм Крочемора (англ. 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