Чтение онлайн

на главную - закладки

Жанры

Фундаментальные алгоритмы и структуры данных в 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;

Поделиться:
Популярные книги

Младший сын князя. Том 2

Ткачев Андрей Юрьевич
2. Аналитик
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Младший сын князя. Том 2

Чужая дочь

Зика Натаэль
Любовные романы:
любовно-фантастические романы
5.00
рейтинг книги
Чужая дочь

Возвышение Меркурия. Книга 12

Кронос Александр
12. Меркурий
Фантастика:
героическая фантастика
попаданцы
аниме
5.00
рейтинг книги
Возвышение Меркурия. Книга 12

Морозная гряда. Первый пояс

Игнатов Михаил Павлович
3. Путь
Фантастика:
фэнтези
7.91
рейтинг книги
Морозная гряда. Первый пояс

Завод 2: назад в СССР

Гуров Валерий Александрович
2. Завод
Фантастика:
попаданцы
альтернативная история
фэнтези
5.00
рейтинг книги
Завод 2: назад в СССР

Последняя Арена 6

Греков Сергей
6. Последняя Арена
Фантастика:
рпг
постапокалипсис
5.00
рейтинг книги
Последняя Арена 6

Инквизитор тьмы 3

Шмаков Алексей Семенович
3. Инквизитор Тьмы
Фантастика:
попаданцы
альтернативная история
аниме
5.00
рейтинг книги
Инквизитор тьмы 3

Орден Багровой бури. Книга 4

Ермоленков Алексей
4. Орден Багровой бури
Фантастика:
фэнтези
попаданцы
5.00
рейтинг книги
Орден Багровой бури. Книга 4

Черный дембель. Часть 3

Федин Андрей Анатольевич
3. Черный дембель
Фантастика:
попаданцы
альтернативная история
5.00
рейтинг книги
Черный дембель. Часть 3

Попаданка в деле, или Ваш любимый доктор - 2

Марей Соня
2. Попаданка в деле, или Ваш любимый доктор
Любовные романы:
любовно-фантастические романы
7.43
рейтинг книги
Попаданка в деле, или Ваш любимый доктор - 2

Кодекс Крови. Книга I

Борзых М.
1. РОС: Кодекс Крови
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Кодекс Крови. Книга I

Убивать чтобы жить 6

Бор Жорж
6. УЧЖ
Фантастика:
боевая фантастика
космическая фантастика
рпг
5.00
рейтинг книги
Убивать чтобы жить 6

Законы Рода. Том 12

Flow Ascold
12. Граф Берестьев
Фантастика:
юмористическое фэнтези
аниме
фэнтези
5.00
рейтинг книги
Законы Рода. Том 12

Наваждение генерала драконов

Лунёва Мария
3. Генералы драконов
Любовные романы:
любовно-фантастические романы
5.00
рейтинг книги
Наваждение генерала драконов