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

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 хеш-таблицы). Если какие-либо соответствия отсутствуют, литеральный символ добавляется в массив кодов и скользящее окно сдвигается на один символ. В противном случае в скользящее окно добавляется пара расстояние/длина, соответствующая наиболее длинной совпадающей строке, и скользящее окно сдвигается на расстояние, равное количеству совпадающих символов.