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

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']));

aInStream.ReadBuffer(Size, sizeof(longint));

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

if (Size = 0) then

Exit;

{подготовиться к восстановлению}

STree := nil;

BitStrm := nil;

try

{создать поток битов}

BitStrm := TtdInputBitStream.Create(aInStream);

BitStrm.Name := 'Splay compressed stream';

{создать скошенное дерево}

STree := TSplayTree.Create;

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

DoSplayDecompression(BitStrm, aOutStream, STree, Size);

finally

BitStrm.Free;

STree.Free;

end;

end;

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

При наличии данных для восстановления мы создаем входной поток битов, который будет содержать входной поток и скошенное дерево. Затем для выполнения реального декодирования вызывается метод DoSplayDecompression (см. листинг 11.21).

Листинг 11.21. Цикл восстановления скошенного дерева

procedure DoSplayDecompression(aBitStream : TtdInputBitStream;

aOutStream : TStream;

aTree : TSplayTree;

aSize : longint);

var

CharCount : longint;

Ch : byte;

Buffer : PByteArray;

BufEnd : integer;

begin

GetMem(Buffer, SplayBufferSize);

try

{предварительная установка значений переменных цикла}

BufEnd := 0;

CharCount := 0;

{повторять цикл до тех пор, пока не будут восстановлены все символы}

while (CharCount < aSize) do

begin {считать следующий байт}

Buffer^[BufEnd] := aTree.DecodeByte(aBitStream);

inc(BufEnd);

inc(CharCount);

{записать буфер в случае его заполнения}

if (BufEnd = SplayBufferSize) then begin

aOutStream.WriteBuffer(Buffer^,SplayBufferSize);

BufEnd := 0;