1679
правок
Изменения
Нет описания правки
Алгоритм Карккайнена-Сандерса (Karkkainen, Sanders) — алгоритм построения [[суффиксный массив | суффиксного массива]] за линейное время.
== Алгоритм «разделяй и властвуй» ==
{{Определение
|definition=
'''Нечетным суффиксом''' — суффикс, начинающийся в нечетной позиции.
}}
# Строим суффиксный массив для нечетных суффиксов, рекурсивно сведя задачу к построению суффиксного массива для строки половинной длины.
# Строим суффиксный массив для четных суффиксов за линейное время, используя результат первого шага.
# Сливаем суффиксные массивы за линейное время.
Получили асимптотическое уравнение <tex> T(n) = T(\frac{n}{2}) + O(n) </tex>, решением которого является <tex> T(n) = O(n) </tex>.
Для упрощения алгоритма вначале дополним нашу строку до четной длины (например, добавлением $ в конец). На шаге слияния мы сможем избавиться от него.
=== База рекурсии ===
Если длина текущей строки <tex> S </tex> меньше двух, надо выполнить обычное сравнение суффиксов.
=== Шаг 1 ===
На первом шаге мы строим суффиксный массив <tex> A_{S_o} </tex> для нечетных суффиксов строки <tex> S </tex>.
# Отобразим исходную строку <tex> S </tex> длины <tex> n </tex> в строку <tex> S' </tex> длины <tex> \frac{n}{2} </tex> следующим образом:
#* Сделаем список, состоящий из пар символов вида <tex> S[i..i + 1] </tex>, где <tex> i \mod 2 == 1 </tex>, причем обозначим <tex> S[n-1..n] </tex> как <tex> S[n-1]\$</tex>.
#* Отсортируем его цифровой сортировкой за линейное время и получим новый алфавит <tex> \Sigma' </tex>.
#* Перекодируем строку <tex> S [1..n] </tex> в алфавит <tex> \Sigma' </tex>, получив строку <tex> S' </tex> половинной длины.
# Рекурсивно построим суффиксный массив <tex> A_{S'} </tex>.
# Построим суффиксный массив <tex> A_{S_o} </tex>. Очевидно, <tex> A_{S_o}[i] = 2 A_{S'}[i] + 1 </tex>, так отношение упорядоченности любых двух строк в старом алфавите <tex> \Sigma </tex> эквивалентно отношению упорядоченности в новом алфавите <tex> \Sigma' </tex> по его построению.
На этом шаге мы за линейное время получим суффиксный массив <tex> A_{S_e} </tex> для четных суффиксов, используя уже построенный <tex> A_{S_o} </tex>.
Заметим, что сортировка множества четных суффиксов <tex> \{ S[i..n] | i \mod 2 == 0 \} </tex> аналогична сортировке множества пар <tex> \{ (S[i], S[i+1..n]) | i \mod 2 == 0 \} </tex>. Однако <tex> S[i+1..n] </tex> — нечетный суффикс, и его относительную позицию мы уже узнали на шаге 1.
Таким образом, чтобы отсортировать эти пары за линейное время, сначала сразу выпишем их в порядке возрастания второго элемента пары (то есть в порядке вхождения в массив <tex> A_{S_o} </tex>), а потом отсортируем устойчивой сортировкой подсчетом по первым элементам. Псевдокод этого шага:
=== Шаг 3 ===
Для суффиксного дерева третий шаг алгоритма опирается на специфические особенности суффиксных деревьев, которые не присущи суффиксным массивам<ref>M. Farach. Optimal suffix tree construction with large alphabets. http://www.cs.rutgers.edu/~farach/pubs/FarFerrMuthu00.pdf </ref> .
В случае суффиксного массива слияние становится очень сложным, но все же оно было реализовано в алгоритме Ким-Сим-Парк-Парка<ref> D. K. Kim, J. S. Sim, H. Park, and K. Park. Linear-time construction of suffix arrays. http://www.springerlink.com/content/568156021q45r320/</ref>. Однако простой модификацией алгоритма можно значительно упростить его.
=== Пример ===
Покажем первые два шага агоритма для строки '''bbaaababababbbaa'''.
Во-первых, добавим добавив защитный символ '''$''', получив строку '''bbaaababababbbaa$'''(для этого алгоритма он не требуется, но может понадобиться в применениях суффиксного массива). Во-вторых, дополним ее до четной длины, получив '''bbaaababababbbaa$$'''.
==== Шаг 1 ====
# В новом алфавите <tex> \Sigma' </tex> будет четыре элемента — '''ba''', '''aabb''', '''ba$''', '''$$'''. После сортировки они получат номера 2, 3, 1, 2 и 0 соответственно.# Переводим строку S[1..n] = '''babbbaa$$$''' в новый алфавит. Сжатой строкой <tex> S' </tex> будет '''3132023210'''.# После рекурсивного вызова получим, что <tex> A_{S'} </tex> = [4, 13, 32, 0, 21], и <tex> A_{S_eS_o} </tex> = [9, 37, 75, 1, 53].
==== Шаг 2 ====
# Обойдя массив <tex> A_{S_o} </tex>, получим <tex> M </tex> = [('''$''', 9), ('''a''', 37), ('''ab''', 75), ('''ba''', 1), ('''a''', 53)].# После сортировки подсчетом по первому элементу, получим <tex> M </tex>= [('''$''', 9), ('''a''', 37), ('''a''', 71), ('''a''', 53), ('''b''', 15)].# Восстановив массив <tex> A_{S_e} </tex>, получаем [8, 6, 0, 2, 6, 4, 0], что действительно является суффиксным массивом для четных суффиксов. ==== Шаг 3 ====Если бы мы умели сливать <tex> A_{S_o} </tex> и <tex> A_{S_e} </tex> за линейное время, получили бы: 9 '''$''' 8 '''$$''' 7 '''a$$''' 6 '''aa$$''' 0 '''ababbbaa$$''' 2 '''abbbaa$$''' 5 '''baa$$''' 1 '''babbbaa$$''' 4 '''bbaa$$''' 3 '''bbbaa$$''' Как и было сказано вначале, избавиться от лишних '''$''' легко, так как суффиксы, им соответствующие, будут первыми в суффиксном массиве (в данном случае достаточно выбросить "9" из суффиксного массива).
== Алгоритм Карккайнена-Сандерса ==
Аналогично первой версии алгоритма, дополним строку <tex> S </tex> до длины, кратной трем, защитными символами <tex> \$ </tex>.
=== База рекурсии ===
Для этого алгоритма базой рекурсии будет строка длиной меньшей или равной 4, так как строка длины 4 дополнится до строки длины 6, после чего вновь будет рекурсивный вызов строки длиной 4. На этом этапе также можно применить обычную сортировку суффиксов, так как это потребует <tex> O(1) </tex> действий.
=== Шаг 1 ===
На этом шаге строится суффиксный массив <tex> A_{S_{12}} </tex> для множества суффиксов <tex> \{ S[i..n-1] | i \mod 3 \ne 0 \} </tex>.
# Получим строку <tex> S' </tex> аналогично предыдущему алгоритму:
#* Сделаем список, состоящий из троек <tex> S[i..i+2]</tex> , где <tex> i \mod 3 \ne 0 </tex>, причем примем <tex> S[n-2..n] = S[n-2..n-1]\$ </tex>, а <tex> S[n-1..n+1] = S[n-1]\$\$ </tex>.
#* Отсортируем его за линейное время цифровой сортировкой и получим новый алфавит <tex> \Sigma' </tex>.
#* Перекодируем строку <tex> S [1..n]S[2..n+1] </tex> в строку <tex> S' </tex> длиной <tex> \frac23 n </tex> в алфавите <tex> \Sigma' </tex> следущим образом: <tex> S' = [ \Sigma'(s[i..i+2]) | i \mod 3 == 1 ] + [ \Sigma'(s[i..i+2]) | i \mod 3 == 2 ] </tex>. Суффиксу Тогда суффиксу <tex> S[i..n-1] </tex> в старом алфавите, где <tex> i \mod 3 == 1 </tex>, в новом алфавите будет соответствовать строка <tex> S'[\frac{i-1}{3}..\frac{n}{3} - 1] </tex>, а если <tex> i \mod 3 == 2 </tex>, то строка <tex> S'[\frac{n}{3} + \frac{i-2}{3}..\frac{2n}{3} - 1] </tex>.
# Вызовем алгоритм рекурсивно для строки <tex> S' </tex>, получив суффиксный массив <tex> A_{S'} </tex>.
# Пройдем по массиву <tex> A_{S'} </tex>. Если <tex> A_{S'}[i] < \frac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j = 3A_{S'}[i] + 1 </tex> в строке <tex> S </tex>, если же <tex> A_{S'}[i] \ge \frac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j = 3(A_{S'}[i] - \frac{n}{3}) + 2 </tex> в строке <tex> S </tex>. Псевдокод получения <tex> A_{S_{12}} </tex>:
=== Шаг 2 ===
Этот шаг также аналогичен первой версии алгоритма. Сортировка множества <tex> \{ S[i..n-1] | i \mod 3 == 0 \} </tex> аналогична сортировке пар <tex> \{ (S[i], S[i+1..n-1]) | i \mod 3 == 0 \} </tex>, где <tex> S[i+1..n-1] </tex> — суффиксы в позициях, равных 1 по модулю 3, относительный порядок которых уже известен. Выпишем эти пары в порядке вхождения их в <tex> A_{S_{12}} </tex> и отсортируем по первому элементу устойчивой сортировкой подсчетом, получив суффиксный массив <tex> A_{S_0} </tex>. Псевдокод этого шага:
<tex>A_{S_0}</tex> = []
==== Шаг 1 ====
# Тройками, соответствующими равными 1 по модулю 3 позициям, будут: '''bba''', '''cab''', '''$$$''', соответствующими равным 2 по модулю 3 — '''bac''', '''ab$''', '''$$$'''. Новый алфавит <tex> \Sigma' </tex> будет содержать элементы '''bba''', '''cab''', '''$$$''', '''bac''', '''ab$''', которые после сортировки получат номера 3, 4, 0, 2, 1 соотвествтенно.
# Строкой '''bbacab$$$bacab$$$$''' в новом алфавите <tex> \Sigma' </tex> будет <tex> S' </tex> будет = '''340210'''.
# После рекурсивного вызова получим <tex> A_{S'} </tex> = [5, 2, 4, 3, 0, 1]. Пересчитав <tex> A_{S_{12}} </tex>, получим [(5 - 3)*3 + 2, 2 * 3 + 1, (4 - 3) * 3 + 2, (3 - 3) * 3 + 2, 0 * 3 + 1, 1 * 3 + 1] = [8, 7, 5, 2, 1, 4].
# В конце итерации получаем <tex> A_{S} </tex> = [8, 7, 5], <tex> i </tex> = 3, <tex> j </tex> = 0.
К концу слияния получим <tex> A_{S} </tex> = [8, 7, 5, 0, 3, 6, 2, 1, 4]. Так как мы добавляли один символ '''$''' в начале алгоритма для дополнения строки до длины, кратной трем, выбросим последний суффикс из <tex> A_{S} </tex>, получим в итоге, что <tex> A_{S} </tex> = [7, 5, 0, 3, 6, 2, 1, 4].
8 '''$''' (будет выброшен, так как в начале алгоритма добавляли один '''$''' к строке)
7 '''$$'''
5 '''ab$$'''
0 '''abbacab$$'''
3 '''acab$$'''
6 '''b$$'''
2 '''bacab$$'''
1 '''bbacab$$'''
4 '''cab$$'''
== Получение LCP ==
== Обобщение алгоритма ==
На самом деле, алгоритм можно обобщить<ref name="generalisation"> Juha Kärkkäinen, Peter Sanders and Stefan Burkhardt. Linear work suffix array construction. http://www.cs.helsinki.fi/juha.karkkainen/publications/jacm05-revised.pdf </ref>, взяв на первом шаге, к примеру, суффиксы, позиции которых по модулю 7 дают 3, 5 и 6. Для этого потребуются некоторое усложнение алгоритма, например, сортировка оставшихся суффиксов в нескольких группах на шаге 2 и слиянием слияние нескольких групп на шаге 3, но основная идея алгоритма остается той же. Множества, которые можно выбрать, на первом шаге определяются '''разностным покрытием''' (''difference cover'').
{{Определение
|definition=
'''Разностное покрытие''' (''difference cover'') <tex> D </tex> по модулю <tex>m </tex> — множество чисел от <tex>0</tex> до <tex>m - 1 </tex> таких, что <tex> \forall i \in [0, m-1]: \exists j, k \in D: i \equiv k - j\ ( \mod m) </tex>.
}}
Заметим, что <tex> \{1, 2\} </tex> является разностным покрытием по модулю <tex> 3 </tex>, <tex> \{3, 5, 6\} </tex> является разностным покрытием по модулю <tex> 7 </tex>, а <tex> \{1\} </tex> — не является разностным покрытием по модулю <tex> 2 </tex>, поэтому этот алгоритм не применим к нему. Подробнее узнать, как вычислять разностное покрытие для заданного модуля можно также здесь. <ref name="generalisation"/>.
== Ссылки ==
<references />
