Фундаментальные алгоритмы и структуры данных в Delphi - Джулиан Бакнелл
Шрифт:
Интервал:
Закладка:
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 процентов. В общем случае, как правило, сжатие файлов с применением этого метода позволяет получать коэффициенты сжатия, лежащие между упомянутыми крайними значениями.
Резюме
В этой главе мы провели исследования методов сжатия данных. Мы начали рассмотрение с двух статических алгоритмов кодирования с минимальной избыточностью: кодирования Шеннона-Фано и кодирования Хаффмана. Мы рассмотрели недостатки этих методов - необходимость двукратного считывания входных данных и какого-либо кодирования дерева, чтобы его можно было поставлять со сжатыми данными. Затем мы ознакомились с адаптивным алгоритмом - сжатия с использованием скошенного дерева - позволяющим устранить обе упомянутых проблемы. И в заключение мы рассмотрели сжатие с применением алгоритма JL11, в котором используется словарь, позволяющий сжимать строки символов, а не отдельные символы. Хотя все четыре рассмотренных алгоритма представляют интерес и сами по себе, для их реализации мы воспользовались рядом более простых алгоритмов и структур данных, которые были описаны в предшествующих главах.
Глава 12. Дополнительные темы.
В этой главе мы отойдем от некоторых стандартных классических алгоритмов и рассмотрим ряд более сложных вопросов. Иногда в этой главе будут использоваться некоторые более простые алгоритмы и структуры данных, но во всех таких случаях они будут служить ступенями к реализации усложненных алгоритмов. Именно так и следует использовать классические алгоритмы и структуры данных - в качестве строительных блоков новых алгоритмов, обеспечивающих реализацию конкретных проектов (в конце концов, проект - это всего лишь эскиз специализированного алгоритма).
Алгоритм считывания-записи
В многопоточных приложениях 32-разрядной операционной системы Windows приходится решать целый ряд проблем, которые в однопоточных программах просто не возникают. Действительно, первая проблема, с которой приходится сталкиваться - определение способа запуска и останова потоков. Но в основном она решается на уровне операционной системы: достаточно внимательно прочесть программную документацию операционной системы и правильно применить почерпнутые сведения.
