Текст книги "Фундаментальные алгоритмы и структуры данных в Delphi"
Автор книги: Джулиан Бакнелл
сообщить о нарушении
Текущая страница: 31 (всего у книги 36 страниц)
Теперь предположим, что лемма справедлива для всех 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
{в противном случае имеет место обычный случай наличия множества различных символов}
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);
{если буфер заполнен, необходимо выполнить его запись}
if (BufEnd = HuffmanBufferSize) then begin
aOutStream.WriteBuffer(Buffer^, HuffmanBufferSize);
BufEnd := 0;
end;
end;
{если в буфере остались какие-либо данные, необходимо выполнить его запись}
if (BufEnd <> 0) then
aOutStream.WriteBuffer(Buffer^, BufEnd);
finally
FreeMem(Buffer, HuffmanBufferSize);
end;
end;
По существу подпрограмма представляет собой цикл, внутри которого многократно выполняется декодирование байтов и заполнение буфера. Когда буфер заполняется, мы записываем его в выходной поток и начинаем заполнять его снова. Декодирование выполняется при помощи метода DecodeNextByte класса THuffmanTree.
Листинг 11.14. Метод DecodeNextByte
function THuffmanTree.DecodeNextByte(aBitStream : TtdInputBitStream): byte;
var
NodeInx : integer;
begin
NodeInx := FRoot;
while (NodeInx >= 256) do
begin
if not aBitStream.ReadBit then
NodeInx := FTree[NodeInx].hnLeftInx else
NodeInx := FTree[NodeInx].hnRightInx;
end;
Result := NodeInx;
end;
Этот метод крайне прост. Он просто начинает обработку с корневого узла дерева Хаффмана, а затем для каждого бита, считанного из входного потока битов, в зависимости от того, был ли он нулевым или единичным, выполняет переход по левой или правой связи. Как только подпрограмма достигает листа, она возвращает индекс достигнутого узла (его значение будет меньше или равно 255). Этот узел является декодированным байтом.
Полный код выполнения восстановления дерева Хаффмана можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDHuffmn.pas.
Кодирование с использованием скошенного дерева
Как было показано, и кодирование Шеннона-Фано, и кодирование Хаффмана связано со значительной проблемой – необходимостью поставлять дерево вместе со сжатыми данными. Это является недостатком, поскольку трудно добиться существенного сжатия дерева, что ведет к снижению коэффициента сжатия данных. Еще один недостаток применения этих методов состоит в том, что входные данные приходится считывать дважды: первый раз для вычисления частоты появления символов в данных, а второй – сразу после построения дерева при выполнении действительного кодирования данных.
Не существует ли какой-либо способ исключения необходимости поставки дерева или двукратного считывания входных данных (желательно было бы избавиться от обоих этих недостатков)? Существует вариант сжатия Хаффмана, называемый адаптивным кодированием Хаффмана, который позволяет это сделать. Однако в этой главе мы рассмотрим малоизвестную адаптивную технологию, использующую скошенные деревья, с которыми мы впервые встретились в главе 8.
Дуглас В. Джонс (Douglas W. Jones) разработал сжатие с использованием скошенного дерева в 1988 году [8]. Если помните, в главе 8 говорилось, что скошенные деревья – это метод балансировки дерева бинарного поиска посредством скоса достигнутого узла к корневому узлу. Таким образом, после отыскания узла он перемещается к корневому узлу с помощью ряда поворотов, называемых операциями двустороннего и одностороннего поворота. В результате скоса узлы, обращение к которым осуществляется наиболее часто, оказываются, как правило, в верхней части дерева, а узлы, обращение к которым происходит реже – ближе к листьям. Если применить эту стратегию к префиксному дереву и закодировать символы, как это делалось при использовании алгоритмов Хаффмана и Шеннона-Фано (левая связь кодируется нулевым битом, а правая единичным), окажется, что со временем кодирование данного символа будет меняться. Дерево будет приспосабливаться к частоте появления закодированных символов. Более того, наиболее часто используемые символы будут располагаться вблизи вершины дерева и, следовательно, как правило, их коды будут короче кодов реже используемых символов.
Следует признать, что скошенные деревья были разработаны для оптимизации деревьев бинарного поиска, т.е. упорядоченных деревьев. Частично их полезность обусловлена тем, что операции скоса поддерживают упорядоченность во время различных поворотов и трансформаций. Префиксные деревья не упорядочены, поэтому можно избежать большей части сложного манипулирования указателями, связного с поворотами. Кроме того, потребуется обеспечить, чтобы листья оставались листьями. В противном случае дерево перестало бы быть префиксным. Поэтому мы будем использовать скос, в результате которого родительский узел листа перемещается ближе к корневому узлу.
Код реализации базового алгоритма выполнения сжатия выглядит подобно приведенному в листинге 11.15.
Листинг 11.15. Базовый алгоритм сжатия с использованием скошенного дерева
procedure TDSplayCompress(aInStream, aOutStream : TStream);
var
STree : TSplayTree;
BitStrm : TtdOutputBitStream;
Signature : longint;
Size : longint;
begin
{вывести информацию заголовка сигнатуру и размер несжатых данных}
Signature := TDSplayHeader;
aOutStream.WriteBuffer(Signature, sizeof(longint));
Size := aInStream.Size;
aOutStream.WriteBuffer(Size, sizeof(longint));
{в случае отсутствия данных для сжатия выйти из подпрограммы}
if (Size = 0) then
Exit;
{подготовка}
STree := nil;
BitStrm := nil;
try
{создать сжатый поток битов}
BitStrm := TtdOutputBitStream.Create(aOutStream);
BitStrm.Name := 'Splay compressed stream';
{создать скошенное дерево}
STree := TSplayTree.Create;
{сжатье символы входного потока и поместить их в поток битов}
DoSplayCompression(aInStream, BitStrm, STree);
finally
BitStrm.Free;
STree.Free;
end;
end;
Для пометки выходного потока как сжатого с использованием скошенного дерева в выходной поток мы записываем сигнатуру типа длинного целого, а затем записываем размер несжатого потока. Если входной поток пуст, выполняется выход из подпрограммы, – в этом случае задача выполнена. В противном случае мы создаем выходной поток битов, который будет содержать выходной поток и скошенное дерево. Затем для выполнения реального сжатия мы вызываем метод DoSplayConapression. Код этой подпрограммы приведен в листинге 11.16.
Листинг 11.16. Цикл выполнения сжатия с использованием скошенного дерева
procedure DoSplayCompression(aInStream : TStream;
aBitStream : TtdOutputBitStream;
aTree : TSplayTree);
var
i : integer;
Buffer : PByteArray;
BytesRead : longint;
BitString : TtdBitString;
begin
GetMem(Buffer, SplayBufferSize);
try
{сбросить входной поток в исходное состояние}
aInStream.Position := 0;
{считать первый блок из входного потока}
BytesRead := aInStream.Read(Buffer^, SplayBufferSize);
while (BytesRead <> 0) do
begin
{записать строку битов для каждого символа в блоке}
for i := 0 to pred(BytesRead) do aTree.EncodeByte(aBitStream, Buffer^[i]);
{считать следующий блок из входного потока}
BytesRead := aInStream.Read(Buffer^, SplayBufferSize);
end;
finally
FreeMem(Buffer, SplayBufferSize);
end;
end;
Фактически эта подпрограмма представляется собой подпрограмму выполнения вложенного цикла. Во внешнем цикле выполняется поблочное считывание входного потока, а во внутреннем (через вызов метода EncodeByte скошенного дерева) -кодирование каждого байта текущего блока и запись результирующего кода в выходной поток битов.
Теперь пора рассмотреть внутренний класс TSplayTree, который выполняет основную часть работы по реализации алгоритма сжатия с использованием скошенного дерева. Код интерфейса этого класса показан в листинге 11.17.
Листинг 11.17. Класс сжатия с использованием скошенного дерева
type
PSplayNode = ^TSplayNode;
TSplayNode = packed record
hnParentInx: longint;
hnLeftInx : longint;
hnRightInx : longint;
hnIndex : longint;
end;
PSplayNodeArray = ^TSplayNodeArray;
TSplayNodeArray = array [0..510] of TSplayNode;
type
TSplayTree = class private
FTree : TSplayNodeArray;
FRoot : integer;
protected
procedure stConvertCodeStr(const aRevCodeStr : ShortString;
var aBitString : TtdBitString);
procedure stInitialize;
procedure stSplay(aNode!nx : integer);
public
constructor Create;
procedure EncodeByte(aBitStream : TtdOutputBitStream; aValue : byte);
function DecodeByte(aBitStream : TtdInputBitStream): byte;
end;
Хотя можно было бы воспользоваться ориентированным на узлы деревом, как это делалось в главе 8, поскольку нам известно количество символов в используемом алфавите (в общем случае используется алфавит, содержащий 256 символов), проще отдать предпочтение применению ориентированной на массивы системе, подобной структуре данных типа сортирующего дерева и дерева Хаффмана. Еще один аргумент в пользу перехода на использование других структур данных состоит в том, что в случае применения неадаптивных методов сжатия можно было строить таблицу кодов, так как они были статическими. При использовании сжатия с применением скошенного дерева битовый код символа зависит от состояния скошенного дерева и момента времени кодирования символа. В этом случае мы больше не можем использовать статическую таблицу. Следовательно, одно из выдвигаемых требований – возможность быстрого и эффективного поиска символа в дереве (предпочтительно при помощи алгоритма типа O(1) – мы не хотим его искать). Как только символ и его узел листа определены, можно легко выполнить обход вверх по дереву до корневого узла с целью вычисления кода символа (вообще говоря, мы получим битовый код с обратным порядком следования битов, но с помощью стека его легко можно изменить на противоположный).
Обработка начинается с известного состояния дерева. Можно было бы определить дерево, отражающее частоту употребления букв английского алфавита или какое либо иное распределение символов, но на практике значительно проще создать идеально сбалансированное дерево. В этом случае каждый узел имеет три "указателя", которые в действительности являются всего лишь индексами других узлов в массиве, и мы определяем его таким же образом, как делали при работе с сортирующим деревом: дочерние узлы узла с индексом n располагаются в позициях 2n + 1 и 2n + 2, а его родительский узел – в позиции (n – 1)/2. Поскольку в действительности узлы не будут перемещаться в массив (мы собираемся манипулировать только индексами), позиции листьев всегда будут известны. Они всегда будут занимать одни и те же позиции в массиве: #0 всегда будет находиться в позиции с индексом 255, #1 – в позиции с индексом 256 и т.д. Код метода, выполняющего инициализацию дерева, показан в листинге 11.18. Этот метод вызывается из конструктора Create.
Листинг 11.18. Метод stInitialize
procedure TSplayTree.stInitialize;
var
i : integer;
begin
{создать полностью сбалансированное дерево; корневой узел будет соответствовать нулевому элементу; родительский узел узла n будет располагаться в позиции (n-1) /2, а его дочерние узлы – в позициях 2n+1 и 2n+2}
FillChar(FTree, sizeof(FTree), 0);
for i := 0 to 254 do
begin
FTree[i].hnLeftInx := (2 * i) + 1;
FTree[i].hnRightInx := (2 * i) + 2;
end;
for i := 1 to 510 do
FTree[i].hnParentInx := (i – 1) div 2;
end;
constructor TSplayTree.Create;
begin
inherited Create;
stInitialize;
end;
При сжатии символа мы находим его узел в дереве. Затем мы выполняем переходы вверх по дереву, сохраняя соответствующие биты в стеке (левой связи соответствует нулевой бит, а правой – единичный). По достижении корневого узла можно вытолкнуть биты из стека. Они определят код символа (в коде, приведенном в листинге 11.19, в качестве стека используется короткая строка).
Затем выполняется скос родительского узла по направлению к корневому узлу. Мы не выполняем скос к корню самого узла символа ввиду того, что требуется сохранить размещение символов в узлах листьев. В противном случае было бы совершенно исключено, чтобы код одного символа становился началом кода следующего. Скос родительского узла повлечет "перетаскивание" вместе с ним и дочернего узла. В результате чаще используемые символы окажутся ближе к верхушке дерева.
Листинг 11.19. Методы EncodeByte и stSplay
procedure TSplayTree.EncodeByte(aBitStream : TtdOutputBitStream;
aValue : byte)/
var
NodeInx : integer;
ParentInx : integer;
RevCodeStr : ShortString;
BitString : TtdBitString;
begin
{начиная с узла aValue, сохранить на каждом шаге (0) бит при перемещении вверх по дереву по левой связи и (1) бит при перемещении по правой связи}
RevCodeStr := 1 ';
NodeInx := aValue + 255;
while (NodeInx <> 0) do
begin
ParentInx := FTree[NodeInx].hnParentInx;
inc(RevCodeStr[0]);
if (FTree[ParentInx].hnLeftInx = NodeInx) then
RevCodeStr[length(RevCodeStr)] := f0' else
RevCodeStr[length(RevCodeStr)] := ' 11;
NodeInx := ParentInx;
end;
{преобразовать строковый код в строку битов}
stConvertCodeStr(RevCodeStr, BitString);
{записать строку битов в поток битов}
aBitStream.WriteBits(BitString);
{выполнить скос узла}
stSplay(aValue + 255);
end;
procedure TSplayTree.stConvertCodeStr(const aRevCodeStr : ShortString;
var aBitString : TtdBitString);
var
ByteNum : integer;
i : integer;
Mask : byte;
Accum : byte;
begin
{подготовиться к выполнению цикла преобразования}
ByteNum := 0;
Mask := 1;
Accum := 0;
{преобразовать порядок следования битов на противоположный}
for i := length (aRevCodeStr) downto 1 do
begin
if (aRevCodeStr[i] = '1') then
Accum := Accum or Mask;
Mask := Mask shl 1;
if (Mask = 0) then begin
aBitString.bsBits[ByteNum] := Accum;
inc(ByteNum);
Mask := 1;
Accum :– 0;
end;
end;
{сохранить биты, расположенные слева от текущего}
if (Mask <> 1) then
aBitString.bsBits [ByteNum] := Accum;
{сохранить двоичный код в массиве кодов}
aBitString.bsCount := length(aRevCodeStr);
end;
procedure TSplayTree.stSplay(aNodeInx : integer);
var
Dad : integer;
GrandDad : integer;
Uncle : integer;
begin
{выполнить скос узла}
repeat
{извлечь родительский узел данного узла}
Dad := FTree[aNodeInx].hnParentInx;
{если родительский узел является корневым, задача выполнена}
if (Dad= 0) then
aNodeInx := 0
{в противном случае необходимо выполнить поворот узла на 90 градусов с целью его перемещения вверх по дереву}
else begin
{извлечь родительский узел родительского узла}
GrandDad := FTree[Dad].hnParentInx;
{выполнить поворот на 90 градусов (т.е. поменять мечтами узел и его узел-дядю)}
if (FTree[GrandDad].hnLeftInx = Dad) then begin
Uncle := FTree[GrandDad].hnRightInx;
FTree[GrandDad].hnRightInx := aNodeInx;
end
else begin
Uncle := FTree[GrandDad].hnLeftInx;
FTree[GrandDad].hnLeftInx := aNodeInx;
end;
if (FTree[Dad].hnLeftInx = aNodeInx) then
FTree[Dad].hnLeftInx := Uncle
else
FTree[Dad].hnRightInx := Uncle;
FTree[Uncle].hnParentInx := Dad;
FTree[aNodeInx].hnParentInx :=GrandDad;
{возобновить цикл с узла-деда}
aNodeInx :=GrandDad;
end;
until (aNodeInx = 0);
end;
При восстановлении мы устанавливаем дерево в исходную конфигурацию, как это делалось на этапе сжатия. Затем мы по одному выбираем биты из потока битов и выполняем обычное перемещение вниз по дереву. По достижении листа, содержащего символ (который мы выводим в качестве восстановленных данных), мы будем выполнять скос родительского узла данного узла к корню дерева. При условии, что обновление дерева выполняется одинаково и во время сжатия, и во время восстановления, алгоритм декодирования может поддерживать дерево в том же состоянии, что и на соответствующем этапе выполнения алгоритма кодирования.
Листинг 11.20. Базовый алгоритм восстановления скошенного дерева
procedure TDSplayDecompress(aInStream, aOutStream : TStream);
var
Signature : longint;
Size : longint;
STree : TSplayTree;
BitStrm : TtdInputBitStream;
begin
{выполнить проверку того, что входной поток является корректно закодированным с использованием скошенного дерева}
aInStream.Seek(0, soFromBeginning);
aInStream.ReadBuffer(Signature, sizeof(Signature));
if (Signature <> TDSplayHeader) then
raise EtdSplayException.Create(FmtLoadStr(tdeSplyBadEncodedStrm,
[UnitName, 'TDSplayDecompress']));
