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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

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 — входные символы.

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

Удаление старых входных символов и добавление новых производится путем прибавления или вычитания первого или последнего члена формулы. Сдвиг окна производится путем домножения всего многочлена H на a, либо делением на a (в кольце вычетов возможно вместо деления производить умножение на обратную величину).

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

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

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

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

  1. Методы и алгоритмы вычислений на строках, 7.3
  2. Jonathan D. Cohen, Recursive hashing functions for n-grams, ACM Trans. Inf. Syst. 15 (3), 1997