После того, как дерево Хаффмана построено, можно вызвать метод SaveToBitStream, чтобы записать структуру дерева в выходной поток.
Затем мы выполняем обработку особого случая и небольшую оптимизацию. Если входной поток состоит всего лишь из нескольких повторений одного и того же символа, корневой узел дерева Хаффмана будет листом. Все префиксное дерево состоит всего из одного узла. В этом случае выходной поток битов будет содержать уже достаточно информации, чтобы программа восстановления могла восстановить исходный файл (мы уже записали в поток битов размер входного потока и единственный бит).
В противном случае входной поток должен содержать, по меньшей мере, два различных символа, и дерево Хаффмана имеет вид обычного дерева, а не единственного узла. В этом случае мы выполняем оптимизацию: вычисляем таблицу кодов для каждого символа, встречающегося во входном потоке. Это позволит сэкономить время на следующем этапе, когда будет выполняться реальное сжатие, поскольку нам не придется постоянно перемещаться по дереву для выполнения кодирования каждого символа. Массив HCodes - простой 256-элементный массив, содержащий коды всех символов и построенный посредством вызова метода CalcCodes объекта дерева Хаффмана.
И, наконец, когда все эти структуры данных определены, мы вызываем подпрограмму DoHuffmanCompression, выполняющую реальное сжатие данных. Код этой подпрограммы приведен в листинге 11.6.
Листинг 11.6. Цикл сжатия Хаффмана
procedure DoHuffmanCompression(aInStream : TStream;
aBitStream: TtdOutputBitStream;
var aCodes : THuffmanCodes);
var
i : integer;
Buffer : PByteArray;
BytesRead : longint;
begin
GetMem(Buffer, HuffmanBufferSize);
try
{сбросить входной поток в начальное состояние}
aInStream.Position := 0;
{считать первый блок из входного потока }
BytesRead := aInStream.Read(Buffer^, HuffmanBufferSize);
while (BytesRead <> 0) do
begin
{записать строку битов для каждого символа блока}
for i := 0 to pred(BytesRead) do aBitStream.WriteBits(aCodes[Buffer^[i]]);
{считать следующий блок из входного потока}
BytesRead := aInStream.Read(Buffer^, HuffmanBufferSize);
end;
finally
FreeMem(Buffer, HuffmanBufferSize);
end;
end;
Подпрограмма DoHuffmanCompression распределяет большой буфер для хранения считываемых из входного потока блоков данных, и будет постоянно считывать блоки из входного потока, сжимая их, до тех пор, пока поток не будет исчерпан. Такая буферизация данных служит простым методом оптимизации с целью повышения эффективности всего процесса. Для каждого символа блока подпрограмма записывает соответствующий код, полученный из массива aCodes, в выходной поток битов.
После того, как мы ознакомились с выполнением сжатия Хаффмана на высоком уровне, следует рассмотреть класс, выполняющий большую часть вычислений. Это внутренний класс THuffmanTree. Объявление связных с ним типов показано в листинге 11.7.
Вначале мы объявляем узел дерева Хаффмана THaffxnanNode и массив этих узлов THaffmanNodeArray фиксированного размера. Этот массив будет использоваться для создания реальной структуры дерева и будет содержать ровно 511 элементов. Почему именно это количество?
Это число определяется небольшой теоремой (или леммой) о свойствах бинарного дерева, которая еще не упоминалась.
Листинг 11.7. Класс дерева Хаффмана
type
PHuffmanNode = ^THuffmanNode;
THuffmanNode = packed record
hnCount : longint;
hnLeftInx : longint;
hnRightInx : longint;
hnIndex : longint;
end;
PHuffmanNodeArray = ^THuffmanNodeArray;
THuffmanNodeAr ray = array [0..510] of THuffmanNode;
type
THuffmanCodeStr = string[255];
type
PHuffmanCodes = ^THuffmanCodes;
THuffmanCodes = array [0..255] of TtdBitString;
type
THuffmanTree = class private
FTree : THuffmanNodeArray;
FRoot : integer;
protected
procedure htBuild;
procedure htCalcCodesPrim( aNodeInx : integer;
var aCodeStr : THuffmanCodeStr;
var aCodes : THuffmanCodes);
function htLoadNode( aBitStream : TtdInputBitStream): integer;
procedure htSaveNode(aBitStream : TtdOutputBitStream;
aNode : integer);
public
constructor Create;
procedure CalcCharDistribution(aStream : TStream);
procedure CalcCodes(var aCodes : THuffmanCodes);
function DecodeNextByte(aBit St ream : TtdInputBitStream): byte;
procedure LoadFromBitStream(aBitStream : TtdInputBitStream);
function RootIsLeaf : boolean;
procedure SaveToBitStream(aBitStream : TtdOutputBitStream);
property Root : integer read FRoot;
end;
Предположим, что дерево содержит только два типа узлов: внутренние, имеющие ровно по два дочерних узла, и листья, не имеющие узлов (иначе говоря, не существует узлов, имеющих только один дочерний узел, - именно такой вид имеет префиксное дерево). Сколько внутренних узлов имеет это дерево, если оно содержит n листьев? Лемма утверждает, что такое дерево содержит ровно n - 1 внутренних узлов. Это утверждение можно доказать методом индукции. Когда n = 1, лемма явно выполняется, поскольку дерево содержит только корневой узел.