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

Формулировка связанной с суффиксными массивами задачи CFTI проста: необходимо найти экономичную по объему памяти структуру данных, поддерживающую эффективное извлечение значения A[i] для любого i. Такое решение и называется ''сжатым суффиксным массивом''. Обычно сжатые суффиксные массивы также поддерживают получение обратного значения <math>A^{-1} [j] = i</math> для любого заданного j.

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

4) асимптотически оптимально относительно размера сжатого текста, т. е. <math>O(nH_k) + o(n \; log \; \sigma)</math> бит.