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,
