Как сгенерировать скользящую контрольную сумму для перекрывающихся фрагментов?

Недавно я столкнулся с алгоритмом Rsync и подумал о его реализации с использованием java. Одной из важных частей этого алгоритма является скользящая контрольная сумма на стороне отправителя.

В http://en.wikipedia.org/wiki/Rsync объясняется, что

«если бы кто-то уже вычислил скользящую контрольную сумму байтов 1–25, можно было бы вычислить > скользящую контрольную сумму байтов 2–26 исключительно из предыдущей контрольной суммы (R), байта 1 (n) и > байта 26 (n+S )".

Я могу сгенерировать контрольную сумму для файла или строки, используя MD5 или SHA. Но я хотел прояснить эту строку, как мы можем ее реализовать.


java checksum algorithm rsync
person Abhinav    schedule 17.09.2012    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Предположим, что ваше скользящее окно занимает 3 байта, а наша входная строка имеет размер 5 байт. Рассмотрим строку 23456. Мы будем использовать простую хеш-функцию: если окно покрывает байты a, b и c, то хеш равен a x 100 + b x 10 + c.

Итак, для нашей входной строки 2345 контрольная сумма первых 3 байтов равна 2 х 100 + 3 х 10 + 4 = 234.

Затем окно перемещается на один шаг влево, охватывая теперь 3, 4 и 5. Вместо вычисления 3 х 100 + 4 х 10 + 5 мы можем использовать предыдущую контрольную сумму и наши знания о числах, которые только что вошли и вышли из окна, 5 и 2 соответственно.

Итак, мы знаем, что 2 только что покинуло окно, мы вычитаем 2 x 100 из 234, получая 34. Умножаем 34 на 10 и добавляем 5. Это дает нам новый хеш, 345, без необходимости перебирать все элементы, присутствующие в новое окно. Для следующей последовательности байтов мы можем использовать тот же метод и не вычислять хэш-значение, перебирая все байты в окне.

person LoneRanger    schedule 17.09.2012