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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Более быстрый поиск)
(Более быстрый поиск)
Строка 183: Строка 183:
  
 
Существует более быстрый алгоритм поиска образца в строке. Для этого используется <tex> lcp </tex> (longest common prefix). <br>
 
Существует более быстрый алгоритм поиска образца в строке. Для этого используется <tex> lcp </tex> (longest common prefix). <br>
Пусть при построении суффиксного массива для строки <tex> s </tex> был построен еще и массив <tex> LCP </tex>, <tex> i </tex>-ой позиции которого соответствует наибольший общий префикс <tex> i </tex>-ого и <tex> (i+1) </tex>-ого суффиксов. Все поиски <tex> lcp </tex> между парой суффиксов строки <tex> s </tex> производятся при помощи него. <br>
+
Пусть при построении суффиксного массива для строки <tex> s </tex> был построен еще и массив <tex> LCP </tex>, <tex> i </tex>-ой позиции которого соответствует наибольший общий префикс <tex> i </tex>-ого и <tex> (i+1) </tex>-ого суффиксов. Все поиски <tex> lcp </tex> между парами суффиксов строки <tex> s </tex> производятся при помощи него. <br>
Пусть <tex> L_p </tex> - левая граница текущего диапазона (изначально равна 0), <tex> R_p </tex> - правая граница текущего диапазона (изначально равна <tex> |S| - 1 </tex>), а <tex> M = (L + R) / 2 </tex> <br>
+
Пусть <tex> L_p </tex> и <tex> R_p </tex> - левая и правая границы диапазона ответов. В пределах этого диапазона в суффиксном массиве <tex> array </tex> лежат суффиксы, префиксы которых полностью совпадают с образцом <tex> p </tex>.
 +
Пусть <tex> L </tex> - левая граница диапазона поиска (изначально равна 0), <tex> R </tex> - правая граница диапазона поиска (изначально равна <tex> |S| - 1 </tex>), а <tex> M = (L + R) / 2 </tex>. <br>
 
Пусть <tex> l = lcp(array[L], p) </tex>, а <tex> r = lcp(array[R], p) </tex>. В самом начале просто посчитаем <tex> l </tex> и <tex> r </tex> за линейное время, а во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить за <tex> O(1) </tex>. <br>
 
Пусть <tex> l = lcp(array[L], p) </tex>, а <tex> r = lcp(array[R], p) </tex>. В самом начале просто посчитаем <tex> l </tex> и <tex> r </tex> за линейное время, а во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить за <tex> O(1) </tex>. <br>
Пусть <tex> m_l = lcp(array[L], array[M]) </tex>, а <tex> r_l = lcp(array[M],array[R]) </tex>. Подсчет <tex> m_l </tex> и <tex> m_r </tex> можно производить за <tex> O(1) </tex>, если применять [[Алгоритм Фарака-Колтона и Бендера|Алгоритм Фарака-Колтона и Бендера]].
+
Пусть <tex> m_l = lcp(array[L], array[M]) </tex>, а <tex> r_l = lcp(array[M],array[R]) </tex>. Подсчет <tex> m_l </tex> и <tex> m_r </tex> можно производить за <tex> O(1) </tex>, если применять [[Алгоритм Фарака-Колтона и Бендера|Алгоритм Фарака-Колтона и Бендера]]. Любая пара суффиксов из диапазона <tex> [L, M] </tex> имеет хотя бы <tex> m_l </tex> совпадений в префиксах (Аналогично для диапазона <tex> [M, R] </tex>). <br>
 +
Рассмотрим поиск левой границы диапазона ответов <tex> L_p </tex>(поиск правой границы производится аналогично). <br>
 +
Сразу проверим образец с краями исходного диапазона поиска. Если образец лексикографически больше последнего суффикса <tex> array </tex> или меньше первого суффикса, то образец не встречается в строке вовсе и поиск можно прекратить. <br>
 +
Границы диапазона ответов ищутся при помощи бинарного поиска. На каждом шаге поиска нам надо определять на каком отрезке (<tex> [L, M] </tex> или <tex> [M, L] </tex>) надо продолжать поиск <tex> L_p </tex>. Сравним <tex> m_l </tex> и <tex> m_r </tex>. Если <tex> m_l > m_r </tex>, то возможно одно из двух: <br>
 +
1) <tex> m_l > l  </tex>. Это означает, что каждый суффикс из диапазона <tex> [L, M] </tex> не подходит для <tex> L_p </tex>, поэтому продолжим поиск в диапазоне <tex> [M, R] </tex>. <tex> l </tex> при этом не меняется, а <tex> L = M </tex>.
 +
2) <tex> m_l < l </tex>. Это означает, то первые <tex> l </tex> символов образца и суффикса <tex> array[M] </tex> совпали.
  
 
==Литература==
 
==Литература==
 
* http://habrahabr.ru/blogs/algorithm/115346/
 
* http://habrahabr.ru/blogs/algorithm/115346/

Версия 05:33, 16 мая 2011

Рассмотрим такую задачу: у нас есть образец [math] p [/math], строка [math] s [/math], суффиксный массив [math] array [/math], построенный для строки [math] s [/math]. Необходимо найти все вхождения образца [math] p [/math] в строку [math] s [/math].

Для наглядности рассмотрим такой пример: образец iss , строка mississippi .
Вот суффиксный массив для данной строки:

# суффикс номер суффикса
1 i 11
2 ippi 8
3 issippi 5
4 ississippi 2
5 mississippi 1
6 pi 10
7 ppi 9
8 sippi 7
9 sissippi 4
10 ssippi 6
11 ssissippi 3

Способы поиска

Простейший поиск подстроки

Простейший способ узнать, встречается ли образец в тексте, используя суффиксный массив, это взять первый символ образца и бинарным поиском по суффиксному массиву (массив у нас отсортирован) найти диапазон с суффиксами, начинающимися на такую же букву. Так как все элементы в полученном диапазоне отсортированы, а первые символы одинаковые, то оставшиеся после отбрасывания первого символа суффиксы тоже отсортированы. А значит, можно повторять процедуру сужения диапазона поиска уже по второму, затем третьему и так далее символу образца до получения либо пустого диапазона, либо успешного нахождения всех символов образца. Бинарный поиск работает за время равное [math] O(log|s|) [/math], а сравнение суффикса с образцом не может превышать длины образца. Таким образом время работы алгоритмы [math] O(|p|log|s|)[/math].
В примере поиск будет выглядеть так:

образец iss iss iss
i i i
ippi ippi ippi
issippi issippi issippi
ississippi ississippi ississippi
mississippi mississippi mississippi
pi pi pi
ppi ppi ppi
sippi sippi sippi
sissippi sissippi sissippi
ssippi ssippi ssippi
ssissippi ssissippi ssissippi

В примере показано, какие суффиксы на каждом шаге алгоритма удовлетворяют нашему образцу: на [math] i [/math]-ом шаге суффикс является подходящим, если [math] i [/math] его первых символов совпадают с [math] i [/math] первыми символами образца. Каждый шаг к рассмотрению добавляется лишь один новый символ образца. В графе "образец" розовым цветом выделен префикс образца, который ищется на данном шаге, а под образцом располагаются суффиксы строки, префиксы которых выделены розовым цветом, если на данном шаге суффикс подходит.
Как видно из примера образцу удовлетворяют суффиксы 3 и 4, начинающиеся на 5 и 2 позициях в строке соответственно(позицию можно посмотреть в таблице повыше).

Псевдокод

Поиск диапазона

/*p - образец
n - длина образца
left - левая граница диапазона // изначально равна единице
right - правая граница диапазона // изначально равна длине строки
lh - вспомогательная переменная для определения левой границы диапазона  
rg - вспомогательная переменная для определения правой границы диапазона
find - функция уточнения диапазона
элементы строк и массивов нумеруются с единицы*/
for i = 1 to n {
  lh = n + 1
  rh = 0
  find(left, right, i)
  left = lh
  right = rh
}
if (left != 0 && right != n + 1) { // если диапазон не пуст
  yield left // вывод левой границы диапазона 
  yield right // вывод правой границы диапазона
} else
 yield "No matches" // вывод информации об отсутствии вхождений

Бинарный поиск для уточнения диапазона - функция find(l, r, k)

/*l - левая граница диапазона при поиске
r - правая граница диапазона при поиске
k - номер символа образца, с которым происходит проверка на данном шаге
s - строка
length - длина строки
array - суффиксный массив
x - индекс, стоящий по середине между l и r*/
if (l > r)
  return
x = (l + r) / 2
if (array[x] + k - 1 <= length){
  if (s[array[x] + k - 1] == p[k]){
    if (x < lh)
      lh = x
    if (x > rh)
      rh = x
    find(l, x - 1, k)
    find(x + 1, r, k)
  } else { 
  if (s[array[x] + k - 1] > p[k]) {
    find(l, x - 1, k)
  } else {
  if (s[array[x] + k - 1] < p[k]) {
    find(x + 1, r, k)
  }
} else { 
  find(l, x - 1, k)
  find(x + 1, r, k)
}

Более быстрый поиск

Существует более быстрый алгоритм поиска образца в строке. Для этого используется [math] lcp [/math] (longest common prefix).
Пусть при построении суффиксного массива для строки [math] s [/math] был построен еще и массив [math] LCP [/math], [math] i [/math]-ой позиции которого соответствует наибольший общий префикс [math] i [/math]-ого и [math] (i+1) [/math]-ого суффиксов. Все поиски [math] lcp [/math] между парами суффиксов строки [math] s [/math] производятся при помощи него.
Пусть [math] L_p [/math] и [math] R_p [/math] - левая и правая границы диапазона ответов. В пределах этого диапазона в суффиксном массиве [math] array [/math] лежат суффиксы, префиксы которых полностью совпадают с образцом [math] p [/math]. Пусть [math] L [/math] - левая граница диапазона поиска (изначально равна 0), [math] R [/math] - правая граница диапазона поиска (изначально равна [math] |S| - 1 [/math]), а [math] M = (L + R) / 2 [/math].
Пусть [math] l = lcp(array[L], p) [/math], а [math] r = lcp(array[R], p) [/math]. В самом начале просто посчитаем [math] l [/math] и [math] r [/math] за линейное время, а во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить за [math] O(1) [/math].
Пусть [math] m_l = lcp(array[L], array[M]) [/math], а [math] r_l = lcp(array[M],array[R]) [/math]. Подсчет [math] m_l [/math] и [math] m_r [/math] можно производить за [math] O(1) [/math], если применять Алгоритм Фарака-Колтона и Бендера. Любая пара суффиксов из диапазона [math] [L, M] [/math] имеет хотя бы [math] m_l [/math] совпадений в префиксах (Аналогично для диапазона [math] [M, R] [/math]).
Рассмотрим поиск левой границы диапазона ответов [math] L_p [/math](поиск правой границы производится аналогично).
Сразу проверим образец с краями исходного диапазона поиска. Если образец лексикографически больше последнего суффикса [math] array [/math] или меньше первого суффикса, то образец не встречается в строке вовсе и поиск можно прекратить.
Границы диапазона ответов ищутся при помощи бинарного поиска. На каждом шаге поиска нам надо определять на каком отрезке ([math] [L, M] [/math] или [math] [M, L] [/math]) надо продолжать поиск [math] L_p [/math]. Сравним [math] m_l [/math] и [math] m_r [/math]. Если [math] m_l \gt m_r [/math], то возможно одно из двух:
1) [math] m_l \gt l [/math]. Это означает, что каждый суффикс из диапазона [math] [L, M] [/math] не подходит для [math] L_p [/math], поэтому продолжим поиск в диапазоне [math] [M, R] [/math]. [math] l [/math] при этом не меняется, а [math] L = M [/math]. 2) [math] m_l \lt l [/math]. Это означает, то первые [math] l [/math] символов образца и суффикса [math] array[M] [/math] совпали.

Литература