NewQueue : PAnsiChar;
begin
{округлить запрошенный объем до ближайшего значения, кратного 64 байтам}
aValue := (aValue + 63) and $7FFFFFC0;
{распределить новый буфер}
GetMem(NewQueue, aValue * 2);
{уничтожить старый буфер}
if ( FBuffer <> nil ) then
FreeMem(FBuffer, FBufferEnd - FBuffer);
{установить начальный/конечный и другие указатели}
FBuffer := NewQueue;
FStart := NewQueue;
FCurrent := NewQueue;
FLookAheadEnd := NewQueue;
FBufferEnd := NewQueue + (aValue * 2);
FMidPoint := NewQueue + aValue;
end;
procedure TtdLZSlidingWindow.swWriteToStream(aFinalBlock : boolean);
var
BytesToWrite : longint;
begin
{записать данные перед текущим скользящим окном}
if aFinalBlock then
BytesToWrite := FCurrent - Fbuffer else
BytesToWrite := FStart - FBuffer;
FStream.WriteBuffer(FBuffer^, BytesToWrite);
end;
Метод AddChar добавляет одиночный литеральный символ в скользящее окно и сдвигает это окно вперед на один байт. Внутренний метод swAdvanceAfterAdd выполняет реальный сдвиг и после сдвига окна проверяет, может ли еще один блок быть записан в выходной поток. Метод AddCode добавляет пару расстояние/длина в скользящее окно, по одному копируя символы из уже декодированной части скользящего окна в текущую позицию. Затем скользящее окно сдвигается вперед.
Теперь достаточно легко создать код восстановления. (Создавать код восстановления раньше кода сжатия кажется несколько неестественным, но в действительности формат сжатых данных настолько определен, что это можно сделать. Кроме того, это проще!) Мы реализуем основной цикл в виде машины состояний с тремя состояниями: считывание и обработка байта флага, считывание и обработка символа и, наконец, считывание и обработка кода расстояния/длины. Код показан в листинге 11.24. Обратите внимание, что определение момента завершения восстановления осуществляется по количеству байтов в несжатом потоке, записанному программой сжатия в начало сжатого потока.
После проверки того, что входной поток является закодированным с применением алгоритма 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). Сигнатура хешируется с применением одного из методов, а затем хеш-значение используется для доступа к элементу в хеш-таблице, использующему связывание. Цепочки или связные списки в каждом элементе хеш-таблицы будут состоять из последовательностей элементов, каждый из которых состоит из трехсимвольных сигнатур и значения смещения сигнатуры во входном потоке.
Итак, мы получаем сигнатуру текущей позиции и хешируем ее в связный список, представляющий собой - одну из цепочек в хеш-таблице. Затем мы просматриваем связный список и сравниваем хранящуюся в нем сигнатуру каждого элемента с имеющимися сигнатурами. При обнаружении совпадающей сигнатуры мы переходим в скользящее окно, используя значение смещения элемента, а затем сравниваем символы в скользящем окне с символами в текущей позиции. Мы повторяем этот процесс для каждого элемента в связном списке, совпадающего с данной сигнатурой, и запоминаем наиболее длинное найденное соответствие.
После выполнения этого поиска, независимо от того, был ли он успешным или безуспешным, текущую сигнатуру нужно добавить в хеш-таблицу, чтобы ее можно было найти при сравнении последующими сигнатурами. Сигнатура добавляется в начало связного списка, чем обеспечивается сортировка связного списка в порядке убывания значений смещения.
Однако если не принять никаких специальных мер, количество элементов в хеш-таблице будет только возрастать, в то время как в действительности нам не нужны элементы, которые больше не присутствуют в 8-Кбайтном скользящем окне. Первым возможным решением этой проблемы может быть удаление элемента, который при следующем сдвиге скользящего окна должен исчезнуть из него. Для этого нужно было бы найти сигнатуру позиции (или, точнее говоря, позиций), которая должна исчезнуть из начала скользящего окна, хешировать ее, пройтись по связному списку, хранящемуся в этой позиции хеш-таблицы, с целью отыскания соответствующего элемента, а затем удалить его.
