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

Суффиксный массив (англ. suffix array) — это структура данных, представляющая собой отсортированный в лексикографическом порядке массив всех суффиксов заданной строки. Каждый элемент массива является целым числом — начальной позицией суффикса в исходной строке (индексация обычно начинается с нуля). Суффиксный массив является компактной альтернативой суффиксному дереву и широко применяется в задачах обработки строк, биоинформатики и информационного поиска.

Определение и формальное описание

Пусть дана строка \( S \) длины \( n \), состоящая из символов некоторого алфавита. Суффиксом строки \( S \), начинающимся в позиции \( i \) (\( 0 \le i < n \)), называется подстрока \( S[i..n-1] \). Суффиксный массив \( SA \) — это перестановка чисел от \( 0 \) до \( n-1 \) такая, что для любых \( i < j \) выполняется условие: суффикс, начинающийся в позиции \( SA[i] \), лексикографически меньше суффикса, начинающегося в позиции \( SA[j] \). Иными словами, \( SA \) содержит номера начальных позиций всех суффиксов строки, упорядоченных по алфавиту.

Для удобства обработки к строке часто добавляют специальный терминальный символ (например, $), который считается меньше любого другого символа алфавита. Это гарантирует, что ни один суффикс не является префиксом другого, и упрощает построение.

История

Концепция суффиксного массива была впервые предложена Уди Манбером и Джином Майерсом в 1990 году как более экономная по памяти альтернатива суффиксному дереву. Суффиксное дерево, хотя и обладает хорошими теоретическими свойствами, требовало значительного объёма памяти (порядка 10–20 байт на символ), что ограничивало его применение на больших строках. Суффиксный массив, напротив, занимает всего \( 4n \) байт для 32-битных индексов (или \( 8n \) для 64-битных). В 1990-е годы были разработаны первые эффективные алгоритмы построения, в том числе алгоритм Карккайнена–Сандерса (2003), работающий за линейное время.

Построение

Существует несколько основных подходов к построению суффиксного массива:

Наивный алгоритм

Наивный способ заключается в генерации всех суффиксов, их сортировке с помощью стандартной функции сравнения строк. Время работы составляет \( O(n^2 \log n) \) из-за затрат на сравнение строк в худшем случае, что неприемлемо для длинных строк.

Алгоритмы на основе сортировки поразрядной

Более эффективные методы используют идею сортировки суффиксов по первым символам, затем по первым двум символам и т.д. (сортировка с удвоением). Классический алгоритм Манбера–Майерса (1993) работает за \( O(n \log n) \). Он использует сортировку подсчётом для каждого шага удвоения длины сравниваемых префиксов.

Линейные алгоритмы

В 2003 году Юха Карккайнен и Питер Сандерс предложили алгоритм, работающий за \( O(n) \) времени. Он рекурсивно строит суффиксный массив для строки, состоящей из символов, стоящих на позициях, не кратных трём, а затем объединяет результаты. Другие линейные алгоритмы: алгоритм Ким–Сим–Парк (2003) и алгоритм Ко–Алуру (2003). На практике для коротких строк (до нескольких миллионов символов) алгоритм за \( O(n \log n) \) часто оказывается быстрее из-за меньших констант.

Алгоритм с использованием суффиксного дерева

Суффиксный массив можно получить обходом суффиксного дерева в глубину, если дерево уже построено. Однако это требует сначала построить дерево, что может быть затратно по памяти.

Сопутствующие структуры

Для эффективного решения задач суффиксный массив часто дополняют другими массивами:

Массив LCP (Longest Common Prefix)

Массив LCP длины \( n-1 \) хранит длины наибольших общих префиксов для соседних в отсортированном порядке суффиксов. Формально: \( LCP[i] = \text{lcp}(S[SA[i]..], S[SA[i+1]..]) \). Массив LCP позволяет быстро отвечать на запросы о поиске подстрок, подсчёте числа различных подстрок и поиске наибольшей повторяющейся подстроки.

Массив рангов

Массив рангов \( Rank \) — это обращение суффиксного массива: \( Rank[SA[i]] = i \). Он позволяет за \( O(1) \) узнать порядковый номер любого суффикса в отсортированном списке.

Применение

Суффиксный массив используется в следующих задачах:

Поиск подстроки

Поиск всех вхождений заданного шаблона \( P \) в строку \( S \) выполняется за \( O(|P| \log n) \) с помощью бинарного поиска по суффиксному массиву. С использованием массива LCP время можно сократить до \( O(|P| + \log n) \).

Вычисление наибольшей общей подстроки

Для двух строк \( S_1 \) и \( S_2 \) строится общий суффиксный массив для строки \( S_1 \$ S_2 \# \). Затем с помощью массива LCP находится максимальное значение LCP между суффиксами, принадлежащими разным исходным строкам.

Подсчёт числа различных подстрок

Количество различных подстрок строки \( S \) равно \( \frac{n(n+1)}{2} - \sum_{i=0}^{n-2} LCP[i] \). Это следует из того, что каждый LCP показывает, сколько подстрок уже учтено предыдущим суффиксом.

Поиск наибольшей повторяющейся подстроки

Максимальное значение в массиве LCP соответствует длине наибольшей подстроки, которая встречается в строке не менее двух раз.

Сжатие данных

Суффиксные массивы используются в алгоритмах сжатия, таких как BWT (Burrows–Wheeler transform), который лежит в основе архиватора bzip2.

Биоинформатика

В биоинформатике суффиксные массивы применяются для выравнивания коротких прочтений ДНК на референсный геном (например, в программах Bowtie и BWA). Они позволяют быстро находить позиции, где прочтение совпадает с геномом с учётом ошибок.

Пример

Рассмотрим строку \( S = "banana" \) (длина \( n = 6 \)). Суффиксы:

• 0: "banana"
• 1: "anana"
• 2: "nana"
• 3: "ana"
• 4: "na"
• 5: "a"

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

• "a" (позиция 5)
• "ana" (позиция 3)
• "anana" (позиция 1)
• "banana" (позиция 0)
• "na" (позиция 4)
• "nana" (позиция 2)

Суффиксный массив: \( SA = [5, 3, 1, 0, 4, 2] \).

Массив LCP для соседних суффиксов:

• LCP("a", "ana") = 1 (общий префикс "a")
• LCP("ana", "anana") = 3 ("ana")
• LCP("anana", "banana") = 0
• LCP("banana", "na") = 0
• LCP("na", "nana") = 2 ("na")

Массив LCP: \( [1, 3, 0, 0, 2] \).

Сравнение с суффиксным деревом

Суффиксное дерево занимает больше памяти (обычно 10–20 байт на символ), но позволяет отвечать на некоторые запросы (например, поиск подстроки) за \( O(|P|) \) без дополнительных структур. Суффиксный массив с массивом LCP занимает меньше памяти (4–8 байт на символ) и может быть построен за линейное время. На практике суффиксный массив часто предпочитают из-за лучшей локальности кэша и меньшего потребления памяти.

Реализации

Суффиксные массивы реализованы во многих библиотеках и языках программирования. В языке C++ стандартная библиотека не содержит готовой реализации, но существуют библиотеки, такие как sdsl-lite (Succinct Data Structure Library). В Python для работы с суффиксными массивами можно использовать библиотеку suffixarray или реализовать алгоритм самостоятельно. В биоинформатике распространены инструменты samtools и bowtie2, использующие суффиксные массивы.

Источники

• Manber, U., & Myers, G. (1993). Suffix arrays: a new method for on-line string searches. SIAM Journal on Computing, 22(5), 935–948.
• Kärkkäinen, J., & Sanders, P. (2003). Simple linear work suffix array construction. Proceedings of the 30th International Colloquium on Automata, Languages and Programming.
• Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press.
• Crochemore, M., Hancart, C., & Lecroq, T. (2007). Algorithms on Strings. Cambridge University Press.