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

Более рациональный подход - игнорировать значения счетчиков символов и сохранять реальную структуру дерева. Префиксное дерево содержит два различных вида узлов: внутренние с двумя дочерними узлами и внешние, не имеющие дочерних узлов. Внешние узлы - это узлы, содержащие символы. Выполним обход дерева, применив один из обычных методов обхода (фактически, мы будем использовать метод обхода в ширину). Для каждого достигнутого узла будем записывать нулевой бит, если узел является внутренним, или единичный бит, если узел является внешним, за которым будет следовать представляемый узлом символ. Код реализации метода 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);

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

if HTree.RootIsLeaf then

WriteMultipleChars(aOutStream, AnsiChar(HTree.Root), Size) {в противном случае выполнить восстановление символов входного потока посредством использования дерева Хаффмана}

else

DoHuffmanDecompression(BitStrm, aOutStream, HTree, Size);

finally

BitStrm.Free;

HTree.Free;

end;

end;

Прежде всего, мы проверяем, начинается ли поток с корректной сигнатуры. Если нет, не имеет смысла продолжать процесс, поскольку поток явно содержит ошибки.

Затем выполняется считывание длины несжатых данных, и если она равна нулю, задача выполнена. В противном случае необходимо проделать определенную работу. В этом случае мы создаем входной поток битов, содержащий входной поток. Затем мы создаем объект дерева Хаффмана, который будет выполнять большую часть работы, и вынуждаем его выполнить собственное считывание из входного потока битов (вызывая для этого метод LoadFromBitStream). Если дерево Хаффмана представляет единственный символ, исходный поток восстанавливается в виде повторений этого символа. В противном случае мы вызываем подпрограмму DoHuffmanDecoonpression для выполнения восстановления данных. Код этой подпрограммы приведен в листинге 11.13.

Листинг 11.13. Подпрограмма DoHuffmanDecompression

procedure DoHuffmanDecompression( aBitStream : TtdInputBitStream;

aOutStream : TStream; aHTree : THuffmanTree; aSize : longint);

var

CharCount : longint;

Ch : byte;

Buffer : PByteArray;

BufEnd : integer;

begin

GetMem(Buffer, HuffmanBufferSize);

try

{предварительная установка переменных цикла}