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

Бакнелл Джулиан М.

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), представили принципиально иной метод сжатия и положили начало исследованиям в совершенно другом направлении. Их основная идея заключалась в кодировании не отдельных символов, а строк символов. Они задались целью использовать словарь ранее встречавшихся в сжимаемом файле фраз для кодирования последующих фраз.