Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
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 байт.
Другой возможный способ - хранение значений счетчика для каждого символа. В этом случае для всех символов, в том числе для отсутствующих во входном потоке, требуется два фиксированных байта. В результате общий размер таблицы во всех ситуациях составил бы 512 байт. Честно говоря, этот результат не многим лучше предыдущего.
Конечно, если бы входной поток был достаточно большим, некоторые из значений счетчиков могли бы превысить размер 2-байтового слова, и для каждого символа пришлось бы использовать по три или даже четыре байта.
Более рациональный подход - игнорировать значения счетчиков символов и сохранять реальную структуру дерева. Префиксное дерево содержит два различных вида узлов: внутренние с двумя дочерними узлами и внешние, не имеющие дочерних узлов. Внешние узлы - это узлы, содержащие символы. Выполним обход дерева, применив один из обычных методов обхода (фактически, мы будем использовать метод обхода в ширину). Для каждого достигнутого узла будем записывать нулевой бит, если узел является внутренним, или единичный бит, если узел является внешним, за которым будет следовать представляемый узлом символ. Код реализации метода 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
{предварительная установка переменных цикла}
BufEnd := 0;
CharCount := 0/
{повторять процесс до тех пор, пока не будут восстановлены все символы}
while (CharCount < aSize) do
begin
{считать следующий байт}
Ch := aHTree.DecodeNextByte (aBitStream);
Buffer^[BufEnd] :=Ch;
inc(BufEnd);
inc(CharCount);
{если буфер заполнен, необходимо выполнить его запись}
