Алгоритм поиска подстроки в строке с помощью суффиксного массива — различия между версиями
(→Псевдокод) |
м (rollbackEdits.php mass rollback) |
||
(не показано 35 промежуточных версий 4 участников) | |||
Строка 19: | Строка 19: | ||
Элементы строк нумеруются с единицы | Элементы строк нумеруются с единицы | ||
− | '''function''' elementary_search(): | + | '''function''' elementary_search(p: '''String''', s: '''String'''): |
left = 0 <font color=darkgreen> // left, right {{---}} границы диапазона </font> | left = 0 <font color=darkgreen> // left, right {{---}} границы диапазона </font> | ||
right = n <font color=darkgreen> // n {{---}} длина образца </font> | right = n <font color=darkgreen> // n {{---}} длина образца </font> | ||
Строка 26: | Строка 26: | ||
right = upper_bound(left, right, p[i], cmp (i) ) | right = upper_bound(left, right, p[i], cmp (i) ) | ||
'''if''' (right - left > 0) | '''if''' (right - left > 0) | ||
− | + | print left | |
− | + | print right | |
'''else''' | '''else''' | ||
− | + | print "No matches" | |
== Более быстрый поиск == | == Более быстрый поиск == | ||
− | Существует более быстрый алгоритм поиска образца в строке. Для этого используется <tex>\mathtt {lcp} </tex> (longest common prefix). | + | Существует более быстрый алгоритм поиска образца в строке. Для этого используется <tex>\mathtt {lcp} </tex> ([[Суффиксный массив#Применения|longest common prefix]]). |
− | === Условные обозначения === | + | === Условные обозначения === |
− | |||
− | |||
− | + | * <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> и <tex> r </tex> за линейное время с помощью [[Алгоритм Касаи и др.|алгоритма Касаи, Арикавы, Аримуры, Ли и Парка]], а во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить за <tex> O(1) </tex>. | |
− | В самом начале просто посчитаем <tex> l </tex> и <tex> r </tex> за линейное время, а во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить за <tex> O(1) | ||
− | |||
− | |||
− | |||
Подсчет <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 </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> | + | Рассмотрим поиск левой границы диапазона ответов <tex>\mathtt{answer} </tex>_<tex>\mathtt{left}</tex>. |
Сразу проверим образец с суффиксами по краям исходного диапазона поиска <tex> L </tex> и <tex> R </tex>: если образец лексикографически больше последнего суффикса <tex> array </tex> или меньше первого суффикса, то образец не встречается в строке вовсе и поиск можно прекратить. | Сразу проверим образец с суффиксами по краям исходного диапазона поиска <tex> L </tex> и <tex> R </tex>: если образец лексикографически больше последнего суффикса <tex> array </tex> или меньше первого суффикса, то образец не встречается в строке вовсе и поиск можно прекратить. | ||
− | <tex> | + | <tex> \mathtt{answer} </tex>_<tex>\mathtt{left}</tex> ищется при помощи бинарного поиска по суффиксному массиву <tex> array </tex>. На каждом шаге поиска нам надо определять, на каком отрезке <tex> [L, M] </tex> или <tex> [M, R] </tex> надо продолжать поиск границы <tex> \mathtt{answer} </tex>_<tex>\mathtt{left}</tex> . Каждую итерацию бинарного поиска будем сравнивать <tex> l </tex> и <tex> r </tex>. Если <tex> l \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> [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> [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> 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> l < r </tex>, то действия аналогичны. Также три случая: | ||
# <tex> m_r > r </tex>. Сдвигаем <tex> R </tex> в <tex> M </tex>. Значение <tex> 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>\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> 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> \mathtt{answer} </tex>_<tex>\mathtt{right}</tex> аналогичны, только нужно не забыть изменить границы поиска на изначальные <tex> L = 0 </tex> и <tex> R = |s| - 1 </tex>. |
+ | |||
+ | Таким образом часть бинарного поиска мы сделаем при сравнении нескольких <tex>\mathtt {lcp} </tex> между собой(каждое за <tex> O(1) </tex>), а если дойдет до сравнения символов, то любой символ <tex> p </tex> сравнивается не более одного раза(при сравнении мы берем <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> O(1) </tex>, начиная с позиции <tex> r </tex>. | ||
+ | |||
+ | ===Рисунки=== | ||
+ | |||
+ | Черная вертикальная линия на рисунке обозначает <tex>\mathtt {lcp} </tex> от <tex> i </tex>-го суффикса суффиксного массива <tex> array </tex> и образца <tex> p </tex>. Чем линия длиннее, тем совпадений символов больше. | ||
+ | |||
+ | <tex> L </tex>, <tex> M </tex> и <tex> R </tex> {{---}} то же самое, что в алгоритме. Кроме того, самая левая черная вертикальная линия на каждом рисунке означает <tex> l </tex>, аналогично, самая правая черная вертикальная линия на каждом рисунке означает <tex> r</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 \geqslant r </tex>: | ||
− | + | [[Файл:left.png]] | |
− | + | Иллюстрации возможных случаев при <tex> l < r </tex>: | |
− | + | [[Файл:Right2.png]] | |
===Псевдокод=== | ===Псевдокод=== | ||
Строка 95: | Строка 99: | ||
Сравнения <tex>< , > , == , \leqslant , \geqslant </tex> при применении к строкам означают полное лексикографическое сравнение строк. | Сравнения <tex>< , > , == , \leqslant , \geqslant </tex> при применении к строкам означают полное лексикографическое сравнение строк. | ||
− | Функция <tex>\mathtt { | + | Функция <tex>\mathtt {common(z,s, p)}</tex> ищет количество совпадений символов строк <tex>s</tex> и <tex>p</tex> начиная с позиции <tex>z</tex>. |
<tex>n</tex> {{---}} длина строки <tex>s</tex>, <tex>w</tex> {{---}} длина строки <tex>p</tex>. | <tex>n</tex> {{---}} длина строки <tex>s</tex>, <tex>w</tex> {{---}} длина строки <tex>p</tex>. | ||
Строка 102: | Строка 106: | ||
− | Поиск левой границы ответов <tex> | + | Поиск левой границы ответов <tex> answer </tex>_<tex>left</tex>. |
− | '''function''' | + | '''function''' find_answer_left(p: '''String''', s: '''String'''): '''int''' |
l = '''lcp'''(p, s[array[0]]) | l = '''lcp'''(p, s[array[0]]) | ||
r = '''lcp'''(p, s[array[n - 1]]) | r = '''lcp'''(p, s[array[n - 1]]) | ||
'''if''' (l == w or p < s[array[0]]) | '''if''' (l == w or p < s[array[0]]) | ||
− | + | answer_left = 0 | |
'''else''' '''if''' (p > s[array[n - 1]) | '''else''' '''if''' (p > s[array[n - 1]) | ||
− | + | answer_left = n | |
'''else''' | '''else''' | ||
L = 0 | L = 0 | ||
Строка 120: | Строка 124: | ||
'''if''' (l <tex>\geqslant</tex> r) | '''if''' (l <tex>\geqslant</tex> r) | ||
'''if''' (m_l <tex>\geqslant</tex> l) | '''if''' (m_l <tex>\geqslant</tex> l) | ||
− | m = l + ''' | + | m = l + '''common'''(l, s[array[M]], p) |
'''else''' | '''else''' | ||
m = m_l | m = m_l | ||
'''else''' | '''else''' | ||
'''if''' (m_r <tex>\geqslant</tex> r) | '''if''' (m_r <tex>\geqslant</tex> r) | ||
− | m = r + ''' | + | m = r + '''common'''(r, s[array[M]], p) |
'''else''' | '''else''' | ||
m = m_r | m = m_r | ||
Строка 134: | Строка 138: | ||
L = M | L = M | ||
l = m | l = m | ||
− | + | answer_left = R | |
== См. также == | == См. также == | ||
Строка 146: | Строка 150: | ||
[[Категория:Алгоритмы и структуры данных]] | [[Категория:Алгоритмы и структуры данных]] | ||
+ | [[Категория:Структуры данных]] | ||
[[Категория:Суффиксный массив]] | [[Категория:Суффиксный массив]] |
Текущая версия на 19:22, 4 сентября 2022
Далее будут рассмотрены некоторые способы нахождения всех вхождений образца в текст с помощью суффиксного массива.
Наивный алгоритм поиска
Простейший способ узнать, встречается ли образец в тексте, используя суффиксный массив, — взять первый символ образца и бинарным поиском по суффиксному массиву найти диапазон с суффиксами, начинающимися на такую же букву. Так как все элементы в полученном диапазоне отсортированы, а первые символы одинаковые, то оставшиеся после отбрасывания первого символа суффиксы тоже отсортированы. А значит, можно повторять процедуру сужения диапазона поиска уже по второму, затем третьему и так далее символу образца до получения либо пустого диапазона, либо успешного нахождения всех символов образца.
Бинарный поиск работает за время равное
, а сравнение суффикса с образцом не может превышать длины образца.Таким образом время работы алгоритмы
, где — текст, — образец.Псевдокод
Поиск диапазона
— функция, сравнивающая строки по -тому символу.
_ , _ — функции бинарного поиска.
Элементы строк нумеруются с единицы
function elementary_search(p: String, s: String): left = 0 // left, right — границы диапазона right = n // n — длина образца for i = 1 to n left = lower_bound(left, right, p[i], cmp (i) ) right = upper_bound(left, right, p[i], cmp (i) ) if (right - left > 0) print left print right else print "No matches"
Более быстрый поиск
Существует более быстрый алгоритм поиска образца в строке. Для этого используется longest common prefix).
(Условные обозначения
- _ и _ — левая и правая границы диапазона ответов в суффиксном массиве ,
- — левая граница текущего диапазона поиска (изначально равна ),
- — правая граница текущего диапазона поиска (изначально равна ),
- — середина текущего диапазона поиска,
- — длина общего префикса образца и левого края текущего диапазона поиска,
- — длина общего префикса образца и правого края текущего диапазона поиска,
- — длина общего префикса середины текущего диапазона и левого края текущего диапазона поиска,
- — длина общего префикса середины текущего диапазона и правого края текущего диапазона поиска.
Алгоритм
Если диапазон ответов не пустой, то у любого суффикса в пределах диапазона ответов есть префикс, который полностью совпадает с образцом.
В самом начале просто посчитаем алгоритма Касаи, Арикавы, Аримуры, Ли и Парка, а во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить за .
и за линейное время с помощьюПодсчет алгоритм Фарака-Колтона и Бендера. Любая пара суффиксов из диапазона имеет хотя бы совпадений в префиксах. Аналогично любая пара суффиксов из диапазона имеет хотя бы совпадений в префиксах.
и можно производить за , если применятьПоиск границ диапазона ответов
Рассмотрим поиск левой границы диапазона ответов
_ .Сразу проверим образец с суффиксами по краям исходного диапазона поиска
и : если образец лексикографически больше последнего суффикса или меньше первого суффикса, то образец не встречается в строке вовсе и поиск можно прекратить._ ищется при помощи бинарного поиска по суффиксному массиву . На каждом шаге поиска нам надо определять, на каком отрезке или надо продолжать поиск границы _ . Каждую итерацию бинарного поиска будем сравнивать и . Если , то возможно одно из трех:
- . Это означает, что каждая пара суффиксов из диапазона имеет между собой больше совпадений, чем суффикс с левого края с образцом, поэтому продолжим поиск в диапазоне . Значение при этом не меняется, а .
- . Это означает, что у каждого суффикса из есть хотя бы совпадений с образцом. Проверим суффикс в позиции , так как с ним совпадений у образца может получиться больше. Начнем сравнивать суффикс в позиции начиная с -ого символа. Мы либо найдем полное вхождение образца в суффикс, либо на каком-то шаге получим несоответствие. В первом случае и , так как мы ищем левую границу диапазона ответов. Во втором случае все зависит от лексикографического несовпадения. Если символ у образца меньше, чем у суффикса, то и , иначе и .
- . Это означает, что совпадений у суффикса с левого края диапазона поиска с образцом больше, чем у суффикса в позиции . Очевидно, что поиск надо продолжать между и , то есть , а новое значение .
Если
, то действия аналогичны. Также три случая:- . Сдвигаем в . Значение не изменяется.
- . Считаем для образца и суффикса, стоящего в позиции , начиная с позиции .
- . Сдвигаем в , .
Бинарный поиск будет работать до тех пор, пока
. После этого можно присвоить левой границе диапазона ответов _ и переходить к поиску правой границы диапазона ответов _ .Рассуждения при поиске
_ аналогичны, только нужно не забыть изменить границы поиска на изначальные и .Таким образом часть бинарного поиска мы сделаем при сравнении нескольких
между собой(каждое за ), а если дойдет до сравнения символов, то любой символ сравнивается не более одного раза(при сравнении мы берем , а значит никогда не возвращаемся назад). В самом начале мы посчитали и за . В итоге получаем сложность алгоритма . Правда нужен предподсчет, чтобы можно было брать для двух любых суффиксов за , начиная с позиции .Рисунки
Черная вертикальная линия на рисунке обозначает
от -го суффикса суффиксного массива и образца . Чем линия длиннее, тем совпадений символов больше., и — то же самое, что в алгоритме. Кроме того, самая левая черная вертикальная линия на каждом рисунке означает , аналогично, самая правая черная вертикальная линия на каждом рисунке означает .
Переменная
— это в суффиксном массиве на промежутке . Переменная — это в суффиксном массиве на промежутке . Серым цветом выделен в суффиксном массиве на рассматриваемом промежутке.Иллюстраци возможных случаев при
:Иллюстрации возможных случаев при
:Псевдокод
Массивы и строки нумеруются с нуля.
Сравнения
означают лексикографическое сравнение двух строк по их первым символам.Сравнения
при применении к строкам означают полное лексикографическое сравнение строк.Функция
ищет количество совпадений символов строк и начиная с позиции .— длина строки , — длина строки .
В алгоритме используются переменные, введенные выше в разделе "более быстрый поиск".
Поиск левой границы ответов _ .
function find_answer_left(p: String, s: String): int l = lcp(p, s[array[0]]) r = lcp(p, s[array[n - 1]]) if (l == w or p < s[array[0]]) answer_left = 0 else if (p > s[array[n - 1]) answer_left = n else L = 0 R = n - 1 while (R - L > 1) do M = (L + R) / 2 m_l = lcp(array[L], array[M]) m_r = lcp(array[M], array[R]) if (lr) if (m_l l) m = l + common(l, s[array[M]], p) else m = m_l else if (m_r r) m = r + common(r, s[array[M]], p) else m = m_r if (m == w || p s[array[M]]){ R = M r = m else L = M l = m answer_left = R
См. также
Источники информации
- Habrahabr — Суффиксный массив — удобная замена суффиксного дерева
- U. Manber and G. Mayers. — "Suffix arrays: A new method for on-line string searches"