Алгоритм Крочемора — различия между версиями
(→Оптимизация) |
м (rollbackEdits.php mass rollback) |
||
(не показано 48 промежуточных версий 6 участников) | |||
Строка 1: | Строка 1: | ||
− | + | '''Алгоритм Крочемора''' (англ. ''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> 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>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>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 \ | + | Далее для <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 || | + | || 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>l</tex> выполняется непосредственная декомпозиция каждой последовательности <tex>c^{ | + | на каждом уровне <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 и пометим их как малые | ||
+ | '''while''' <tex>\exists</tex> малая последовательность на уровне <tex>l</tex>''':''' | ||
+ | '''out''' <tex>\gets</tex> кратные строки с периодом l | ||
+ | Вычислим декомпозицию последовательностей уровня <tex>l</tex>, используя только малые последовательности | ||
+ | l++ | ||
+ | Найдем малые последовательности на уровне <tex>l</tex> | ||
− | = | + | == См. также == |
− | + | * [[Алгоритм Ландау-Шмидта]] | |
− | = | + | == Источники информации == |
+ | * ''Билл Смит'' '''Методы и алгоритмы вычислений на строках'''. Пер. с англ.{{---}} М.:Издательский дом "Вильямс", 2006. ISBN 5-8459-1081-1 | ||
− | + | [[Категория: Алгоритмы и структуры данных]] | |
+ | [[Категория: Основные определения. Простые комбинаторные свойства слов]] |
Текущая версия на 19:23, 4 сентября 2022
Алгоритм Крочемора (англ. Crochemore algorithm) — алгоритм на строках, позволяющий найти все тандемные повторы в строке
заАлгоритм
Разобьем описание алгоритма на две части: сначала покажем упрощенный алгоритм, работающий за
, а затем попытаемся его оптимизировать доУпрощенный алгоритм
Прежде чем перейти к объяснению алгоритма Крочемора, вначале опишем простой алгоритм, который на каждом этапе достигает такого же результата, что и алгоритм Крочемора, а именно: в строке
он вычисляет все повторяющиеся подстроки длиной , где .Рассмотрим следующую строку Фиббоначи:
a | b | a | a | b | a | b | a | a | b | a | a | b | $ |
Будем вычислять все повторяющиеся подстроки длины
для всех , таких что . Зная эти данные, мы автоматически находим все тандемные повторы.Предположим, что в строке
вычислены последовательности позиций, в которых встречаются одинаковые символы:a | b | $ |
Если нам заранее известен алфавит, и он индексирован, то мы можем выполнить данное вычисление за
.Далее для
мы хотим найти все повторяющиеся подстроки длины . Поскольку повторяющиеся подстроки длины будут иметь общий префикс длиной , то вычисления уровня должны привести к последовательностям, которые будут подпоследовательностями последовательностей, вычисленных на уровне . Другими словами, разбиение на уровне — декомпозиция разбиения на уровне :Последовательная декомпозиция строки | |||||
---|---|---|---|---|---|
ab | aa | ba | b$ | ||
aba | ab$ | aab | baa | bab | |
abaa | abab | aaba | aab$ | baab | |
abaab | aabab | aabaa | baaba | baab$ | |
abaaba | abaab$ | baabab | baabaa | ||
abaabab | abaabaa |
Если реализовывать процесс декомпозиции "наивно", то получаем сложность
Заметим также, что приведенная выше декомпозиция дает сразу же понять, где существуют тандемные повторы.
Оптимизация
Декомпозицию каждой последовательности можно получить косвенным путем, а не путем прямых вычислений. Идея такого подхода состоит в следующем: на каждом уровне
выполняется непосредственная декомпозиция каждой последовательности . Более точно, если , то необходимо проверить совпадение букв , и, если какие-либо пары букв и равны, то и помещаются в одну и ту же последовательность на уровне .Заметим, что декомпозицию можно выполнить, основываясь не на разбиваемой последовательности, а на последовательностях, относительно которых будут разбиваться другие последовательности.
Для каждой позиции
известно, что подстрока (длиной ) относится к некоторой последовательности на уровне . Поскольку последовательность соответствует уникальной подстроке строки , то каждая такая последовательность должна формироваться из тех же позиций последовательности , которые определяют класс эквивалентности .Таким образом, декомпозицию на уровне
можно выполнить косвенным путем, рассматривая каждую последовательность уровня с позиции, находящейся на левее от начальной позиции этой последовательности.Лемма: |
В каждом наборе последовательностей, порожденных одной последовательностью уровня , всегда можно исключить использование одной из них для декомпозиции последовательностей на уровне |
При использовании хеш-таблицы, где ключом является подстрока, а значением — список позиций, где эта строка входит в , декомпозицию на уровне найдем за время, в среднем пропорциональное количеству позиций на уровне .
Определение: |
В декомпозиции последовательности | на последовательности назовем одну последовательность с наибольшим количеством элементов большой, а остальные последовательности — малыми. Для все последовательности будем считать малыми.
Лемма: |
Предположим, что декомпозиция последовательностей, соответствующих произвольной строке , выполняется для уровней , где — наименьший уровень, на котором каждая последовательность содержит единственную позицию. Тогда каждая позиция строки входит в малые последовательности раз |
Доказательство: |
Заметим, что если последовательность | разбивается на подпоследовательности , то каждая малая последовательность удовлетворяет условию . Другими словами, при каждая малая последовательность не превышает половины размера своей исходной последовательности. Поскольку для начальная малая последовательность может содержать не более позиций, то из этого следует, что ни одна из позиций не может входить в больше, чем малых последовательностей.
Поскольку строка
содержит позиций, то из предыдущей леммы следует, что всего в малых последовательностях на всех уровнях содержится позиций. Таким образом, если время обработки последовательностей на каждом уровне пропорционально количеству элементов в малых последовательностях этого уровня, то полный процесс декомпозиции будет выполнен за , что мы и хотели получить.Псевдокод
function crochemore(s: string): string1 Вычислим все последовательности на уровне 1 и пометим их как малые while малая последовательность на уровне : out кратные строки с периодом l Вычислим декомпозицию последовательностей уровня , используя только малые последовательности l++ Найдем малые последовательности на уровне
См. также
Источники информации
- Билл Смит Методы и алгоритмы вычислений на строках. Пер. с англ.— М.:Издательский дом "Вильямс", 2006. ISBN 5-8459-1081-1