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

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

на обложку

Бакнелл Джулиан М.

Шрифт:

HTree.CalcCharDistribution(aInStream);

{вывести дерево в поток битов для облегчения задачи программы восстановления данных}

HTree.SaveToBitStream (BitStrm);

{если корневой узел дерева Хаффмана является листом, входной поток состоит лишь из единственного повторяющегося символа, и следовательно, задача выполнена. В противном случае необходимо выполнить сжатие входного потока}

if not HTree.RootIsLeaf then begin

{распределить память под массив кодов}

New(HCodes);

{вычислить все коды}

HTree.CalcCodes(HCodes^ );

{сжать

символы входного потока в поток битов}

DoHuffmanCompression(aInStream, BitStrm, HCodes^ );

end;

finally

BitStrm.Free;

HTree.Free;

if (HCodes <> nil) then

Dispose(HCodes);

end;

Код содержит множество элементов, которые мы еще не рассматривали. Но мы вполне можем вначале рассмотреть работу программы в целом, а затем приступить к рассмотрению каждого отдельного этапа. Прежде всего, мы записываем в выходной поток небольшой заголовок, за которым следует значение длины входного потока. Впоследствии эта информация упростит задачу восстановления данных, гарантируя, что сжатый поток соответствует созданному нами. Затем мы создаем объект потока битов, содержащий выходной поток. Следующий шаг -создание экземпляра класса THuffmanTree. Этот класс, как вскоре будет показано, будет использоваться для создания дерева Хаффмана и содержит различные методы, помогающие в решении этой задачи. Один из методов этого нового объекта, вызываемых в первую очередь, метод CalcCharDistribution, определяет статистическую информацию распределения символов во входном потоке, а затем строит префиксное дерево Хаффмана.

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

Подпрограмма 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;