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