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

2012-03-29T10:37:49Z

109.188.168.237: /* Шаг 2 */

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

{{Определение
|definition=
'''Четным суффиксом''' назовем суффикс, начинающийся в четной позиции. <br>
'''Нечетным суффиксом''' — суффикс, начинающийся в нечетной позиции.
}}

== Базовая идея ==
Алгоритм базируется на алгоритме Фараха<ref>M. Farach. Optimal suffix tree construction with large alphabets. http://www.cs.rutgers.edu/~farach/pubs/FarFerrMuthu00.pdf </ref> построения суффиксного дерева за линейное время:
# Строим суффиксное дерево для четных суффиксов рекурсивно сведя задачу к построению суффиксного дерева для строки половинной длины.
# Строим суффиксное дерево для нечетных суффиксов за линейное время, используя результат для четных позиций.
# Сливаем суффиксные деревья за линейное время.

Получили асимптотическое уравнение <tex> T(n) = T(\frac{n}{2}) + O(n) </tex>, решением которого является <tex> T(n) = O(n) </tex>.

== Алгоритм ==
Для упрощения алгоритма вначале дополним нашу строку до четной длины (например, добавлением $ в конец). На шаге сливания мы сможем избавиться от него.
=== Шаг 1 ===
На первом шаге мы строим суффиксный массив <tex> A_{S_e} </tex> для суффиксов строки <tex> S </tex>, начинающихся в четных позициях.

# Отобразим исходную строку <tex> S </tex> длины <tex> n </tex> в строку <tex> S' </tex> длины <tex> \frac{n}{2} </tex> следующим образом:
#* Сделаем список, состоящий из пар символов вида <tex> S[2i]S[2i + 1] </tex>, где <tex> i \in [0; n / 2) </tex>.
#* Отсортируем его цифровой сортировкой за линейное время и получим новый алфавит <tex> \Sigma' </tex>.
#* Перекодируем строку <tex> S </tex> в алфавит <tex> \Sigma' </tex>, получив строку <tex> S' </tex> половинной длины.
# Рекурсивно построим суффиксный массив <tex> A_{S'} </tex>.
# Построим суффиксный массив <tex> A_{S_e} </tex>. Очевидно, <tex> A_{S_e}[i] = 2 A_{S'}[i] </tex>, так отношение упорядоченности любых двух строк в старом алфавите <tex> \Sigma </tex> эквивалентно отношению упорядоченности в новом алфавите <tex> \Sigma' </tex> по его построению.

=== Шаг 2 ===
На этом шаге мы за линейное время получим суффиксный массив <tex> A_{S_o} </tex> для нечетных суффиксов, используя уже построенный <tex> A_{S_e} </tex>.

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

Таким образом, чтобы отсортировать эти пары за линейное время, сначала сразу выпишем их в порядке возрастания второго элемента пары (то есть в порядке вхождения в массив <tex> A_{S_e} </tex>), а потом отсортируем устойчивой сортировкой подсчетом по первым элементам. Так была потребована четность длины строки, последним суффиксом будет нечетный, ему будет соответствовать пара <tex> (S[n-1], n) </tex>. Псевдокод этого шага:
M = []
M.add(Pair(S[n-1], n))
for i = 0..n/2 - 1:
if <tex> A_{S_e}[i] </tex> == 0: //перед первым положительным суффиксом ничего не может стоять, поэтому пропускаем его
continue
else:
M.add(Pair(S[<tex> A_{S_e}[i] </tex>-1], <tex> A_{S_e}[i]</tex>))

Заметим, что массив <tex> M </tex> явно не отсортирован по вторым элементам и хранит не суффиксы, а их позиции в строке <tex> S </tex>, но главное — что он отсортирован по возрастанию соответствующих этим позициям четным суффиксам. После устойчивой сортировки массива <tex> M </tex> подсчетом по первому элементу легко восстановить массив <tex> A_{S_o} </tex>:
<tex> A_{S_o} </tex> = []
for i = 0..n/2 - 1:
<tex> A_{S_o} </tex>.add(M[i].second - 1)

Получили, что весь второй шаг требует <tex> O(n) </tex> времени.

=== Шаг 3 ===
Для суффиксного дерева третий шаг алгоритма опирается на специфические особенности суффиксных деревьев, которые не присущи суффиксным массивам.
В случае суффиксного массива слияние становится очень сложным <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>. Однако простой модификацией алгоритма можно значительно упростить его.

=== Пример ===
Покажем первые два шага агоритма для строки '''abaaab'''.

Во-первых, добавим защитный символ $, получив строку '''abaaab$'''. Во-вторых, дополним ее до четной длины, получив '''abaaab$$'''.

==== Шаг 1 ====
# В новом алфавите <tex> \Sigma' </tex> будет три элемента — '''ab''', '''aa''', '''$$'''. Они получат номера 2, 1 и 0 соответственно.
# Сжатой строкой <tex> S' </tex> будет '''2120'''.
# После рекурсивного вызова получим, что <tex> A_{S'} </tex> = [3, 1, 2, 0], и <tex> A_{S_e} </tex> = [6, 2, 4, 0].

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

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

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

{{TODO| t = впилить описание сливания }}

== Ссылки ==
<references />

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Суффиксный массив]]

Викиконспекты - Вклад участника [ru]

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