Base & Delta = Version

FOOTPRINT -- слепок.

предположим длина футпринта 16 символов.

берём бэйз файл.

встали на позицию ноль.

прочитали футпринт - взяли от него хэш-функцию.

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

короче таким образом формируем табличку:

hash table

link table

в хэш-таблице находятся сами хэш-функции и ссылки на линк.таблицу.

в линк-табле - находятся строки.

так как у хэш-функций может быть коллизия... т.е x1!=x2, f(x1)==f(x2), то когда мы находим строку с тем же хэшем, что уже есть в таблице, то добавляем линк на эту строку тоже.

напр.

ыафврваы - хэш 232134

ололололо - хэш 232134

хэш[232134] ----> ссылка на соотв. линк

линк

------

ыафврваы, 235 (место где встретилось, оффсет), ссылка на след. "ололо"

ололололо, 52314 (оффсет), ссылка на NIL

NIL

короче загоняем всевозможные хэши и строки в табличку.

потом открываем версион-файл

прочитали футпринт

взяли от него хэш - напр. 232134

например нашли

тогда проверяем совпадает ли он с "ололо"

нет, ибо ыафврваы

след. линк. - значит ололо!

проверяем еще например - еще одно ололо! всё.

проверяем с первым ололо - и оказывается что кроме ололА если еще дальше прочесть 40 символов - тоже всё отлично совпадает.

то есть реально длина = длина футпринта + 40

проверяем другое ололо - нет совпадений, совпало лишь только ололо.

вот берем максимальное совпадение - ололо по адресу 52314.

пишем COPY с оффсета 52314 56 символов 

пошли следующие футпринты с версионфайла

а не встретилось

идем пока не встретится то что надо

нашли?

тогда пишем ADD LENGTH(...) dasfkhakjsdfkladljfadsljsdffasdldasf

а потом уже COPY (ололо№2, оффсет№хз)