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

Ключевые слова и синонимы

Создание сжатого полнотекстового индекса; сжатое суффиксное дерево

Постановка задачи

Пусть дана текстовая строка [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-го порядка строки [math]\displaystyle{ T^1 }[/math]; или даже

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(l)] = 1 }[/math], так что функция [math]\displaystyle{ \Psi }[/math] является перестановкой.

Гросси и Виттер используют иерархическую декомпозицию массива А, основанную на [math]\displaystyle{ \Psi^2 }[/math]. рассмотрим первый уровень этой иерархической декомпозиции. Пусть [math]\displaystyle{ A_0 = A }[/math] – исходный суффиксный массив. Битовый вектор [math]\displaystyle{ B^0 [1, n] }[/math] определен таким образом, что [math]\displaystyle{ B^0 [i] = 1 }[/math] в том и только том случае, если A[i] четно. Кроме того, пусть содержит последовательность значений 4>{i) для аргументов i, где B°[i] = 0. Наконец, пусть A1[1; BN/2C] будет подпоследовательностью A0[1; n], образованной четными значениями A0[i], деленными на 2.

1Hk — это минимальное среднее количество битов, необходимых для кодирования одного символа с помощью любого алгоритма сжатия, который фиксирует кодовое слово на основе контекста k-го символа, следующего за кодируемым символом. В [6] дано более формальное определение.

2 Далее приводится описание, близкое к изложенному в [9].

Тогда A = A0 может быть представлен с использованием только ^Q, B° и A1. Чтобы получить A[i], сначала проверим, верно ли B°[i] = 1. Если это так, то A[i] (делится на 2) где-то в A1. Точное положение зависит от того, сколько единиц встречается в B° до позиции i, обозначенной rank(B°;i), т.е. A[i] = 2 ■ A1[rank1(B° ; i)]. Если B°[i] = 0, то A[i] является нечетным и не представлен в A1. Однако в этом случае элемент A[i] + 1 = A[^(i)] должен быть четным и, таким образом, должен быть представлен в A1. Так как WQ включает только 4> значения, где B°[i] = 0, из этого следует, что A[V(i)] = A[W0[rank0(B°, i)]]. После вычисления A[^(i)] (для четных ФЦ)) можно просто получить A[i] = A[4s(i)] - 1.

Эта идея может быть использована рекурсивно. Вместо того, чтобы представлять A1, замените его на B2, 4>2 и A2. Продолжайте процесс до тех пор, пока Ah не станет достаточно мал, чтобы быть представленным в явном виде. Сложность будет равна O(h), предполагая выполнение операции rank за постоянное время; к битовому вектору длины n можно прикрепить o(n) бит структур данных так, чтобы ответы на запросы rank могли быть даны за постоянное время [4,7].

Удобно использовать h = dlog log ne, так что n/2h записей Ah, каждая из которых требует O(log n) бит, занимают суммарно O(n) бит. Все массивы В добавляют максимум 2n бит, так как их длина уменьшается вдвое на каждом следующем уровне, а их дополнительные структуры rank добавляют дополнительно o(n) бит. Единственной нерешенной задачей остается представление массивов Ч'ц. Можно использовать следующую закономерность, обусловленную лексикографическим порядком:

Лемма 1. Пусть дан текст T[1; n], его суффиксный массив A[1; n] и соответствующая функция 4>. Тогда неравенство ^(i) < ^{i + 1) выполняется всякий раз, когда TA[i] = TA[i+1].