Коткий геш

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

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

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

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

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

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

${\displaystyle H=c_{1}a^{k-1}+c_{2}a^{k-2}+c_{3}a^{k-3}+...+c_{k}a^{0}}$,

де ${\displaystyle a}$ це стала величина, а ${\displaystyle c_{1},...,c_{k}}$ це входові символи (але ця функція не є «відбитками пальців» Рабіна).

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

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

Примітки

1. Daniel Lemire, Owen Kaser: Recursive n-gram hashing is pairwise independent, at best, Computer Speech & Language 24 (4), pages 698–710, 2010. arXiv:0705.4676.