Фундаментальные алгоритмы и структуры данных в Delphi - Джулиан Бакнелл

И, наконец, когда все эти структуры данных определены, мы вызываем подпрограмму 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. Это метод считывает входной поток, вычисляет количество появлений каждого символа, а затем строит дерево.

Листинг 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

{в противном случае имеет место обычный случай наличия множества различных символов}