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

После проверки того, что входной поток является закодированным с применением алгоритма LZ77, программа считывает количество несжатых данных. Затем осуществляется вход в простую машину состояний, состояния которой определяются байтом флага, считываемого из входного потока. Если текущее состояние -dsGetFlagByte, программа считывает из входного потока следующий байт флага. Если состояние - dsGetChar, программа считывает из входного потока литеральный символ и добавляет его в скользящее окно. В противном случае состоянием будет dsGetDistLen, и программа считывает из входного потока пару расстояние/ длина и добавляет ее в скользящее окно. Этот процесс продолжается до тех пор, пока не будут восстановлены все данные входного потока.

Листинг 11.24. Основной код программы сжатия, использующей алгоритм LZ77

procedure TDLZDecompress(aInStream, aOutStream : TStream);

type

TDecodeState = (dsGetFlagByte, dsGetChar, dsGetDistLen);

var

SlideWin : TtdLZSlidingWindow;

BytesUnpacked : longint;

TotalSize : longint;

LongValue : longint;

DecodeState : TDecodeState;

FlagByte : byte;

FlagMask : byte;

NextChar : AnsiChar;

NextDistLen : longint;

CodeCount : integer;

Len : integer;

begin

SlideWin := TtdLZSlidingWindow.Create(aOutStream, false);

try

SlideWin.Name := 'LZ77 Decompress sliding window';

{считать из потока заголовок: символы 'TDLZ', за которыми следует размер входного потока}

aInStream.ReadBuffer(LongValue, sizeof(LongValue));

if (LongValue <> TDLZHeader) then

RaiseError(tdeLZBadEncodedStream, 'TDLZDecompress');

aInStream.ReadBuffer(TotalSize, sizeof(TotalSize));

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

BytesUnpacked := 0;

NextDistLen := 0;

DecodeState := dsGetFlagByte;

CodeCount := 0;

FlagMask := 1;

{до тех nop, пока остаются байты для восстановления...}

while (BytesUnpacked < TotalSize) do

begin

{считывать следующий элемент в данном состоянии декодирования}

case DecodeState of

dsGetFlagByte : begin

aInStream.ReadBuffer(FlagByte, 1);

CodeCount := 0;

FlagMask := 1;

end;

dsGetChar : begin

aInStream.ReadBuffer(NextChar, 1);

SlideWin.AddChar(NextChar);

inc(BytesUnpacked);

end;

dsGetDistLen : begin

aInStream.ReadBuffer(NextDistLen, 2);

Len := (NextDistLen and tdcLZLengthMask) + 3;

SlideWin.AddCode( (NextDistLen shr tdcLZDistanceShift) + 1, Len);

inc(BytesUnpacked, Len);

end;

end;

{вычислить следующее состояние декодирования}

inc(CodeCount);

if (CodeCount > 8) then

DecodeState := dsGetFlagByte else begin

if ((FlagByte and FlagMask) = 0) then

DecodeState := dsGetChar

else

DecodeState := dsGetDistLen;

FlagMask := FlagMask shl 1;

end;

end;

finally

SlideWin.Free;

end;

{try.. finally}

end;

Сжатие LZ77

Теперь пора рассмотреть реализацию сжатия. При этом очень быстро мы сталкиваемся со следующей проблемой: поиском наиболее длинного соответствия между строкой в текущей позиции и предшествующими 8192 байтами. От одного возможного метода - поиска во всем буфере - придется полностью отказаться из-за его слишком низкой эффективности.

В своей первоначальной работе Зив и Лемпель не предложили почти никаких решений. Кое-кто использует дерево бинарного поиска, построенное поверх скользящего окна, для хранения максимальных встречавшихся совпадающих строк (примером может служить реализация, созданная Марком Нельсоном (Mark Nelson) [15]). Однако применение этого метода приводит к возникновению проблем, связанных с тем, что нужно беспокоиться о балансировке дерева и об избавлении от строк, которые должны быть удалены из скользящего окна. Поэтому мы воспользуемся советом, приведенным в онлайновом документе Deflate Compressed

Data Format Specification (Спецификация формата данных, сжатых методом Deflate) (RFC 1951) и применим хеш-таблицу.

Алгоритм выглядит следующим образом: мы просматриваем три символа в текущей позиции - будем называть их сигнатурой (signature). Сигнатура хешируется с применением одного из методов, а затем хеш-значение используется для доступа к элементу в хеш-таблице, использующему связывание. Цепочки или связные списки в каждом элементе хеш-таблицы будут состоять из последовательностей элементов, каждый из которых состоит из трехсимвольных сигнатур и значения смещения сигнатуры во входном потоке.

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

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