Коткий геш

Коткий геш (Шаблон:Lang-en) (також відомий як рекурсивне гешування або котка контрольна сума) — це геш-функція, яка гешує дані у вікні, що рухається уздовж входових даних.

Декілька геш-функцій дозволяють швидке обчислення коткого гешу маючи лише попередній геш і видалене з і до додане до вікна значення. Це подібно до функції рухомого середнього, яку можна обчислити швидше ніж інші низькочастотні фільтри.

Одне з найпомініших застосувань це алгоритм Рабіна — Карпа пошуку підрядка, який використовує геш описаний нижче. Інше поширене застосування це застосунок rsync, який в якості коткого гешу використовує контрольну суму породжену з adler-32. Вузькосмугова мережева файлова система (LBFS) використовує «відбиткі пальців» Рабіна як коткий геш.

Щонайбільше, значення коткого гешу попарно незалежні або сильно універсальні. Наприклад, вони не можуть бути Шаблон:Нп.

Поліномний коткий геш

Алгоритм Рабіна — Карпа часто пояснюють за допомогою функції коткого гешу, яка використовує лише множення і додавання:

$H=c_1{a}^{k-1}+c_2{a}^{k-2}+c_3{a}^{k-3}+...+c_k{a}^0$,

де $a$ це стала величина, а $c_1,...,c_k$ це входові символи (але ця функція не є «відбитками пальців» Рабіна).

Щоб не довелось працювати з величезними значеннями $H$, всю математику роблять за модулем $n$. Вибір $a$ і $n$ критичний для отримання хорошого гешування; дивись лінійний конгруентний метод.

Видаляння і додавання символів потребує просто додавання або віднімання першого або останнього доданку. Зсування всіх символів на одну позицію ліворуч вимагає домноження усієї суми $H$ на $a$. Зауважте, що в модульній арифметиці $a$ можна обрати так, щоб вона мала множильне обернене $a^{-1}$, на яке можна домножити $H$, щоб отримати ділення не роблячи його насправді.