1.4.1. Декодирование Хаффмана

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

В любом случае, декодер должен прочесть начало файла и построить дерево Хаффмана для алфавита. Только после этого он может читать и декодировать весь файл. Алгоритм декодирования очень прост. Следует начать с корня и прочитать первый бит сжатого файла. Если это нуль, следует двигаться по нижней ветке дерева; если это единица, то двигаться надо по верхней ветке дерева. Далее читается второй бит и происходит движение по следующей ветке по направлению к листьям. Когда декодер достигнет листа дерева, он узнает код первого несжатого символа (обычно это символ ASCII). Процедура повторяется для следующего бита, начиная опять из корня дерева.

Описанная процедура проиллюстрирована на рис. 1.10 для алфавита из 5 символов. Входная строка «» кодируется последовательностью 1001100111. Декодер начинает с корня, читает первый бит «1» и идет вверх. Второй бит «0» направляет его вниз. То же самое делает третий бит. Это приводит декодер к листу . Получен первый несжатый символ. Декодер возвращается в корень и читает 110, движется вверх, вверх и вниз и получает символ , и так далее.

Рис. 1.10. Коды Хаффмана с равными вероятностями.