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

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