Кольцевой хеш

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Кольцевой хэш»)
Перейти к: навигация, поиск

Кольцевой хеш (англ. rolling hash) — хеш-функция, обрабатывающая вход в рамках некоторого окна. Получение значения хеш-функции для сдвинутого окна (window) в таких функциях является дешевой операцией. Для пересчета значения требуется знать лишь предыдущее значение хеша, значение входных данных, которые остались за пределами окна, и значение данных, которые попали в окно. Процесс сходен с вычислением Скользящей средней.

Применяется в алгоритме поиска подстроки Рабина — Карпа, а также в программе rsync для сравнения двоичных файлов (используется кольцевая версия adler-32).

Кольцевой хеш Рабина-Карпа[править | править вики-текст]

В алгоритме Рабина — Карпа часто используется простой полиномиальный кольцевой хеш, построенный на операциях умножения и сложения[1][2]:

,

где — случайное число от до , — фиксированное простое число, а  — входные символы.

Чтобы избежать использования целочисленной арифметики произвольной точности, используется арифметика в кольце вычетов по модулю , умещающемуся в одно машинное слово. Выбор констант и очень важен для получения качественного хеша (см. алгоритм Рабина — Карпа).

Удаление старых входных символов и добавление новых производится путём прибавления или вычитания первого или последнего члена формулы. Сдвиг окна производится путём домножения всего многочлена на либо делением на (в кольце вычетов возможно вместо деления производить умножение на обратную величину). При надлежащем выборе параметра можно выполнять операции взятия по модулю с помощью легковесных битовых операций, при этом сохраняя гарантии на низкую вероятность возникновения коллизий (см. алгоритм Рабина — Карпа).

Buzhash[править | править вики-текст]

Возможно также построение кольцевой хеш-функции без умножения (на операции сдвига)[3]. Подобные функции иногда называют Buzhash.

Ссылки[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Методы и алгоритмы вычислений на строках, 7.3
  2. R. M. Rabin, M. O. Karp. Efficient randomized pattern-matching algorithms // IBM Journal of Research and Development, USA: IBM — 1987 — Т. 31, № 2, С. 249-260.
  3. Jonathan D. Cohen, Recursive hashing functions for n-grams, ACM Trans. Inf. Syst. 15 (3), 1997