Усиление степени сжатия текста
Ключевые слова и синонимы
Постановка задачи
Неформально техника усиления представляет собой метод, который при применении к определенному классу алгоритмов повышает их эффективность. Повышение должно быть доказуемым и четко определенным в виде одного или нескольких параметров, характеризующих эффективность работы алгоритма. Примеры подобных «усилителей» можно найти в сегментах рандомизированных алгоритмов (здесь усилитель позволяет превратить алгоритм BPP в RP [6]) и теории вычислительного обучения (в данном случае усилитель позволяет повысить точность прогнозирования у слабого обучающего алгоритма [10]). Задача усиления сжатия заключается в разработке техники, повышающей эффективность сжатия широкого класса алгоритмов. В частности, результатом работы Ферраджины и др. явилась обобщенная техника, позволяющая «заставить» компрессор, не использовавший контекстной информации вовсе, всегда использовать наилучший возможный контекст.
Классические алгоритмы Хаффмана и арифметического кодирования [ ] могут служить примерами статистических алгоритмов сжатия, обычно кодирующих входной символ в соответствии с частотой его вхождения в данных, подлежащих сжатию.1 Этот подход эффективен и прост в реализации, однако обеспечивает невысокий уровень сжатия. Эффективность работы статистических алгоритмов сжатия можно повысить в результате использования моделей более высокого порядка, получающих более качественную оценку частоты встречаемости входных символов. Алгоритм сжатия PPM [ ] реализует эту идею за сбора данных о частоте вхождения всех символов, попадающих в любой контекст длины k, и сжатия их при помощи арифметического кодирования. Длина контекста k представляет собой параметр алгоритма, который определяется подлежащими сжатию данными: он будет разным при сжатии текста на английском языке, последовательности ДНК или документа в формате XML. Можно привести и другие примеры сложных программ сжатия, таких как алгоритмы Лемпеля-Зива и Барроуза-Уилера [ ]. Все эти алгоритмы, учитывающие контекст, хороши по критерию эффективности работы, однако сложны для реализации и анализа.
1 Динамические версии этих алгоритмов рассматривают частоту схождения символа в уже просканированной порции входных данных.
Применение техники усиления Ферраджины и др. к алгоритмам Хаффмана и арифметического кодирования позволяет получить новый алгоритм сжатия со следующими характеристиками:
(i) новый алгоритм использует усиленный алгоритм сжатия в качестве черного ящика;
(ii) новый алгоритм выполняет сжатие в стиле PPM, автоматически выбирая оптимальное значение к k;
(iii) асимптотическая эффективность нового алгоритма по соотношению времени и памяти соответствует эффективности усиленного алгоритма сжатия.
В следующих разделах будет изложено точное формальное обоснование перечисленных характеристик.
Основные результаты
Нотация. Эмпирическая энтропия
Пусть s – строка над алфавитом S = {a1, ..., ah}. Обозначим для каждого ai 2 S за ni количество вхождений ai в s. Эмпирическая энтропия нулевого порядка строки s определяется как H0(s) = - £?=1(M,7|S|) log(ni/jsj), где все алгоритмы берутся по основанияю 2, а 0 log 0 = 0. Хорошо известно, что H0 представляет собой максимальный уровень сжатия, которого можно достичь при использовании уникального декодируемого кода, в котором каждому символу алфавита назначается уникальное кодовое слово. Более высокой степени сжатия можно достичь, если кодовое слово символа зависит от k символов, следующих за ним (то есть от его контекста).2 Определим ws как строку единичных символов, непосредственно предшествующих вхождениям w в s. Например, для s = bcabcabdca получим cas = bbd. Значение
(1) = 1 X jwsjH0(w w2 представляет эмпирическую энтропию k-го порядка для s и является нижней границей степени сжатия, которой можно достичь при использовании кодовых слов, которые зависят только от k символов, непоследственно следующих за кодируемым.
2 Большинство алгоритмов сжатия данных обычно рассматривают контекст, предшествующий кодируемым символам. В данном описании используется нестандартный «прямой» контекст для упрощения нотации в последующих разделах. Работа с «прямым» контекстом эквивалентна работе с традиционным «обратным» контекстом для обращенной строки s (подробнее см. в [3]).
Пример 1 Пусть строка s = mississippi. Для k = 1 имеем is = mssp, ss = isis, ps = ip. Следовательно,
4 4 2
H1(s) = 4 H0(mssp) + 4 H0(isis) + 2 H0(ip)
6 11
4 11 2 11 12 11
Отметим, что эмпирическая энтропия определяется для любой строки и может использоваться для измерения эффективности алгоритмов сжатия без каких-либо предположений о входных данных. К сожалению, для некоторых строк (с очень высокой сжимаемостью) эмпирическая энтропия обеспечивает слишком консервативное значение нижней границы. Например, для s = an имеет место sj Hk(s) = 0 для любого k > 0. Чтобы лучше справляться со строками с высокой сжимаемостью, в работе [ ] было введено понятие модифицированной эмпирической энтропии нулевого порядка H*(s), имеющей следующее свойство: s\H*(s) по меньшей мере равно количеству бит, необходимых для записи длины s в двоичной форме. Модифицированная эмпирическая энтропия k-го порядка H* определяется как максимальная степень сжатия, которой можно достичь при просмотре не более чем k символов, следующих за кодируемым.
