Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
FStart : PAnsiChar;{начало скользящего окна}
FStartOffset : longint;{смещение потока для FStart}
FStream : TStream;{базовый поток}
protected
procedure swAdvanceAfterAdd(aCount : integer);
procedure swReadFromStream;
procedure swSetCapacity(aValue : longint);
procedure swWriteToStream(aFinalBlock : boolean);
public
constructor Create(aStream : TStream;
aCompressing : boolean);
destructor Destroy; override;
{методы, используемые как во время сжатия, так и во время восстановления}
procedure Clear;
{методы, используемые во время сжатия}
procedure Advance(aCount : integer);
function Compare(aOffset : longint;
var aDistance : integer): integer;
procedure GetNextSignature(var aMS : TtdLZSignature;
varaOffset : longint);
{методы, используемые во время восстановления}
procedure AddChar(aCh : AnsiChar);
procedureAddCode(aDistance : integer;
aLength : integer);
property Name : TtdNameString read FName write FName;
end;
constructor TtdLZSlidingWindow.Create(aStream : TStream;
aCompressing : boolean);
begin
inherited Create;
{сохранить параметры}
FCompressing := aCompressing;
FStream := aStream;
{установить размер скользящего окна: согласно принятого определения размер скользящего окна равен 8192 байтам плюс 10 байтов для упреждающего просмотра}
swSetCapacity(tdcLZSlidingWindowSize + tdcLZLookAheadSize);
{сбросить буфер и, если выполняется сжатие, считать определенные данные из сжимаемого потока}
Clear;
if aCompressing then
swReadFromStream;
end;
destructor TtdLZSlidingWindow.Destroy;
begin
if Assigned(FBuffer) then begin
{завершить запись в выходной поток, если выполняется сжатие}
if not FCompressing then
swWriteToStream(true);
{освободить буфер}
FreeMem(FBuffer, FBufferEnd - FBuffer);
end;
inherited Destroy;
end;
procedure TtdLZSlidingWindow.AddChar(aCh : AnsiChar);
begin
{добавить символ в буфер}
FCurrent^ :=aCh;
{сместить скользящее окно на один символ}
swAdvanceAfterAdd(1);
end;
procedure TtdLZSlidingWindow.AddCode(aDistance : integer;
aLength : integer);
var
FromChar : PAnsiChar;
ToChar : PAnsiChar;
i : integer;
begin
{установить указатели для выполнения копирования данных; обратите внимание, что в данном случае нельзя использовать процедуру Move, поскольку часть копируемых данных может быть определена реальным копированием данных}
FromChar := FCurrent - aDistance;
ToChar := FCurrent;
for i := 1 to aLength do
begin
ToChar^ := FromChar^;
inc(FromChar);
inc(ToChar);
end;
{сместить начало скользящего окна}
swAdvanceAfterAdd(aLength);
end;
procedure TtdLZSlidingWindow.swAdvanceAfterAdd(aCount : integer);
begin
{при необходимости сместить начало скользящего окна}
if ( (FCurrent - FStart) >= tdcLZSlidingWindowSize) then begin
inc(FStart, aCount);
inc(FStartOffset, aCount);
end;
{сместить текущий указатель}
inc(FCurrent, aCount);
{проверить смещение в зону переполнения}
if (FStart >= FMidPoint) then begin
{записать дополнительные данные в поток (от позиции FBuffer до позиции FStart)}
swWriteToStream(false);
{переместить текущие данные обратно в начало буфера}
Move(FStart^, FBuffer^, FCurrent - FStart );
{сбросить различные указатели}
dec(FCurrent, FStart - FBuffer);
FStart := FBuffer;
end;
end;
procedure TtdLZSlidingWindow.swSetCapacity(aValue : longint);
var
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). Сигнатура хешируется с применением одного из методов, а затем хеш-значение используется для доступа к элементу в хеш-таблице, использующему связывание. Цепочки или связные списки в каждом элементе хеш-таблицы будут состоять из последовательностей элементов, каждый из которых состоит из трехсимвольных сигнатур и значения смещения сигнатуры во входном потоке.
Итак, мы получаем сигнатуру текущей позиции и хешируем ее в связный список, представляющий собой - одну из цепочек в хеш-таблице. Затем мы просматриваем связный список и сравниваем хранящуюся в нем сигнатуру каждого элемента с имеющимися сигнатурами. При обнаружении совпадающей сигнатуры мы переходим в скользящее окно, используя значение смещения элемента, а затем сравниваем символы в скользящем окне с символами в текущей позиции. Мы повторяем этот процесс для каждого элемента в связном списке, совпадающего с данной сигнатурой, и запоминаем наиболее длинное найденное соответствие.
