Методы сжатия без потерь

В основе всех методов сжатия лежит простая идея: если представлять часто используемые элементы короткими кодами, а редко используемые - длинными кодами, то для хранения блока данных требуется меньший объем памяти, чем если бы все элементы представлялись кодами одинаковой длины. Данный факт известен давно: вспомним, например, азбуку Морзе, в которой часто используемым символам поставлены в соответствие короткие последовательности точек и тире, а редко встречающимся - длинные.

Точная связь между вероятностями и кодами установлена в теореме Шеннона о кодировании источника, которая гласит, что элемент $${\rm{s}}_{\rm{i}}$$, вероятность появления которого равняется $$p(s_i)$$, выгоднее всего представлять $${\rm{ - log}}_{\rm{2}} p(s_i)$$ битами. Если при кодировании размер кодов всегда в точности получается равным $${\rm{ - log}}_{\rm{2}} p(s_i)$$ битам, то в этом случае длина закодированной последовательности будет минимальной для всех возможных способов кодирования. Если распределение вероятностей $$F = \{ p(s_i )\}$$ неизменно, и вероятности появления элементов независимы, то мы можем найти среднюю длину кодов как среднее взвешенное

$$H = - \sum\limits_i {p(s_i ) \cdot \log _2 p(s_i )}$$

Это значение также называется энтропией распределения вероятностей F или энтропией источника в заданный момент времени.

Обычно вероятность появления элемента является условной, т.е. зависит от какого-то события. В этом случае при кодировании очередного элемента $${\rm{s}}_{\rm{i}}$$ распределение вероятностей F принимает одно из возможных значений $$F_k$$, то есть $$F = F_k$$, и, соответственно, $$H = H_k$$. Можно сказать, что источник находится в состоянии k, которому соответствует набор вероятностей $$p_k (s_i)$$ генерации всех возможных элементов $$s_i$$. Поэтому среднюю длину кодов можно вычислить по формуле

$$H = - \sum\limits_k {P_k \cdot H_k } = - \sum\limits_{k,i} {P_k \cdot p_k (s_i )\log _2 p_k (s_i )}$$,

где $$p_k$$ - вероятность того, что F примет k -ое значение, или, иначе, вероятность нахождения источника в состоянии k.

Итак, если нам известно распределение вероятностей элементов, генерируемых источником, то мы можем представить данные наиболее компактным образом, при этом средняя длина кодов может быть вычислена по формуле (1).

Но в подавляющем большинстве случаев истинная структура источника нам не известна, поэтому необходимо строить модель источника, которая позволила бы нам в каждой позиции входной последовательности оценить вероятность $$p(s_i)$$ появления каждого элемента $${\rm{s}}_{\rm{i}}$$ алфавита входной последовательности. В этом случае мы оперируем оценкой $$q(s_i)$$ вероятности элемента $${\rm{s}}_{\rm{i}}$$.

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

Процесс моделирования может быть либо явным, либо скрытым. Вероятности элементов могут использоваться в методе как явным, так и неявным образом. Но всегда сжатие достигается за счет устранения статистической избыточности в представлении информации.

Ни один компрессор не может сжать любой файл. После обработки любым компрессором размер части файлов уменьшится, а оставшейся части - увеличится или останется неизменным. Данный факт можно доказать исходя из неравномерности кодирования, т.е. разной длины используемых кодов, но наиболее прост для понимания следующий комбинаторный аргумент.

Существует $$2^n$$ различных файлов длины $$n$$ битов, где $$n = 0, 1, 2, …$$ Если размер каждого такого файла в результате обработки уменьшается хотя бы на 1 бит, то $$2^n$$ исходным файлам будет соответствовать самое большее $$2^{n - 1}$$ различающихся архивных файлов. Тогда по крайней мере одному архивному файлу будет соответствовать несколько различающихся исходных, и, следовательно, его декодирование без потерь информации невозможно в принципе.

Вышесказанное предполагает, что файл отображается в один файл, и объем данных указывается в самих данных. Если это не так, то следует учитывать не только суммарный размер архивных файлов, но и объем информации, необходимой для описания нескольких взаимосвязанных архивных файлов и/или размера исходного файла. Общность доказательства при этом сохраняется.

Поэтому невозможен "вечный" архиватор, который способен бесконечное число раз сжимать свои же архивы. "Наилучшим" архиватором является программа копирования, поскольку в этом случае мы можем быть всегда уверены в том, что объем данных в результате обработки не увеличится.

Регулярно появляющиеся заявления о создании алгоритмов сжатия, "обеспечивающих сжатие в десятки раз лучшее, чем у обычных архиваторов", являются либо ложными слухами, порожденными невежеством и погоней за сенсациями, либо рекламой аферистов. В области сжатия без потерь, т.е. собственно сжатия, такие революции невозможны. Безусловно, степень сжатия компрессорами типичных данных будет неуклонно расти, но улучшения составят в среднем десятки или даже единицы процентов, при этом каждый последующий этап эволюции будет обходиться значительно дороже предыдущего. С другой стороны, в сфере сжатия с потерями, в первую очередь компрессии видеоданных, все еще возможно многократное улучшение сжатия при сохранении субъективной полноты получаемой информации.

Канонический алгоритм Хаффмана

Один из классических алгоритмов, известных с 60-х годов. Использует только частоту появления одинаковых байт во входном блоке данных. Сопоставляет символам входного потока, которые встречаются чаще, цепочку битов меньшей длины. И, напротив, встречающимся редко - цепочку большей длины. Для сбора статистики требует двух проходов по входному блоку (также существуют однопроходные адаптивные варианты алгоритма).

Для начала введем несколько определений.

Определение. Пусть задан алфавит $$\Psi = \{ a_1 ,...,a_r \}$$, состоящий из конечного числа букв. Конечную последовательность символов из $$\psi$$

$$A = a_{i_1 } a_{i_2 } ...a_{i_n }$$

будем называть словом в алфавите $$\psi$$, а число $$n$$ - длиной слова $$A$$. Длина слова обозначается как $$l(A)$$

Пусть задан алфавит, $$\Omega = \{ b_1 ,...,b_q \} $$. Через $$B$$ обозначим слово в алфавите $$\Omega$$ и через $$S(\Omega )$$ - множество всех непустых слов в алфавите $$\Omega $$.

Пусть $$S = S(\Psi )$$ - множество всех непустых слов в алфавите $$\psi $$, и $$$S'$$$ - некоторое подмножество множества $$S$$. Пусть также задано отображение $$F$$, которое каждому слову $$A$$, $$A \in S(\Psi )$$, ставит в соответствие слово

$$B = S(A)$$, $$B \in S(\Omega )$$.

Слово $$В$$ будем назвать кодом сообщения $$A$$, а переход от слова $$A$$ к его коду - кодированием.

Определение. Рассмотрим соответствие между буквами алфавита $$\psi $$ и некоторыми словами алфавита $$\Omega $$:

$$a_1 - B_1$$

$$a_2 - B_2$$

$$..$$.

$$a_r - B_r$$

Это соответствие называют схемой и обозначают через $$\sum {} $$. Оно определяет кодирование следующим образом: каждому слову $$A = a_{i_1 } a_{i_2 } ...a_{i_n } $$ из $${\rm{ S'(}}\Omega {\rm{) = S(}}\Omega {\rm{)}}$$ ставится в соответствие слово $$B = B_{i_1 } B_{i_2 } ...B_{i_n } $$, называемое кодом слова $$A$$. Слова $$B_1 ...B_r $$ называются элементарными кодами. Данный вид кодирования называют алфавитным кодированием.

Определение. Пусть слово $$В$$ имеет вид

$$B = B' \cdot B''$$

Тогда слово $$B'$$ называется началом или префиксом слова $$B$$, а $$B''$$ - концом слова $$B$$. При этом пустое слово $$\Lambda $$ и само слово $$B$$ считаются началами и концами слова $$B$$.

Определение. Схема $$\sum {} $$ обладает свойством префикса, если для любых $$i$$ и $$j$$ ( $$1 \le i,{\rm{ }}j \le r,{\rm{ }}i \ne j$$ ) слово $$B_i $$ не является префиксом слова $$B_j $$.

Теорема 1. Если схема $$\sum {} $$ обладает свойством префикса, то алфавитное кодирование будет взаимно однозначным.

Доказательство теоремы можно найти в [1.4].

Предположим, что задан алфавит $$\psi = \{ a_1 ,...a_r \} ,{\rm{ }}r > 1$$ и набор вероятностей $$p_1 ,...,p_r {\rm{ }}(\sum\limits_{i = 1}^r {p_i = 1} )$$ появления символов $${\rm{ }}a_1 ,...,a_r$$. Пусть, далее, задан алфавит $${\rm{ }}\Omega $$, $${\rm{ }}\Omega = \{ b_1 ,...,b_q \} ,{\rm{ (}}q > 1)$$. Тогда можно построить целый ряд схем $$\sum {} $$ алфавитного кодирования

$$a_1 - B_1$$

$$a_2 - B_2$$

$$..$$.

$$a_r - B_r$$

обладающих свойством взаимной однозначности.

Для каждой схемы можно ввести среднюю длину $$l_{cp} $$, определяемую как математическое ожидание длины элементарного кода:

$$l_{cp} = \sum\limits_{i = 1}^r {l_i p_i } ,{\rm{ }}l_i = l(B_i )$$ - длины слов.

Длина $$l_{cp} $$ показывает, во сколько раз увеличивается средняя длина слова при кодировании с помощью схемы $$\sum {} $$.

Можно показать, что $$l_{cp} $$ достигает величины своего минимума $$l_*$$ на некоторой $$\sum {} $$ и определяется как

$$l_* = \mathop {\min }\limits_\Sigma l_{cp}^\Sigma $$

Определение. Коды, определяемые схемой $$\sum {} $$ с $$l_{cp} = l_*,$$ называются кодами с минимальной избыточностью, или кодами Хаффмана.

Коды с минимальной избыточностью дают в среднем минимальное увеличение длин слов при соответствующем кодировании.

В нашем случае, алфавит $$\Psi = \{ a_1 ,...,a_r \} $$ задает символы входного потока, а алфавит $$\Omega = \{ 0,1\} $$ т.е. состоит всего из нуля и единицы.

Алгоритм построения схемы $$\sum {} $$ можно представить следующим образом:

Шаг 1. Упорядочиваем все буквы входного алфавита в порядке убывания вероятности. Считаем все соответствующие слова $$B_i $$ из алфавита $$\Omega = \{ 0,1\} $$ пустыми.

Шаг 2. Объединяем два символа $$a_{i_{r - 1} } $$ и $$a_{i_r } $$ с наименьшими вероятностями $$p_{i_{r - 1} }$$ и $$p_{i_r }$$ в псевдосимвол $$a'{\rm{ }}\{ a_{i_{r - 1} } a_{i_r } \} $$ c вероятностью $$p_{i_{r - 1} } + p_{i_r } $$. Дописываем 0 в начало слова $$B_{i_{r - 1} } (B_{i_{r - 1} } = 0B_{i_{r - 1} } )$$, и 1 в начало слова $$B_{i_r } (B_{i_r } = 1B_{i_r } )$$.

Шаг 3. Удаляем из списка упорядоченных символов $$a_{i_{r - 1} } $$ и $$a_{i_r } $$, заносим туда псевдосимвол $$a'{\rm{ }}\{ a_{i_{r - 1} } a_{i_r } \} $$. Проводим шаг 2, добавляя при необходимости 1 или ноль для всех слов $$B_i $$, соответствующих псевдосимволам, до тех пор, пока в списке не останется 1 псевдосимвол.

Пример: Пусть у нас есть 4 буквы в алфавите $$\Psi = \{ a_1 ,...,a_4 \} {\rm{ }}(r = 4)$$, $$p_1 = 0.5,{\rm{ }}p_2 = 0.24,{\rm{ }}p _3 = 0.15,{\rm{ }}p_4 = 0.11{\rm{ }}\left( {\sum\limits_{i = 1}^4 {{\rm{p}}_i = 1} } \right)$$. Процесс построения схемы представлен на рис 1.1 :

(рис 1.1)

Производя действия, соответствующие 2-му шагу, мы получаем псевдосимвол с вероятностью 0.26 (и приписываем 0 и 1 соответствующим словам). Повторяя же эти действия для измененного списка, мы получаем псевдосимвол с вероятностью 0.5. И, наконец, на последнем этапе мы получаем суммарную вероятность 1.

Для того, чтобы восстановить кодирующие слова, нам надо пройти по стрелкам от начальных символов к концу получившегося бинарного дерева. Так, для символа с вероятностью $$p_4 $$ получим $$B_4 = 101$$, для $$p_3 $$ получим $$B_3 = 100$$, для $$p_2 $$ получим $$B_2 = 11$$, для $$p_1 $$ получим $$B_1 = 0$$. Что соответствует схеме:

$$\eqalign{ a_1 - 0 \cr a_2 - 11 \cr a_3 - 100 \cr a_4 - 101 \cr} $$

Эта схема представляет собой префиксный код, являющийся кодом Хаффмана. Самый часто встречающийся в потоке символ $$a_1 $$ мы будем кодировать самым коротким словом 0, а самый редко встречающийся $$a_4 $$ - длинным словом 101.

Для последовательности из 100 символов, в которой символ $$a_1 $$ встретится 50 раз, символ $$a_2 $$ - 24 раза, символ $$a_3 $$ - 15 раз, а символ $$a_4 $$ - 11 раз, данный код позволит получить последовательность из 176 битов $$(100 \cdot l_{cp} = \sum\limits_{i = 1}^4 {p_i l_i } ).$$ Т.е. в среднем мы потратим 1.76 бита на символ потока.

Доказательства теоремы, а также того, что построенная схема действительно задает код Хаффмана, заинтересованный читатель найдет в [1.4].

Как стало понятно из изложенного выше, канонический алгоритм Хаффмана требует помещения в файл со сжатыми данными таблицы соответствия кодируемых символов и кодирующих цепочек.

На практике используются его разновидности. Так, в некоторых случаях резонно либо использовать постоянную таблицу, либо строить ее адаптивно, т.е. в процессе архивации/разархивации. Эти приемы избавляют нас от двух проходов по входному блоку и необходимости хранения таблицы вместе с файлом. Кодирование с фиксированной таблицей применяется в качестве последнего этапа архивации в JPEG и в алгоритме CCITT Group, рассмотренных в разделе "Алгоритмы сжатия изображений".

Арифметическое сжатие

Классический вариант алгоритма

Сжатие по методу Хаффмана постепенно вытесняется арифметическим сжатием. Свою роль в этом сыграло то, что закончились сроки действия патентов, ограничивающих использование арифметического сжатия. Кроме того, алгоритм Хаффмана приближает относительные частоты появления символов в потоке частотами кратными степени двойки (например, для символов $$a$$, $$b$$, $$c$$, $$d$$ с вероятностями 1/2, 1/4, 1/8, 1/8 будут использованы коды 0, 10, 110, 111), а арифметическое сжатие дает лучшую степень приближения частоты. По теореме Шеннона, наилучшее сжатие в двоичной арифметике мы получим, если будем кодировать символ с относительной частотой $$f$$ с помощью $${\rm{ - log}}_{\rm{2}} (f)$$ битов.

На графике, показанном на рис 1.2 приводится сравнение оптимального кодирования и кодирования по методу Хаффмана. Хорошо видно, что в ситуации, когда относительные частоты не являются степенями двойки, сжатие становится менее эффективным (мы тратим больше битов, чем это необходимо). Например, если у нас два символа $$a$$ и $$b$$ с вероятностями 253/256 и 3/256, то в идеале мы должны потратить на цепочку из 256 байт $${\rm{ - log}}_{\rm{2}} (253/256) \cdot 253 - \log _2 (3/256) \cdot 3 = 23.546$$, т.е. 24 бита. При кодировании по Хаффману мы закодируем $$a$$ и $$b$$ как 0 и 1, и нам придется потратить 1·253+1·3= 256 битов, т.е. в 10 раз больше. Рассмотрим алгоритм, дающий результат, близкий к оптимальному.

Арифметическое сжатие - достаточно изящный метод, в основе которого лежит очень простая идея. Мы представляем кодируемый текст в виде дроби, при этом строим дробь таким образом, чтобы наш текст был представлен как можно компактнее. Для примера рассмотрим построение такой дроби на интервале [0, 1) (0 - включается, 1 - нет). [0, 1) выбран потому, что он удобен для объяснений. Мы разбиваем его на подинтервалы с длинами, равными вероятностям появления символов в потоке. В дальнейшем будем называть их диапазонами соответствующих символов.

Пусть мы сжимаем текст "КОВ.КОРОВА" (что, очевидно, означает "коварная корова"). Распишем вероятности появления каждого символа в тексте (в порядке убывания) и соответствующие этим символам диапазоны (см. табл 1.1):

Будем считать, что эта таблица известна в компрессоре и декомпрессоре. Кодирование заключается в уменьшении рабочего интервала. Для первого символа в качестве рабочего интервала берется [0, 1). Мы разбиваем его на диапазоны в соответствии с заданными частотами символов (см. таблицу диапазонов). В качестве следующего рабочего интервала берется диапазон, соответствующий текущему кодируемому символу. Его длина пропорциональна вероятности появления этого символа в потоке. Далее считываем следующий символ. В качестве исходного берем рабочий интервал, полученный на предыдущем шаге, и опять разбиваем его в соответствии с таблицей диапазонов. Длина рабочего интервала уменьшается пропорционально вероятности текущего символа, а точка начала сдвигается вправо пропорционально началу диапазона для этого символа. Новый построенный диапазон берется в качестве рабочего, и т.д.

Используя исходную таблицу диапазонов, кодируем текст "КОВ.КОРОВА":

Исходный рабочий интервал [0, 1).

Символ "К" [0.3; 0.5) получаем [0.3000; 0.5000).

Символ "О" [0.0; 0.3) получаем [0.3000; 0.3600).

Символ "В" [0.5; 0.7) получаем [0.3300; 0.3420).

Символ "." [0.9; 1.0) получаем [0,3408; 0.3420).

Графически процесс кодирования первых трех символов представлен на рис 1.3

Таким образом, окончательная длина интервала равна произведению вероятностей всех встретившихся символов, а его начало зависит от порядка следования символов в потоке. Если обозначить диапазон символа c как $$[a[c],b[c])$$, а интервал для $$i$$ -го кодируемого символа потока как $$[l_i ,h_i )$$, то алгоритм сжатия может быть записан как:

l0=0; h0=1; i=0;
while(not DataFile.EOF()){
	c = DataFile.ReadSymbol(); i++;
	li = li-1 + a[c]*(hi-1 - li-1);
	hi = hi-1 + b[c]*(hi-1 - li-1);
};

Большой вертикальной чертой на рисунке выше обозначено произвольное число, лежащее в полученном при работе интервале $$[l_i ,h_i )$$. Для последовательности "КОВ.", состоящей из 4 символов, за такое число можно взять 0.341. Этого числа достаточно для восстановления исходной цепочки, если известна исходная таблица диапазонов и длина цепочки.

Рассмотрим работу алгоритма восстановления цепочки. Каждый следующий интервал вложен в предыдущий. Это означает, что если есть число 0.341, то первым символом в цепочке может быть только "К", поскольку только его диапазон включает это число. В качестве интервала берется диапазон "К" - [0.3; 0.5) и в нем находится диапазон $$[a[c],b[c])$$, включающий 0.341. Перебором всех возможных символов по приведенной выше таблице находим, что только интервал [0.3; 0.36), соответствующий диапазону для "О" включает число 0.341. Этот интервал выбирается в качестве следующего рабочего и т.д. Алгоритм декомпрессии можно записать так:

l0=0; h0=1; value=File.Code();
for(i=1; i<=File.DataLength(); i++){
	for(для всех cj){
		li = li-1 + a[cj]*(hi-1 - li-1);
		hi = hi-1 + b[cj]*(hi-1 - li-1);
		if ((li  <= value)  (value < hi)) break;
	};
	DataFile.WriteSymbol(cj);
};

Где value - прочитанное из потока число (дробь), а c - записываемые в выходной поток распаковываемые символы. При использовании алфавита из 256 символов $$c_j $$, внутренний цикл выполняется достаточно долго, однако его можно ускорить. Заметим, что поскольку $$b[c_{j + 1} ] = a[c_j ]$$ (см. приведенную выше таблицу диапазонов), то $$l_i $$ для $$c_{j + 1} $$ равно $$h_i $$ для $$c_j $$, а последовательность $$h_i $$ для $$c_j $$ строго возрастает с ростом j. Т.е. количество операций во внутреннем цикле можно сократить вдвое, поскольку достаточно проверять только одну границу интервала. Также, если у нас мало символов, то, отсортировав их в порядке уменьшения вероятностей, мы сокращаем число итераций цикла и, таким образом, ускоряем работу декомпрессора. Первыми будут проверяться символы с наибольшей вероятностью, например в нашем примере мы с вероятностью $${1 \over 2}$$ будем выходить из цикла уже на втором символе из шести. Если число символов велико, существуют другие эффективные методы ускорения поиска символов (например, бинарный поиск).

Хотя приведенный выше алгоритм вполне работоспособен, он будет работать медленно, по сравнению с алгоритмом, оперирующим двоичными дробями. Двоичная дробь задается как $$0a_1 a_2 a_3 ...a_i = a_1 \cdot {1 \over 2} + a_2 \cdot {1 \over 4} + a_3 \cdot {1 \over 8} + ... + a_i \cdot {1 \over {2^i }}$$. Таким образом, при сжатии нам необходимо дописывать в дробь дополнительные знаки до тех пор, пока получившееся число не попадет в интервал, соответствующий закодированной цепочке. Получившееся число полностью задает закодированную цепочку при аналогичном алгоритме декодирования. Графически схема работы алгоритма показана на рис 1.4

Интересной особенностью арифметического кодирования является способность сильно сжимать отдельные длинные цепочки. Например, один бит "1" (двоичное число "0.1") для нашей таблицы интервалов однозначно задает цепочку "ВОООООООООО…" произвольной длины (например, 1000000000 символов). Т.е. если наш файл заканчивается одинаковыми символами, например массивом нулей, то этот файл может быть сжат с весьма впечатляющей степенью сжатия. Очевидно, что длину исходного файла при этом следует передавать декомпрессору явным образом перед сжатыми данными, как это делалось в приведенных выше примерах.

Приведенный выше алгоритм может сжимать только достаточно короткие цепочки из-за ограничений разрядности всех переменных. Чтобы избежать этих ограничений, реальный алгоритм работает с целыми числами и оперирует с дробями, числитель и знаменатель которых являются целыми числами (например, знаменатель равен 10000h = 65536). При этом с потерей точности можно бороться, отслеживая сближение $$l_i $$ и $$h_i $$ и умножая числитель и знаменатель представляющей их дроби на какое-то число (удобно на 2). С переполнением сверху можно бороться, записывая старшие биты в $$l_i $$ и $$h_i $$ в файл, тогда, когда они перестают меняться (т.е. реально уже не участвуют в дальнейшем уточнении интервала). Перепишем таблицу диапазонов с учетом сказанного выше. Полученные данные занесём в табл. 1.2