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

• Название: Фундаментальные алгоритмы и структуры данных в Delphi
• Автор: Джулиан Бакнелл
• Издательство: ДиаСофтЮП
• Жанр: Программирование
• Год: 2003
• ISBN: ISBN 5-93772-087-3

Книга "Фундаментальные алгоритмы и структуры данных в Delphi" представляет собой уникальное учебное и справочное пособие по наиболее распространенным алгоритмам манипулирования данными, которые зарекомендовали себя как надежные и проверенные многими поколениями программистов. По данным журнала "Delphi Informant" за 2002 год, эта книга была признана сообществом разработчиков прикладных приложений на Delphi как «самая лучшая книга по практическому применению всех версий Delphi».

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

Несмотря на то что книга рассчитана в первую очередь на профессиональных разработчиков приложений на Delphi, она окажет несомненную пользу и начинающим программистам, демонстрируя им приемы и трюки, которые столь популярны у истинных «профи». Все коды примеров, упомянутые в книге, доступны для выгрузки на Web-сайте издательства.

---

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

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