Как да генерирам подвижна контролна сума за припокриващи се парчета?

Наскоро попаднах на алгоритъма Rsync и си помислих да го внедря с помощта на java. Една от важните части на този алгоритъм е Rolling Checksum от страната на подателя.

В 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 x 100 + 3 x 10 + 4 = 234.

След това прозорецът се премества една стъпка наляво, покривайки сега 3, 4 и 5. Вместо да пресмятаме 3 x 100 + 4 x 10 + 5, можем да използваме предишната контролна сума и знанията си за числата, които току-що са влезли и са напуснали прозореца, съответно 5 и 2.

И така, знаем, че 2 току-що е напуснало прозореца, изваждаме 2 x 100 от 234, получаваме 34. Умножете 34 по 10 и добавете 5. Това ни дава новия хеш, 345, без да се налага да обикаляме всички елементи, присъстващи в новия прозорец. За следващата последователност от байтове можем да използваме същия метод и да избегнем изчисляването на хеш стойността, като итерираме всички байтове в прозореца.

person LoneRanger    schedule 17.09.2012