Первым методом, вызываемым для дерева Хаффмана в подпрограмме сжатия, был метод CalcCharDistribution. Это метод считывает входной поток, вычисляет количество появлений каждого символа, а затем строит дерево.
Листинг 11.9. Вычисление количеств появлений символов
procedure THuffmanTree.CalcCharDistribution(aStream : TStream);
var
i : integer;
Buffer : PByteArray;
BytesRead : integer;
begin
{считывать все байты с поддержанием счетчиков появлений для каждого значения байта, начиная с начала потока}
aStream.Position := 0;
GetMem(Buffer, HuffmanBufferSize);
try
BytesRead := aStream.Read(Buffer^, HuffmanBufferSize);
while (BytesRead <> 0) do
begin
for i := pred(BytesRead) downto 0 do
inc(FTree[Buffer^[i]].hnCount);
BytesRead := aStream.Read(Buffer^, HuffmanBufferSize);
end;
finally
FreeMem(Buffer, HuffmanBufferSize);
end;
{построить дерево}
htBuild;
end;
Как видно из листинга 11.9, большая часть кода метода вычисляет количества появлений символов и сохраняет эти значения в первых 256 узлах массива. Для повышения эффективности метод обеспечивает поблочное считывание входного потока (прежде чем выполнить цикл вычисления, он распределяет в куче большой блок памяти, а после вычисления освобождает его). И в завершение, в конце подпрограммы вызывается внутренний метод htBuild, выполняющий построение дерева.
Прежде чем изучить реализацию этого важного внутреннего метода, рассмотрим возможную реализацию алгоритма построения дерева. Вспомним, что мы начинаем с создания 'пула' узлов, по одному для каждого символа. Мы выбираем два наименьших узла (т.е. два узла с наименьшими значениями счетчиков) и присоединяем их к новому родительскому узлу (устанавливая значение его счетчика равным сумме значений счетчиков его дочерних узлов), а затем помещаем родительский узел обратно в пул. Мы продолжаем этот процесс до тех пор, пока в пуле не останется только один узел. Если вспомнить описанное в главе 9, станет очевидным, какую структуру можно использовать для реализации этого аморфного 'пула': очередь по приоритету. Строго говоря, мы должны использовать сортирующее дерево с выбором наименьшего элемента (обычно очередь по приоритету реализуется так, чтобы возвращать наибольший элемент).
Листинг 11.10. Построение дерева Хаффмана
function CompareHuffmanNodes(aData1, aData2 : pointer): integer; far;
var
Node1 : PHuffmanNode absolute aData1;
Node2 : PHuffmanNode absolute aData2;
begin
{ПРИМЕЧАНИЕ: эта подпрограмма сравнения предназначена для реализации очереди по приоритету Хаффмана, которая является *сортирующим деревом с выбором наименьшего элемента*. Поэтому она должна возвращать элементы в порядке, противоположном ожидаемому}
if (Node1^.hnCount) > (Node2^.hnCount) then
Result := -1
else
if (Node1^.hnCount) = (Node2^.hnCount)
then Result := 0
else Result := 1;
end;
procedure THuffmanTree.htBuild;
var
i : integer;
PQ : TtdPriorityQueue;
Node1 : PHuffmanNode;
Node2 : PHuffmanNode;
RootNode : PHuffmanNode;
begin
{создать очередь по приоритету}
PQ := TtdPriorityQueue.Create(CompareHuffmanNodes, nil);
try
PQ.Name := 'Huffman tree minheap';
{добавить в очередь все ненулевые узлы}
for i := 0 to 255 do
if (FTree[i].hnCount <> 0) then
PQ.Enqueue(@FTree[i]);
{ОСОБЫЙ СЛУЧАЙ: существует только один ненулевой узел, т.е. входной поток состоит только из одного символа, повторяющегося один или более раз. В этом случае значение корневого узла устанавливается равным значению индекса узла единственного символа}
if (PQ.Count = 1) then begin
RootNode := PQ.Dequeue;
FRoot := RootNode^.hnIndex;
end
{в противном случае имеет место обычный случай наличия множества различных символов}
else begin
{до тех пор, пока в очереди присутствует более одного элемента, необходимо выполнять удаление двух наименьших элементов, присоединять их к новому родительскому узлу и добавлять его в очередь}
FRoot := 255;
while (PQ.Count > 1) do
begin
Node1 := PQ.Dequeue;
Node2 := PQ.Dequeue;
inc(FRoot);
RootNode := @FTree[FRoot];
with RootNode^ do
begin
