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

Бакнелл Джулиан М.

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

Однако если не принять никаких специальных мер, количество элементов в хеш-таблице будет только возрастать, в то время как в действительности нам не нужны элементы, которые больше не присутствуют в 8-Кбайтном скользящем окне. Первым возможным решением

этой проблемы может быть удаление элемента, который при следующем сдвиге скользящего окна должен исчезнуть из него. Для этого нужно было бы найти сигнатуру позиции (или, точнее говоря, позиций), которая должна исчезнуть из начала скользящего окна, хешировать ее, пройтись по связному списку, хранящемуся в этой позиции хеш-таблицы, с целью отыскания соответствующего элемента, а затем удалить его.

Более эффективный способ, однако, влекущий за собой увеличение количества элементов в хеш-таблице - сокращение связного списка во время поиска в нем текущей сигнатуры. Вспомните, что связные списки сортируются в порядке убывания значений смещения. Если при перемещении по связному списку в ходе поиска максимального соответствия текущей позиции будет обнаружен элемент, значение смещения которого указывает, что он больше не присутствует в скользящем окне, этот элемент и все последующие элементы данного связного списка должны быть удалены. При использовании этого метода удаление старых элементов откладывается до момента выполнения подпрограммы поиска в связном списке - фактически, до момента, когда мы оказываемся в середине связного списка. Это означает, что хеш-таблица содержит больше элементов, нежели нужно, но этот недостаток весьма незначителен по сравнению с преимуществом ускорения работы алгоритма.

Естественно, необходимо выбрать функцию хеширования. Вместо того чтобы использовать одну из подпрограмм хеширования общего назначения, описанных в главе 7, мы воспользуемся тем фактом, что сигнатуры содержат три символа. В качестве сигнатуры мы определим три младших байта значения типа длинного целого (longint), старший байт которого является нулевым. В результате мы получаем хеш-значение, не требующее никаких вычислений. Как обычно, размер хеш-таблицы должен быть равен простому числу. Я выбрал значение 521 -наименьшее простое число, превышающее 512. Это означает, что в среднем 16 сигнатур из 8-Кбайтного скользящего окна будут преобразовываться в один и тот же номер элемента, образуя для просмотра во время поиска связный список приемлемого размера.

Для восстановления LZ77 целесообразно создать специальный класс хеш-таблице, поскольку в ней должен выполняться ряд специализированных операций. Код этого класса хеш-таблицы приведен в листинге 11.25.

Листинг 11.25. Хеш-таблица LZ77

type

TtdLZSigEnumProc =procedure (aExtraData : pointer;

const aSignature : TtdLZSignature;

aOffset : longint);

PtdLZHashNode = ^TtdLZHashNode;

TtdLZHashNode = packed record hnNext : PtdLZHashNode;

hnSig : TtdLZSignature;

hnOffset : longint;

end;

type

TtdLZHashTable = class private

FHashTable : TList;

FName : TtdNameString;

protected

procedure htError(aErrorCode : integer;

const aMethodName : TtdNameString);

procedure htFreeChain( aParentNode : PtdLZHashNode );

public

constructor Create;

destructor Destroy; override;

procedure Empty;

function EnumMatches(const aSignature : TtdLZSignature;

aCutOffset : longint; aAction : TtdLZSigEnumProc;

aExtraData : pointer): boolean;

procedure Insert(const aSignature : TtdLZSignature; aOffset : longint);

property Name : TtdNameString read FName write FName;

end;

constructor TtdLZHashTable.Create;

var

Inx : integer;

begin

inherited Create;

if (LZHashNodeManager = nil) then begin

LZHashNodeManager := TtdNodeManager.Create(sizeof(TtdLZHashNode));

LZHashNodeManager.Name := 1LZ77 node manager1;

end;

{создать

хеш-таблицу, преобразовать все элементы в связные списки с фиктивным заглавным узлом}

FHashTable := TList.Create;

FHashTable.Count := LZHashTableSize;

for Inx := 0 to pred(LZHashTableSize) do FHashTable.List^[Inx] := LZHashNodeManager.AllocNodeClear;

end;

destructor TtdLZHashTable.Destroy;

var

Inx : integer;

begin

{полностью уничтожить хеш-таблицу, включая фиктивные заглавные узлы}

if (FHashTable <> nil) then begin

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;