Рисунок 11.2. Построение дерева Хоффмана
Используя это дерево точно так же, как и дерево, созданное для кодирования Шеннона-Фано, можно вычислить код для каждого из символов в исходном предложении и построить таблицу 11.5.
Таблица 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';
{распределить память под дерево Хаффмана}
HTree := THuffmanTree.Create;
{определить распределение символов во входном потоке и выполнить восходящее построение дерева Хаффмана}
HTree.CalcCharDistribution(aInStream);
{вывести дерево в поток битов для облегчения задачи программы восстановления данных}
HTree.SaveToBitStream (BitStrm);
{если корневой узел дерева Хаффмана является листом, входной поток состоит лишь из единственного повторяющегося символа, и следовательно, задача выполнена. В противном случае необходимо выполнить сжатие входного потока}
if not HTree.RootIsLeaf then begin
{распределить память под массив кодов}
New(HCodes);
{вычислить все коды}
HTree.CalcCodes(HCodes^ );
{сжать символы входного потока в поток битов}
DoHuffmanCompression(aInStream, BitStrm, HCodes^ );
end;
finally
BitStrm.Free;
HTree.Free;
if (HCodes <> nil) then
Dispose(HCodes);
end;
end;
Код содержит множество элементов, которые мы еще не рассматривали. Но мы вполне можем вначале рассмотреть работу программы в целом, а затем приступить к рассмотрению каждого отдельного этапа. Прежде всего, мы записываем в выходной поток небольшой заголовок, за которым следует значение длины входного потока. Впоследствии эта информация упростит задачу восстановления данных, гарантируя, что сжатый поток соответствует созданному нами. Затем мы создаем объект потока битов, содержащий выходной поток. Следующий шаг -создание экземпляра класса THuffmanTree. Этот класс, как вскоре будет показано, будет использоваться для создания дерева Хаффмана и содержит различные методы, помогающие в решении этой задачи. Один из методов этого нового объекта, вызываемых в первую очередь, метод CalcCharDistribution, определяет статистическую информацию распределения символов во входном потоке, а затем строит префиксное дерево Хаффмана.