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