4446
правок
Сжатый суффиксный массив: различия между версиями
Материал из WEGA
нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 18: | Строка 18: | ||
Классические полнотекстовые индексы занимают O(n log n) бит, обычно с поправкой на довольно большой константный коэффициент. Типичные цели задачи CFTI могут быть охарактеризованы степенью амбициозности; например, необходимо найти структуру, удовлетворяющую одному из следующих требований к объему памяти: | Классические полнотекстовые индексы занимают <math>O(n \; log \; n)</math> бит, обычно с поправкой на довольно большой константный коэффициент. Типичные цели задачи CFTI могут быть охарактеризованы степенью амбициозности; например, необходимо найти структуру, удовлетворяющую одному из следующих требований к объему памяти: | ||
1) пропорционально размеру текста, т. е. <math>O(n \; log \; \sigma)</math> бит; | 1) пропорционально размеру текста, т. е. <math>O(n \; log \; \sigma)</math> бит; | ||
| Строка 24: | Строка 24: | ||
2) асимптотически оптимально относительно размера текста, т. е. <math>n \; log \; \sigma (1 + o(1))</math> бит; | 2) асимптотически оптимально относительно размера текста, т. е. <math>n \; log \; \sigma (1 + o(1))</math> бит; | ||
3) пропорционально размеру ''сжатого'' текста, т.е. O( | 3) пропорционально размеру ''сжатого'' текста, т. е. <math>O(nH_k)</math> бит, где <math>O(H_k)</math> — это (эмпирическая) ''энтропия k-го порядка'' строки <math>T^1</math>; или даже | ||
4) асимптотически оптимально относительно размера сжатого текста, т. е. <math>O(nH_k) + o(n \; log \; \sigma)</math> бит. | |||
== Основные результаты == | == Основные результаты == | ||
Первое решение проблемы предложили Гросси и Виттер [3] использовавшие свойство регулярности суффиксного массива посредством функции | Первое решение проблемы предложили Гросси и Виттер [3], использовавшие свойство регулярности суффиксного массива посредством <math>\Psi</math>-функции: | ||
Определение 1. Пусть дан суффиксный массив A[1 | '''Определение 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> является перестановкой. | ||
