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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Литература)
(Псевдокод)
(не показано 9 промежуточных версий 1 участника)
Строка 9: Строка 9:
 
=== Псевдокод ===
 
=== Псевдокод ===
  
  '''suf_array'''(s)
+
  '''int[]''' sufArray('''string''' s)
     suf <tex>\leftarrow \{0, 1, \dots, |s|\}</tex>
+
     suf = {0, 1 .. s.length}
     '''sort''' (suf, '''compare''')
+
     '''sort'''(suf, compare)
     '''ret''' suf
+
     '''return''' suf
 
   
 
   
  '''compare''' (<tex>j_1</tex>, <tex>j_2</tex>)
+
  '''order''' compare('''int''' j1, '''int''' j2)
    '''for''' <tex>i</tex> = 0 '''to''' <tex>|s|</tex> '''do'''
+
    '''for''' i = 0 .. s.length
         '''if''' (s[(<tex>j_1+i</tex>) '''mod''' <tex>|s|</tex>] > s[(<tex>j_2+i</tex>) '''mod''' <tex>|s|</tex>])
+
         '''if''' (s[(j1 + i) '''mod''' s.length] > s[(j2 + i) '''mod''' s.length])
             '''ret''' 1
+
             '''return''' ''GT''
            '''if''' (s[(<tex>j_1+i</tex>) '''mod''' <tex>|s|</tex>] < s[(<tex>j_2+i</tex>) '''mod''' <tex>|s|</tex>])
+
        '''if''' (s[(j1 + i) '''mod''' s.length] < s[(j2 + i) '''mod''' s.length])
             '''ret''' -1
+
             '''return''' ''LT''
     '''ret''' 0
+
     '''return''' ''EQ''
  
 
== Алгоритм, использующий хеши ==
 
== Алгоритм, использующий хеши ==
Строка 32: Строка 32:
 
=== Псевдокод ===
 
=== Псевдокод ===
  
  '''suf_array'''(s)
+
  '''int[]''' sufArray('''string''' s)
     suf <tex>\leftarrow \{0, 1, \dots, |s|\}</tex>
+
     suf = {0, 1 .. s.length}
     '''sort''' (suf, '''compare''')
+
     '''sort'''(suf, compare)
     '''ret''' suf
+
     '''return''' suf
 
   
 
   
  '''compare''' (<tex>j_1</tex>, <tex>j_2</tex>)
+
  '''order''' compare('''int''' j1, '''int''' j2)
        same <tex>\leftarrow</tex> '''lcp'''(<tex>j_1</tex>, <tex>j_2</tex>)
+
    same = '''lcp'''(j1, j2)
        '''ret''' s[<tex>j_1</tex> + same] - s[<tex>j_2</tex> + same]
+
    '''if''' s[j1 + same] < s[j2 + same]
 +
        '''return''' ''LT''
 +
    '''else if''' s[j1 + same] == s2[j2 + same]
 +
        '''return''' ''EQ''
 +
    '''else'''
 +
        '''return''' ''GT''
 
   
 
   
  '''lcp''' (<tex>j_1</tex>, <tex>j_2</tex>)
+
  '''int''' lcp(j1, j2)
     <tex>l</tex> <tex>\leftarrow</tex> <tex>-1</tex>
+
     l = -1
     <tex>r</tex> <tex>\leftarrow</tex> <tex>|s|+1</tex>
+
     r = s.length + 1
     '''while''' (<tex>r - l > 1</tex>)
+
     '''while''' r - l > 1
         <tex>m</tex> <tex>\leftarrow</tex> <tex>(r + l) / 2</tex>
+
         m = (r + l) / 2
         '''if''' (hash[<tex>j_1\dots j_1 +m</tex>] = hash[<tex>j_2\dots j_2 + m</tex>])
+
         '''if''' hash[j1 .. j1 + m] == hash[j2 .. j2 + m]
           <tex>l \leftarrow m </tex>
+
           l = m
 
         '''else'''
 
         '''else'''
           <tex> r \leftarrow m </tex>
+
           r = m
     '''ret''' <tex>l</tex>
+
     '''return''' l
  
 
== Алгоритм, использующий префиксы циклических сдвигов ==
 
== Алгоритм, использующий префиксы циклических сдвигов ==
Строка 60: Строка 65:
 
Рассмотрим теперь переход от префиксов длины <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} \geqslant n</tex> все циклические сдвиги будут отсортированы. Всего шагов <tex>O(\log n)</tex>, каждый шаг проводится за <tex>O(n \log n)</tex>, итоговая асимптотика <tex>O(n \log^2 n)</tex>.
  
 +
Схожая идея используется и в [[Алгоритм цифровой сортировки суффиксов циклической строки|алгоритме цифровой сортировки суффиксов циклической строки]], который имеет лучшую асимптотику.
 
=== Псевдокод ===
 
=== Псевдокод ===
  '''suf_array'''(s)
+
  '''int[]''' suf_array('''string''' s)
     suf <tex>\leftarrow \{0, 1, \dots, |s|\}</tex>
+
     suf = {0, 1 .. s.length}
     '''sort''' (suf, '''compare1''')
+
     '''sort'''(suf, compare1)
     <tex>c \leftarrow \{</tex>s[0], s[1], ..., s[|s| - 1]<tex>\}</tex>
+
     c = {s[0], s[1] .. s[s.length - 1]}
 
   
 
   
     '''for''' <tex>l</tex> = 1 '''to''' <tex>2^{\lceil \log_2 n\rceil - 1}</tex> '''step''' <tex>l \leftarrow 2l</tex> '''do'''
+
     '''for''' l = 1 .. 2^('''ceil'''('''log2'''(n)) - 1) '''step''' l *= 2
         '''sort''' (suf, '''compare2''')
+
         '''sort'''(suf, compare2)
         <tex>c'</tex>[suf[0]] <tex>\leftarrow</tex> 0
+
         c'[suf[0]] = 0
         '''for''' <tex>i</tex> =  1 '''to''' <tex>|s|-1</tex> '''do'''
+
         '''for''' i =  1 .. s.length - 1
             <tex>l_1 \leftarrow </tex> suf[<tex>i - 1</tex>]
+
             l1 = suf[i - 1]
             <tex>r_1 \leftarrow </tex> suf[<tex>i - 1</tex>] + <tex>l</tex>
+
             r1 = suf[i - 1] + l
             <tex>l_2 \leftarrow </tex> suf[<tex>i</tex>]
+
             l2 = suf[i]
             <tex>r_2 \leftarrow </tex> suf[<tex>i</tex>] + <tex>l</tex>
+
             r2 = suf[i] + l
             '''if''' (<tex>c</tex>[<tex>l_1</tex>] <tex>\neq</tex> <tex>c</tex>[<tex>l_2</tex>] '''or''' <tex>c</tex>[<tex>r_1</tex>] <tex>\neq</tex> <tex>c</tex>[<tex>r_2</tex>])
+
             '''if''' c[l1] <tex>\neq</tex> c[l2] '''or''' c[r1] <tex>\neq</tex> c[r2]
                 <tex>c'</tex>[suf[<tex>i</tex>]] = <tex>c'</tex>[suf[<tex>i - 1</tex>]] + 1
+
                 c'[suf[i]] = c'[suf[i - 1]] + 1
 
             '''else'''
 
             '''else'''
                 <tex>c'</tex>[suf[<tex>i</tex>]] = <tex>c'</tex>[suf[<tex>i - 1</tex>]]
+
                 c'[suf[i]] = c'[suf[i - 1]]
        <tex>c \leftarrow c'</tex>
+
        c = c'
     '''ret''' suf
+
     '''return''' suf
 
   
 
   
  '''compare1''' (<tex>j_1</tex>, <tex>j_2</tex>)
+
  '''order''' compare1('''int''' j1, '''int''' j2)
         '''ret''' s[<tex>j_1</tex>] - s[<tex>j_2</tex>]
+
    '''if''' s[j1] < s[j2]
 +
         '''return''' ''LT''
 +
    '''else if''' s[j1] == s[j2]
 +
        '''return''' ''EQ''
 +
    '''else'''
 +
        '''return''' ''GT''
 
   
 
   
  '''compare2''' (<tex>j_1</tex>, <tex>j_2</tex>)
+
'''// Почему compare2 использует compare1, который сравнивает лишь символы, а не классы эквивалентности?'''
     '''if''' (<tex>c</tex>[<tex>j_1</tex>] <tex>\neq</tex> <tex>c</tex>[<tex>j_2</tex>])
+
  '''order''' compare2('''int''' j1, '''int''' j2)
         '''ret''' <tex>c</tex>[<tex>j_1</tex>] - <tex>c</tex>[<tex>j_2</tex>]
+
     '''if''' c[j1] <tex>\neq</tex> c[j2]
 +
         '''return''' '''compare1'''(j1, j2)
 
     '''else'''
 
     '''else'''
         '''ret''' <tex>c</tex>[<tex>j_1 + l</tex>] - <tex>c</tex>[<tex>j_2 + l</tex>]
+
         '''return''' '''compare1'''(j1 + l, j2 + l)
 +
 
 +
==См. также==
 +
* [[Суффиксный массив]]
 +
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
  
 
==Источники информации==
 
==Источники информации==
* Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — 2-е изд.
+
[http://en.wikipedia.org/wiki/Suffix_array#Construction_Algorithms Wikipedia Suffix array construction algorithms]
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Суффиксный массив]]
 
[[Категория:Суффиксный массив]]

Версия 21:56, 21 апреля 2016

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

Согласно определению суффиксного массива, для его построения достаточно отсортировать все суффиксы строки. Заменим сортировку суффиксов строки [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].

Наивный алгоритм

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

Псевдокод

int[] sufArray(string s)
   suf = {0, 1 .. s.length}
   sort(suf, compare)
   return suf

order compare(int j1, int j2)
    for i = 0 .. s.length
        if (s[(j1 + i) mod s.length] > s[(j2 + i) mod s.length])
            return GT
        if (s[(j1 + i) mod s.length] < s[(j2 + i) mod s.length])
            return LT
    return EQ

Алгоритм, использующий хеши

Данный алгоритм является некоторым улучшением предыдущего. Основная цель — сократить оценку времени сравнения двух циклических сдвигов до [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]suf + pref[/math] исходной строки, то с помощью двух хешей префиксов исходной строки можно найти хеш [math]suf[/math] или префикса [math]suf[/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].

Псевдокод

int[] sufArray(string s)
   suf = {0, 1 .. s.length}
   sort(suf, compare)
   return suf

order compare(int j1, int j2)
    same = lcp(j1, j2)
    if s[j1 + same] < s[j2 + same]
        return LT
    else if s[j1 + same] == s2[j2 + same]
        return EQ
    else
        return GT

int lcp(j1, j2)
   l = -1
   r = s.length + 1
   while r - l > 1
       m = (r + l) / 2
       if hash[j1 .. j1 + m] == hash[j2 .. j2 + m]
          l = m
       else
          r = m
   return l

Алгоритм, использующий префиксы циклических сдвигов

Этот алгоритм сильно отличается от двух предыдущих и от него несложно перейти к алгоритму за [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} \geqslant n[/math] все циклические сдвиги будут отсортированы. Всего шагов [math]O(\log n)[/math], каждый шаг проводится за [math]O(n \log n)[/math], итоговая асимптотика [math]O(n \log^2 n)[/math].

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

Псевдокод

int[] suf_array(string s)
   suf = {0, 1 .. s.length}
   sort(suf, compare1)
   c = {s[0], s[1] .. s[s.length - 1]}

   for l = 1 .. 2^(ceil(log2(n)) - 1) step l *= 2
       sort(suf, compare2)
       c'[suf[0]] = 0
       for i =  1 .. s.length - 1
           l1 = suf[i - 1]
           r1 = suf[i - 1] + l
           l2 = suf[i]
           r2 = suf[i] + l
           if c[l1] [math]\neq[/math] c[l2] or c[r1] [math]\neq[/math] c[r2]
               c'[suf[i]] = c'[suf[i - 1]] + 1
           else
               c'[suf[i]] = c'[suf[i - 1]]
        c = c'
   return suf

order compare1(int j1, int j2)
    if s[j1] < s[j2]
        return LT
    else if s[j1] == s[j2]
        return EQ
    else
        return GT

// Почему compare2 использует compare1, который сравнивает лишь символы, а не классы эквивалентности?

order compare2(int j1, int j2)
    if c[j1] [math]\neq[/math] c[j2]
        return compare1(j1, j2)
    else
        return compare1(j1 + l, j2 + l)

См. также

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

Wikipedia — Suffix array construction algorithms