Сжатие по Хаффмену

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

Рассмотрим два адаптивных метода сжатия по Хаффмену. Первый из них заключается в использовании модели, которая изначально является равномерной, содержащей все возможные символы (в том числе и символ конца файла EOF) с частотами, равными 1. После кодирования очередного символа его частота увеличивается на единицу. При этом подсчитывается суммарная частота и если она достигает заранее заданного, максимального, значения, то производится нормализация – уменьшение частот всех символов. Как правило, при нормализации все частоты делят на 2. При этом частотам, получившимся равными 0, присваивают значение 1. Процесс продолжается до тех пор, пока не будет достигнут конец файла (считан символ EOF).

Второй метод адаптивного сжатия по Хаффмену основан на использовании дополнительного символа ESC, частота которого всегда равна 1. Исходная модель в этом случае содержит только два символа – ESC и EOF с единичными частотами. При появлении очередного символа проверяется его наличие в текущей модели. Если символ имеется в модели (его частота не равна 0), то ему присваивается код по методу Хаффмена. Если же символ в модели отсутствует (его частота равна 0), то ему присваивается код, состоящий из кода Хаффмена символа ESC, к которому приписывается справа исходный код символа (код, считанный из файла). Если символ при кодировании уже присутствовал в модели, то после кодирования его частота увеличивается на 1, иначе – он добавляется в модель с частотой 1. Так же как и в предыдущем случае подсчитывается суммарная частота и производится нормализация, когда суммарная частота достигает заданного, максимального, значения. При этом можно модифицировать нормализацию: после уменьшения значений частот все символы (кроме ESC и EOF), у которых частоты стали меньше 1, удаляются из модели. Отметим, что кодирование выполняется таким образом, что бы коды символов ESC и EOF имели не меньшую длину, чем другие символы.

Восстановление данных, сжатых с помощью первого адаптивного метода, выполняется следующим образом: побитно считывается код из сжатого файла, производится попытка его декодировать и если это удается, то соответствующий символ записывается в выходной файл, его частота увеличивается на 1, определяется суммарная частота и при необходимости выполняется нормализация. Процесс продолжается до тех пор, пока не будет декодирован символ EOF. Восстановление по второму методу отличается только тем, что если декодирован символ ESC, то далее считывается известное количество бит несжатого символа, который затем добавляется в модель с частотой 1. При использовании обоих методов исходная модель должна быть точно такой же, что и при сжатии данных.

Проиллюстрируем описание методов сжатия по Хаффмену на примерах. Пусть файл данных, который нужно сжать, имеет вид

s ₁ s ₂ s ₂ s ₂ s ₁ s ₃ s ₃EOF.

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

01111000000001.

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

Таблица 6.1

Полуадаптивные коды Хаффмена

Теперь выполним сжатие того же файла, но с помощью адаптивных методов. При этом будем полагать, что максимальное значение суммарной частоты, при которой необходимо проводить нормализацию, равно 8. Коды, получаемые при сжатии первым адаптивным методом, приведены в таблице 6.2. На выходе в результате будет получена последовательность

1001001010101001.

Таблица 6.2

Кодирование первым адаптивным методом Хаффмена

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

Для сжатия вторым адаптивным методом необходимо определить исходные коды символов в несжатом виде. Пусть они будут следующими:

s ₁ – 00, s ₂ – 01, s ₃ – 10, EOF – 11.

Тогда в результате на выходе получим

0000001110001101001011.

Процесс получения соответствующих кодов показан в таблице 6.3. Здесь также после шестого (перед седьмым) шагом выполнялась нормализация модели.

Таблица 6.3

Кодирование вторым адаптивным методом Хаффмена