Фундаментальные алгоритмы и структуры данных в Delphi

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

Другой возможный способ - хранение значений счетчика для каждого символа. В этом случае для всех символов, в том числе для отсутствующих во входном потоке, требуется два фиксированных байта. В результате общий размер таблицы во всех ситуациях составил бы 512 байт. Честно говоря, этот результат не многим лучше предыдущего.

Конечно, если бы входной поток был достаточно большим, некоторые из значений счетчиков могли бы превысить размер 2-байтового слова, и для каждого символа пришлось бы использовать по три или даже четыре байта.

Более рациональный подход - игнорировать значения счетчиков символов и сохранять реальную структуру дерева. Префиксное дерево содержит два различных вида узлов: внутренние с двумя дочерними узлами и внешние, не имеющие дочерних узлов. Внешние узлы - это узлы, содержащие символы. Выполним обход дерева, применив один из обычных методов обхода (фактически, мы будем использовать метод обхода в ширину). Для каждого достигнутого узла будем записывать нулевой бит, если узел является внутренним, или единичный бит, если узел является внешним, за которым будет следовать представляемый узлом символ. Код реализации метода SaveToBitStream и вызываемого им рекурсивного метода htSaveNode, который выполняет реальный обход дерева и запись информации в поток битов, представлен в листинге 11.11.

Листинг 11.11. Запись дерева Хаффмана в поток битов

procedure THuffmanTree.htSaveNode(aBitStream : TtdOutputBitStream;

aNode : integer);

begin

{если этот узел является внутренним, выполнить запись нулевого бита, затем левого дочернего дерева, а затем - правого дочернего дерева}

if (aNode >= 256) then begin

aBitStream.WriteBit(false);

htSaveNode(aBitStream, FTree[aNode].hnLeftInx);

htSaveNode(aBitStream, FTree[aNode].hnRightInx);

end

{в противном случае узел является листом и нужно записать единичный бит, а затем символ}

else begin

aBitStream.WriteBit(true);

aBitStream.WriteByte (aNode);

{aNode - символ}

end;

end;

procedure THuffmanTree.SaveToBitStream(aBitStream : TtdOutputBitStream);

begin

htSaveNode(aBitStream, FRoot);

end;

Если бы во входном потоке присутствовало 100 отдельных символов, он содержал бы 99 внутренних узлов, и требовалось бы всего 199 битов для хранения информации об узлах плюс 100 байтов для хранения самих символов - всего около 125 байтов. Если бы во входном потоке были представлены все символы, требовалось бы 511 битов для хранения информации об узлах плюс место для хранения 256 символов. Таким образом, всего для хранения дерева требовалось бы 320 байтов.

Полный код подпрограммы сжатия дерева Хаффмана можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDHuffmn.pas.

После того, как мы рассмотрели реализацию сжатия Хаффмана, приступим к вопросу решения задачи восстановления данных. Код подпрограммы TDHuffmanDeconpress, управляющей этим процессом, приведен в листинге 11.12.

Листинг 11.12. Подпрограмма TDHuffmanDecoropress

procedure TDHuffmanDecompress(aInStream, aOutStream : TStream);

var

Signature : longint;

Size : longint;

HTree : THuffmanTree;

BitStrm : TtdInputBitStream;

begin

{выполнить проверку на предмет того, что входной поток является потоком, правильно закодированным методом Хаффмана}

aInStream.Seek(0, soFromBeginning);

aInStream.ReadBuffer(Signature, sizeof(Signature));

if (Signature <> TDHuffHeader) then

raise EtdHuffmanException.Create( FmtLoadStr(tdeHuffBadEncodedStrm,[UnitName, 'TDHuffmanDecompress']));

aInStream.ReadBuffer(Size, sizeof(longint));

{если данные для восстановления отсутствуют, осуществить выход из подпрограммы}

if (Size = 0) then

Exit;

{подготовиться к восстановлению}

HTree := nil;

BitStrm := nil;

try

{создать поток битов}

BitStrm := TtdInputBitStream.Create(aInStream);

BitStrm.Name := 'Huffman compressed stream';

{создать дерево Хаффмана}

HTree := THuffmanTree.Create;

{считать данные дерева из входного потока}

HTree.LoadFromBitStream(BitStrm);