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

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

Базовая идея

Алгоритм базируется на алгоритме Фараха построения суффиксного дерева за линейное время:

1. Строим суффиксное дерево для четных суффиксов рекурсивно сведя задачу к построению суффиксного дерева для строки половинной длины.
2. Строим суффиксное дерево для нечетных суффиксов за линейное время, используя результат для четных позиций.
3. Сливаем суффиксные деревья за линейное время.

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

Алгоритм «разделяй и властвуй»

Определение:

Четным суффиксом назовем суффикс, начинающийся в четной позиции. Нечетным суффиксом — суффикс, начинающийся в нечетной позиции.

Для упрощения алгоритма вначале дополним нашу строку до четной длины (например, добавлением $ в конец). На шаге слияния мы сможем избавиться от него.

Шаг 1

На первом шаге мы строим суффиксный массив [math] A_{S_o} [/math] для нечетных суффиксов строки [math] S [/math].

1. Отобразим исходную строку [math] S [/math] длины [math] n [/math] в строку [math] S' [/math] длины [math] \frac{n}{2} [/math] следующим образом:
   • Сделаем список, состоящий из пар символов вида [math] S[i..i + 1] [/math], где [math] i \mod 2 == 1 [/math], причем обозначим [math] S[n-1..n] [/math] как [math] S[n-1]\$[/math].
   • Отсортируем его цифровой сортировкой за линейное время и получим новый алфавит [math] \Sigma' [/math].
   • Перекодируем строку [math] S [/math] в алфавит [math] \Sigma' [/math], получив строку [math] S' [/math] половинной длины.
2. Рекурсивно построим суффиксный массив [math] A_{S'} [/math].
3. Построим суффиксный массив [math] A_{S_o} [/math]. Очевидно, [math] A_{S_o}[i] = 2 A_{S'}[i] + 1 [/math], так отношение упорядоченности любых двух строк в старом алфавите [math] \Sigma [/math] эквивалентно отношению упорядоченности в новом алфавите [math] \Sigma' [/math] по его построению.

Шаг 2

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

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

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

M = []
for i = 0..n/2 - 1:
    M.add(Pair(S[[math] A_{S_o}[/math][i] - 1], [math] A_{S_o}[/math][i]))

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

stable_sort(M)
[math] A_{S_e} [/math] = []
for i = 0..n/2 - 1:
   [math] A_{S_e} [/math].add(M[i].second - 1)

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

Шаг 3

Для суффиксного дерева третий шаг алгоритма опирается на специфические особенности суффиксных деревьев, которые не присущи суффиксным массивам. В случае суффиксного массива слияние становится очень сложным, но все же оно было реализовано в алгоритме Ким-Сим-Парк-Парка. Однако простой модификацией алгоритма можно значительно упростить его.

Пример

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

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

Шаг 1

1. В новом алфавите [math] \Sigma' [/math] будет четыре элемента — ba, aa, b$, $$. После сортировки они получат номера 3, 1, 2 и 0 соответственно.
2. Сжатой строкой [math] S' [/math] будет 31320.
3. После рекурсивного вызова получим, что [math] A_{S'} [/math] = [4, 1, 3, 0, 2], и [math] A_{S_e} [/math] = [9, 3, 7, 1, 5].

Шаг 2

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

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

Изменим изначальный алгоритм следующим образом:

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

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

Аналогично первой версии алгоритма, дополним строку [math] S [/math] до длины, кратной трем, защитными символами [math] \$ [/math].

Шаг 1

На этом шаге строится суффиксный массив [math] A_{S_{12}} [/math] для множества суффиксов [math] \{ S[i..n-1] | i \mod 3 \ne 0 \} [/math].

1. Получим строку [math] S' [/math] аналогично предыдущему алгоритму:
   • Сделаем список, состоящий из троек [math] S[i..i+2][/math] , где [math] i \mod 3 \ne 0 [/math], причем примем [math] S[n-2..n] = S[n-2..n-1]\$ [/math], а [math] S[n-1..n+1] = S[n-1]\$\$ [/math].
   • Отсортируем его за линейное время цифровой сортировкой и получим новый алфавит [math] \Sigma' [/math].
   • Перекодируем строку [math] S [/math] в строку [math] S' [/math] длиной [math] \frac23 n [/math] в алфавите [math] \Sigma' [/math] следущим образом: [math] S' = [ \Sigma'(s[i..i+2]) | i \mod 3 == 1 ] + [ \Sigma'(s[i..i+2]) | i \mod 3 == 2 ] [/math]. Суффиксу [math] S[i..n-1] [/math] в старом алфавите, где [math] i \mod 3 == 1 [/math], в новом алфавите будет соответствовать строка [math] S'[\frac{i-1}{3}..\frac{n}{3} - 1] [/math], а если [math] i \mod 3 == 2 [/math], то строка [math] S'[\frac{n}{3} + \frac{i-2}{3}..\frac{2n}{3} - 1] [/math].
2. Вызовем алгоритм рекурсивно для строки [math] S' [/math], получив суффиксный массив [math] A_{S'} [/math].
3. Пройдем по массиву [math] A_{S'} [/math]. Если [math] A_{S'}[i] \lt \frac{n}{3} [/math], то этот суффикс соответствует позиции [math] j = 3A_{S'}[i] + 1 [/math] в строке [math] S [/math], если же [math] A_{S'}[i] \ge \frac{n}{3} [/math], то этот суффикс соответствует позиции [math] j = 3(A_{S'}[i] - \frac{n}{3}) + 2 [/math] в строке [math] S [/math]. Псевдокод получения [math] A_{S_{12}} [/math]:

[math] A_{S_{12}} [/math] = []
for i = 0..[math]A_{S'}[/math].length - 1:
   if [math]A_{S'}[/math][i] < n / 3:
       [math]A_{S_{12}}[/math].add(3 * [math]A_{S'}[/math][i] + 1)
   else:
       [math]A_{S_{12}}[/math].add(3 * ([math]A_{S'}[/math][i] - n / 3) + 2)

Шаг 2

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

[math]A_{S_0}[/math] = []
M = []
for i = 0..2n/3 - 1:
    if [math] A_{S_{12}}[/math][i] % 3 == 1:
        M.add(Pair(S[[math]A_{S_{12}}[/math][i] - 1], [math]A_{S_{12}}[/math][i]))
stable_sort(M)
for i = 0..n/3 - 1:
    [math]A_{S_0}[/math].add(M[i].second - 1)

Аналогично, второй шаг требует [math] O(n) [/math] времени.

Шаг 3

На этом шаге мы должны слить суффиксные массивы [math] A_{S_0} [/math] и [math] A_{S_{12}} [/math], чтобы получить суффиксный массив [math] A_{S} [/math] для всей строки [math] S [/math].

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

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

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

Псевдокод этой фазы:

[math]A_{S}[/math] = []
// Вначале предподсчитаем за O(n) обратную перестановку для суффиксного массива [math] A_{S_{12}}[/math], то есть массив rank такой, что [math] A_{S_{12}}[/math][rank[i]] = i.
// Тогда мы сможем за O(1) сравнивать суффиксы по их позиции.
rank = inverse([math]A_{S_{12}}[/math]) 
while i < 2 * n / 3 and j < n / 3:
    pos12 = [math] A_{S_{12}} [/math][i]
    pos0  = [math] A_{0} [/math][j]
    if pos12 % 3 == 1:
        if Pair(S[pos12], rank[pos12 + 1]) < Pair(S[pos0], rank[pos0 + 1]):
            [math]A_{S}[/math].add(pos12)
            i++
        else:
            [math]A_{S}[/math].add(pos0)
            j++  
    else:
        if Triple(S[pos12], S[pos12 + 1], rank[pos12 + 2]) < Triple(S[pos0], S[pos0 + 1], rank[pos0 + 2]):
            [math]A_{S}[/math].add(pos12)
            i++
        else:
            [math]A_{S}[/math].add(pos0)
            j++ 
while i < 2 * n / 3:
    [math]A_{S}[/math].add([math] A_{S_{12}} [/math][i])
    i++
while j < n / 3:
   [math]A_{S}[/math].add([math] A_{S_{0}} [/math][j])
   i++

Таким образом, получили простой метод слияния за [math] O(n) [/math].

Пример

Построим суффиксный массив для строки abbacab. После добавления защитного символа и дополнения до кратной трем длины, получим abbacab$$.

Шаг 1

1. Тройками, соответствующими равными 1 по модулю 3 позициям, будут: bba, cab, $$$, соответствующими равным 2 по модулю 3 — bac, ab$, $$$. Новый алфавит [math] \Sigma' [/math] будет содержать элементы bba, cab, $$$, bac, ab$, которые после сортировки получат номера 3, 4, 0, 2, 1 соотвествтенно.
2. Строкой [math] S' [/math] будет 340210.
3. После рекурсивного вызова получим [math] A_{S'} [/math] = [5, 2, 4, 3, 0, 1]. Пересчитав [math] A_{S_{12}} [/math], получим [(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].

Шаг 2

1. Обойдя массив [math] A_{S_{12}} [/math] и выбрав в нем элементы, равные 1 по модулю 3, получим массив пар [math]M[/math] = [(b, 7), (a, 1), (a, 4)]
2. После устойчивой сортировки подсчетом по первому элементу, получим [math] M [/math] = [(a, 1), (a, 4), (b, 7)]
3. Восстановив [math] A_{S_0} [/math], получаем [0, 3, 6].

Шаг 3

Рассмотрим, к примеру, третью итерацию слияния, к этой итерации массив [math] A_{S} [/math] = [8, 7], [math] i [/math] = 2, [math] j [/math] = 0, на ней мы сливаем суффиксы, соответствующие позициям 5 и 0.

1. Образуем тройки (S[5], S[6], S[7..8]) и (S[0], S[1], S[2..8]).
2. После получения относительного порядка суффиксов, получим тройки (a, b, 1) и (a, b, 3). Первая тройка меньше второй, поэтому добавляем суффикс, соответствующий позиции 5 в массив [math] A_{S} [/math].
3. В конце итерации получаем [math] A_{S} [/math] = [8, 7, 5], [math] i [/math] = 3, [math] j [/math] = 0.

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

Получение LCP

LCP можно получить за линейное время алгоритмом Касаи.

Обобщение алгоритма

На самом деле, алгоритм можно обобщить, взяв на первом шаге, к примеру, суффиксы, позиции которых по модулю 7 дают 3, 5 и 6. Для этого потребуются некоторое усложнение алгоритма, например, сортировка оставшихся суффиксов в нескольких группах на шаге 2 и слиянием нескольких групп на шаге 3, но основная идея алгоритма остается той же. Множества, которые можно выбрать, на первом шаге определяются разностным покрытием (difference cover).

Определение:

Разностное покрытие (difference cover) [math] D [/math] по модулю [math]m [/math] — множество чисел от [math]0[/math] до [math]m - 1 [/math] таких, что [math] \forall i \in [0, m-1]: \exists j, k \in D: i \equiv k - j\ ( \mod m) [/math].

Заметим, что [math] \{1, 2\} [/math] является разностным покрытием по модулю [math] 3 [/math], [math] \{3, 5, 6\} [/math] является разностным покрытием по модулю [math] 7 [/math], а [math] \{1\} [/math] — не является разностным покрытием по модулю [math] 2 [/math], поэтому этот алгоритм не применим к нему. Подробнее узнать, как вычислять разностное покрытие для заданного модуля можно также здесь.

Источники

• Суффиксный массив
• Juha Kärkkäinen and Peter Sanders. Simple linear work suffix array construction