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

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

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

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