1.5. Адаптивные коды Хаффмана

Метод Хаффмана предполагает, что частоты символов алфавита известны декодеру. На практике это бывает крайне редко. Одно возможное решение для компрессора – это прочитать исходные данные два раза. В первый раз, чтобы вычислить частоты, а во второй раз, чтобы сделать сжатие. В промежутке компрессор строит дерево Хаффмана. Такой метод называется полуадаптивным (см. § 1.3), и он работает медленно для практического использования. На практике применяется метод адаптивного (или динамического) кодирования Хаффмана. Этот метод лежит в основе программы compact операционной системы UNIX.

Рис. 1.13. Деревья для кодов Хаффмана.

Более подробно про адаптивный метод, излагаемый ниже, можно прочитать в [Lelewer, Hirschberg 87], [Knuth 85] и [Vitter 87].

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

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

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

Рис. 1.14. Коды ecs.

Однако, имеется одно тонкое место. Декодер должен знать является ли данный образчик просто несжатым символом (обычно, это 8-битный код ASCII, однако, см. § 1.5.1) или же это код переменной длины. Для преодоления двусмысленности, каждому несжатому символу будет предшествовать специальный esc (escape) код переменной длины. Когда декомпрессор читает этот код, он точно знает, что за ним следуют 8 бит кода ASCII, который впервые появился на входе.

Беспокойство вызывает то, что esc код не должен быть переменным кодом, используемым для символов алфавита. Поскольку это коды все время претерпевают изменения, то и код для esc следует также модифицировать. Естественный путь – это добавить к дереву еще один пустой лист с постоянно нулевой частотой, чтобы ему все время присваивалась ветвь из одних нулей. Поскольку этот лист будет все время присутствовать на дереве, ему все время будет присваиваться код переменной длины. Это и будет код esc, предшествующий каждому новому несжатому символу. Дерево будет все время модифицироваться, будет изменяться положение на нем пустого листа и его кода, но сам этот код будет идентифицировать каждый новый несжатый символ в сжатом файле. На рис. 1.14 показано движение этого ecs кода по мере роста дерева.

Этот метод также используется в известном протоколе V.32 передачи данных по модему со скоростью 14400 бод.