Теперь пора рассмотреть реализацию сжатия. При этом очень быстро мы сталкиваемся со следующей проблемой: поиском наиболее длинного соответствия между строкой в текущей позиции и предшествующими 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 = ATtdLZHashNode;
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 EnumMat che s (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.ListA[Inx] : = LZHashNodeManager.AllocNodeClear;
ends-destructor TtdLZHashTable.Destroy;
var
Inx : integer;
begin
{полностью уничтожить хеш-таблицу, включая фиктивные заглавные узлы) if (FHashTable о nil) then begin Empty;
for Inx : = 0 to pred(FHashTable.Count) do
LZHashNodeManager.FreeNode(FHashTable.ListA[Inx]);
FHashTable.Free;
ends-inherited Destroy;
ends-procedure TtdLZHashTable.Empty;
var
Inx : integers-begin
for Inx := 0 to pred(FHashTable .Count) do htFreeChain(PtdLZHashNode(FHashTable.ListA[Inx]));
ends-function TtdLZHashTable. EnumMatches( const aSignature : TtdLZSignature;
aCutOffset : longint;
aAction : TtdLZSigEnumProc;
aExtraData : pointer) : boolean;
var
Inx : integers-Temp : PtdLZHashNode;
Dad : PtdLZHashNode;
begin
{предположим, что ни один элемент не найден) Result := false;
{вычислить индекс хеш-таблицы для этой сигнатуры)
Inx := (aSignature.AsLong shr 8) mod LZHashTableSize;
{выполнить обход цепочки, расположенной в позиции с этим индексом)
Dad : = PtdLZHashNode (FHashTable.List* [Inx]) ;
Temp : = DadA. hnNext ;
while (Temp <>
nil) do begin
{если смещение этого узла меньше значения смещения, по которому выполняется усечение, остальная часть цепочки удаляется, и выполняется выход из подпрограммы) if (TempA.hn0ffset <
aCutOffset) then begin htFreeChain(Dad);
Expend;
{если сигнатура узла совпадает с данной сигнатурой, выполняется вызов подпрограммы, выполняющей действие) if (TempА.hnSig.AsLong = aSignature.AsLong) then begin
Result true;
aAction(aExtraData, aSignature, TempA.hnOffset);
end;
(перешли к следующему узлу) Dad := Temp;
Temp : = DadA.hnNext;
end;
end;
procedure TtdLZHashTable.htFreeChain(aParentNode : PtdLZHashNode); var
Walker, Temp : PtdLZHashNo4e;
begin
Walker : = aParentNodeA.hnNext;
aParentNodeA.hnNext : = nil;
while (Walker <>
nil) do begin
Temp := Walker;
Walker : = WalkerA.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 ; NewNodeA.hnSig := aSignature;
NewNodeA.hnQffset :=a0ffset;
HeadNode : - PtdLZHashNode(FHashTable.ListA[Inx]);
NewNode A. hnNext : = HeadNode A. hnNext;
HeadNodeA.hnNext : = NewNode;
end;

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

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

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

procedure TtdLZSlidingWindow.Advance(aCount : integer); var
ByteCount : integers-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(FStartA, FBufferA, 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* «
CurrentChA) 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] : = PA;
inc(P);
end;
aOffset := FStartOffset + (FCurrent - FStart) ;
end;
procedure TtdLZSlidingWindow. swReadFromStream;
var
BytesRead : longint;
BytesToRead : longint;
begin
{выполнить считывание дополнительных данных в зону упреждающего просмотра} BytesToRead := FBufferEnd - FLookAheadEnd;
BytesRead : = FStream.Read(FLookAheadEndA, BytesToRead);
inc(FLookAheadEnd, BytesRead);
end;

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

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

type PEnumExtraData -» ATEnumExtraData; {запись дополнительных данных для ) TEnumExtraData = packed record { метода FindAll хеш-таблицы) edSW : TtdLZSlidingWindow; {. .объект скользящего окна) edMaxLen : integer; {. .максимальная длина совпадающих ) {строк на данный момент) edDistMaxMatch: integer-end; type TEncoding = packed record

AsDistLen : cardinal;
As Char : AnsiChar;
IsChar : boolean; { $IFNDEF Delphi 1} 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)A 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
і : integer;
FlagByte : byte;
Mask : byte;
begin
{построить байт флага и записать его в поток) FlagByte := 0; Mask :=1;
for і : = 0 to pred (aEncodings. eaCount) do begin
if not aEncodings. eaData [ і ] . IsChar then FlagByte := FlagByte or Mask;
Mask := Mask shl 1;
end;
aStream.WriteBuffer(FlagByte, sіzeof(FlagByte)); {записать коды)
for і : = 0 to pred (aEncodings. eaCount) do begin if aEncodings.eaData[і].IsChar then
aStream.WriteBuffer(aEncodings.eaData[і].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);
ends-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 := fal serine (eaCount) ; if (eaCount = 8) then WriteEncodings(aStream, aEncodings);
end;
ends-procedure TDLZCompress(alnStream, aOutStream : TStream); var
HashTable : TtdLZHashTable;
SlideWin : TtdLZSlidingWindow;
Signature : TtdLZSignature;
Offset : longint;
Encodings : TEncodingArray;
EnumData : TEnumExtraData;
LongValue : longint;
i : integer;
begin
HashTable :=nil;
SlideWin ^nils-try
HashTable := TtdLZHashTable.Create;
HashTable. Name := 'LZ77 Compression hash table1 ; SlideWin := TtdLZSlidingWindow.Create(alnStream, true);
SlideWin.Name := 'LZ77 Compression sliding window1;
{записать заголовок в поток: 'TDLZ', за который следует размер несжатого исходного потока] LongValue := TDLZHeader;
aOutStream.WrijteBuffer(LongValue, sizeof(LongValue));
LongValue alnStream.Size;
aOutStream.WriteBuffer(LongValue, sizeof(LongValue)); {подготовка к сжатию] Encodings.eaCount := 0;
EnumData. edSW := SlideWin; {получить первую сигнатуру)
SlideWin.GetNextSignature(Signature, Offset);
{до тех nop, пока длина сигнатуры равна трем символам...}
while ( length ( Signature. AsString) = 3 ) do begin
{выполнить поиск в скользящем окне самой длинной совпадающей строки с использованием хеш-таблицы для идентификации соответствий) EnumData.edMaxLen := 0; if HashTable.EnumMatches(Signature, Offset - tdcLZSlidingWindowSize, MatchLongest, @EnumData) then begin {имеется no меньшей мере одно соответствие : необходимо сохранить пару расстояние/длина самой длинной совпадающей строки и сдвинуть скользящее окно на расстояние, равное этой длине) 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;

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

Код программы сжатия \JL11 разбит на несколько файлов: ТОЬгвазе.раз содержит несколько общих констант, ТЭЬгНазп.раз создает специализированную хеш-таблицу, Т0Ьг8К1п - класс скользящего окна, а ТЭЬгСшрг.раз - код выполнения сжатия и восстановления. Все перечисленные файлы можно найти на \¥еЬ-сайте издательства, в разделе материалов.

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

Восстановление с применением алгоритма LZ77 || Оглавление || Резюме11


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



Новости за месяц

  • Май
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс