Сжатый суффиксный массив
Ключевые слова и синонимы
Создание сжатого полнотекстового индекса; сжатое суффиксное дерево
Постановка задачи
Пусть дана текстовая строка [math]\displaystyle{ T = t_1 t_2 ... t_n }[/math] над алфавитом [math]\displaystyle{ \Sigma }[/math] размера [math]\displaystyle{ \sigma }[/math]. Задача создания сжатого полнотекстового индекса (compressed full-text indexing, CFTI) заключается в построении экономичной по объему памяти структуры данных, способной эффективно моделировать функциональность полнотекстового индекса, построенного на основе T.
Простым примером полнотекстового индекса является суффиксный массив A[1, n], содержащий перестановку интервала [1, n], такую, что T[A[i], n] < T[A[i + 1], n] для всех [math]\displaystyle{ 1 \le i \lt n }[/math], где отношение "<" между строками обозначает лексикографический порядок. Используя суффиксный массив, можно найти вхождения заданного шаблона [math]\displaystyle{ P = p_1 p_2 ... p_m }[/math] в строке T с помощью двух бинарных поисков за время O(m log n).
Формулировка связанной с суффиксными массивами задачи CFTI проста: необходимо найти экономичную по объему памяти структуру данных, поддерживающую эффективное извлечение значения A[i] для любого i. Такое решение и называется сжатым суффиксным массивом. Обычно сжатые суффиксные массивы также поддерживают получение обратного значения [math]\displaystyle{ A^{-1} [j] = i }[/math] для любого заданного j.
Если сжатый полнотекстовый индекс функционирует без текста и содержит достаточно информации для получения любой подстроки T, такой индекс называется самоиндексом, так как его можно использовать в качестве представления T. См. статью «Индексирование сжатого текста» с изложением альтернативного подхода к самоиндексированию, а также работу [9] с исчерпывающим обзором по данной теме.
Задача CFTI может быть сформулирована для любого полнотекстового индекса при условии, что набор операций, которые должна поддерживать структура данных, строго определен. Например, сжатое суффиксное дерево должно воспроизводить все операции классических суффиксных деревьев.
Классические полнотекстовые индексы занимают [math]\displaystyle{ O(n \; log \; n) }[/math] бит, обычно с поправкой на довольно большой константный коэффициент. Типичные цели задачи CFTI могут быть охарактеризованы степенью амбициозности; например, необходимо найти структуру, удовлетворяющую одному из следующих требований к объему памяти:
1) пропорционально размеру текста, т. е. [math]\displaystyle{ O(n \; log \; \sigma) }[/math] бит;
2) асимптотически оптимально относительно размера текста, т. е. [math]\displaystyle{ n \; log \; \sigma (1 + o(1)) }[/math] бит;
3) пропорционально размеру сжатого текста, т. е. [math]\displaystyle{ O(nH_k) }[/math] бит, где [math]\displaystyle{ O(H_k) }[/math] — это (эмпирическая) энтропия k-го порядка строки T //где [math]\displaystyle{ H_k }[/math] — минимальное среднее количество бит, необходимых для кодирования одного символа с помощью любого алгоритма сжатия, который фиксирует кодовое слово на основе контекста k-го символа, следующего за кодируемым символом. В [6] дано более формальное определение//;
или даже 4) асимптотически оптимально относительно размера сжатого текста, т. е. [math]\displaystyle{ O(nH_k) + o(n \; log \; \sigma) }[/math] бит.
Основные результаты
Первое решение проблемы предложили Гросси и Виттер [3], использовавшие свойство регулярности суффиксного массива посредством [math]\displaystyle{ \Psi }[/math]-функции:
Определение 1. Пусть дан суффиксный массив A[1, n]. Функция [math]\displaystyle{ \Psi : [1, n] \to [1, n] }[/math] определена таким образом, что для всех [math]\displaystyle{ 1 \le i \lt n }[/math] выполняется соотношение [math]\displaystyle{ A[\Psi(i)] = A[i] + 1 }[/math]. Исключением является A[1] = n, в этом случае имеет место [math]\displaystyle{ A[\Psi(1)] = 1 }[/math], так что функция [math]\displaystyle{ \Psi }[/math] является перестановкой.
Гросси и Виттер используют иерархическую декомпозицию массива А, основанную на [math]\displaystyle{ \Psi }[/math] //далее приводится описание, близкое к изложенному в [9]//. рассмотрим первый уровень этой иерархической декомпозиции. Пусть [math]\displaystyle{ A_0 = A }[/math] – исходный суффиксный массив. Битовый вектор [math]\displaystyle{ B^0 [1, n] }[/math] определен таким образом, что [math]\displaystyle{ B^0 [i] = 1 }[/math] в том и только том случае, если A[i] четно. Кроме того, пусть [math]\displaystyle{ \Psi_0 [1, \lceil n/2 \rceil ] }[/math] содержит последовательность значений [math]\displaystyle{ \Psi(i) }[/math] для тех аргументов i, для которых [math]\displaystyle{ B^0[i] = 0 }[/math]. Наконец, пусть [math]\displaystyle{ A_1 [1, \lfloor n/2 \rfloor ] }[/math] будет подпоследовательностью [math]\displaystyle{ A_0 [1, n] }[/math], образованной четными значениями [math]\displaystyle{ A_0[i] }[/math], деленными на 2.
Тогда [math]\displaystyle{ A = A_0 }[/math] может быть представлен с использованием только [math]\displaystyle{ \Psi_0, B^0 }[/math] и [math]\displaystyle{ A_1 }[/math]. Чтобы извлечь A[i], сначала проверим, выполняется ли [math]\displaystyle{ B^0[i] = 1 }[/math]. Если это так, то A[i] было разделено на 2 где-то в [math]\displaystyle{ A_1 }[/math]. Точное положение зависит от того, сколько единиц встречается в [math]\displaystyle{ B^0 }[/math] до позиции i, обозначенной как [math]\displaystyle{ rank(B^0, i) }[/math], т. е. [math]\displaystyle{ A[i] = 2 \cdot A_1[rank_1(B^0, i)] }[/math]. Если B°[i] = 0, то A[i] является нечетным и не представлен в [math]\displaystyle{ A_1 }[/math]. Однако в этом случае элемент [math]\displaystyle{ A[i] + 1 = A[\Psi(i)] }[/math] должен быть четным и, таким образом, должен быть представлен в [math]\displaystyle{ A_1 }[/math]. Так как [math]\displaystyle{ \Psi_0 }[/math] содержит только значения [math]\displaystyle{ \Psi }[/math], у которых [math]\displaystyle{ B^0[i] = 0 }[/math], из этого следует, что [math]\displaystyle{ A[\Psi(i)] = A[\Psi_0[rank_0(B^0, i)]] }[/math]. После вычисления [math]\displaystyle{ A[\Psi(i)] }[/math] (для четных [math]\displaystyle{ \Psi(i) }[/math]) элементарно получаем [math]\displaystyle{ A[i] = A[\Psi(i)] - 1 }[/math].
Эта идея может быть использована рекурсивно. Вместо того, чтобы представлять [math]\displaystyle{ A_1 }[/math], замените его на [math]\displaystyle{ B^2 }[/math], [math]\displaystyle{ \Psi_2 }[/math] и [math]\displaystyle{ A_2 }[/math]. Продолжайте процесс до тех пор, пока [math]\displaystyle{ A_h }[/math] не станет достаточно мал, чтобы быть представленным в явном виде. Сложность будет равна O(h), предполагая выполнение операции rank за постоянное время; к битовому вектору длины n можно прикрепить o(n) бит структур данных так, чтобы ответы на запросы rank могли быть даны за постоянное время [4,7].
Удобно использовать [math]\displaystyle{ h = \lceil log \; log \; n \rceil }[/math], так что [math]\displaystyle{ n/2^h }[/math] записей [math]\displaystyle{ A_h }[/math], каждая из которых требует O(log n) бит, занимают суммарно O(n) бит. Все массивы [math]\displaystyle{ B^{\ell} }[/math] добавляют максимум 2n бит, так как их длина уменьшается вдвое на каждом следующем уровне, а их дополнительные структуры rank добавляют дополнительно o(n) бит. Единственной нерешенной задачей остается представление массивов [math]\displaystyle{ \Psi_{\ell} }[/math]. Можно использовать следующую закономерность, обусловленную лексикографическим порядком:
Лемма 1. Пусть дан текст T[1; n], его суффиксный массив A[1; n] и соответствующая функция 4>. Тогда неравенство ^(i) < ^{i + 1) выполняется всякий раз, когда TA[i] = TA[i+1].