Суффиксный массив

Суффиксный массив — лексикографически отсортированный массив всех суффиксов строки. Эта структура данных была разработана Джином Майерсом и Уди Манбером как более экономная альтернатива суффиксному дереву с точки зрения необходимой памяти. Она часто применяется там, где необходим быстрый поиск подстрок, например в преобразовании Барроуза — Уилера (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» встречается на первом и восьмом символе в исходном слове.

Алгоритмы

• Алгоритм Касаи построения массива наибольших общих префиксов.

См. также

• Суффиксное дерево

Ссылки

• Суффиксный массив. Алгоритм построения и применения
• Суффиксный массив и BWT
• Визуализатор алгоритма (требуется Java)
• Дискретная математика: алгоритмы. Суффиксные массивы
• Реализация суффиксного массива на Java

Литература

• Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — 2-е изд. — СПб.: «Невский Диалект», 2003.