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

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