1632
правки
Изменения
м
Здесь мы рассмотрим Далее будут рассмотрены некоторые способы нахождения всех вхождений образца в текст с помощью [[суффиксный массив|суффиксного массива]].
/* array - суффиксный масcив. p - образец. n - длина образца. left - левая граница диапазона. right - правая граница диапазона. '''cmp<tex>_k\mathtt {cmp (k)}</tex>''' {{- --}} Функцияфункция, сравнивающая строки по <tex>k</tex>-тому символу. '''lower_bound'''<tex> \mathtt {lower}</tex>_<tex>\mathtt {bound (left, right, value, cmp)}</tex>, '''upper_bound'''<tex> \mathtt {upper}</tex>_<tex>\mathtt {bound (left, right, value, cmp) }</tex> {{- --}} функции бинарного поиска. Элементы строк нумеруются с единицы */
Пусть:* <tex> L_p </tex> и <tex> R_p </tex> - левая и правая границы диапазона ответов в суффиксном массиве <tex> array </tex>.=== Условные обозначения ===
У любого суффикса * <tex> \mathtt{answer} </tex>_<tex>\mathtt{left}</tex> и <tex>\mathtt{answer} </tex>_<tex>\mathtt{right}</tex> {{---}} левая и правая границы диапазона ответов в пределах этого суффиксном массиве <tex> array </tex>,* <tex> L </tex> {{---}} левая граница текущего диапазона поиска (изначально равна <tex>0</tex>),* <tex> R </tex> {{---}} правая граница текущего диапазона поиска (изначально равна <tex> |S| - 1 </tex>),* <tex> M = (L + R) / 2 </tex> {{---}} середина текущего диапазона есть префикспоиска, который полностью совпадает с образцом* <tex> l = </tex> <tex>\mathtt {lcp(array[L], p)} </tex> {{---}} длина общего префикса образца и левого края текущего диапазона поиска,* <tex> r = </tex> <tex>\mathtt {lcp(array[R], p)} </tex> {{---}} длина общего префикса образца и правого края текущего диапазона поиска,* <tex> m_l = </tex> <tex>\mathtt {lcp(array[L], array[M])} </tex> {{---}} длина общего префикса середины текущего диапазона и левого края текущего диапазона поиска,* <tex> m_r = </tex> <tex>\mathtt {lcp(array[M], array[R])} </tex> {{---}} длина общего префикса середины текущего диапазона и правого края текущего диапазона поиска.
* <tex> L </tex> - левая граница диапазона поиска (изначально равна 0).* <tex> R </tex> - правая граница диапазона поиска (изначально равна <tex> |S| - 1 </tex>).* <tex> M = (L + R) / 2 </tex>.== Алгоритм ===
* Если диапазон ответов не пустой, то у любого суффикса в пределах диапазона ответов есть префикс, который полностью совпадает с образцом. В самом начале просто посчитаем <tex> l = lcp(array[L], p) </tex>.* и <tex> r = lcp(array</tex> за линейное время с помощью [[RАлгоритм Касаи и др.|алгоритма Касаи, Арикавы, Аримуры, Ли и Парка]], pа во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить за <tex> O(1) </tex>.
В самом начале просто посчитаем Подсчет <tex> l m_l </tex> и <tex> r m_r </tex> за линейное время, а во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить можно производить за <tex> O(1) </tex>, если применять [[Алгоритм Фарака-Колтона и Бендера|алгоритм Фарака-Колтона и Бендера]]. * Любая пара суффиксов <tex> m_l = lcp(array</tex> из диапазона <tex> [L], array[M]) </tex>имеет хотя бы <tex> m_l </tex> совпадений в префиксах.* Аналогично любая пара суффиксов <tex> m_r = lcp(array</tex> из диапазона <tex> [M], array[R]) </tex>имеет хотя бы <tex> m_r </tex> совпадений в префиксах.
Подсчет <tex> m_l </tex> и <tex> m_r </tex> можно производить за <tex> O(1) </tex>, если применять [[Алгоритм Фарака-Колтона и Бендера|алгоритм Фарака-Колтона и Бендера]]. Любая пара суффиксов <tex> array </tex> из === Поиск границ диапазона <tex> [L, M] </tex> имеет хотя бы <tex> m_l </tex> совпадений в префиксах. Аналогично любая пара суффиксов <tex> array </tex> из диапазона <tex> [M, R] </tex> имеет хотя бы <tex> m_r </tex> совпадений в префиксах.ответов ===
# <tex> m_l > l </tex>. Это означает, что каждая пара суффиксов из диапазона <tex> [L, M] </tex> имеет между собой больше совпадений, чем суффикс с левого края с образцом, поэтому продолжим поиск в диапазоне <tex> [M, R] </tex>. Значение <tex> l </tex> при этом не меняется, а <tex> L = M </tex>.
Если Рассуждения при поиске <tex> l \mathtt{answer} < r /tex>_<tex>\mathtt{right}</tex> аналогичны, то действия аналогичнытолько нужно не забыть изменить границы поиска на изначальные <tex> L = 0 </tex> и <tex> R = |s| - 1 </tex>.
Бинарный поиск будет работать Таким образом часть бинарного поиска мы сделаем при сравнении нескольких <tex>\mathtt {lcp} </tex> между собой(каждое за <tex> O(1) </tex>), а если дойдет до тех порсравнения символов, пока то любой символ <tex> R - L p </tex> 1 сравнивается не более одного раза(при сравнении мы берем <tex>\mathtt {max}</tex><tex>(l, r) </tex>, а значит никогда не возвращаемся назад). В самом начале мы посчитали <tex> l </tex> и <tex> r </tex> за <tex> O(p) </tex>. В итоге получаем сложность алгоритма <tex> O(p + log(s)) </tex>. После этого Правда нужен предподсчет, чтобы можно присвоить левой границе диапазона ответов было брать <tex>\mathtt {lcp} </tex> для двух любых суффиксов <tex> array </tex> за <tex> L_p = R O(1) </tex> и переходить к поиску правой границы диапазона ответов , начиная с позиции <tex> R_p r </tex>.
Рассуждения при поиске <tex> R_p </tex> аналогичны, только нужно не забыть изменить границы поиска на изначальные <tex> L = 0 </tex> и <tex> R = |s| - 1 </tex>.=Рисунки===
Таким образом часть бинарного поиска мы сделаем при сравнении нескольких Черная вертикальная линия на рисунке обозначает <tex> \mathtt {lcp } </tex> между собой(каждое за от <tex> O(1) i </tex>), а если дойдет до сравнения символов, то любой символ -го суффикса суффиксного массива <tex> p </tex> сравнивается не более одного раза(при сравнении мы берем <tex> max(l, r) </tex>, а значит никогда не возвращаемся назад). В самом начале мы посчитали <tex> l array </tex> и образца <tex> r </tex> за <tex> O(p) </tex>. В итоге получаем сложность алгоритма <tex> O(p + log(s)) </tex>. Правда нужен предподсчетЧем линия длиннее, чтобы можно было брать <tex> lcp </tex> для двух любых суффиксов <tex> array </tex> за <tex> O(1) </tex>тем совпадений символов больше.
===Разбор случаев===<tex> L </tex>, <tex> M </tex> и <tex> R </tex> {{---}} то же самое, что в алгоритме. Кроме того, самая левая черная вертикальная линия на каждом рисунке означает <tex> l </tex>, аналогично, самая правая черная вертикальная линия на каждом рисунке означает <tex> r</tex>.
Условные обозначения:* Черная вертикальная линия на рисунке обозначает <tex> lcp </tex> от <tex> i </tex>-го суффикса суффиксного массива <tex> array </tex> и образца <tex> p </tex>. Чем линия длиннее, тем совпадений символов больше. * <tex> L </tex>, <tex> M </tex> и <tex> R </tex> {{---}} то же самое, что в алгоритме. Кроме того, самая левая черная вертикальная линия на каждом рисунке означает Иллюстраци возможных случаев при <tex> l </tex>, аналогично, самая правая черная вертикальная линия на каждом рисунке означает <tex> \geqslant r </tex>. Переменная <tex> m_l </tex> {{---}} это <tex> lcp </tex> в суффиксном массиве на промежутке <tex> [L, M] </tex>. Переменная <tex> m_r </tex> {{---}} это <tex> lcp </tex> в суффиксном массиве на промежутке <tex> [M, R] </tex>.* Серым цветом выделен <tex> lcp </tex> в суффиксном массиве на рассматриваемом промежутке.:
Простой пример для образца <tex>aaa</tex> на отсортированных суффиксах строки <tex>aaaaaa</tex>[[Файл:left.Жирным выделены буквы, которые на рисунках будут представлены черными линиями (совпадения с образцом), а серым {{---}} совпадения суффиксов друг с другом на промежутке <tex> [M, Rpng]] </tex>.
[[ФайлИллюстрации возможных случаев при <tex> l < r </tex>:examp3.png]]
Дальнейший разбор случаев никак не связан со строкой <tex>aaaaaa</tex> и образцом <tex>aaa</tex>. <br>Ищется левая граница ответов <tex> L_p </tex>. <br>Разберем случай <tex> l \ge r </tex>[[Файл:Right2. Возможны три варианта: png]]
[[Файл:left===Псевдокод===Массивы и строки нумеруются с нуля.png]]
* a) Сравнения <tex> l < m_l </tex_z , >. Сдвигаем <tex> L </tex> в <tex> M </tex>. Значение <tex> l </tex> не изменяется.* b) <tex> l _z , = m_l </tex>. Считаем <tex> lcp </tex> для образца и суффикса_z , стоящего в позиции <tex> M </tex>\leqslant_z , начиная с позиции <tex> l \geqslant_z </tex>.* с) означают лексикографическое сравнение двух строк по их первым <tex> l > m_l </tex>. Сдвигаем <tex> R </tex> в <tex> M </tex>, <tex> r = m_l z</tex>символам.
Разберем случай при Сравнения <tex> l < r , > , == , \leqslant , \geqslant </tex>при применении к строкам означают полное лексикографическое сравнение строк. Также возможны три варианта:
[[Файл:right2Функция <tex>\mathtt {common(z,s, p)}</tex> ищет количество совпадений символов строк <tex>s</tex> и <tex>p</tex> начиная с позиции <tex>z</tex>.png]]
* a) <tex> r < m_r </tex>. Сдвигаем <tex> R </tex> в <tex> M </tex>. Значение <tex> r </tex> не изменяется.* b) <tex> r = m_r </tex>. Считаем <tex> lcp n</tex> для образца и суффикса, стоящего в позиции {{---}} длина строки <tex> M s</tex>, начиная с позиции <tex> r </tex>. * с) <tex> r > m_r </tex>. Сдвигаем <tex> L w</tex> в <tex> M </tex>, {{---}} длина строки <tex> l = m_r p</tex>.
===Псевдокод===В алгоритме используются переменные, введенные выше в разделе "более быстрый поиск".
/* Массивы и строки нумеруются с нуля. Сравнения <<tex>_z </tex> , ><tex>_z </tex> , =<tex>_z </tex> , <=<tex>_z </tex> , >=<tex>_z </tex> означают лексикографическое сравнение двух строк по их первым z символам. Сравнения < , > , == , <= , >= при применении к строкам означают полное лексикографическое сравнение строк. Функция '''lcpfunction'''<tex>_z</tex>find_answer_left(p: '''String''', s, p: '''String''') ищет количество совпадений символов: '''int''' строк s и p начиная с позиции z. n - длина строки s. w - длина строки p. В алгоритме используются переменные, введенные выше в разделе "более быстрый поиск". */ l = '''lcp'''(p, s[array[0]]) r = '''lcp'''(p, s[array[n - 1]]) '''if''' (l == w or p < s[array[0]]) L<tex>_p</tex> answer_left = 0 '''else''' ''' if ''' (p > s[array[n - 1]) L<tex>_p</tex> answer_left = n '''else''' { L = 0 R = n - 1 '''while''' (R - L > 1) '''do''' { M = (L + R) / 2 m<tex>_l</tex> m_l = '''lcp'''(array[L], array[M]) m<tex>_r</tex> m_r = '''lcp'''(array[M], array[R]) '''if''' (l <tex>\geqslant</tex>= r) '''if''' (mm_l <tex>_l\geqslant</tex> >= l) m = l + '''lcpcommon'''<tex>_l</tex>(l, s[array[M]], p) '''else''' m = m_l
m = m<tex>_l</tex> '''else''' '''if''' (mm_r <tex>_r\geqslant</tex> >= r) m = r + '''lcpcommon'''<tex>_r</tex>(r, s[array[M]], p) '''else''' m = m<tex>_r</tex>m_r '''if''' (m == w || p <=tex>\leqslant</tex><tex>_m</tex> s[array[M]]){ R = M r = m } '''else''' { L = M l = m }answer_left = R } L<tex>_p</tex> = R = См. также ==* [[Алгоритм цифровой сортировки суффиксов циклической строки]]* [[Алгоритм Касаи и др.]] }* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
rollbackEdits.php mass rollback
== Наивный алгоритм поиска ==
Простейший способ узнать, встречается ли образец в тексте, используя суффиксный массив, {{---}} взять первый символ образца и [[Целочисленный двоичный поиск|бинарным поиском ]] по [[суффиксный массив|суффиксному массиву]] найти диапазон с суффиксами, начинающимися на такую же букву. Так как все элементы в полученном диапазоне отсортированы, а первые символы одинаковые, то оставшиеся после отбрасывания первого символа суффиксы тоже отсортированы. А значит, можно повторять процедуру сужения диапазона поиска уже по второму, затем третьему и так далее символу образца до получения либо пустого диапазона, либо успешного нахождения всех символов образца.
Бинарный поиск работает за время равное <tex> O(\log|s|) </tex>, а сравнение суффикса с образцом не может превышать длины образца.
'''Поиск диапазона '''
'''function''' elementary_search(p: '''String''', s: '''String'''): left = 0; <font color=darkgreen> // left, right {{---}} границы диапазона </font> right = n; <font color=darkgreen> // n {{---}} длина образца </font> '''for''' i = 1 '''to''' n { left = '''lower_bound'''(left, right, p[i], cmp<tex>_i</tex>(i) ); right = '''upper_bound'''(left, right, p[i], cmp<tex>_i</tex>(i) ); } '''if''' (right - left > 0) { yield print left; yield print right; } '''else''' yield print "No matches";
== Более быстрый поиск ==
Существует более быстрый алгоритм поиска образца в строке. Для этого используется <tex> \mathtt {lcp } </tex> ([[Суффиксный массив#Применения|longest common prefix]]).
Рассмотрим поиск левой границы диапазона ответов <tex> L_p \mathtt{answer} </tex>_<tex>\mathtt{left}</tex>.
Сразу проверим образец с суффиксами по краям исходного диапазона поиска <tex> L </tex> и <tex> R </tex>: если образец лексикографически больше последнего суффикса <tex> array </tex> или меньше первого суффикса, то образец не встречается в строке вовсе и поиск можно прекратить.
<tex> L_p \mathtt{answer} </tex>_<tex>\mathtt{left}</tex> ищется при помощи бинарного поиска по суффиксному массиву <tex> array </tex>. На каждом шаге поиска нам надо определять, на каком отрезке <tex> [L, M] </tex> или <tex> [M, R] </tex> надо продолжать поиск границы <tex> L_p \mathtt{answer} </tex>_<tex>\mathtt{left}</tex>. Каждую итерацию бинарного поиска будем сравнивать <tex> l </tex> и <tex> r </tex>. Если <tex> l \ge geqslant r </tex>, то возможно одно из трех:
# <tex> m_l > l </tex>. Это означает, что каждая пара суффиксов из диапазона <tex> [L, M] </tex> имеет между собой больше совпадений, чем суффикс с левого края с образцом, поэтому продолжим поиск в диапазоне <tex> [M, R] </tex>. Значение <tex> l </tex> при этом не меняется, а <tex> L = M </tex>.
# <tex> m_l = l </tex>. Это означает, что у каждого суффикса из <tex> [L, M] </tex> есть хотя бы <tex> l </tex> совпадений с образцом. Проверим суффикс в позиции <tex> M </tex>, так как с ним совпадений у образца может получиться больше. Начнем сравнивать суффикс в позиции <tex> M </tex> начиная с <tex> l </tex>-ого символа. Мы либо найдем полное вхождение образца в суффикс, либо на каком-то шаге <tex> k </tex> получим несоответствие. В первом случае <tex> R = M </tex> и <tex> r = |p| </tex>, так как мы ищем левую границу диапазона ответов. Во втором случае все зависит от лексикографического несовпадения. Если символ <tex> l + k + 1 </tex> у образца меньше, чем у суффикса, то <tex> R = M </tex> и <tex> r = l + k + 1</tex>, иначе <tex> L = M </tex> и <tex> l = l + k + 1</tex>.
# <tex> m_l < l </tex>. Это означает, что совпадений у суффикса с левого края диапазона поиска с образцом больше, чем у суффикса в позиции <tex> M </tex>. Очевидно, что поиск надо продолжать между <tex> L </tex> и <tex> M </tex>, то есть <tex> R = M </tex>, а новое значение <tex> r = m_l </tex>.
Если <tex> l < r </tex>, то действия аналогичны. Также три случая:
# <tex> m_r > r </tex>. Сдвигаем <tex> R </tex> в <tex> M </tex>. Значение <tex> r </tex> не изменяется.
# <tex> m_r = r </tex>. Считаем <tex>\mathtt {lcp} </tex> для образца и суффикса, стоящего в позиции <tex> M </tex>, начиная с позиции <tex> r </tex>.
# <tex> m_r < r </tex>. Сдвигаем <tex> L </tex> в <tex> M </tex>, <tex> l = m_r </tex>.
Бинарный поиск будет работать до тех пор, пока <tex> R - L > 1 </tex>. После этого можно присвоить левой границе диапазона ответов <tex> \mathtt{answer} </tex>_<tex>\mathtt{left} = R </tex> и переходить к поиску правой границы диапазона ответов <tex> \mathtt{answer} </tex>_<tex>\mathtt{right}</tex> .
Переменная <tex> m_l </tex> {{---}} это <tex>\mathtt {lcp} </tex> в суффиксном массиве на промежутке <tex> [L, M] </tex>. Переменная <tex> m_r </tex> {{---}} это <tex>\mathtt {lcp} </tex> в суффиксном массиве на промежутке <tex> [M, R] </tex>.
Серым цветом выделен <tex>\mathtt {lcp} </tex> в суффиксном массиве на рассматриваемом промежутке.
Поиск левой границы ответов <tex> L_p answer </tex>_<tex>left</tex>.
'''else'''
==ЛитератураИсточники информации==* [http://habrahabr.ru/blogs/algorithm/115346/Habrahabr {{---}} Суффиксный массив {{---}} удобная замена суффиксного дерева] *U. Manber and G. Mayers. {{---}} "Suffix arrays: A new method for on-line string searches"
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Структуры данных]]
[[Категория:Суффиксный массив]]
