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

Дуглас В. Джонс (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;