После того, как дерево Хаффмана построено, можно вызвать метод 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, лемма явно выполняется, поскольку дерево содержит только корневой узел.

Теперь предположим, что лемма справедлива для всех i < n, где n < 1, и рассмотрим случай, когда i = n. В этом случае дерево должно содержать, по меньшей мере, один внутренний узел - корневой. Этот корневой узел имеет два дочерних дерева: левое и правое. Если левое дочернее дерево имеет x листьев, то, согласно сделанному нами допущению, оно должно содержать x - 1 внутренних узлов, поскольку x < n. Аналогично, согласно сделанному допущению, если правое дочернее дерево имеет y листьев, оно должно содержать y - 1 внутренних узлов. Все дерево содержит n листьев, причем это число должно быть равно X + Y (вспомните, что корневой узел является внутренним). Следовательно, количество внутренних узлов равно (x-1) + (y-1) + 1, что составляет в точности n-1.

Чем же эта лемма может нам помочь? В префиксном дереве все символы должны храниться в листьях. В противном случае было бы невозможно получить однозначные коды. Следовательно, независимо от его внешнего вида, префиксное дерево, подобное дереву Хаффмана, будет содержать не более 511 узлов: не более 256 листьев и не более 255 внутренних узлов. Следовательно, мы должны быть в состоянии реализовать дерево Хаффмана (по крайней мере, обеспечивающее кодирование значений байтов) в виде 511-элементного массива.

Структура узла включает в себя поле счетчика (содержащее значение общего количества появлений символов для самого узла и всех его дочерних узлов), индексы левого и правого дочерних узлов и, наконец, поле, содержащее индекс самого этого узла (эта информация облегчит построение дерева Хаффмана).

Причина выбора типов кода Хаффмана (THuffmanCodeStr и THuffmanCodes) станет понятной после рассмотрения генерации кодов для каждого из символов.

Конструктор Create класса дерева Хаффмана всего лишь выполняет инициализацию внутреннего массива дерева.

Листинг 11.8. Конструирование объекта дерева Хаффмана

constructor THuffmanTree.Create;

var

i : integer;

begin

inherited Create;

FillChar(FTree, sizeof(FTree), 0);

for i := 0 to 510 do

FTree[i].hnIndex := i;

end;

Поскольку конструктор не распределяет никакой памяти, и никакое распределение памяти не выполняется ни в каком другом объекте класса, явному деструктору нечего делать. Поэтому по умолчанию класс использует метод TObject.Destroy.

Первым методом, вызываемым для дерева Хаффмана в подпрограмме сжатия, был метод CalcCharDistribution. Это метод считывает входной поток, вычисляет количество появлений каждого символа, а затем строит дерево.