Усиление степени сжатия текста

Ключевые слова и синонимы

Модели сжатия высокого порядка; сжатие с учетом контекста

Постановка задачи

Неформально техника усиления представляет собой метод, который при применении к определенному классу алгоритмов повышает их эффективность. Повышение должно быть доказуемым и четко определенным в виде одного или нескольких параметров, характеризующих эффективность работы алгоритма. Примеры подобных «усилителей» можно найти в сегментах рандомизированных алгоритмов (здесь усилитель позволяет превратить алгоритм BPP в RP [6]) и теории вычислительного обучения (в данном случае усилитель позволяет повысить точность прогнозирования у слабого обучающего алгоритма [10]). Задача усиления сжатия заключается в разработке техники, повышающей эффективность сжатия широкого класса алгоритмов. В частности, результатом работы Ферраджины и др. явилась обобщенная техника, позволяющая «заставить» компрессор, не использовавший контекстной информации вовсе, всегда использовать наилучший возможный контекст.

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

1 Динамические версии этих алгоритмов рассматривают частоту схождения символа в уже просканированной порции входных данных.

Применение техники усиления Ферраджины и др. к алгоритмам Хаффмана и арифметического кодирования позволяет получить новый алгоритм сжатия со следующими характеристиками:

(i) новый алгоритм использует усиленный алгоритм сжатия в качестве черного ящика;

(ii) новый алгоритм выполняет сжатие в стиле PPM, автоматически выбирая оптимальное значение к k;

(iii) асимптотическая эффективность нового алгоритма по соотношению времени и памяти соответствует эффективности усиленного алгоритма сжатия.

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