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

Простым примером полнотекстового индекса является ''суффиксный массив'' A[1, n], содержащий перестановку интервала [1, n], такую, что T[A[i], n] < T[A[i + 1], n] для всех <math>1 \le i < n</math>, где отношение "<" между строками обозначает лексикографический порядок. Используя суффиксный массив, можно найти вхождения заданного шаблона <math>P = p_1 p_2 ... p_m</math> в строке T с помощью двух бинарных поисков за время O(m log n).

3) пропорционально размеру ''сжатого'' текста, т. е. <math>O(nH_k)</math> бит, где <math>O(H_k)</math> — это (эмпирическая) ''энтропия k-го порядка'' строки T ''//где <math>H_k</math> — минимальное среднее количество бит, необходимых для кодирования одного символа с помощью любого алгоритма сжатия, который фиксирует кодовое слово на основе контекста k-го символа, следующего за кодируемым символом. В [6] дано более формальное определение//'';

Гросси и Виттер используют иерархическую декомпозицию массива А, основанную на <math>\Psi</math> ''//далее приводится описание, близкое к изложенному в [9]//''. рассмотрим первый уровень этой иерархической декомпозиции. Пусть <math>A_0 = A</math> – исходный суффиксный массив. Битовый вектор <math>B^0 [1, n]</math> определен таким образом, что <math>B^0 [i] = 1</math> в том и только том случае, если A[i] четно. Кроме того, пусть <math>\Psi_0 [1, \lceil n/2 \rceil ]</math> содержит последовательность значений <math>\Psi(i)</math> для тех аргументов i, для которых <math>B^0[i] = 0</math>. Наконец, пусть <math>A_1 [1, \lfloor n/2 \rfloor ]</math> будет подпоследовательностью <math>A_0 [1, n]</math>, образованной четными значениями <math>A_0[i]</math>, деленными на 2.