Построение суффиксного массива с помощью стандартных методов сортировки — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(стиль)
Строка 1: Строка 1:
 
== Идея построения суффиксного массива ==
 
== Идея построения суффиксного массива ==
  
Согласно [[Суффиксный массив|определению]] суффиксного массива, для его построения достаточно отсортировать все суффиксы строки. Заменим сортировку суффиксов строки <tex>\alpha</tex> на сортировку циклических сдвигов строки <tex>\alpha\$</tex>, где символ <tex>\$</tex> строго меньше любого символа из <tex>\alpha</tex>. Тогда если в упорядоченных циклических сдвигах отбросить суффикс, начинающийся на <tex>\$</tex>, то получим упорядоченные суффиксы исходной строки <tex>\alpha</tex>. В дальнейшем положим <tex>|\alpha\$| = N </tex> (заметим, что все циклические сдвиги также длины <tex>N</tex>), а также <tex>\alpha\$ = s</tex>.
+
Согласно [[Суффиксный массив|определению]] суффиксного массива, для его построения достаточно отсортировать все суффиксы строки. Заменим сортировку суффиксов строки <tex>\alpha</tex> на сортировку циклических сдвигов строки <tex>\alpha\$</tex>, где символ <tex>\$</tex> строго меньше любого символа из <tex>\alpha</tex>. Тогда если в упорядоченных циклических сдвигах отбросить суффикс, начинающийся на <tex>\$</tex>, то получатся упорядоченные суффиксы исходной строки <tex>\alpha</tex>. В дальнейшем положим <tex>|\alpha\$| = N </tex> (заметим, что все циклические сдвиги также имеют длину <tex>N</tex>), а также <tex>\alpha\$ = s</tex>.
  
 
== Алгоритм за O(N^2 log(N)) (наивно) ==
 
== Алгоритм за O(N^2 log(N)) (наивно) ==
  
Данный алгоритм достаточно тривиален. Отсортируем все циклические сдвиги строки <tex>\alpha\$</tex> воспользовавшись любым известным ранее методом логарифмической сортировки (например "сортировка слиянием"). Тогда сравнение любых двух циклических сдвигов будет осуществляться за <tex>O(N)</tex> и суммарная сложность алгоритма составит <tex>O(N^2\log(N))</tex>.
+
Данный алгоритм достаточно тривиален. Отсортируем все циклические сдвиги строки <tex>\alpha\$</tex>, воспользовавшись любым известным методом логарифмической сортировки (например "сортировка слиянием"). Тогда сравнение любых двух циклических сдвигов будет осуществляться за <tex>O(N)</tex> и суммарная сложность алгоритма составит <tex>O(N^2\log(N))</tex>.
  
 
=== Псевдокод ===
 
=== Псевдокод ===
Строка 24: Строка 24:
 
== Алгоритм за O(N log^2(N)) (хеши) ==
 
== Алгоритм за O(N log^2(N)) (хеши) ==
  
Данный алгоритм является некоторым улучшением предыдущего. Основная цель - сократить оценку времени сравнения двух циклических сдвигов до <tex>O(\log(n))</tex>, тогда мы по аналогии с предыдущим алгоритмом получим оценку <tex>O(N \log^2(N))</tex>. У нас есть возможность быстро сравнивать на равенство подстроки используя метод, описанный [[Поиск_подстроки_в_строке_с_использованием_хеширования._Алгоритм_Рабина-Карпа | здесь]].
+
Данный алгоритм является некоторым улучшением предыдущего. Основная цель {{---}} сократить оценку времени сравнения двух циклических сдвигов до <tex>O(\log(n))</tex>, тогда мы по аналогии с предыдущим алгоритмом получим оценку <tex>O(N \log^2(N))</tex>. У нас есть возможность быстро сравнивать подстроки на равенство используя метод, описанный [[Поиск_подстроки_в_строке_с_использованием_хеширования._Алгоритм_Рабина-Карпа | здесь]].
  
Далее пусть нам необходимо сравнить два циклических сдвига <tex>s[i_1..i_1-1]</tex> и <tex>s[i_2..i_2-1]</tex>. Найдем сначала их наибольший общий префикс (<tex>lcp(i_1,i_2)</tex>), для этого будем использовать двоичный поиск по длине совпадающего префикса, а проверку осуществлять с помощью посчитанных хешей префиксов.
+
Пусть нам необходимо сравнить два циклических сдвига <tex>s[i_1..i_1-1]</tex> и <tex>s[i_2..i_2-1]</tex>. Найдем сначала их наибольший общий префикс (<tex>lcp(i_1,i_2)</tex>), для этого будем использовать двоичный поиск по длине совпадающего префикса, а проверку осуществлять с помощью посчитанных хешей префиксов.
  
 
+
Если оказалось, что <tex>lcp(i_1,i_2) = N</tex>, то строки равны. Если же <tex>lcp(i_1,i_2) < N</tex>, то символы <tex>s[i_1 + lcp]</tex> и <tex>s[i_2+lcp]</tex> точно различаются, и их сравнение позволяет сделать вывод, какой из циклических сдвигов меньше в лексикографическом порядке. Итак, двоичный поиск работает за <tex>O(\log(N))</tex>, остальные операции требуют константного времени, следовательно, время, необходимое на сравнение двух циклических сдвигов, оценивается как <tex>O(\log(N))</tex>.
Если оказалось, что <tex>lcp(i_1,i_2) = N</tex>, то строки равны. Если же <tex>lcp(i_1,i_2) < N</tex>, то символы <tex>s[i_1 + lcp]</tex> и <tex>s[i_2+lcp]</tex> точно различаются, их сравнение позволяет сделать вывод, какой из циклических сдвигов меньше в лексикографическом порядке. Итак, двоичный поиск работает за <tex>O(\log(N))</tex> остальные операции требуют константного времени, получаем оценку времени, необходимого на сравнение двух циклических сдвигов <tex>O(\log(N))</tex>.
 
  
 
=== Псевдокод ===
 
=== Псевдокод ===
Строка 55: Строка 54:
 
== Алгоритм за O(N log^2(N)) (префиксы циклических сдвигов) ==
 
== Алгоритм за O(N log^2(N)) (префиксы циклических сдвигов) ==
  
Этот алгоритм сильно отличается от двух предыдущих и от него не сложно перейти к алгоритму за <tex>O(N \log(N))</tex>. Итак, основная идея: на каждом шаге будем сортировать префиксы циклических сдвигов длины <tex>1,2,4,..., 2^{\lceil \log_2(n)\rceil}</tex>. Еще одно важное дополнение: после каждой фазы, каждому префиксу циклического сдвига <tex>s[i..i-1]</tex> будет присваиваться номер класса эквивалентности  <tex>c[i]</tex> среди этих префиксов. Причем классы эквивалентности должны быть пронумерованы в лексикографическом порядке соответствующих представителей.
+
Этот алгоритм сильно отличается от двух предыдущих и от него несложно перейти к алгоритму за <tex>O(N \log(N))</tex>. Итак, основная идея: на каждом шаге будем сортировать префиксы циклических сдвигов длины <tex>1,2,4,..., 2^{\lceil \log_2(n)\rceil}</tex>. Еще одно важное дополнение: после каждой фазы каждому префиксу циклического сдвига <tex>s[i..i-1]</tex> будет присваиваться номер класса эквивалентности  <tex>c[i]</tex> среди этих префиксов. Причем классы эквивалентности должны быть пронумерованы в лексикографическом порядке соответствующих представителей.
  
В начале легко можно отсортировать за <tex>O(N \log(N))</tex> префиксы длины <tex>1</tex>, т.е. символы. А номера классов поставить в соответствии с порядковым номером символа в алфавите.
+
Сначала легко можно отсортировать за <tex>O(N \log(N))</tex> префиксы длины <tex>1</tex>, то есть символы. А номера классов поставить в соответствии с порядковым номером символа в алфавите.
  
Рассмотрим теперь переход от префиксов длины <tex>l</tex> к префиксам длины <tex>2l</tex>. Научимся сравнивать два префикса длины <tex>2l</tex> за <tex>O(1)</tex>: Пусть даны префиксы <tex>s[i..i+2l-1]</tex>, <tex>s[j..j+2l-1]</tex>, сравним сначала их левые половинки, использовав значения <tex>c[i], c[j]</tex> с предыдущего шага, если <tex>c[i]\neq c[j]</tex>, то префиксы соотносятся так как же, как <tex>c[i]</tex> и <tex> c[j]</tex>, если <tex>c[i]=c[j]</tex>, то переходим к сравнению <tex>c[i+l]</tex> и <tex> c[j+l]</tex>. Итак, отсортировать префиксы длины <tex>2l</tex> можно за <tex>O(N\log(n))</tex>. Вычислить новые <tex>c[i]</tex> можно легко просто пробежавшись в лексикографическом порядке по префиксам, и увеличивая значение соответствующего класса на <tex>1</tex> если текущий префикс не совпадает с предыдущим (сравнивать с помощью старых <tex>c[i], c[i+l]</tex>).
+
Рассмотрим теперь переход от префиксов длины <tex>l</tex> к префиксам длины <tex>2l</tex>. Научимся сравнивать два префикса длины <tex>2l</tex> за <tex>O(1)</tex>: Пусть даны префиксы <tex>s[i..i+2l-1]</tex>, <tex>s[j..j+2l-1]</tex>, сравним сначала их левые половинки, использовав значения <tex>c[i], c[j]</tex> с предыдущего шага, если <tex>c[i]\neq c[j]</tex>, то префиксы соотносятся так как же, как <tex>c[i]</tex> и <tex> c[j]</tex>, если <tex>c[i]=c[j]</tex>, то переходим к сравнению <tex>c[i+l]</tex> и <tex> c[j+l]</tex>. Итак, отсортировать префиксы длины <tex>2l</tex> можно за <tex>O(N\log(n))</tex>. Вычислить новые <tex>c[i]</tex> можно просто пробежавшись в лексикографическом порядке по префиксам, и увеличивая номер соответствующего класса на <tex>1</tex>, если текущий префикс не совпадает с предыдущим (сравнивать с помощью старых <tex>c[i], c[i+l]</tex>).
  
После шага <tex>l =2^{\lceil \log_2(n)\rceil} \ge N</tex>. Все циклические сдвиги будут отсортированы. Всего шагов <tex>O(\log(N))</tex>, каждый шаг проводится за <tex>O(N \log(n))</tex>, итоговая асимптотика <tex>O(N \log^2(N))</tex>.
+
После шага <tex>l =2^{\lceil \log_2(n)\rceil} \ge N</tex> все циклические сдвиги будут отсортированы. Всего шагов <tex>O(\log(N))</tex>, каждый шаг проводится за <tex>O(N \log(n))</tex>, итоговая асимптотика <tex>O(N \log^2(N))</tex>.
  
 
=== Псевдокод ===
 
=== Псевдокод ===

Версия 18:34, 28 июня 2011

Идея построения суффиксного массива

Согласно определению суффиксного массива, для его построения достаточно отсортировать все суффиксы строки. Заменим сортировку суффиксов строки [math]\alpha[/math] на сортировку циклических сдвигов строки [math]\alpha\$[/math], где символ [math]\$[/math] строго меньше любого символа из [math]\alpha[/math]. Тогда если в упорядоченных циклических сдвигах отбросить суффикс, начинающийся на [math]\$[/math], то получатся упорядоченные суффиксы исходной строки [math]\alpha[/math]. В дальнейшем положим [math]|\alpha\$| = N [/math] (заметим, что все циклические сдвиги также имеют длину [math]N[/math]), а также [math]\alpha\$ = s[/math].

Алгоритм за O(N^2 log(N)) (наивно)

Данный алгоритм достаточно тривиален. Отсортируем все циклические сдвиги строки [math]\alpha\$[/math], воспользовавшись любым известным методом логарифмической сортировки (например "сортировка слиянием"). Тогда сравнение любых двух циклических сдвигов будет осуществляться за [math]O(N)[/math] и суммарная сложность алгоритма составит [math]O(N^2\log(N))[/math].

Псевдокод

suf_array(s)
   suf [math]\leftarrow \{0, 1, \dots, |s|\}[/math]
   sort (suf, compare)
   ret suf

compare ([math]j_1[/math], [math]j_2[/math])
        for [math]i[/math] = 0 to [math]|s|[/math] do
            if (s[([math]j_1+i[/math]) mod [math]|s|[/math]] > s[([math]j_2+i[/math]) mod [math]|s|[/math]])
               ret 1
               if (s[([math]j_1+i[/math]) mod [math]|s|[/math]] < s[([math]j_2+i[/math]) mod [math]|s|[/math]])
               ret -1
        ret 0

Алгоритм за O(N log^2(N)) (хеши)

Данный алгоритм является некоторым улучшением предыдущего. Основная цель — сократить оценку времени сравнения двух циклических сдвигов до [math]O(\log(n))[/math], тогда мы по аналогии с предыдущим алгоритмом получим оценку [math]O(N \log^2(N))[/math]. У нас есть возможность быстро сравнивать подстроки на равенство используя метод, описанный здесь.

Пусть нам необходимо сравнить два циклических сдвига [math]s[i_1..i_1-1][/math] и [math]s[i_2..i_2-1][/math]. Найдем сначала их наибольший общий префикс ([math]lcp(i_1,i_2)[/math]), для этого будем использовать двоичный поиск по длине совпадающего префикса, а проверку осуществлять с помощью посчитанных хешей префиксов.

Если оказалось, что [math]lcp(i_1,i_2) = N[/math], то строки равны. Если же [math]lcp(i_1,i_2) \lt N[/math], то символы [math]s[i_1 + lcp][/math] и [math]s[i_2+lcp][/math] точно различаются, и их сравнение позволяет сделать вывод, какой из циклических сдвигов меньше в лексикографическом порядке. Итак, двоичный поиск работает за [math]O(\log(N))[/math], остальные операции требуют константного времени, следовательно, время, необходимое на сравнение двух циклических сдвигов, оценивается как [math]O(\log(N))[/math].

Псевдокод

suf_array(s)
   suf [math]\leftarrow \{0, 1, \dots, |s|\}[/math]
   sort (suf, compare)
   ret suf

compare ([math]j_1[/math], [math]j_2[/math])
        same [math]\leftarrow[/math] lcp([math]j_1[/math], [math]j_2[/math])
        ret s[[math]j_1[/math] + same] - s[[math]j_2[/math] + same]

lcp ([math]j_1[/math], [math]j_2[/math])
   [math]l[/math] [math]\leftarrow[/math] [math]-1[/math]
   [math]r[/math] [math]\leftarrow[/math] [math]|s|+1[/math]
   while ([math]r - l \gt  1[/math])
       [math]m[/math] [math]\leftarrow[/math] [math](r + l) / 2[/math]
       if (hash[[math]j_1\dots j_1 +m[/math]] = hash[[math]j+2\dots j_2 + m[/math]])
           [math]l \leftarrow m [/math]
       else
          [math] r \leftarrow m [/math]
   ret [math]l[/math]

Алгоритм за O(N log^2(N)) (префиксы циклических сдвигов)

Этот алгоритм сильно отличается от двух предыдущих и от него несложно перейти к алгоритму за [math]O(N \log(N))[/math]. Итак, основная идея: на каждом шаге будем сортировать префиксы циклических сдвигов длины [math]1,2,4,..., 2^{\lceil \log_2(n)\rceil}[/math]. Еще одно важное дополнение: после каждой фазы каждому префиксу циклического сдвига [math]s[i..i-1][/math] будет присваиваться номер класса эквивалентности [math]c[i][/math] среди этих префиксов. Причем классы эквивалентности должны быть пронумерованы в лексикографическом порядке соответствующих представителей.

Сначала легко можно отсортировать за [math]O(N \log(N))[/math] префиксы длины [math]1[/math], то есть символы. А номера классов поставить в соответствии с порядковым номером символа в алфавите.

Рассмотрим теперь переход от префиксов длины [math]l[/math] к префиксам длины [math]2l[/math]. Научимся сравнивать два префикса длины [math]2l[/math] за [math]O(1)[/math]: Пусть даны префиксы [math]s[i..i+2l-1][/math], [math]s[j..j+2l-1][/math], сравним сначала их левые половинки, использовав значения [math]c[i], c[j][/math] с предыдущего шага, если [math]c[i]\neq c[j][/math], то префиксы соотносятся так как же, как [math]c[i][/math] и [math] c[j][/math], если [math]c[i]=c[j][/math], то переходим к сравнению [math]c[i+l][/math] и [math] c[j+l][/math]. Итак, отсортировать префиксы длины [math]2l[/math] можно за [math]O(N\log(n))[/math]. Вычислить новые [math]c[i][/math] можно просто пробежавшись в лексикографическом порядке по префиксам, и увеличивая номер соответствующего класса на [math]1[/math], если текущий префикс не совпадает с предыдущим (сравнивать с помощью старых [math]c[i], c[i+l][/math]).

После шага [math]l =2^{\lceil \log_2(n)\rceil} \ge N[/math] все циклические сдвиги будут отсортированы. Всего шагов [math]O(\log(N))[/math], каждый шаг проводится за [math]O(N \log(n))[/math], итоговая асимптотика [math]O(N \log^2(N))[/math].

Псевдокод

suf_array(s)
   suf [math]\leftarrow \{0, 1, \dots, |s|\}[/math]
   sort (suf, compare1)
   [math]c \leftarrow \{[/math]s[0], s[1], ..., s[|s| - 1][math]\}[/math]

   for [math]l[/math] = 1 to [math]2^{\lceil \log_2(n)\rceil - 1}[/math] step [math]l \leftarrow 2l[/math] do
       sort (suf, compare2)
       [math]c'[/math][suf[0]] [math]\leftarrow[/math] 0
       for [math]i[/math] =  1 to [math]|s|-1[/math] do
           [math]l_1 \leftarrow c[/math][suf[[math]i - 1[/math]]]
           [math]r_1 \leftarrow c[/math][suf[[math]i - 1[/math]] + [math]l[/math]]
           [math]l_2 \leftarrow c[/math][suf[[math]i[/math]]]
           [math]r_2 \leftarrow c[/math][suf[[math]i[/math]] + [math]l[/math]]
           if ([math]c[/math][[math]l_1[/math]] [math]\neq[/math] [math]c[/math][[math]l_2[/math]] or [math]c[/math][[math]r_1[/math]] [math]\neq[/math] [math]c[/math][[math]r_2[/math]])
               [math]c'[/math][suf[[math]i[/math]]] = [math]c'[/math][suf[[math]i - 1[/math] + 1]]
           else
               [math]c'[/math][suf[[math]i[/math]]] = [math]c'[/math][suf[[math]i - 1[/math]]]
       [math]c \leftarrow c'[/math]
   ret suf

compare1 ([math]j_1[/math], [math]j_2[/math])
        ret s[[math]j_1[/math]] - s[[math]j_2[/math]]

compare2 ([math]j_1[/math], [math]j_2[/math])
    if ([math]c[/math][[math]j_1[/math]] [math]\neq[/math] [math]c[/math]_[[math]j_2[/math]])
        ret [math]c[/math][[math]j_1[/math]] - [math]c[/math][[math]j_2[/math]]
    else
        ret [math]c[/math][[math]j_1 + l[/math]] - [math]c[/math][[math]j_2 + l[/math]]