Таблица 11.5. Коды Хаффмана для символов примера предложения
Символ - Количество появлений
Пробел - 00
c - 100
o - 101
u - 010
d - 1100
h - 1101
w - 1110
k - 11110
H - 11111
a - 01100
l - 01101
m - 01110
? - 01111
Обратите внимание, что эта таблица кодов - не единственная возможная. Каждый раз, когда имеется три или больше узлов, из числа которых нужно выбрать два, существуют альтернативные варианты результирующего дерева и, следовательно, результирующих кодов. Но на практике все эти возможные варианты деревьев и кодов будут обеспечивать максимальное сжатие. Все они эквивалентны.
Теперь можно вычислить код для всего предложения. Он начинается с битов:
1111110111100001110010100...
и содержит всего 131 бит. Если бы исходное предложение было закодировано кодами ASCII, по одному байту на символ, оно содержало бы 286 битов. Таким образом, в данном случае коэффициент сжатия составляет приблизительно 54%.
Повторим снова, что, как и при применении алгоритма Шеннона-Фано, необходимо каким-то образом сжать дерево и включить его в состав сжатых данных.
Восстановление выполняется совершенно так же, как при использовании кодирования Шеннона-Фано: необходимо восстановить дерево из данных, хранящихся в сжатом потоке, и затем воспользоваться им для считывания сжатого потока битов.
Рассмотрим кодирование Хаффмана с высокоуровневой точки зрения. В ходе реализации каждого из методов сжатия, которые будут описаны в этой главе, мы создадим простую подпрограмму, которая принимает как входной, так и выходной поток, и сжимает все данные входного потока и помещает их в выходной поток.
Эта высокоуровневая подпрограмма TDHuffroanCompress, выполняющая кодирование Хаффмана, приведена в листинге 11.5.
Листинг 11.5. Высокоуровневая подпрограмма кодирования Хаффмана
procedure TDHuffmanCompress(aInStream, aOutStream : TStream);
var
HTree : THuffmanTree;
HCodes : PHuffmanCodes;
BitStrm : TtdOutputBitStream;
Signature : longint;
Size : longint;
begin
{вывести информацию заголовка (сигнатуру и размер несжатых данных)}
Signature := TDHuffHeader;
aOutStream.WriteBuffer(Signature, sizeof(longint));
Size := aInStream.Size;
aOutStream.WriteBuffer(Size, sizeof(longint));
{при отсутствии данных для сжатия необходимо выйти из подпрограммы}
if (Size = 0) then
Exit;
{подготовка}
HTree := nil;
HCodes := nil;
BitStrm := nil;
try
{создать сжатый поток битов}
BitStrm := TtdOutputBitStream.Create(aOutStream);
BitStrm.Name := 'Huffman compressed stream';
{распределить память под дерево Хаффмана}