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

Empty;

for Inx := 0 to pred(FHashTable.Count) do

LZHashNodeManager.FreeNode(FHashTable.List^[Inx]);

FHashTable.Free;

end;

inherited Destroy;

end;

procedure TtdLZHashTable.Empty;

var

Inx : integer;

begin

for Inx := 0 to pred(FHashTable.Count) do htFreeChain(PtdLZHashNode(FHashTable.List^[Inx]));

end;

function TtdLZHashTable.EnumMatches( const aSignature : TtdLZSignature;

aCutOffset : longint;

aAction : TtdLZSigEnumProc;

aExtraData : pointer): boolean;

var

Inx : integer;

Temp : PtdLZHashNode;

Dad : PtdLZHashNode;

begin

{предположим, что ни один элемент не найден}

Result := false;

{вычислить индекс хеш-таблицы для этой сигнатуры}

Inx := (aSignature.AsLong shr 8) mod LZHashTableSize;

{выполнить обход цепочки, расположенной в позиции с этим индексом}

Dad := PtdLZHashNode (FHashTable.List^[Inx]);

Temp := Dad^.hnNext;

while (Temp <> nil) do

begin

{если смещение этого узла меньше значения смещения, по которому выполняется усечение, остальная часть цепочки удаляется, и выполняется выход из подпрограммы}

if (Temp^.hn0ffset < aCutOffset) then begin

htFreeChain(Dad);

Exit;

end;

{если сигнатура узла совпадает с данной сигнатурой, выполняется вызов подпрограммы, выполняющей действие}

if (Temp^.hnSig.AsLong = aSignature.AsLong) then begin

Result true;

aAction(aExtraData, aSignature, Temp^.hnOffset);

end;

(перешли к следующему узлу) Dad := Temp;

Temp := Dad^.hnNext;

end;

end;

procedure TtdLZHashTable.htFreeChain(aParentNode : PtdLZHashNode);

var

Walker, Temp : PtdLZHashNo4e;

begin

Walker := aParentNode^.hnNext;

aParentNode^.hnNext := nil;

while (Walker <> nil) do

begin

Temp := Walker;

Walker := Walker^.hnNext;

LZHashNodeManager.FreeNode(Temp);

end;

end;

procedure TtdLZHashTable.Insert(const aSignature : TtdLZSignature;

aOffset : longint);

var

Inx : integer;

NewNode : PtdLZHashNode;

HeadNode : PtdLZHashNode;

begin

{вычислить индекс хеш-таблицы для этой сигнатуры}

Inx := (aSignature.AsLong shr 8) mod LZHashTableSize;

{распределить новый узел и вставить его в начало цепочки, расположенной в позиции хеш-таблицы, определяемой этим индексом; тем самым обеспечивается упорядочение узлов в цепочке в порядке убывания значений смещения}

NewNode := LZHashNodeManager.AllocNode;

NewNode^.hnSig := aSignature;

NewNode^.hnQffset :=a0ffset;

HeadNode := PtdLZHashNode(FHashTable.List^[Inx]);

NewNode^.hnNext := HeadNode^.hnNext;

HeadNode^.hnNext := NewNode;

end;

В целях повышения эффективности в хеш-таблице используется диспетчер узлов, поскольку придется распределить и освободить несколько тысяч узлов. Это выполняется внутри конструктора Create. Через непродолжительное время метод EnumMatches вызывается снова. Он просматривает все элементы в хеш-таблице на предмет совпадения с конкретной сигнатурой и для каждого найденного такого элемента вызывает процедуру aAction. Так реализуется основная логика установления соответствия алгоритма LZ77.

Класс скользящего окна выполняет также ряд важных функций, кроме сохранения ранее встречавшихся байтов. Во-первых, во время кодирования скользящее окно считывает данные из входного потока большими боками, чтобы об этом не нужно было беспокоиться во время выполнения подпрограммы сжатия. Во-вторых, оно возвращает текущую сигнатуру и ее смещение во входном потоке. Третий метод выполняет сопоставление: он принимает смещение во входном потоке, преобразует его в смещение в буфере скользящего окна, а затем сравнивает хранящиеся там символы с символами в текущей позиции. Метод будет возвращать количество совпадающих символов и значение расстояния, что позволяет создать пару расстояние/длина. Заключительный фрагмент кода реализации этого класса скользящего окна приведен в листинге 11.26 (код остальных методов можно найти в листинге 11.23).

Листинг 11.26. Методы скользящего окна, используемые во время сжатия

procedure TtdLZSlidingWindow.Advance(aCount : integer);

var

ByteCount : integer;

begin

{при необходимости сместить начало скользящего окна}

if ((FCurrent - FStart) >= tdcLZSlidingWindowSize) then begin

inc(FStart, aCount);

inc(FStartOffset, aCount);

end;

{сместить текущий указатель}

inc(FCurrent, aCount);

{проверить смещение в зону переполнения}

if (FStart >= FMidPoint) then begin

{переместить текущие данные обратно в начало буфера}

ByteCount := FLookAheadEnd - FStart;

Move(FStart^, FBuffer^, ByteCount);

{сбросить различные указатели}

ByteCount := FStart - FBuffer;

FStart := FBuffer;

dec(FCurrent, ByteCount);

dec(FLookAheadEnd, ByteCount);

{выполнить считывание дополнительных данных из потока}

swReadFromStream;

end;

end;

function TtdLZSlidingWindow.Compare(aOffset : longint;

var aDistance : integer): integer;

var

MatchStr : PAnsiChar;

CurrentCh : PAnsiChar;

begin

{Примечание: когда эта подпрограмма вызывается, она предполагает, что между переданной и текущей позицией будет найдено по меньшей мере три совпадающих символа}

{вычислить позицию в скользящем окне, соответствующую переданному смещению и ее расстоянию от текущей позиции}

MatchStr := FStart + (aOffset - FStartOffset);

aDistance := FCurrent - MatchStr;

inc(MatchStr, 3);

{вычислить длину строки совпадающих символов между данной и текущей позицией. Эта длина не должна превышать максимальной длины. Для конца входного потока определен специальный случай}

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