Фундаментальные алгоритмы и структуры данных в Delphi - читать онлайн бесплатно полную версию книги . Страница 209

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