Построение суффиксного массива с помощью стандартных методов сортировки — различия между версиями
(→Алгоритм, использующий хеши) |
(→Псевдокод) |
||
(не показано 16 промежуточных версий 2 участников) | |||
Строка 5: | Строка 5: | ||
== Наивный алгоритм == | == Наивный алгоритм == | ||
− | Данный алгоритм достаточно тривиален. Отсортируем все циклические сдвиги строки <tex>\alpha\$</tex>, воспользовавшись любым известным методом логарифмической сортировки (например "сортировка слиянием"). Тогда сравнение любых двух циклических сдвигов будет осуществляться за <tex>O(n)</tex> и суммарная сложность алгоритма составит <tex>O(n^2\log | + | Данный алгоритм достаточно тривиален. Отсортируем все циклические сдвиги строки <tex>\alpha\$</tex>, воспользовавшись любым известным методом логарифмической сортировки (например "сортировка слиянием"). Тогда сравнение любых двух циклических сдвигов будет осуществляться за <tex>O(n)</tex> и суммарная сложность алгоритма составит <tex>O(n^2\log n)</tex>. |
=== Псевдокод === | === Псевдокод === | ||
− | ''' | + | '''int[]''' sufArray('''string''' s) |
− | suf | + | suf = {0, 1 .. s.length} |
− | '''sort''' (suf, | + | '''sort'''(suf, compare) |
− | ''' | + | '''return''' suf |
− | ''' | + | '''order''' compare('''int''' j1, '''int''' j2) |
− | + | '''for''' i = 0 .. s.length | |
− | '''if''' (s[( | + | '''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'' |
== Алгоритм, использующий хеши == | == Алгоритм, использующий хеши == | ||
− | Данный алгоритм является некоторым улучшением предыдущего. Основная цель {{---}} сократить оценку времени сравнения двух циклических сдвигов до <tex>O(\log | + | Данный алгоритм является некоторым улучшением предыдущего. Основная цель {{---}} сократить оценку времени сравнения двух циклических сдвигов до <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>suf + pref</tex> исходной строки, то с помощью двух хешей префиксов исходной строки можно найти хеш <tex>suf</tex> или префикса <tex>suf</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 | + | Если оказалось, что <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>. |
=== Псевдокод === | === Псевдокод === | ||
− | ''' | + | '''int[]''' sufArray('''string''' s) |
− | suf | + | suf = {0, 1 .. s.length} |
− | '''sort''' (suf, | + | '''sort'''(suf, compare) |
− | ''' | + | '''return''' suf |
− | '''compare''' | + | '''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''' | + | '''while''' r - l > 1 |
− | + | m = (r + l) / 2 | |
− | '''if''' | + | '''if''' hash[j1 .. j1 + m] == hash[j2 .. j2 + m] |
− | + | l = m | |
'''else''' | '''else''' | ||
− | + | r = m | |
− | ''' | + | '''return''' l |
== Алгоритм, использующий префиксы циклических сдвигов == | == Алгоритм, использующий префиксы циклических сдвигов == | ||
− | Этот алгоритм сильно отличается от двух предыдущих и от него несложно перейти к алгоритму за <tex>O(n \log | + | Этот алгоритм сильно отличается от двух предыдущих и от него несложно перейти к алгоритму за <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 | + | Сначала легко можно отсортировать за <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 | + | Рассмотрим теперь переход от префиксов длины <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 | + | После шага <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''' | + | '''int[]''' suf_array('''string''' s) |
− | suf | + | suf = {0, 1 .. s.length} |
− | '''sort''' (suf, | + | '''sort'''(suf, compare1) |
− | + | c = {s[0], s[1] .. s[s.length - 1]} | |
− | '''for''' | + | '''for''' l = 1 .. 2^('''ceil'''('''log2'''(n)) - 1) '''step''' l *= 2 |
− | '''sort''' (suf, | + | '''sort'''(suf, compare2) |
− | + | c'[suf[0]] = 0 | |
− | '''for''' | + | '''for''' i = 1 .. s.length - 1 |
− | + | l1 = suf[i - 1] | |
− | + | r1 = suf[i - 1] + l | |
− | + | l2 = suf[i] | |
− | + | r2 = suf[i] + l | |
− | '''if''' | + | '''if''' c[l1] <tex>\neq</tex> c[l2] '''or''' c[r1] <tex>\neq</tex> c[r2] |
− | + | c'[suf[i]] = c'[suf[i - 1]] + 1 | |
'''else''' | '''else''' | ||
− | + | c'[suf[i]] = c'[suf[i - 1]] | |
− | + | c = c' | |
− | ''' | + | '''return''' suf |
− | '''compare1''' | + | '''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''' | + | '''// Почему compare2 использует compare1, который сравнивает лишь символы, а не классы эквивалентности?''' |
− | '''if''' | + | '''order''' compare2('''int''' j1, '''int''' j2) |
− | ''' | + | '''if''' c[j1] <tex>\neq</tex> c[j2] |
+ | '''return''' '''compare1'''(j1, j2) | ||
'''else''' | '''else''' | ||
− | ''' | + | '''return''' '''compare1'''(j1 + l, j2 + l) |
+ | |||
+ | ==См. также== | ||
+ | * [[Суффиксный массив]] | ||
+ | * [[Алгоритм цифровой сортировки суффиксов циклической строки]] | ||
− | == | + | ==Источники информации== |
− | + | [http://en.wikipedia.org/wiki/Suffix_array#Construction_Algorithms Wikipedia — Suffix array construction algorithms] | |
[[Категория:Алгоритмы и структуры данных]] | [[Категория:Алгоритмы и структуры данных]] | ||
[[Категория:Суффиксный массив]] | [[Категория:Суффиксный массив]] |
Версия 21:56, 21 апреля 2016
Содержание
Идея построения суффиксного массива
Согласно определению суффиксного массива, для его построения достаточно отсортировать все суффиксы строки. Заменим сортировку суффиксов строки на сортировку циклических сдвигов строки , где символ строго меньше любого символа из . Тогда если в упорядоченных циклических сдвигах отбросить суффикс, начинающийся на , то получатся упорядоченные суффиксы исходной строки . В дальнейшем положим (заметим, что все циклические сдвиги также имеют длину ), а также .
Наивный алгоритм
Данный алгоритм достаточно тривиален. Отсортируем все циклические сдвиги строки
, воспользовавшись любым известным методом логарифмической сортировки (например "сортировка слиянием"). Тогда сравнение любых двух циклических сдвигов будет осуществляться за и суммарная сложность алгоритма составит .Псевдокод
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
Алгоритм, использующий хеши
Данный алгоритм является некоторым улучшением предыдущего. Основная цель — сократить оценку времени сравнения двух циклических сдвигов до алгоритме Рабина-Карпа .
, тогда мы по аналогии с предыдущим алгоритмом получим оценку . У нас есть возможность быстро сравнивать подстроки на равенство используя метод, описанный вПусть нам необходимо сравнить два циклических сдвига
и . Найдем сначала их наибольший общий префикс ( ), для этого будем использовать двоичный поиск по длине совпадающего префикса, а проверку осуществлять с помощью посчитанных хешей префиксов. Поскольку циклический сдвиг состоит из суффикса и префикса исходной строки, то с помощью двух хешей префиксов исходной строки можно найти хеш или префикса . Таким образом можно найти хеш префикса циклического сдвига.Если оказалось, что
, то строки равны. Если же , то символы и точно различаются, и их сравнение позволяет сделать вывод, какой из циклических сдвигов меньше в лексикографическом порядке. Итак, двоичный поиск работает за , остальные операции требуют константного времени, следовательно, время, необходимое на сравнение двух циклических сдвигов, оценивается как .Псевдокод
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
Алгоритм, использующий префиксы циклических сдвигов
Этот алгоритм сильно отличается от двух предыдущих и от него несложно перейти к алгоритму за
. Итак, основная идея: на каждом шаге будем сортировать префиксы циклических сдвигов длины . Еще одно важное дополнение: после каждой фазы каждому префиксу циклического сдвига будет присваиваться номер класса эквивалентности среди этих префиксов. Причем классы эквивалентности должны быть пронумерованы в лексикографическом порядке соответствующих представителей.Сначала легко можно отсортировать за
префиксы длины , то есть символы. А номера классов поставить в соответствии с порядковым номером символа в алфавите.Рассмотрим теперь переход от префиксов длины
к префиксам длины . Научимся сравнивать два префикса длины за : Пусть даны префиксы , , сравним сначала их левые половинки, использовав значения с предыдущего шага, если , то префиксы соотносятся так как же, как и , если , то переходим к сравнению и . Итак, отсортировать префиксы длины можно за . Вычислить новые можно просто пробежавшись в лексикографическом порядке по префиксам, и увеличивая номер соответствующего класса на , если текущий префикс не совпадает с предыдущим (сравнивать с помощью старых ).После шага
все циклические сдвиги будут отсортированы. Всего шагов , каждый шаг проводится за , итоговая асимптотика .Схожая идея используется и в алгоритме цифровой сортировки суффиксов циклической строки, который имеет лучшую асимптотику.
Псевдокод
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]c[l2] or c[r1] 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]
c[j2]
return compare1(j1, j2)
else
return compare1(j1 + l, j2 + l)