Алгоритм Карккайнена-Сандерса — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(sta)
м (rollbackEdits.php mass rollback)
 
(не показана 41 промежуточная версия 4 участников)
Строка 1: Строка 1:
'''Алгоритм Карккайнена-Сандерса''' (Karkkainen, Sanders) — алгоритм построения [[суффиксный массив | суффиксного массива]] за линейное время.
+
'''Алгоритм Карккайнена-Сандерса''' (Kärkkäinen, Sanders) — алгоритм построения [[суффиксный массив | суффиксного массива]] за линейное время.
  
 
__TOC__
 
__TOC__
Строка 6: Строка 6:
 
* В данном конспекте используется 0-индексация.
 
* В данном конспекте используется 0-индексация.
 
* <tex>S[i..j] </tex> — подстрока строки <tex> S </tex> с <tex>i</tex>-го по <tex>j</tex>-й символы включительно.
 
* <tex>S[i..j] </tex> — подстрока строки <tex> S </tex> с <tex>i</tex>-го по <tex>j</tex>-й символы включительно.
* Пусть длина строки <tex> S </tex> равна <tex> n </tex>. Обозначим <tex> S[i..j] </tex>, где <tex> j \ge n </tex> как строку <tex> S[i..n-1] </tex>, дополненную защитными символами <tex> \$ </tex> до длины <tex> n </tex>.  
+
* Пусть длина строки <tex> S </tex> равна <tex> n </tex>. Обозначим <tex> S^*[i..j] </tex>, где <tex> j \geqslant n </tex> как строку <tex> S[i..n-1] </tex>, дополненную защитными символами <tex> \$ </tex> до длины <tex> n </tex>.
  
 
== Алгоритм «разделяй и властвуй» ==  
 
== Алгоритм «разделяй и властвуй» ==  
Строка 20: Строка 20:
 
# Сливаем суффиксные массивы за линейное время.
 
# Сливаем суффиксные массивы за линейное время.
  
Получили асимптотическое уравнение <tex> T(n) = T(\frac{n}{2}) + O(n) </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> в конец). На шаге слияния мы сможем избавиться от него.
  
=== База рекурсии ===
+
=====База рекурсии=====
Если длина текущей строки <tex> S </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^* </tex> длины <tex> n </tex> в строку <tex> S' </tex> длины <tex> \dfrac{n}{2} </tex> следующим образом:
#* Сделаем список, состоящий из пар символов вида <tex> S[i..i + 1] </tex>, где <tex> i \bmod 2 = 1 </tex>.
+
#* Сделаем список, состоящий из пар символов вида <tex> S^*[i..i + 1] </tex>, где <tex> i \bmod 2 = 1 </tex>.
 
#* Отсортируем его цифровой сортировкой за линейное время и получим новый алфавит <tex> \Sigma' </tex>.
 
#* Отсортируем его цифровой сортировкой за линейное время и получим новый алфавит <tex> \Sigma' </tex>.
#* Перекодируем строку <tex> S[1..n] </tex> в алфавит <tex> \Sigma' </tex>, получив строку <tex> S' </tex> половинной длины.
+
#* Перекодируем строку <tex> S^*[1..n] </tex> в алфавит <tex> \Sigma' </tex>, получив строку <tex> S' </tex> половинной длины.
 
# Рекурсивно построим суффиксный массив <tex> A_{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_o} </tex>. Очевидно, <tex> A_{S_o}[i] = 2 A_{S'}[i] + 1 </tex>, так отношение упорядоченности любых двух строк в старом алфавите <tex> \Sigma </tex> эквивалентно отношению упорядоченности в новом алфавите <tex> \Sigma' </tex> по его построению.
  
=== Шаг 2 ===
+
=====Суффиксный массив для четных суффиксов=====
 
На этом шаге мы за линейное время получим суффиксный массив <tex> A_{S_e} </tex> для четных суффиксов, используя уже построенный <tex> A_{S_o} </tex>.
 
На этом шаге мы за линейное время получим суффиксный массив <tex> A_{S_e} </tex> для четных суффиксов, используя уже построенный <tex> A_{S_o} </tex>.
  
Заметим, что сортировка множества четных суффиксов <tex> \{ S[i..n] | i \bmod 2 = 0 \} </tex> аналогична сортировке множества пар <tex> \{ (S[i], S[i+1..n]) | i \bmod 2 = 0 \} </tex>. Однако <tex> S[i+1..n] </tex> — нечетный суффикс, и его относительную позицию мы уже узнали на шаге 1.
+
Заметим, что сортировка множества четных суффиксов <tex> \{ S^*[i..n] \mid i \bmod 2 = 0 \} </tex> аналогична сортировке множества пар <tex> \{ (S^*[i], S^*[i+1..n]) \mid i \bmod 2 = 0 \} </tex>. Однако <tex> S^*[i+1..n] </tex> — нечетный суффикс, и его относительную позицию мы уже узнали на шаге 1.
  
 
Таким образом, чтобы отсортировать эти пары за линейное время, сначала сразу выпишем их в порядке возрастания второго элемента пары (то есть в порядке вхождения в массив <tex> A_{S_o} </tex>), а потом отсортируем устойчивой сортировкой подсчетом по первым элементам. После этого легко можно восстановить массив <tex> A_{S_e} </tex>:
 
Таким образом, чтобы отсортировать эти пары за линейное время, сначала сразу выпишем их в порядке возрастания второго элемента пары (то есть в порядке вхождения в массив <tex> A_{S_o} </tex>), а потом отсортируем устойчивой сортировкой подсчетом по первым элементам. После этого легко можно восстановить массив <tex> A_{S_e} </tex>:
 
  M = []
 
  M = []
  '''for''' i = 0..n/2 - 1:
+
  '''for''' i = 0 '''to''' n / 2 - 1
 
     M.add(Pair(S[<tex> A_{S_o}</tex>[i] - 1], <tex> A_{S_o}</tex>[i]))
 
     M.add(Pair(S[<tex> A_{S_o}</tex>[i] - 1], <tex> A_{S_o}</tex>[i]))
  stable_sort(M)
+
  quick_stable_sort(M)
 
  <tex> A_{S_e} </tex> = []
 
  <tex> A_{S_e} </tex> = []
  '''for''' i = 0..n/2 - 1:
+
  '''for''' i = 0 '''to''' n/2 - 1:
 
     <tex> A_{S_e} </tex>.add(M[i].second - 1)
 
     <tex> A_{S_e} </tex>.add(M[i].second - 1)
  
Строка 55: Строка 54:
 
Получили, что весь второй шаг требует <tex> O(n) </tex> времени.
 
Получили, что весь второй шаг требует <tex> O(n) </tex> времени.
  
=== Шаг 3 ===
+
=====Слияние суффиксных массивов=====
 
Для суффиксного дерева третий шаг алгоритма опирается на специфические особенности суффиксных деревьев, которые не присущи суффиксным массивам<ref>M. Farach. Optimal suffix tree construction with large alphabets. http://www.cs.rutgers.edu/~farach/pubs/FarFerrMuthu00.pdf </ref> .   
 
Для суффиксного дерева третий шаг алгоритма опирается на специфические особенности суффиксных деревьев, которые не присущи суффиксным массивам<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>. Однако простой модификацией алгоритма можно значительно упростить его.
+
В случае [[Суффиксный массив|суффиксного массива]] слияние становится очень сложным, но все же оно было реализовано в алгоритме Ким-Сим-Парк-Парка<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>. Однако простой модификацией алгоритма можно значительно упростить его.
  
 
=== Пример ===
 
=== Пример ===
Строка 64: Строка 63:
 
Во-первых, добавив защитный символ '''$''', получив строку '''ababbbaa$''' (для этого алгоритма он не требуется, но может понадобиться в применениях суффиксного массива). Во-вторых, дополним ее до четной длины, получив '''ababbbaa$$'''.
 
Во-первых, добавив защитный символ '''$''', получив строку '''ababbbaa$''' (для этого алгоритма он не требуется, но может понадобиться в применениях суффиксного массива). Во-вторых, дополним ее до четной длины, получив '''ababbbaa$$'''.
  
==== Шаг 1 ====
+
=====Суффиксный массив для нечетных суффиксов=====
 
# В новом алфавите <tex> \Sigma' </tex> будет четыре элемента — '''ba''', '''bb''', '''a$''', '''$$'''. После сортировки они получат номера 2, 3, 1 и 0 соответственно.
 
# В новом алфавите <tex> \Sigma' </tex> будет четыре элемента — '''ba''', '''bb''', '''a$''', '''$$'''. После сортировки они получат номера 2, 3, 1 и 0 соответственно.
# Переводим строку S[1..n] = '''babbbaa$$$''' в новый алфавит. Сжатой строкой <tex> S' </tex> будет '''23210'''.
+
# Переводим строку <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'} </tex> = [4, 3, 2, 0, 1], и <tex> A_{S_o} </tex> = [9, 7, 5, 1, 3].
  
==== Шаг 2 ====
+
=====Суффиксный массив для четных суффиксов=====
# Обойдя массив <tex> A_{S_o} </tex>, получим <tex> M </tex> = [('''$''', 9), ('''a''', 7), ('''b''', 5), ('''a''', 1), ('''a''', 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>= [('''$''', 9), ('''a''', 7), ('''a''', 1), ('''a''', 3), ('''b''', 5)].
+
# После сортировки подсчетом по первому элементу, получим <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_e} </tex>, получаем [8, 6, 0, 2, 4], что действительно является суффиксным массивом для четных суффиксов.
  
==== Шаг 3 ====
+
=====Слияние суффиксных массивов=====
 
Если бы мы умели сливать <tex> A_{S_o} </tex> и <tex> A_{S_e} </tex> за линейное время, получили бы:
 
Если бы мы умели сливать <tex> A_{S_o} </tex> и <tex> A_{S_e} </tex> за линейное время, получили бы:
9 '''$'''
+
 
8 '''$$'''
+
{| style="background-color:#CCC;margin:0.5px"
7 '''a$$'''
+
!style="background-color:#EEE"| №
6 '''aa$$'''
+
!style="background-color:#EEE"| Подстрока
0 '''ababbbaa$$'''
+
|-
2 '''abbbaa$$'''
+
|style="background-color:#FFF;padding:2px 30px"| <tex> 9 </tex>
5 '''baa$$'''
+
|style="background-color:#FFF;padding:2px 30px"| <tex> \$ </tex>
1 '''babbbaa$$'''
+
|-
4 '''bbaa$$'''
+
|style="background-color:#FFF;padding:2px 30px"| <tex> 8 </tex>
3 '''bbbaa$$'''
+
|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\$\$ </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex> 6 </tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex> aa\$\$ </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex> 0 </tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex> ababbbaa\$\$ </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex> 2 </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> 1 </tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex> babbbaa\$\$ </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex> 4 </tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex> bbaa\$\$ </tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 30px"| <tex> 3 </tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex> bbbaa\$\$ </tex>
 +
|}
  
 
Как и было сказано вначале, избавиться от лишних '''$''' легко, так как суффиксы, им соответствующие, будут первыми в суффиксном массиве (в данном случае достаточно выбросить "9" из суффиксного массива).
 
Как и было сказано вначале, избавиться от лишних '''$''' легко, так как суффиксы, им соответствующие, будут первыми в суффиксном массиве (в данном случае достаточно выбросить "9" из суффиксного массива).
Строка 95: Строка 119:
 
# Сольем эти суффиксные массивы в один за линейное время.
 
# Сольем эти суффиксные массивы в один за линейное время.
  
Получили асимптотическое уравнение <tex> T(n) = T(\frac23 n) + O(n) </tex>, решением которого также является <tex> T(n) = O(n) </tex> (это видно из того, что сумма геометрической прогрессии с основанием <tex> \frac23 </tex> равна <tex> 3 </tex>).
+
Получили асимптотическое уравнение <tex> T(n) = T\left(\dfrac23 n\right) + O(n) </tex>, решением которого также является <tex> T(n) = O(n) </tex> (это видно из того, что сумма геометрической прогрессии с основанием <tex> \dfrac23 </tex> равна <tex> 3 </tex>).
  
Аналогично первой версии алгоритма, дополним строку <tex> S </tex> до длины, кратной трем, защитными символами <tex> \$ </tex>.
+
Аналогично первой версии алгоритма, дополним строку <tex> S </tex> до длины, кратной трем, защитными символами <tex> \$ </tex> и получим <tex>S^*</tex>.
  
=== База рекурсии ===
+
* '''База рекурсии'''
 
Для этого алгоритма минимальной базой рекурсии будет строка длиной 4, так как она дополняется до длины 6, после чего вновь следует рекурсивный вызов строки длиной 4, и, если бы база была меньше 4, алгоритм вошел бы в бесконечную рекурсию. На этом этапе также можно применить обычную сортировку суффиксов, так как это потребует <tex> O(1) </tex> действий.
 
Для этого алгоритма минимальной базой рекурсии будет строка длиной 4, так как она дополняется до длины 6, после чего вновь следует рекурсивный вызов строки длиной 4, и, если бы база была меньше 4, алгоритм вошел бы в бесконечную рекурсию. На этом этапе также можно применить обычную сортировку суффиксов, так как это потребует <tex> O(1) </tex> действий.
  
=== Шаг 1 ===
+
* '''Суффиксный массив для позиций не кратных 3'''
На этом шаге строится суффиксный массив <tex> A_{S_{12}} </tex> для множества суффиксов <tex> \{ S[i..n-1] | i \bmod 3 \ne 0 \} </tex>.
+
На этом шаге строится суффиксный массив <tex> A_{S_{12}} </tex> для множества суффиксов <tex> \{ S^*[i..n-1] \mid i \bmod 3 \ne 0 \} </tex>.
 
# Получим строку <tex> S' </tex> аналогично предыдущему алгоритму:
 
# Получим строку <tex> S' </tex> аналогично предыдущему алгоритму:
#* Сделаем список, состоящий из троек <tex> S[i..i+2]</tex> , где <tex> i \bmod 3 \ne 0 </tex>.
+
#* Сделаем список, состоящий из троек <tex> S^*[i..i+2]</tex> , где <tex> i \bmod 3 \ne 0 </tex>.
 
#* Отсортируем его за линейное время цифровой сортировкой и получим новый алфавит <tex> \Sigma' </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[i..n-1] </tex> в старом алфавите, где <tex> i \bmod 3 = 1 </tex>, в новом алфавите будет соответствовать строка <tex> S'[\frac{i-1}{3}..\frac{n}{3} - 1] </tex>, а если <tex> i\bmod 3 = 2 </tex>, то строка <tex> S'[\frac{n}{3} + \frac{i-2}{3}..\frac{2n}{3} - 1] </tex>.
+
#* Перекодируем строку <tex> S^*[1..n]S^*[2..n+1] </tex> в строку <tex> S' </tex> длиной <tex> \dfrac23 n </tex> в алфавите <tex> \Sigma' </tex>. Тогда суффиксу <tex> S^*[i..n-1] </tex> в старом алфавите, где <tex> i \bmod 3 = 1 </tex>, в новом алфавите будет соответствовать строка <tex> S'\left[\dfrac{i-1}{3}..\dfrac{n}{3} - 1\right] </tex>, а если <tex> i\bmod 3 = 2 </tex>, то строка <tex> S'\left[\dfrac{n}{3} + \dfrac{i-2}{3}..\dfrac{2n}{3} - 1\right] </tex>.
 
# Вызовем алгоритм рекурсивно для строки <tex> S' </tex>, получив суффиксный массив <tex> A_{S'} </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>:
+
# Пройдем по массиву <tex> A_{S'} </tex>. Если <tex> A_{S'}[i] < \dfrac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j = 3A_{S'}[i] + 1 </tex> в строке <tex> S </tex>, если же <tex> A_{S'}[i] \geqslant \dfrac{n}{3} </tex>, то этот суффикс соответствует позиции <tex> j =  3\left(A_{S'}[i] - \dfrac{n}{3}\right) + 2 </tex> в строке <tex> S^* </tex>. Псевдокод получения <tex> A_{S_{12}} </tex>:
 
  <tex> A_{S_{12}} </tex> = []
 
  <tex> A_{S_{12}} </tex> = []
  '''for''' i = 0..<tex>A_{S'}</tex>.length - 1:
+
  '''for''' i = 0 '''to''' <tex>A_{S'}</tex>.length - 1:
     '''if''' <tex>A_{S'}</tex>[i] < n / 3:
+
     '''if''' <tex>A_{S'}</tex>[i] < n/3:
 
         <tex>A_{S_{12}}</tex>.add(3 * <tex>A_{S'}</tex>[i] + 1)
 
         <tex>A_{S_{12}}</tex>.add(3 * <tex>A_{S'}</tex>[i] + 1)
 
     '''else''':
 
     '''else''':
         <tex>A_{S_{12}}</tex>.add(3 * (<tex>A_{S'}</tex>[i] - n / 3) + 2)
+
         <tex>A_{S_{12}}</tex>.add(3 * (<tex>A_{S'}</tex>[i] - n/3) + 2)
  
=== Шаг 2 ===
+
* '''Суффиксный массив для позиций кратных 3'''
Этот шаг также аналогичен первой версии алгоритма. Сортировка множества <tex> \{ S[i..n-1] | i \bmod 3 = 0 \} </tex> аналогична сортировке пар <tex> \{ (S[i], S[i+1..n-1]) | i \bmod 3 = 0 \} </tex>, где <tex> S[i+1..n-1] </tex> — суффиксы в позициях, равных 1 по модулю 3, относительный порядок которых уже известен. Выпишем эти пары в порядке вхождения их в <tex> A_{S_{12}} </tex> и отсортируем по первому элементу устойчивой сортировкой подсчетом, получив суффиксный массив <tex> A_{S_0} </tex>. Псевдокод этого шага:
+
Этот шаг также аналогичен первой версии алгоритма. Сортировка множества <tex> \{ S^*[i..n-1] \mid i \bmod 3 = 0 \} </tex> аналогична сортировке пар <tex> \{ (S^*[i], S^*[i+1..n-1]) \mid i \bmod 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> = []
 
  <tex>A_{S_0}</tex> = []
 
  M = []
 
  M = []
  '''for''' i = 0..2n/3 - 1:
+
  '''for''' i = 0 '''to''' 2n/3 - 1:
 
     '''if''' <tex> A_{S_{12}}</tex>[i] % 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]))
+
         M.add(Pair(S*[<tex>A_{S_{12}}</tex>[i] - 1], <tex>A_{S_{12}}</tex>[i]))
 
  stable_sort(M)
 
  stable_sort(M)
  '''for''' i = 0..n/3 - 1:
+
  '''for''' i = 0 '''to''' n/3 - 1:
 
     <tex>A_{S_0}</tex>.add(M[i].second - 1)
 
     <tex>A_{S_0}</tex>.add(M[i].second - 1)
 
Аналогично, второй шаг требует <tex> O(n) </tex> времени.
 
Аналогично, второй шаг требует <tex> O(n) </tex> времени.
  
=== Шаг 3 ===
+
* '''Слияние суффиксных массивов'''
 
На этом шаге мы должны слить суффиксные массивы <tex> A_{S_0} </tex> и <tex> A_{S_{12}} </tex>, чтобы получить суффиксный массив <tex> A_{S} </tex> для всей строки <tex> S </tex>.
 
На этом шаге мы должны слить суффиксные массивы <tex> A_{S_0} </tex> и <tex> A_{S_{12}} </tex>, чтобы получить суффиксный массив <tex> A_{S} </tex> для всей строки <tex> S </tex>.
  
Применим стандартный алгоритм слияния двух отсортированных массивов. Заметим, что явно массивы не отсортированы, но сотвествующие элементам массива суффиксы — отсортированы.  
+
Применим стандартный алгоритм слияния двух отсортированных массивов. Заметим, что явно массивы не отсортированы, но соответствующие элементам массива суффиксы — отсортированы.  
  
Пусть на какой-то итерации слияния мы сравниваем суффиксы, соответствующие позициям <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>, равной 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>.  
+
Аналогично, пусть на какой-то итерации слияния мы сравниваем суффиксы, соответствующие позициям <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>.  
  
 
Псевдокод этой фазы:
 
Псевдокод этой фазы:
  
 
  <tex>A_{S}</tex> = []
 
  <tex>A_{S}</tex> = []
  // Вначале предподсчитаем за O(n) обратную перестановку для суффиксного массива <tex> A_{S_{12}}</tex>, то есть массив rank такой, что <tex> A_{S_{12}}</tex>[rank[i]] = i.
+
  <font color=green>// Вначале предподсчитаем за O(n) обратную перестановку для суффиксного массива <tex> A_{S_{12}}</tex>, то есть массив rank такой, что <tex> A_{S_{12}}</tex>[rank[i]] = i.
  // Тогда мы сможем за O(1) сравнивать суффиксы по их позиции.
+
  // Тогда мы сможем за O(1) сравнивать суффиксы по их позиции. </font>
 
  rank = inverse(<tex>A_{S_{12}}</tex>)  
 
  rank = inverse(<tex>A_{S_{12}}</tex>)  
  '''while''' i < 2 * n / 3 '''and''' j < n / 3:
+
  '''while''' i < 2 * n/3 '''and''' j < n/3:
 
     pos12 = <tex> A_{S_{12}} </tex>[i]
 
     pos12 = <tex> A_{S_{12}} </tex>[i]
 
     pos0  = <tex> A_{0} </tex>[j]
 
     pos0  = <tex> A_{0} </tex>[j]
 
     '''if''' pos12 % 3 == 1:
 
     '''if''' pos12 % 3 == 1:
         ''' if''' Pair(S[pos12], rank[pos12 + 1]) < Pair(S[pos0], rank[pos0 + 1]):
+
         ''' if''' Pair(S*[pos12], rank[pos12 + 1]) < Pair(S*[pos0], rank[pos0 + 1]):
 
             <tex>A_{S}</tex>.add(pos12)
 
             <tex>A_{S}</tex>.add(pos12)
 
             i++
 
             i++
Строка 156: Строка 180:
 
             j++   
 
             j++   
 
     '''else''':
 
     '''else''':
         '''if''' Triple(S[pos12], S[pos12 + 1], rank[pos12 + 2]) < Triple(S[pos0], S[pos0 + 1], rank[pos0 + 2]):
+
         '''if''' Triple(S*[pos12], S*[pos12 + 1], rank[pos12 + 2]) < Triple(S*[pos0], S*[pos0 + 1], rank[pos0 + 2]):
 
             <tex>A_{S}</tex>.add(pos12)
 
             <tex>A_{S}</tex>.add(pos12)
 
             i++
 
             i++
Строка 162: Строка 186:
 
             <tex>A_{S}</tex>.add(pos0)
 
             <tex>A_{S}</tex>.add(pos0)
 
             j++  
 
             j++  
  '''while''' i < 2 * n / 3:
+
  '''while''' i < 2 * n/3:
 
     <tex>A_{S}</tex>.add(<tex> A_{S_{12}} </tex>[i])
 
     <tex>A_{S}</tex>.add(<tex> A_{S_{12}} </tex>[i])
 
     i++
 
     i++
  '''while''' j < n / 3:
+
  '''while''' j < n/3:
 
     <tex>A_{S}</tex>.add(<tex> A_{S_{0}} </tex>[j])
 
     <tex>A_{S}</tex>.add(<tex> A_{S_{0}} </tex>[j])
 
     j++
 
     j++
Строка 173: Строка 197:
 
=== Пример ===
 
=== Пример ===
 
Построим суффиксный массив для строки '''abbacab'''. После добавления защитного символа и дополнения до кратной трем длины, получим '''abbacab$$'''.
 
Построим суффиксный массив для строки '''abbacab'''. После добавления защитного символа и дополнения до кратной трем длины, получим '''abbacab$$'''.
==== Шаг 1 ====
+
* '''Суффиксный массив для позиций не кратных 3'''
# Тройками, соответствующими равными 1 по модулю 3 позициям, будут: '''bba''', '''cab''', '''$$$''', соответствующими равным 2 по модулю 3 — '''bac''', '''ab$''', '''$$$'''. Новый алфавит <tex> \Sigma' </tex> будет содержать элементы '''bba''', '''cab''', '''$$$''', '''bac''', '''ab$''', которые после сортировки получат номера 3, 4, 0, 2, 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'''.  
+
# Строкой '''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> = [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].
  
==== Шаг 2 ====
+
* '''Суффиксный массив для позиций кратных 3'''
# Обойдя массив <tex> A_{S_{12}} </tex> и выбрав в нем элементы, равные 1 по модулю 3, получим массив пар <tex>M</tex> = [('''b''', 7), ('''a''', 1), ('''a''', 4)]
+
# Обойдя массив <tex> A_{S_{12}} </tex> и выбрав в нем элементы, равные 1 по модулю 3, получим массив пар <tex>M</tex> = [(<tex>b</tex>, 7), (<tex>a</tex>, 1), (<tex>a</tex>, 4)]
 
# После устойчивой сортировки подсчетом по первому элементу, получим <tex> M </tex> = [('''a''', 1), ('''a''', 4), ('''b''', 7)]
 
# После устойчивой сортировки подсчетом по первому элементу, получим <tex> M </tex> = [('''a''', 1), ('''a''', 4), ('''b''', 7)]
 
# Восстановив <tex> A_{S_0} </tex>, получаем [0, 3, 6].
 
# Восстановив <tex> A_{S_0} </tex>, получаем [0, 3, 6].
==== Шаг 3 ====
+
* '''Слияние суффиксных массивов'''
 
Рассмотрим, к примеру, третью итерацию слияния, к этой итерации массив <tex> A_{S} </tex> = [8, 7], <tex> i </tex> = 2, <tex> j </tex> = 0, на ней мы сливаем суффиксы, соответствующие позициям 5 и 0.  
 
Рассмотрим, к примеру, третью итерацию слияния, к этой итерации массив <tex> A_{S} </tex> = [8, 7], <tex> i </tex> = 2, <tex> j </tex> = 0, на ней мы сливаем суффиксы, соответствующие позициям 5 и 0.  
# Образуем тройки (S[5], S[6], S[7..8]) и (S[0], S[1], S[2..8]).
+
# Образуем тройки <tex>(S^*[5], S^*[6], S^*[7..8])</tex> и <tex>(S^*[0], S^*[1], S^*[2..8])</tex>.
 
# После получения относительного порядка суффиксов, получим тройки ('''a''', '''b''', 1) и ('''a''', '''b''', 3). Первая тройка меньше второй, поэтому добавляем суффикс, соответствующий позиции 5 в массив <tex> A_{S} </tex>.
 
# После получения относительного порядка суффиксов, получим тройки ('''a''', '''b''', 1) и ('''a''', '''b''', 3). Первая тройка меньше второй, поэтому добавляем суффикс, соответствующий позиции 5 в массив <tex> A_{S} </tex>.
 
# В конце итерации получаем <tex> A_{S} </tex> = [8, 7, 5], <tex> i </tex> = 3, <tex> j </tex> = 0.
 
# В конце итерации получаем <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].
+
К концу слияния получим <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].
8 '''$''' (будет выброшен, так как в начале алгоритма добавляли один '''$''' к строке)
+
 
7 '''$$'''
+
{| style="background-color:#CCC;margin:0.5px"
5 '''ab$$'''
+
!style="background-color:#EEE"| №
0 '''abbacab$$'''
+
!style="background-color:#EEE"| Подстрока
3 '''acab$$'''
+
|-
6 '''b$$'''
+
|style="background-color:#FFF;padding:2px 30px"| <tex> 8 </tex>
2 '''bacab$$'''
+
|style="background-color:#FFF;padding:2px 30px"| <tex> \$ </tex>
1 '''bbacab$$'''
+
|-
4 '''cab$$'''
+
|style="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>
 +
|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_stage1.png|325px|thumb| Фаза 1]]
Строка 202: Строка 251:
 
| [[Файл:Kark_sanders_stage3.png|325px|thumb| Фаза 3]]
 
| [[Файл:Kark_sanders_stage3.png|325px|thumb| Фаза 3]]
 
|}
 
|}
== Получение массива LCP ==
+
 
 +
== Обобщение алгоритма ==
 
Массив LCP можно получить за линейное время [[Алгоритм_Касаи_и_др. | алгоритмом Касаи]].
 
Массив 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'').
 
На самом деле, алгоритм можно обобщить<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=
 
|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 \pmod m </tex>.
+
'''Разностное покрытие''' (англ. ''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 \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"/>.
 
Например, <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 />
+
* [[Суффиксный массив]]
 +
 
 +
== Примечания ==
 +
<references/>
  
== Источники ==
+
== Источники информации==
 
* [[Суффиксный массив]]
 
* [[Суффиксный массив]]
 
* [http://www.cs.helsinki.fi/juha.karkkainen/publications/icalp03.pdf Juha Kärkkäinen and Peter Sanders. Simple linear work suffix array construction]
 
* [http://www.cs.helsinki.fi/juha.karkkainen/publications/icalp03.pdf Juha Kärkkäinen and Peter Sanders. Simple linear work suffix array construction]

Текущая версия на 19:03, 4 сентября 2022

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

Используемые обозначения

  • В данном конспекте используется 0-индексация.
  • [math]S[i..j] [/math] — подстрока строки [math] S [/math] с [math]i[/math]-го по [math]j[/math]-й символы включительно.
  • Пусть длина строки [math] S [/math] равна [math] n [/math]. Обозначим [math] S^*[i..j] [/math], где [math] j \geqslant n [/math] как строку [math] S[i..n-1] [/math], дополненную защитными символами [math] \$ [/math] до длины [math] n [/math].

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

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


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

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

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

База рекурсии

Если длина текущей строки [math] S [/math] равна двум, надо выполнить обычное сравнение суффиксов.

Суффиксный массив для нечетных суффиксов
  1. Отобразим исходную строку [math] S^* [/math] длины [math] n [/math] в строку [math] S' [/math] длины [math] \dfrac{n}{2} [/math] следующим образом:
    • Сделаем список, состоящий из пар символов вида [math] S^*[i..i + 1] [/math], где [math] i \bmod 2 = 1 [/math].
    • Отсортируем его цифровой сортировкой за линейное время и получим новый алфавит [math] \Sigma' [/math].
    • Перекодируем строку [math] S^*[1..n] [/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] по его построению.
Суффиксный массив для четных суффиксов

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

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

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

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

Заметим, что массив [math] M [/math] перед сортировкой подсчетом не был явно отсортирован по вторым элементам, и хранил не суффиксы, а их позиции в строке [math] S [/math], но важно, что он был отсортирован по возрастанию соответствующих этим позициям нечетных суффиксов.

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

Слияние суффиксных массивов

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

Пример

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

Во-первых, добавив защитный символ $, получив строку ababbbaa$ (для этого алгоритма он не требуется, но может понадобиться в применениях суффиксного массива). Во-вторых, дополним ее до четной длины, получив ababbbaa$$.

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

Если бы мы умели сливать [math] A_{S_o} [/math] и [math] A_{S_e} [/math] за линейное время, получили бы:

Подстрока
[math] 9 [/math] [math] \$ [/math]
[math] 8 [/math] [math] \$\$ [/math]
[math] 7 [/math] [math] a\$\$ [/math]
[math] 6 [/math] [math] aa\$\$ [/math]
[math] 0 [/math] [math] ababbbaa\$\$ [/math]
[math] 2 [/math] [math] abbbaa\$\$ [/math]
[math] 5 [/math] [math] baa\$\$ [/math]
[math] 1 [/math] [math] babbbaa\$\$ [/math]
[math] 4 [/math] [math] bbaa\$\$ [/math]
[math] 3 [/math] [math] bbbaa\$\$ [/math]

Как и было сказано вначале, избавиться от лишних $ легко, так как суффиксы, им соответствующие, будут первыми в суффиксном массиве (в данном случае достаточно выбросить "9" из суффиксного массива).

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

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

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

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

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

  • База рекурсии

Для этого алгоритма минимальной базой рекурсии будет строка длиной 4, так как она дополняется до длины 6, после чего вновь следует рекурсивный вызов строки длиной 4, и, если бы база была меньше 4, алгоритм вошел бы в бесконечную рекурсию. На этом этапе также можно применить обычную сортировку суффиксов, так как это потребует [math] O(1) [/math] действий.

  • Суффиксный массив для позиций не кратных 3

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

  1. Получим строку [math] S' [/math] аналогично предыдущему алгоритму:
    • Сделаем список, состоящий из троек [math] S^*[i..i+2][/math] , где [math] i \bmod 3 \ne 0 [/math].
    • Отсортируем его за линейное время цифровой сортировкой и получим новый алфавит [math] \Sigma' [/math].
    • Перекодируем строку [math] S^*[1..n]S^*[2..n+1] [/math] в строку [math] S' [/math] длиной [math] \dfrac23 n [/math] в алфавите [math] \Sigma' [/math]. Тогда суффиксу [math] S^*[i..n-1] [/math] в старом алфавите, где [math] i \bmod 3 = 1 [/math], в новом алфавите будет соответствовать строка [math] S'\left[\dfrac{i-1}{3}..\dfrac{n}{3} - 1\right] [/math], а если [math] i\bmod 3 = 2 [/math], то строка [math] S'\left[\dfrac{n}{3} + \dfrac{i-2}{3}..\dfrac{2n}{3} - 1\right] [/math].
  2. Вызовем алгоритм рекурсивно для строки [math] S' [/math], получив суффиксный массив [math] A_{S'} [/math].
  3. Пройдем по массиву [math] A_{S'} [/math]. Если [math] A_{S'}[i] \lt \dfrac{n}{3} [/math], то этот суффикс соответствует позиции [math] j = 3A_{S'}[i] + 1 [/math] в строке [math] S [/math], если же [math] A_{S'}[i] \geqslant \dfrac{n}{3} [/math], то этот суффикс соответствует позиции [math] j = 3\left(A_{S'}[i] - \dfrac{n}{3}\right) + 2 [/math] в строке [math] S^* [/math]. Псевдокод получения [math] A_{S_{12}} [/math]:
[math] A_{S_{12}} [/math] = []
for i = 0 to [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)
  • Суффиксный массив для позиций кратных 3

Этот шаг также аналогичен первой версии алгоритма. Сортировка множества [math] \{ S^*[i..n-1] \mid i \bmod 3 = 0 \} [/math] аналогична сортировке пар [math] \{ (S^*[i], S^*[i+1..n-1]) \mid i \bmod 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 to 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 to n/3 - 1:
    [math]A_{S_0}[/math].add(M[i].second - 1)

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

  • Слияние суффиксных массивов

На этом шаге мы должны слить суффиксные массивы [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])
    j++

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

Пример

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

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

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

  1. Образуем тройки [math](S^*[5], S^*[6], S^*[7..8])[/math] и [math](S^*[0], S^*[1], S^*[2..8])[/math].
  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]\$[/math] в начале алгоритма для дополнения строки до длины, кратной трем, выбросим последний суффикс из [math] A_{S} [/math], получим в итоге, что [math] A_{S} [/math] = [7, 5, 0, 3, 6, 2, 1, 4].

Подстрока
[math] 8 [/math] [math] \$ [/math]
[math] 7 [/math] [math] \$\$ [/math]
[math] 5 [/math] [math] ab\$\$ [/math]
[math] 0 [/math] [math] abbacab\$\$ [/math]
[math] 3 [/math] [math] acab\$\$ [/math]
[math] 6 [/math] [math] b\$\$ [/math]
[math] 2 [/math] [math] bacab\$\$ [/math]
[math] 1 [/math] [math] bbacab\$\$ [/math]
[math] 4 [/math] [math] cab\$\$ [/math]

Заметим, что № 9 будет выброшен, так как в начале алгоритма был добавлен один [math] \$ [/math] к строке

Фаза 1
Фаза 2
Фаза 3

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

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

На самом деле, алгоритм можно обобщить[3], взяв на первом шаге, к примеру, суффиксы, позиции которых по модулю 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 \pmod m [/math].

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

См. также

Примечания

  1. M. Farach. Optimal suffix tree construction with large alphabets. http://www.cs.rutgers.edu/~farach/pubs/FarFerrMuthu00.pdf
  2. D. K. Kim, J. S. Sim, H. Park, and K. Park. Linear-time construction of suffix arrays. http://www.springerlink.com/content/568156021q45r320/
  3. 3,0 3,1 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

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