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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Алгоритмы[править | править исходный текст]

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]

Литература[править | править исходный текст]

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