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
hnLeftInx := Node1^.hnIndex;
hnRightInx Node2^.hnIndex;
hnCount := Node1^.hnCount + Node2^.hnCount;
end;
PQ.Enqueue(RootNode);
end;
end;
finally
PQ.Free;
end;
end;
Мы начинаем с создания экземпляра класса TtdPriorityQueue. Мы передаем ему подпрограмму CompareHuffmanNodes. Вспомним, что в созданной в главе 9 очереди по приоритету подпрограмма сравнения использовалась для возврата элементов в порядке убывания. Для создания сортирующего дерева с выбором наименьшего элемента, необходимой для создания дерева Хаффмана, мы изменяем цель подпрограммы сравнения, чтобы она возвращала положительное значение, если первый элемент меньше второго, и отрицательное, если он больше.
Как только очередь по приоритету создана, мы помещаем в нее все узлы с ненулевыми значениями счетчиков. В случае существования только одного такого узла, значение поля корневого узла дерева Хаффмана устанавливается равным индексу этого единственного узла. В противном случае мы применяем алгоритм Хаффмана, причем обращение к первому родительскому узлу осуществляется по индексу, равному 256. Удаляя из очереди два узла и помещая в нее новый родительский узел, мы поддерживаем значение переменной FRoot, чтобы она указывала на последний родительский узел. В результате по окончании процесса нам известен индекс элемента, представляющего корневой узел дерева.
И, наконец, мы освобождаем объект очереди по приоритету. Теперь дерево Хаффмана полностью построено.
Следующий метод, вызываемый в высокоуровневой подпрограмме сжатия - метод, который выполняет запись дерева Хаффмана в выходной поток битов. По существу, нам необходимо применить какой-либо алгоритм, выполняющий запись достаточного объема информации, чтобы можно было восстановить дерево. Одна из возможностей предусматривает запись символов и их значений счетчика появлений. При наличии этой информации программа восстановления может без труда восстановить дерево Хаффмана, просто вызывая метод htBuild. Это кажется здравой идеей, если не учитывать объем, занимаемый таблицей символов и количеств их появлений в сжатом выходном потоке. В этом случае каждый символ занимал бы в выходном потоке полный байт, а его значение счетчика занимало бы определенное фиксированное количество байтов (например, два байта на символ, чтобы можно было подсчитывать вплоть до 65535 появлений). При наличии во входном потоке 100 отдельных символов вся таблица занимала бы 300 байт. Если бы во входном потоке присутствовали все возможные символы, таблица занимала бы 768 байт.