Усиление степени сжатия текста: различия между версиями

Классические алгоритмы Хаффмана и арифметического кодирования [1] могут служить примерами ''статистических'' алгоритмов сжатия, обычно кодирующих входной символ в соответствии с ''общей'' частотой его вхождения в данных, подлежащих сжатию. [''Динамические версии этих алгоритмов рассматривают частоту вхождения символа в уже просканированной порции входных данных''.] Этот подход эффективен и прост в реализации, однако обеспечивает невысокий уровень сжатия. Эффективность работы статистических алгоритмов сжатия можно повысить за счет использования моделей ''более высокого порядка'', получающих более качественную оценку частоты встречаемости входных символов. Алгоритм сжатия PPM [9] реализует эту идею путем сбора данных о частоте вхождения всех символов, попадающих в ''любой'' контекст длины k, и сжатия их при помощи арифметического кодирования. Длина контекста k представляет собой параметр алгоритма, который определяется подлежащими сжатию данными: он будет разным при сжатии текста на английском языке, последовательности ДНК или документа в формате XML. Можно привести и другие примеры сложных программ сжатия, таких как алгоритмы Лемпеля-Зива и Барроуза-Уилера [9], использующих информацию о контексте ''неявным'' образом. Все эти алгоритмы, учитывающие контекст, хороши по критерию эффективности работы, однако сложны для реализации и анализа.

В следующих разделах будет изложено точное формальное обоснование перечисленных характеристик.