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

Обработка начинается с известного состояния дерева. Можно было бы определить дерево, отражающее частоту употребления букв английского алфавита или какое либо иное распределение символов, но на практике значительно проще создать идеально сбалансированное дерево. В этом случае каждый узел имеет три "указателя", которые в действительности являются всего лишь индексами других узлов в массиве, и мы определяем его таким же образом, как делали при работе с сортирующим деревом: дочерние узлы узла с индексом 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']));

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;

end;

end;

{записать любые оставшиеся в буфере данные}

if (BufEnd <> 0) then

aOutStream.WriteBuffer(Buffer^, BufEnd);

finally

FreeMem(Buffer, SplayBufferSize);

end;

end;

Как и в цикле декодирования дерева Хаффмана, буфер заполняется декодированными байтами с последующей их записью в выходной поток. Реальное декодирование и запись выполняется методом DecodeByte класса скошенного дерева.

Листинг 11.22. Метод TSplayTree.DecodeByte

function TSplayTree.DecodeByte(aBitStream : TtdInputBitStream): byte;

var

NodeInx : integer;

begin

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

NodeInx := 0;

while NodeInx < 255 do

begin

if not aBitStream.ReadBit then

NodeInx := FTree[NodeInx].hnLeftInx else

NodeInx := FTree[NodeInx].hnRightInx;

end;

{вычислить байт, исходя из значения индекса конечного узла}

Result := NodeInx - 255;

{выполнить скос узла}

stSplay(NodeInx);

end;

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

Полный код реализации алгоритма сжатия с использованием скошенного дерева можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDSplyCm.pas.