Изменения

'''Алгоритм КаркайненаКарккайнена-Сандерса ''' (KarkkainenKärkkäinen, Sanders) — алгоритм построения [[суффиксный массив | суффиксного массива]] за линейное время.

Получили асимптотическое уравнение == Используемые обозначения ==* В данном конспекте используется 0-индексация.* <tex>S[i..j] </tex> — подстрока строки <tex> S </tex> с <tex>i</tex>-го по <tex>j</tex>-й символы включительно.* Пусть длина строки <tex> S </tex> равна <tex> T(n) = T(</tex>. Обозначим <tex> S^*[i..j] </tex>, где <tex> j \frac{geqslant n}{2}) + O(</tex> как строку <tex> S[i..n) -1] </tex>, решением которого является дополненную защитными символами <tex> \$ </tex> до длины <tex> T(n) = O(n) </tex>.

# Строим суффиксный массив для нечетных суффиксов, рекурсивно сведя задачу к построению суффиксного массива для строки половинной длины.# Строим суффиксный массив для четных суффиксов за линейное время, используя результат первого шага.# Сливаем суффиксные массивы за линейное время. Получили асимптотическое уравнение <tex> T(n) = T\left( \dfrac{n}{2}\right) + O(n) </tex>, решением которого является <tex> T(n) = O(n) </tex>. Для упрощения алгоритма вначале дополним нашу строку до четной длины (например, добавлением <tex>\$ </tex> в конец). На шаге слияния мы сможем избавиться от него.=== Шаг 1 ===На первом шаге мы строим суффиксный массив <tex> A_{S_o} </tex> для нечетных суффиксов строки <tex> S </tex>.

=====База рекурсии=====Если длина текущей строки <tex> S </tex> равна двум, надо выполнить обычное сравнение суффиксов. =====Суффиксный массив для нечетных суффиксов===== # Отобразим исходную строку <tex> S ^* </tex> длины <tex> n </tex> в строку <tex> S' </tex> длины <tex> \fracdfrac{n}{2} </tex> следующим образом:#* Сделаем список, состоящий из пар символов вида <tex> S^*[i..i + 1] </tex>, где <tex> i \mod bmod 2 == 1 </tex>, причем обозначим <tex> S[n-1..n] </tex> как <tex> S[n-1]\$</tex>.

#* Перекодируем строку <tex> S ^*[1..n] </tex> в алфавит <tex> \Sigma' </tex>, получив строку <tex> S' </tex> половинной длины.

=== Шаг 2 ==Суффиксный массив для четных суффиксов=====

Заметим, что сортировка множества четных суффиксов <tex> \{ S^*[i..n] | \mid i \mod bmod 2 == 0 \} </tex> аналогична сортировке множества пар <tex> \{ (S^*[i], S^*[i+1..n]) | \mid i \mod bmod 2 == 0 \} </tex>. Однако <tex> S^*[i+1..n] </tex> — нечетный суффикс, и его относительную позицию мы уже узнали на шаге 1.

Таким образом, чтобы отсортировать эти пары за линейное время, сначала сразу выпишем их в порядке возрастания второго элемента пары (то есть в порядке вхождения в массив <tex> A_{S_o} </tex>), а потом отсортируем устойчивой сортировкой подсчетом по первым элементам. Псевдокод После этого шагалегко можно восстановить массив <tex> A_{S_e} </tex>:

'''for ''' i = 0..'''to''' n/2 - 1:

 Заметим, что массив <tex> M </tex> явно не отсортирован по вторым элементам и хранит не суффиксы, а их позиции в строке <tex> S </tex>, но главное — что он отсортирован по возрастанию соответствующих этим позициям нечетным суффиксам. После устойчивой сортировки массива <tex> M </tex> подсчетом по первому элементу легко восстановить массив <tex> A_{S_e} </tex>: stable_sortquick_stable_sort(M)

'''for ''' i = 0..'''to''' n/2 - 1:

=== Шаг 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'''. Во-первых, добавив защитный символ '''$''', получив строку '''ababbbaa$''' (для этого алгоритма он не требуется, но может понадобиться в применениях суффиксного массива). Во-вторых, дополним ее до четной длины, получив '''ababbbaa$$'''. =====Суффиксный массив для нечетных суффиксов=====# В новом алфавите <tex> \Sigma' </tex> будет четыре элемента — '''ba''', '''bb''', '''a$''', '''$$'''. После сортировки они получат номера 2, 3, 1 и 0 соответственно.# Переводим строку <tex>S^*[1..n]</tex> = '''babbbaa$$$''' в новый алфавит. Сжатой строкой <tex> S' </tex> будет '''23210'''.# После рекурсивного вызова получим, что <tex> A_{S'} </tex> = [4, 3, 2, 0, 1], и <tex> A_{S_o} </tex> = [9, 7, 5, 1, 3]. =====Суффиксный массив для четных суффиксов=====# Обойдя массив <tex> A_{S_o} </tex>, получим <tex> M </tex> = [(<tex>\$</tex>, 9), (<tex>a</tex>, 7), (<tex>b</tex>, 5), (<tex>a</tex>, 1), (<tex>a</tex>, 3)].# После сортировки подсчетом по первому элементу, получим <tex> M </tex>= [(<tex>\$</tex>, 9), (<tex>a</tex>, 7), (<tex>a</tex>, 1), (<tex>a</tex>, 3), (<tex>b</tex>, 5)].# Восстановив массив <tex> A_{S_e} </tex>, получаем [8, 6, 0, 2, 4], что действительно является суффиксным массивом для четных суффиксов.

Во-первых=====Слияние суффиксных массивов=====Если бы мы умели сливать <tex> A_{S_o} </tex> и <tex> A_{S_e} </tex> за линейное время, добавим защитный символ $, получив строку '''bbaaabab$'''. Во-вторых, дополним ее до четной длины, получив '''bbaaabab$$'''.получили бы:

{| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| №!style="background-color:#EEE"| Подстрока|-|style= Шаг 1 "background-color:#FFF;padding:2px 30px"| <tex> 9 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> \$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 8 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> \$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 7 </tex>|style="background-color:# В новом алфавите FFF;padding:2px 30px"| <tex> a\$\Sigma' $ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 6 </tex> будет четыре элемента — '''ba''', '''|style="background-color:#FFF;padding:2px 30px"| <tex> aa''', '''b\$''', '''\$</tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 0 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> ababbbaa\$\$'''. После сортировки они получат номера 3, 1, </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 2 и 0 соответственно.</tex>|style="background-color:#FFF;padding:2px 30px"| <tex> abbbaa\$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 5 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> baa\$\$ </tex>|-|style="background-color:# Сжатой строкой FFF;padding:2px 30px"| <tex> S' 1 </tex> будет '''31320'''.|style="background-color:# После рекурсивного вызова получим, что FFF;padding:2px 30px"| <tex> A_{S'} babbbaa\$\$ </tex> |-|style= ["background-color:#FFF;padding:2px 30px"| <tex> 4, 1, 3, 0, 2], и </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> A_{S_e} bbaa\$\$ </tex> |-|style= [9, "background-color:#FFF;padding:2px 30px"| <tex> 3, 7, 1, 5].</tex>|style="background-color:#FFF;padding:2px 30px"| <tex> bbbaa\$\$ </tex>|}

==== Шаг 2 ====# Обойдя массив <tex> A_{S_o} </tex>Как и было сказано вначале, получим <tex> M </tex> = [(избавиться от лишних '''$'''легко, 9), ('''a''', 3), ('''a''', 7), ('''b''', 1), ('''a'''так как суффиксы, 5)].# После сортировки подсчетом по первому элементуим соответствующие, получим <tex> M </tex>= [будут первыми в суффиксном массиве ('''$''', в данном случае достаточно выбросить "9" из суффиксного массива), ('''a''', 3), ('''a''', 7), ('''a''', 5), ('''b''', 1)].# Восстановив массив <tex> A_{S_e} </tex>, получаем [8, 2, 6, 4, 0], что действительно является суффиксным массивом для четных суффиксов.

== Алгоритм КаркайненаКарккайнена-Сандерса ==

# Построим суффиксный массив для суффиксов, соответствующих позициям, не кратным трем позициям. Рекурсивно сведем это к построению суффиксного массива для строки длиной в две трети исходной.# Построим суффиксный массив для суффиксов, соответствующих кратным трем позициям, используя результат первого шага , за линейное время.# Сливаем Сольем эти суффиксные массивы в один за линейное время.

Получили асимптотическое уравнение <tex> T(n) = T\left(\frac23 dfrac23 n\right) + O(n) </tex>, решением которого также является <tex> T(n) = O(n) </tex> (это видно из того, что сумма геометрической прогрессии с основанием <tex> \frac23 dfrac23 </tex> равна <tex> 3n 3 </tex>).

Аналогично первой версии алгоритма, дополним строку <tex> S </tex> до длины, кратной трем, защитными символами <tex> \$ </tex> и получим <tex>S^*</tex>.

=== Шаг * '''База рекурсии'''Для этого алгоритма минимальной базой рекурсии будет строка длиной 4, так как она дополняется до длины 6, после чего вновь следует рекурсивный вызов строки длиной 4, и, если бы база была меньше 4, алгоритм вошел бы в бесконечную рекурсию. На этом этапе также можно применить обычную сортировку суффиксов, так как это потребует <tex> O(1 ===) </tex> действий. * '''Суффиксный массив для позиций не кратных 3'''На этом шаге строится суффиксный массив <tex> A_{S_{12}} </tex> для множества суффиксов <tex> \{ S^*[i..n-1] | \mid i \mod bmod 3 \ne 0 \} </tex>.

#* Сделаем список, состоящий из троек <tex> S^*[i..i+2]</tex> , где <tex> i \mod bmod 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> S ^*[1..n]S^*[2..n+1] </tex> в строку <tex> S' </tex> длиной <tex> \frac23 dfrac23 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 bmod 3 == 1 </tex>, в новом алфавите будет соответствовать строка <tex> S'\left[\fracdfrac{i-1}{3}..\fracdfrac{n}{3} - 1\right] </tex>, а если <tex> i \mod bmod 3 == 2 </tex>, то строка <tex> S'\left[\fracdfrac{n}{3} + \fracdfrac{i-2}{3}..\fracdfrac{2n}{3} - 1\right] </tex>.

# Пройдем по массиву <tex> A_{S'} </tex>. Если <tex> A_{S'}[i] < \fracdfrac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j = 3A_{S'}[i] + 1 </tex> в строке <tex> S </tex>, если же <tex> A_{S'}[i] \ge geqslant \fracdfrac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j = 3\left(A_{S'}[i] - \fracdfrac{n}{3}\right) + 2 </tex> в строке <tex> S ^* </tex>. Псевдокод получения <tex> A_{S_{12}} </tex>:

'''for ''' i = 0..'''to''' <tex>A_{S'}</tex>.length - 1: '''if ''' <tex>A_{S'}</tex>[i] < n / 3:

'''else''': <tex>A_{S_{12}}</tex>.add(3 * (<tex>A_{S'}</tex>[i] - n / 3) + 2)

=== Шаг 2 ===* '''Суффиксный массив для позиций кратных 3'''Этот шаг также аналогичен первой версии алгоритма. Сортировка множества <tex> \{ S^*[i..n-1] | \mid i \mod bmod 3 == 0 \} </tex> аналогична сортировке пар <tex> \{ (S^*[i], S^*[i+1..n-1]) | \mid i \mod bmod 3 == 0 \} </tex>, где <tex> S^*[i+1..n-1] </tex> — суффиксы в позициях, равных 1 по модулю 3, относительный порядок которых уже известен. Выпишем эти пары в порядке вхождения их в <tex> A_{S_{12}} </tex> и отсортируем по первому элементу устойчивой сортировкой подсчетом, получив суффиксный массив <tex> A_{S_0} </tex>. Псевдокод этого шага:

'''for ''' i = 0..'''to''' 2n/3 - 1: '''if ''' <tex> A_{S_{12}}</tex>[i] % 3 == 1: M.add(Pair(S*[<tex>A_{S_{12}}</tex>[i] - 1], <tex>A_{S_{12}}</tex>[i]))

'''for ''' i = 0..'''to''' n/3 - 1:

Применим стандартный алгоритм слияния двух отсортированных массивов. Заметим, что явно массивы не отсортированы, но сотвествующие соответствующие элементам массива суффиксы — отсортированы.

Пусть на какой-то итерации слияния мы сравниваем суффиксы, соответствующие позициям <tex> i </tex>, равной 1 по модулю 3, и <tex> j </tex> (она всегда будет равна 0 по модулю 3). Это аналогично сравнению пар <tex> (S^*[i], S^*[i+1..n-1]) </tex> и <tex> (S^*[j], S^*[j+1..n-1]) </tex>. Сравнить первые элементы пар мы можем за <tex> O(1) </tex>, а относительный порядок вторых элементов пар нам уже известен, так как они соотвествуют соответствуют позициям, равным 2 и 1 по модулю 3 соответственно.

Аналогично, пусть на какой-то итерации слияния мы сравниваем суффиксы, соответствующие позициям <tex> i </tex>, равной 2 по модулю 3, и <tex> j </tex> (она всегда будет равна 0 по модулю 3). Тогда это аналогично сравнению троек <tex> (S^*[i], S^*[i+1], S^*[i+2..n-1]) </tex> и <tex> (S^*[j], S^*[j+1], S^*[j+2..n-1]) </tex>, что также можно делать за <tex> O(1) </tex>.

<font color=green>// Вначале предподсчитаем за O(n) обратную перестановку для суффиксного массива <tex> A_{S_{12}}</tex>, то есть массив rank такой, что <tex> A_{S_{12}}</tex>[rank[i]] = i. // Тогда мы сможем за O(1) сравнивать суффиксы по их позиции.</font>

'''while ''' i < 2 * n / 3 '''and ''' j < n / 3:

'''if ''' pos12 % 3 == 1: ''' if ''' Pair(S*[pos12], rank[pos12 + 1]) < Pair(S*[pos0], rank[pos0 + 1]):

'''else''':

'''else''': '''if ''' Triple(S*[pos12], S*[pos12 + 1], rank[pos12 + 2]) < Triple(S*[pos0], S*[pos0 + 1], rank[pos0 + 2]):

'''else''':

'''while ''' i < 2 * n / 3:

'''while ''' j < n / 3: <tex>A_{S}</tex>.add(<tex> A_{S_{0}} </tex>[j]) i j++

==== Шаг 1 ====* '''Суффиксный массив для позиций не кратных 3'''# Тройками, соответствующими равными 1 по модулю 3 позициям, будут: '''bba''', '''cab''', '''$$$''', соответствующими равным 2 по модулю 3 — '''bac''', '''ab$''', '''$$$'''. Новый алфавит <tex> \Sigma' </tex> будет содержать элементы '''bba''', '''cab''', '''$$$''', '''bac''', '''ab$''', которые после сортировки получат номера 3, 4, 0, 2, 1 соотвествтенносоответственно.# Строкой '''bbacab$$$bacab$$$$''' в новом алфавите <tex> S\Sigma' </tex> будет <tex> S'''</tex> = 340210'''.

==== Шаг 2 ====* '''Суффиксный массив для позиций кратных 3'''# Обойдя массив <tex> A_{S_{12}} </tex> и выбрав в нем элементы, равные 1 по модулю 3, получим массив пар <tex>M</tex> = [('''<tex>b'''</tex>, 7), ('''<tex>a'''</tex>, 1), ('''<tex>a'''</tex>, 4)]

# Образуем тройки <tex>(S^*[5], S^*[6], S^*[7..8]) </tex> и <tex>(S^*[0], S^*[1], S^*[2..8])</tex>.

К концу слияния получим <tex> A_{S} </tex> = [8, 7, 5, 0, 3, 6, 2, 1, 4]. Так как мы добавляли один символ '''<tex>\$''' </tex> в начале алгоритма для дополнения строки до длины, кратной трем, выбросим последний суффикс из <tex> A_{S} </tex>, получим в итоге, что <tex> A_{S} </tex> = [7, 5, 0, 3, 6, 2, 1, 4].

{| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| №!style="background-color:#EEE"| Подстрока|-|style="background-color:#FFF;padding:2px 30px"| <tex> 8 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> \$ </tex>|-|style= Получение LCP "background-color:#FFF;padding:2px 30px"| <tex> 7 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> \$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 5 </tex>LCP можно получить за линейное время |style="background-color:#FFF;padding:2px 30px"| <tex> ab\$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 0 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> abbacab\$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 3 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> acab\$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 6 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> b\$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 2 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> bacab\$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 1 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> bbacab\$\$ </tex>|-|style="background-color:#FFF;padding:2px 30px"| <tex> 4 </tex>|style="background-color:#FFF;padding:2px 30px"| <tex> cab\$\$ </tex>|}Заметим, что № 9 будет выброшен, так как в начале алгоритма был добавлен один <tex> \$ </tex> к строке {|| [[Алгоритм_Касаи_и_дрФайл:Kark_sanders_stage1. png|325px|thumb| алгоритмом КасаиФаза 1]]| [[Файл:Kark_sanders_stage2.png|325px|thumb| Фаза 2]]| [[Файл:Kark_sanders_stage3.png|325px|thumb| Фаза 3]]|}

Массив 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'').

'''Разностное покрытие''' (англ. ''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 pmod 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 />

== Источники информации==