Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
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';
{записать
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