Patarakin: 1 версия импортирована

2022-10-19T07:30:42Z

1 версия импортирована

← Предыдущая версия		Версия от 10:30, 19 октября 2022
(нет различий)

ru_wikipedia>Ok822: Исправлена ошибка в структуре предложения

2022-04-05T16:39:14Z

Исправлена ошибка в структуре предложения

Новая страница

'''Суффиксный массив''' — [[Лексикографический порядок|лексикографически]] [[Алгоритм сортировки|отсортированный]] [[Массив (программирование)|массив]] всех [[Суффикс (информатика)|суффиксов]] [[Строковый тип|строки]]. Эта [[структура данных]] была разработана [[Майерс, Юджин|Юджином Майерсом]] и [[Уди Манбер]]ом как более экономная альтернатива [[суффиксное дерево|суффиксному дереву]] с точки зрения необходимой памяти. Она часто применяется там, где необходим быстрый поиск подстрок, например в [[Преобразование Барроуза — Уилера|преобразовании Барроуза — Уилера]] (BWT), а также в качестве структуры данных в [[поисковый индекс|поисковом индексе]].

== Пример ==

Рассмотрим строку «abracadabra» длиной 11 символов.

a b r a c a d a b r a
1 2 3 4 5 6 7 8 9 10 11

Отсортированный список её суффиксов:

a
abra
abracadabra
acadabra
adabra
bra
bracadabra
cadabra
dabra
ra
racadabra

Суффиксный массив этой строки — {11,8,1,4,6,9,2,5,7,10,3}, потому что суффикс «a» начинается с 11-го знака, суффикс «abra» — с 8-го, и так далее, вплоть до последнего суффикса «racadabra», который начинается с третьего символа исходного слова.

Теперь с помощью этого массива можно легко найти все подстроки. Например, если нужно найти подстроку «ab», достаточно найти все суффиксы, которые начинаются на «ab». За счёт сортировки по алфавиту они находятся рядом друг с другом. Используя [[бинарный поиск]], мы находим 2-й и 3-й суффиксы «abra» и «abracadabra», которым соответствуют 2-й и 3-й элемент суффиксного массива (8 и 1). Это означает, что искомая подстрока «ab» встречается на первом и восьмом символе в исходном слове.

== Построение ==
Суффиксный массив можно построить как с помощью суффиксного дерева, так и без него, дополнив строку до циклической длины степени двойки, и применив к нему конкретный алгоритм.

=== Через суффиксное дерево ===
{|
|
# Строим суффиксное дерево для строки T$. Где T — текст.
# В этом суффиксном дереве запускаем поиск в глубину с приоритетом выбора лексиграфически минимальных рёбер.
# Во время поиска считаем, что $ (сентинел) лексикографически наименьший символ.
# Приход в лист достижение некоторого ещё не рассмотренного в данный момент лексикографически наименьшего суффикса, значение в листе которого, начальный индекс в, нужно записать в текущую ячейку суффиксного массива.
# Так получается суффиксный массив для всего текста.
|}

Сложность построения — <math>O(|T|)</math>, линия включает в себя построение суффиксного дерева и обход в глубину.

== Поиск ==
Поиск в суффиксном массиве можно осуществить через бинарный поиск. Его худшая оценка <math>O(n\log{m})</math>. Но можно ускорить до <math>O(n + \log_2{m})</math>.

=== Наивный бинарный поиск ===
{|
|
* Идея поиска в том, что если образец встречается в тексте, то все суффиксы, начинающиеся с <math>P</math> в суффиксном массиве <math>Pos</math> будет располагаться рядом.
* Запускаем двоичный поиск <math>P</math> в суффиксном массиве <math>Pos</math> и находим такой наименьший индекс <math>i</math>: <math>Pos(i-1)</math> не начинается с <math>P</math> и наибольший индекс <math>i'</math>: <math>Pos(i'+1)</math> тоже не начинается с <math>P</math>.
* Тогда образец входит в позициях <math>Pos(i)</math> до <math>Pos(i')</math>.
* Если существует много префиксов паттерна, то оценка работы падает до <math>O(n\log{m})</math>.
|}

=== Простое ускорение ===
{|
|
* <math>L</math>, <math>R</math> — границы интервала поиска. На начале <math>L = 1</math>, <math>R = m</math>.
* Запоминаем длину префиксов <math>Pos(L)</math>, <math>Pos(R)</math>, совпадающих с префиксом <math>P: l, r</math>.
* <math>mlr = min(l,r)</math>.
* При очередном сравнении в позиции <math>M = \frac{L + R}{2}</math> начинаем обрабатывать символы не с первой позиции, а с <math>mlr(l,r) + 1</math>.
* Обычно время работы <math>O(n + \log{m})</math>, но худшее время работы всё ещё <math>O(n\log{m})</math>.
|}

=== Ускорение через LCP ===
Наибольший общий префикс ({{lang-en|Largest Common Prefix}}) — для двух строк <math>S_1</math>, <math>S_2</math> <math>LCP(S_1, S_2)</math> — длина наибольшего совпадающего префикса.

В этом алгоритме будем считать, что <math>LCP</math> для любых двух суффиксов вычисляется за <math>O(1)</math>. Функция вычисляется на этапе препроцессинга при построении дерева. Также верно утверждение: <math>LCP(i, j) = min(LCP(k, k + 1)), i\leq k < j</math>.

Благодаря этой функции можно оптимизировать бинарный поиск по суффиксному массиву.

'''Лемма''': Если на левой и правой границе (<math>L</math>, <math>R</math> соответственно индексы суффиксного массива) совпадают первые <math>k</math> символов суффикса, то столько же символов будет совпадать для всех суффиксов на отрезке <math>[L,R]</math>.

{|
|
# <math>L = 1</math>, <math>R = |T|</math>, <math>l = LCP(P, L)</math>, <math>r = LCP(P, R)</math>. Дальше возможны следующие случаи
## <math>l = r</math>.
### Сравниваем суффикс в <math>M = \frac{L + R}{2}</math> с паттерном с позиции <math>l + 1</math>.
### Суффикс лексикографически больше или равен <math>P</math> и на <math>i</math> позиции в суффиксе произошло несовпадение (если произошло лексикографическое совпадение <math>M</math> и <math>P</math>, то считаем <math>i</math> равным <math>|P|+1</math>), то меняем границы поиска: <math>L = M, R = R, l = i - 1</math>.
### Иначе меняем границы так: <math>L = L, R = M, r = i - 1</math>.
## <math>l > r</math>. Проверяем <math>LCP(L, M), M = \frac{L+R}{2}</math>.
### <math>LCP(L, M) > l</math>. В таком случае после позиции <math>l</math> в суффиксе на позиции <math>M</math> следует некоторое количество тех же самых символов, что и в <math>L</math>, которые не совпадают с паттерном (если бы совпадали, то <math>l</math> было бы больше). Значит, нужно изменить границы следующим образом: <math>L = M,R = R, l = l</math>.
### <math>LCP(L, M) < l</math>, это значит, что после позиции <math>LCP(L, M)</math> в суффиксе на позиции <math>M</math> следует несовпадение с некоторыми символами префикса <math>L</math>, причём в <math>L</math> содержится большая часть совпадения с паттерном — значит в отрезке <math>[M, R]</math> точно не найдется вхождений паттерна. Изменить границы нужно следующим образом: <math>L = L, R = M, r = LCP(L, M)</math>.
### <math>LCP(L,M)=l</math>, это значит, что на отрезке <math>[L,M]</math> во всех суффиксах совпадают первые <math>l</math> символов, и нельзя сразу сказать, в какой подотрезок нужно пойти. Для разрешения этого необходимо сравнить с паттерном <math>P</math> следующие за позицией <math>l</math> символы в суффиксе <math>M</math>. Если <math>M</math> лексикографически меньше или равно <math>P</math> и на <math>i</math>-ой позиции произошло несовпадение (если произошло лексикографическое совпадение <math>M</math> и <math>P</math>, то считаем <math>i</math> равным <math>|P|+1</math>), то изменяем границы так: <math>L=M</math>, <math>R=R</math>, <math>l = i - 1</math>; иначе (<math>M</math> лексикографически больше): <math>R=M</math>, <math>L=L</math>,<math>r = i - 1</math>.
## <math>l < r</math>. Проверяем <math>LCP(R, M), M = \frac{L+R}{2}</math> и сравниваем с <math>r</math> как на прошлом шаге, но <math>L</math> меняем на <math>R</math> и <math>l</math> на <math>r</math>.
# Алгоритм работает, пока <math>l</math> и <math>r</math> не станут равными <math>|P|</math>. Это значит, что есть отрезок совпадения. Если не выполняется инвариант <math>L < P < R</math>, то паттерна как подстроки в тексте нет.
|}

Такое сверхускорение даёт время <math>O(|P|+\log_2{|T|})</math>, так как выполняется <math>\log_2{|T|}</math> итераций по суффиксному массиву.

== Связанные алгоритмы ==
* [[Алгоритм Касаи]] построения массива наибольших общих префиксов.

== См. также ==
* [[Суффиксное дерево]]

== Ссылки ==
* [http://e-maxx.ru/algo/suffix_array Суффиксный массив. Алгоритм построения и применения]
* [http://compression.ru/download/articles/bwt/khmelev_2003_bwt.html#tth_sEc3 Суффиксный массив и BWT]
* [https://web.archive.org/web/20100820195150/http://rain.ifmo.ru/cat/view.php/vis/strings/suffix-arrays-2005 Визуализатор алгоритма] (требуется [[Java]])
* [https://web.archive.org/web/20071223021534/http://rain.ifmo.ru/cat/view.php/theory/unsorted/suffix-arrays-2005 Дискретная математика: алгоритмы. Суффиксные массивы]
* [http://sites.google.com/site/indy256/algo/suffix_array Реализация суффиксного массива на Java]

== Литература ==
* {{книга
|автор = {{nobr|Гасфилд Д.}}
|заглавие = Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология
|ссылка =
|ответственный = Пер. с англ. И. В. Романовского
|издание = 2-е изд
|место = СПб.
|издательство = Невский Диалект
|год = 2003
|страниц = 654
}}
* {{книга
|автор = {{nobr|Смит Б.}}
|заглавие = Методы и алгоритмы вычислений на строках
|оригинал = Computing Patterns in Strings
|ссылка =
|ответственный =
|издание =
|место = М.
|издательство = Вильямс
|год = 2006
|страниц = 496
|isbn = 5-8459-1081-1, 0-201-39839-7
}}
{{Строки}}
[[Категория:Строковые алгоритмы]]
[[Категория:Поиск подстроки]]
[[Категория:Структуры данных]]

Суффиксный массив - История изменений

Patarakin: 1 версия импортирована

ru_wikipedia>Ok822: Исправлена ошибка в структуре предложения