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

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.

Вплоть до 1977 года, основные усилия в области исследования алгоритмов сжатия концентрировались вокруг алгоритмов кодирования с минимальной избыточностью, подобных алгоритмам Шеннона-Фано или Хаффмана, и были посвящены либо преобразованию их в динамические (чтобы таблица кодов не являлась частью сжатого файла), либо повышению быстродействия, уменьшению объема используемой памяти или увеличению эффективности. Затем неожиданно два израильских исследователя, Якоб Зив (Jacob Ziv) и Абрахам Лемпель (Abraham Lempel), представили принципиально иной метод сжатия и положили начало исследованиям в совершенно другом направлении. Их основная идея заключалась в кодировании не отдельных символов, а строк символов. Они задались целью использовать словарь ранее встречавшихся в сжимаемом файле фраз для кодирования последующих фраз.