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

Сжатие LZ77

Сжатие LZ77

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

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

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

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

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

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

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

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

Естественно, необходимо выбрать функцию хеширования. Вместо того чтобы использовать одну из подпрограмм хеширования общего назначения, описанных в главе 7, мы воспользуемся тем фактом, что сигнатуры содержат три символа. В качестве сигнатуры мы определим три младших байта значения типа длинного целого (longint), старший байт которого является нулевым. В результате мы получаем хеш-значение, не требующее никаких вычислений. Как обычно, размер хеш-таблицы должен быть равен простому числу. Я выбрал значение 521 -наименьшее простое число, превышающее 512. Это означает, что в среднем 16 сигнатур из 8-Кбайтного скользящего окна будут преобразовываться в один и тот же номер элемента, образуя для просмотра во время поиска связный список приемлемого размера.

Для восстановления LZ77 целесообразно создать специальный класс хеш-таблице, поскольку в ней должен выполняться ряд специализированных операций. Код этого класса хеш-таблицы приведен в листинге 11.25.

Листинг 11.25. Хеш-таблица LZ77

type

TtdLZSigEnumProc =procedure (aExtraData : pointer;

const aSignature : TtdLZSignature;

aOffset : longint);

PtdLZHashNode = ^TtdLZHashNode;

TtdLZHashNode = packed record hnNext : PtdLZHashNode;

hnSig : TtdLZSignature;

hnOffset : longint;

end;

type

TtdLZHashTable = class private

FHashTable : TList;

FName : TtdNameString;

protected

procedure htError(aErrorCode : integer;

const aMethodName : TtdNameString);

procedure htFreeChain( aParentNode : PtdLZHashNode );

public

constructor Create;

destructor Destroy; override;

procedure Empty;

function EnumMatches(const aSignature : TtdLZSignature;

aCutOffset : longint; aAction : TtdLZSigEnumProc;

aExtraData : pointer): boolean;

procedure Insert(const aSignature : TtdLZSignature; aOffset : longint);

property Name : TtdNameString read FName write FName;

end;

constructor TtdLZHashTable.Create;

var

Inx : integer;

begin

inherited Create;

if (LZHashNodeManager = nil) then begin

LZHashNodeManager := TtdNodeManager.Create(sizeof(TtdLZHashNode));

LZHashNodeManager.Name := 1LZ77 node manager1;

end;

{создать хеш-таблицу, преобразовать все элементы в связные списки с фиктивным заглавным узлом}

FHashTable := TList.Create;

FHashTable.Count := LZHashTableSize;

for Inx := 0 to pred(LZHashTableSize) do FHashTable.List^[Inx] := LZHashNodeManager.AllocNodeClear;

end;

destructor TtdLZHashTable.Destroy;

var

Inx : integer;

begin

{полностью уничтожить хеш-таблицу, включая фиктивные заглавные узлы}

if (FHashTable <> nil) then begin

Empty;

for Inx := 0 to pred(FHashTable.Count) do

LZHashNodeManager.FreeNode(FHashTable.List^[Inx]);

FHashTable.Free;

end;

inherited Destroy;

end;

procedure TtdLZHashTable.Empty;

var

Inx : integer;

begin

for Inx := 0 to pred(FHashTable.Count) do htFreeChain(PtdLZHashNode(FHashTable.List^[Inx]));

end;

function TtdLZHashTable.EnumMatches( const aSignature : TtdLZSignature;

aCutOffset : longint;

aAction : TtdLZSigEnumProc;

aExtraData : pointer): boolean;

var

Inx : integer;

Temp : PtdLZHashNode;

Dad : PtdLZHashNode;

begin

{предположим, что ни один элемент не найден}

Result := false;

{вычислить индекс хеш-таблицы для этой сигнатуры}

Inx := (aSignature.AsLong shr 8) mod LZHashTableSize;

{выполнить обход цепочки, расположенной в позиции с этим индексом}

Dad := PtdLZHashNode (FHashTable.List^[Inx]);

Temp := Dad^.hnNext;

while (Temp <> nil) do

begin

{если смещение этого узла меньше значения смещения, по которому выполняется усечение, остальная часть цепочки удаляется, и выполняется выход из подпрограммы}

if (Temp^.hn0ffset < aCutOffset) then begin

htFreeChain(Dad);

Exit;

end;

{если сигнатура узла совпадает с данной сигнатурой, выполняется вызов подпрограммы, выполняющей действие}

if (Temp^.hnSig.AsLong = aSignature.AsLong) then begin

Result true;

aAction(aExtraData, aSignature, Temp^.hnOffset);

end;

(перешли к следующему узлу) Dad := Temp;

Temp := Dad^.hnNext;

end;

end;

procedure TtdLZHashTable.htFreeChain(aParentNode : PtdLZHashNode);

var

Walker, Temp : PtdLZHashNo4e;

begin

Walker := aParentNode^.hnNext;

aParentNode^.hnNext := nil;

while (Walker <> nil) do

begin

Temp := Walker;

Walker := Walker^.hnNext;

LZHashNodeManager.FreeNode(Temp);

end;

end;

procedure TtdLZHashTable.Insert(const aSignature : TtdLZSignature;

aOffset : longint);

var

Inx : integer;

NewNode : PtdLZHashNode;

HeadNode : PtdLZHashNode;

begin

{вычислить индекс хеш-таблицы для этой сигнатуры}

Inx := (aSignature.AsLong shr 8) mod LZHashTableSize;

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

NewNode := LZHashNodeManager.AllocNode;

NewNode^.hnSig := aSignature;

NewNode^.hnQffset :=a0ffset;

HeadNode := PtdLZHashNode(FHashTable.List^[Inx]);

NewNode^.hnNext := HeadNode^.hnNext;

HeadNode^.hnNext := NewNode;

end;

В целях повышения эффективности в хеш-таблице используется диспетчер узлов, поскольку придется распределить и освободить несколько тысяч узлов. Это выполняется внутри конструктора Create. Через непродолжительное время метод EnumMatches вызывается снова. Он просматривает все элементы в хеш-таблице на предмет совпадения с конкретной сигнатурой и для каждого найденного такого элемента вызывает процедуру aAction. Так реализуется основная логика установления соответствия алгоритма LZ77.

Класс скользящего окна выполняет также ряд важных функций, кроме сохранения ранее встречавшихся байтов. Во-первых, во время кодирования скользящее окно считывает данные из входного потока большими боками, чтобы об этом не нужно было беспокоиться во время выполнения подпрограммы сжатия. Во-вторых, оно возвращает текущую сигнатуру и ее смещение во входном потоке. Третий метод выполняет сопоставление: он принимает смещение во входном потоке, преобразует его в смещение в буфере скользящего окна, а затем сравнивает хранящиеся там символы с символами в текущей позиции. Метод будет возвращать количество совпадающих символов и значение расстояния, что позволяет создать пару расстояние/длина. Заключительный фрагмент кода реализации этого класса скользящего окна приведен в листинге 11.26 (код остальных методов можно найти в листинге 11.23).

Листинг 11.26. Методы скользящего окна, используемые во время сжатия

procedure TtdLZSlidingWindow.Advance(aCount : integer);

var

ByteCount : integer;

begin

{при необходимости сместить начало скользящего окна}

if ((FCurrent - FStart) >= tdcLZSlidingWindowSize) then begin

inc(FStart, aCount);

inc(FStartOffset, aCount);

end;

{сместить текущий указатель}

inc(FCurrent, aCount);

{проверить смещение в зону переполнения}

if (FStart >= FMidPoint) then begin

{переместить текущие данные обратно в начало буфера}

ByteCount := FLookAheadEnd - FStart;

Move(FStart^, FBuffer^, ByteCount);

{сбросить различные указатели}

ByteCount := FStart - FBuffer;

FStart := FBuffer;

dec(FCurrent, ByteCount);

dec(FLookAheadEnd, ByteCount);

{выполнить считывание дополнительных данных из потока}

swReadFromStream;

end;

end;

function TtdLZSlidingWindow.Compare(aOffset : longint;

var aDistance : integer): integer;

var

MatchStr : PAnsiChar;

CurrentCh : PAnsiChar;

begin

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

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

MatchStr := FStart + (aOffset - FStartOffset);

aDistance := FCurrent - MatchStr;

inc(MatchStr, 3);

{вычислить длину строки совпадающих символов между данной и текущей позицией. Эта длина не должна превышать максимальной длины. Для конца входного потока определен специальный случай}

Result := 3;

CurrentCh := FCurrent + 3;

if (CurrentCh <> FLookAheadEnd) then begin

while (Result < tdcLZMaxMatchLength) and (MatchStr^ = CurrentCh^ ) do

begin

inc(Result);

inc(MatchStr);

inc(CurrentCh);

if (CurrentCh = FLookAheadEnd) then

Break;

end;

end;

end;

procedure TtdLZSlidingWindow.GetNextSignature(var aMS : TtdLZSignature;

var aOffset : longint);

var

P : PAnsiChar;

i : integer;

begin

{вычислить длину совпадающей строки; обычно она равна 3, но в конце входного потока она может быть равна 2 или менее.}

if ((FLookAheadEnd - FCurrent) < 3) then

aMS.AsString[0] := AnsiChar (FLookAheadEnd - FCurrent) else

aMS.AsString[0] := #3;

P := FCurrent;

for i := 1 to length (aMS.AsString) do

begin

aMS.AsString[i] := P^;

inc(P);

end;

aOffset := FStartOffset + (FCurrent - FStart);

end;

procedure TtdLZSlidingWindow.swReadFromStream;

var

BytesRead : longint;

BytesToRead : longint;

begin

{выполнить считывание дополнительных данных в зону упреждающего просмотра}

BytesToRead := FBufferEnd - FLookAheadEnd;

BytesRead := FStream.Read(FLookAheadEnd^, BytesToRead);

inc(FLookAheadEnd, BytesRead);

end;

Теперь, когда наш арсенал пополнился этими классами, можно создать подпрограмму сжатия, показанную в листинге 11.27. Она слегка осложняется необходимостью накапливать коды сжатия по восемь. Это делается для того, чтобы можно было вычислить байт флага для всех восьми байтов, а затем записать байт флага, за которым следуют восемь кодов. Именно этой цели служит массив Encodings. Однако, поскольку мы рассмотрели достаточно много вспомогательных подпрограмм, сама эта подпрограмма не слишком сложна для понимания.

Листинг 11.27. Подпрограмма ZL77

type

PEnumExtraData = ^TEnumExtraData; {запись дополнительных данных для }

TEnumExtraData = packed record { метода FindAll хеш-таблицы}

edSW : TtdLZSlidingWindow; {..объект скользящего окна}

edMaxLen : integer;{..максимальная длина совпадающих }

{строк на данный момент}

edDistMaxMatch: integer;

end;

type

TEncoding = packed record

AsDistLen : cardinal;

AsChar : AnsiChar;

IsChar : boolean;

{ $IFNDEF Delphi1}

Filler : word;

{$ENDIF}

end;

TEncodingArray = packed record

eaData : array [0..7] of TEncoding;

eaCount: integer;

end;

procedure MatchLongest(aExtraData : pointer;

const aSignature : TtdLZSignature;

aOffset : longint);

far;

var

Len : integer;

Dist : integer;

begin

with PEnumExtraData(aExtraData)^ do

begin

Len :=edSW.Compare(aOffset, Dist);

if (Len > edMaxLen) then begin

edMaxLen := Len;

edDistMaxMatch := Distend;

end;

end;

procedure WriteEncodings(aStream : TSTream;

var aEncodings : TEncodingArray);

var

i : integer;

FlagByte : byte;

Mask : byte;

begin

{построить байт флага и записать его в поток}

FlagByte := 0;

Mask :=1;

for i := 0 to pred(aEncodings.eaCount) do

begin

if not aEncodings.eaData[i].IsChar then

FlagByte := FlagByte or Mask;

Mask := Mask shl 1;

end;

aStream.WriteBuffer(FlagByte, sizeof(FlagByte));

{записать коды}

for i := 0 to pred(aEncodings.eaCount) do

begin

if aEncodings.eaData[i].IsChar then

aStream.WriteBuffer(aEncodings.eaData[i].AsChar, 1) else

aStream.WriteBuffer(aEncodings.eaData[i].AsDistLen, 2);

end;

aEncodings.eaCount := 0;

end;

procedure AddCharToEncodings(aStream : TStream;

aCh : AnsiChar;

var aEncodings : TEncodingArray);

begin

with aEncodings do

begin

eaData[eaCount].AsChar := aCh;

eaData[eaCount].IsChar := true;

inc(eaCount);

if (eaCount = 8) then

WriteEncodings(aStream, aEncodings);

end;

end;

procedure AddCodeToEncodings(aStream : TStream;

aDistance : integer;

aLength : integer;

var aEncodings : TEncodingArray);

begin

with aEncodings do

begin

eaData[eaCount].AsDistLen :=

(pred(aDistance) shl tdcLZDistanceShift) + (aLength - 3);

eaData[eaCount].IsChar := false;

inc(eaCount);

if (eaCount = 8) then

WriteEncodings(aStream, aEncodings);

end;

end;

procedure TDLZCompress(aInStream, aOutStream : TStream);

var

HashTable : TtdLZHashTable;

SlideWin : TtdLZSlidingWindow;

Signature : TtdLZSignature;

Offset : longint;

Encodings : TEncodingArray;

EnumData : TEnumExtraData;

LongValue : longint;

i : integer;

begin

HashTable :=nil;

SlideWin := nil;

try

HashTable := TtdLZHashTable.Create;

HashTable.Name := 'LZ77 Compression hash table';

SlideWin := TtdLZSlidingWindow.Create(aInStream, true);

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

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

LongValue := TDLZHeader;

aOutStream.WrijteBuffer(LongValue, sizeof(LongValue));

LongValue aInStream.Size;

aOutStream.WriteBuffer(LongValue, sizeof(LongValue));

{подготовка к сжатию}

Encodings.eaCount := 0;

EnumData.edSW := SlideWin;

{получить первую сигнатуру}

SlideWin.GetNextSignature(Signature, Offset);

{до тех пор, пока длина сигнатуры равна трем символам...}

while ( length ( Signature.AsString) = 3 ) do

begin

{выполнить поиск в скользящем окне самой длинной совпадающей строки с использованием хеш-таблицы для идентификации соответствий}

EnumData.edMaxLen := 0;

if HashTable.EnumMatches(Signature,

Offset - tdcLZSlidingWindowSize, MatchLongest, @EnumData) then begin

{имеется по меньшей мере одно соответствие : необходимо сохранить пару расстояние/длина самой длинной совпадающей строки и сдвинуть скользящее окно на расстояние, равное этой длине}

AddCodeToEncodings(aOutStream,

EnumData.edDistMaxMatch, EnumData.edMaxLen, Encodings);

SlideWin.Advance(EnumData.edMaxLen);

end

else begin

{соответствие отсутствует: необходимо сохранить текущий символ и сдвинуть скользящее окно на один символ}

AddCharToEncodings(aOutStream,

Signature.AsString[1], Encodings);

SlideWin.Advance(1);

end;

{добавить эту сигнатуру в хеш-таблицу}

HashTable.Insert(Signature, Offset);

{извлечь следующую сигнатуру}

SlideWin.GetNextSignature(Signature, Offset);

end;

{если последняя сигнатура содержала не более двух символов, их нужно сохранить как коды литеральных символов}

if (length(Signature.AsString) > 0) then begin

for i := 1 to length (Signature.AsString) do AddCharToEncodings(aOutStream,

Signature.AsString[i], Encodings);

end;

{обеспечить запись заключительных кодов}

if (Encodings.eaCount > 0) then

WriteEncodings(aOutStream, Encodings);

finally SlideWin.Free;

HashTable.Free;

end; {try.. finally}

end;

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

Код программы сжатия LZ77 разбит на несколько файлов: TDLZBase.pas содержит несколько общих констант, TDLZHash.pas создает специализированную хеш-таблицу, TDLZSWin - класс скользящего окна, а TDLZCmpr.pas - код выполнения сжатия и восстановления. Все перечисленные файлы можно найти на web-сайте издательства, в разделе материалов.

После того, как мы ознакомились с алгоритмом и кодом реализации сжатия и восстановления LZ77, можно теоретически оценить возможные значения коэффициентов сжатия. Если бы можно было сжать все 10 байтовые строки в файле до 2 байт - иначе говоря, каждый раз получать максимальное соответствие - для каждых 80 байтов файла можно было бы записывать по 17 байт (один байт флага и восемь 2-байтовых кодов). В этом случае коэффициент сжатия равнялся бы 79 процентам. С другой стороны, если бы соответствия в файле вообще не удалось бы найти, для каждых восьми байтов исходного файла в действительности пришлось бы записывать по девять байтов. В этом случае коэффициент сжатия составил бы -13 процентов. В общем случае, как правило, сжатие файлов с применением этого метода позволяет получать коэффициенты сжатия, лежащие между упомянутыми крайними значениями.

Оглавление книги