Поиск сигнатур
Для эффективности поиска используется хеширование быстрой сигнатуры и трехуровневый поиск. Ключом хеш-функции является значение 32 битной сигнатуры, а значением сумма двух её (16 битных) половин.
Поиск сигнатур.
На первом уровне, формируется хеш-таблица размером в 2^16 элементов. Ключом хеш-функции является быстрая 32 битная сигнатура. Для каждой пары быстрой и стойкой сигнатуры полученной от Beta вычисляется 16 битный хеш 32 битной сигнатуры, после чего все это сортируется согласно 16 битному хешу. Каждый элемент хеш-таблицы указывает на первый элемент сортированных сигнатур, хеш значения которых совпадают, либо хранит в себе NULL, если сигнатур с таким хешом нет. Номер элемента хеш-таблицы соответствует значению хеш-функции, а именно сумме двух половин быстрой 32 битной сигнатуры.
Затем, для каждого байтового смещения вычисляется быстрая 32 битная сигнатура и 16 битное хеш-значение. Если элемент хеш-таблицы для этого хеш-значения не равен NULL, алгоритм поиска переходит на следующий уровень.
На втором уровне происходит линейный поиск по сортированному списку сигнатур, начиная с элемента указанного в хеш-таблице. Мы ищем быструю 32 битную сигнатуру, чьё значение совпадает с необходимым нам значением. Поиск прекращается при первом же несовпадении 16 битной сигнатуры. Если мы нашли такую 32 битную сигнатуру, алгоритм переходит на следующий уровень.
На третьем уровне, происходит вычисление стойкой сигнатуры для текущего смещения в файле и сравнение его со значением стойкой сигнатуры в сортированном списке. При совпадении, предполагается, что мы нашли блок в файле A , который есть в файле B . Фактически, блоки могут быть различны, но вероятность этого очень мала.
При совпадении блоков, Alpha отсылает Beta данные из файла A между текущим смещением и предыдущим совпадением, а также индекс совпавшего блока который есть в B . Эти данные отсылаются сразу же при нахождении совпадения.
Если совпадения найдено не было для текущего смещения в файле A , вычисляется быстрая сигнатура для следующего байтового смещения и процедура поиска повторяется. При совпадении, смещение увеличивается на размер совпавшего блока и поиск продолжается.
