Сжатый суффиксный массив: различия между версиями

'''Определение 1.''' Пусть дан суффиксный массив A[1, n]. Функция <math>\Psi : [1, n] \to [1, n]</math> определена таким образом, что для всех <math>1 \le i < n</math> выполняется соотношение <math>A[\Psi(i)] = A[i] + 1</math>. Исключением является A[1] = n, в этом случае имеет место <math>A[\Psi(l)] = 1</math>, так что функция <math>\Psi</math> является перестановкой.

Гросси и Виттер используют иерархическую декомпозицию массива А, основанную на <math>\Psi^2</math>. рассмотрим первый уровень этой иерархической декомпозиции. Пусть <math>A_0 = A</math> – исходный суффиксный массив. Битовый вектор <math>B^0 [1, n]</math> определен таким образом, что <math>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] дано более формальное определение.