Скользящий хеш

Скользящий хеш (Шаблон:Lang-en, также кольцевой хеш) — хеш-функция, обрабатывающая вход в рамках некоторого окна. Получение значения хеш-функции для сдвинутого окна в таких функциях является дешевой операцией. Для пересчета значения требуется знать лишь предыдущее значение хеша, значение входных данных, которые остались за пределами окна, и значение данных, которые попали в окно. Другими словами, если $x=h(a_1{a}_2\cdots a_n)$ представляет собой хеш последовательности $a_1{a}_2\cdots a_n$, то хеш $h(a_2{a}_3\cdots a_n{a}_{n+1})$ для «сдвинутой» последовательности $a_2{a}_3\cdots a_n{a}_{n+1}$ может быть получен с помощью легко вычислимой функции $f(x,a_1,a_{n+1})$.

Возможность быстрого «сдвига» хеша накладывает некоторые ограничения на теоретические гарантии. В частности, показаноШаблон:Sfn, что семейства кольцевых хешей не могут быть Шаблон:Iw; максимум — универсальными или Шаблон:Iw. Впрочем, для большинства приложений достаточно универсальности (даже приблизительной).

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

Полиномиальный хеш

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

$h(a_1{a}_2\cdots a_n)=(a_1{x}^{n-1}+a_2{x}^{n-2}+a_3{x}^{n-3}+\cdots +a_n{x}^0)modq$.

Чтобы избежать использования целочисленной арифметики произвольной точности, используется арифметика в кольце вычетов по модулю $q$, умещающемуся в одно машинное слово. Выбор констант $x$ и $q$ очень важен для получения качественного хеша. В исходном варианте хеша предполагалось, что $q$ должно быть случайно выбранным простым числом, а $x=2$.Шаблон:Sfn Но ввиду того, что алгоритм выбора случайного простого числа не такой простой, предпочитают использовать вариант хеша, в котором $q$ является фиксированным простым числом, а $x$ выбирается случайно из диапазона $\{0,1,\dots ,q-1\}$. Дитзфелбингер и др.Шаблон:Sfn показали, что такой вариант хеша имеет те же теоретические характеристики, что и исходный. В частности, вероятность совпадения значений хешей двух различных строк $a_1{a}_2\cdots a_n$ и $b_1{b}_2\cdots b_n$ не превосходит $1/n^c$, если $a_1,\dots ,a_n$ и $b_1,\dots ,b_n$ представляют собой целые числа из диапазона $[0,q)$, $q>n^{c+1}$ и $x$ выбирается действительно случайно.

Удаление старых входных символов и добавление новых производится путём прибавления или вычитания первого или последнего члена формулы (по модулю $q$). Для удаления члена $a_1{x}^{n-1}$ хранят заранее посчитанное значение $x^{n-1}modq$. Сдвиг окна производится путём домножения всего многочлена $h(a_1{a}_2\cdots a_n)$ на $x$ либо делением на $x$ (если $q$ простое, то в кольце вычетов возможно вместо деления производить умножение на обратную величину). На практике удобнее всего полагать $q=2^{31}-1$ или $q=2^{61}-1$ для, соответственно, 32- и 64-битовых машинных слов (это так называемые простые числа Мерсенна). В таком случае операция взятия модуля может быть выполнена на многих компьютерах с помощью быстрых операций побитового сдвига и сложения. Другой возможный выбор — значения $q=2^{32}-5$ или $q=2^{64}-59$, для которых тоже существуют быстрые алгоритмы взятия остатка от деления на $q$ (при этом диапазон допустимых значений $x$ немного сужают)Шаблон:Sfn. Частое заблуждение — полагать $q=2^{32}$. Существуют семейства строк, на которых хеш с $q=2^L$ будет всегда давать множество коллизий, независимо от выбора $L$.Шаблон:Sfn Эти и другие дальнейшие детали реализации и теоретического анализ полиномиального хеша можно найти в статье об алгоритме Рабина — Карпа.

Полиномиальный хеш над полем GF(2^L)

Данный хеш похож на обычный полиномиальный хеш, но все вычисления в нём производятся в конечном поле $\mathrm{G}\mathrm{F}(2^L)$. Обычно $L$ выбирается равным 64. Элементы поля — это числа $0,1,\dots ,2^L-1$. Сложение в поле реализуется с помощью операции побитового исключающего «или» $\oplus$, а умножение выполняется с помощью операции $a\star b$, которая сначала Шаблон:Iw $a$ на $b$, а потом берёт остаток от «беспереносного» деления результата на некоторый выбранный фиксированный элемент $q\in \{2^L,2^L+1,\dots ,2^{L+1}-1\}$ (беспереносным делением здесь названа операция, обратная беспереносному умножению). Элемент $q=2^{i_1}+2^{i_2}+\cdots +2^{i_k}$ должен быть выбран так, что $L=i_1>i_2>\cdots >i_k\ge 0$ и $x^{i_1}+x^{i_2}+\cdots +x^{i_0}$ — это неприводимый многочлен над полем $GF(2)$ (на поле $\mathrm{G}\mathrm{F}(2^L)$ часто смотрят как на множество многочленов над полем $\mathrm{G}\mathrm{F}(2)$ по модулю произвольного неприводимого многочлена степени $L$). Например, можно положить $q=2^{64}+2^4+2^3+2+1$Шаблон:Sfn. Тогда хеш вычисляется следующим образомШаблон:Sfn:

$h(a_1{a}_2\cdots a_n)=(a_1\star x^{n-1})\oplus (a_2\star x^{n-2})\oplus \cdots \oplus (a_{n-1}\star x)\oplus a_n$,

где $x$ — это случайно выбранное на этапе инициализации хеша число из диапазона $\{0,1,\dots ,2^L-1\}$, а $x^m$ — это короткая запись для $x\star x\star \cdots \star x$, где $x$ повторён $m$ раз. С помощью основной теоремы алгебры можно показать, что вероятность коллизии хешей двух различных строк длины $n$ не превосходит $n/2^L$. ПоказаноШаблон:Sfn, что на современных процессорах Intel и AMD вся необходимая для хеша арифметика над полем $\mathrm{G}\mathrm{F}(2^L)$ может быть эффективно вычислена с помощью инструкций из расширения Шаблон:Iw.

Хеш циклическими полиномами (Buzhash)

Пусть $h^{\prime }$ — какой-то хеш, который отображает символы $a_1,\dots ,a_n$ хешируемой строки в $L$-битовые числа (обычно $L=32$ или $L=64$). Хеш циклическими полиномами определяется следующим образомШаблон:Sfn:

$h(a_1{a}_2\cdots a_n)=s^{n-1}(h^{\prime }(a_1))\oplus s^{n-2}(h^{\prime }(a_2))\oplus \cdots \oplus s(h^{\prime }(a_{n-1}))\oplus h^{\prime }(a_n),$

где $\oplus$ — это операция побитового исключающего «или», а $s^i(x)$ — это операция циклического сдвига $L$-битового числа $x$ на $i$ битов влево. Несложно показать, что данный хеш кольцевой:

$h(a_2{a}_3\dots a_{n+1})=s(h(a_1{a}_2\dots a_n))\oplus s^n(h^{\prime }(a_1))\oplus h^{\prime }(a_{n+1}).$

Главное преимущество этого хеша в том, что он использует только быстрые побитовые операции доступные на многих современных компьютерах. Качество хеша напрямую зависит от выбора функции $h^{\prime }$. Лемире и КасерШаблон:Sfn доказали, что если функция $h^{\prime }$ выбирается случайно из семейства Шаблон:Iw, то вероятность совпадения хешей двух различных строк длины $n$ не превосходит $1/2^{L-n+1}$. Это накладывает определённые ограничения на диапазон задач, в которых данный хеш может использоваться. Во-первых, длина хешируемых строк должна быть меньше $L$. Для алгоритмов хеширования общего назначения это условие может быть проблемой, но, например, для хеширования $n$-грамм, где $n$ обычно не превосходит 16, такое ограничение является естественным (в случае $n$-грамм роль символов играют отдельные лексемы текста). Во-вторых, выбор семейства независимых функций $h^{\prime }$ в некоторых случаях тоже может быть проблемой. Для байтового алфавита свойством независимости обладает семейство функций $h^{\prime }$, закодированных таблицей из 256-и различных случайных $L$-битовых чисел (выбор функции — это заполнение таблицы). Для хеширования $n$-грамм можно присваивать различные случайные $L$-битовые числа различным лексемам (обычно число разных лексем в таких задачах относительно невелико) и такое семейство хеш-функций $h^{\prime }$ тоже имеет свойство независимости.

Хеш Рабина

Данный хеш применим только в специальном случае, когда символы хешируемой строки $a_1{a}_2\cdots a_n$ суть числа 0 и 1. Идея хеша в том, чтобы смотреть на входную строку $a_1{a}_2\cdots a_n$ как на многочлен $A(x)=a_1{x}^{n-1}\oplus a_2{x}^{n-2}\oplus \cdots \oplus a_{n-1}x\oplus a_n{x}^0$ над полем $\mathrm{G}\mathrm{F}(2)$, а сам хеш представляет собой взятие остатка от деления $A(x)$ на случайно выбранный на этапе инициализации хеша неприводимый многочлен $P(x)$ степени $L$ над полем $\mathrm{G}\mathrm{F}(2)$. По существу это та же процедура, что используется в CRC. Рассмотрим её более подробно.

Результат хеширования строки $a_1{a}_2\cdots a_n$ — это последовательность битов $b_{L-1}{b}_{L-2}\cdots b_0$. Число $L$ выбирается простымШаблон:Sfn и достаточно большим, но так чтобы последовательность $b_{L-1}{b}_{L-2}\cdots b_0$ умещалась в одно машинное слово (обычно берут $L=31$ или $L=61$Шаблон:Sfn). Пусть $P(x)=p_L{x}^L\oplus p_{L-1}{x}^{L-1}\oplus \cdots \oplus p_{1}x\oplus p_0$ представляет собой некоторый неприводимый многочлен степени $L$ над полем $\mathrm{G}\mathrm{F}(2)$. Обозначим через $p$ соответствующее число с битовым представлением $p_L{p}_{L-1}\cdots p_0$. Хеш-функция $h(a_1{a}_2\cdots a_n)$ определяется как число с битовым представлением $b_{L-1}{b}_{L-2}\cdots b_0,$ таким что многочлен $B(x)=b_{L-1}{x}^{L-1}\oplus b_{L-2}{x}^{L-2}\oplus \cdots \oplus b_{1}x\oplus b_0$ является остатком от деления многочлена $A(x)=a_1{x}^{n-1}\oplus a_2{x}^{n-2}\oplus \cdots \oplus a_{n-1}x\oplus a_n$ на многочлен $P(x)$, то есть $B(x)=A(x)modP(x)$.

Несмотря на весьма запутанное определение, хеш Рабина довольно просто реализуем (если неприводимый многочлен $P(x)$ уже найден). Вычисления опираются на такое несложное наблюдение: если число $b$ с битовым представлением $b_{L-1}{b}_{L-2}\cdots b_0$ кодирует многочлен $B(x)=b_{L-1}{x}^{L-1}\oplus b_{L-2}{x}^{L-2}\oplus \cdots \oplus b_{1}x\oplus b_0$, то число $sh(b)$ кодирует многочлен $x\cdot B(x)$, где $sh(b)$ обозначает операцию побитового сдвига числа $b$ на один бит влево с замещением младшего бита нулём (не путать с циклическим сдвигом $s$, определённым выше!). Пусть $b=h(a_1{a}_2\cdots a_i)$, и $b_{L-1}{b}_{L-2}\cdots b_0$ — это битовое представление $b$. Тогда $h(a_1{a}_2\cdots a_i{a}_{i+1})$ вычисляется следующим образом:

$sh(b)\oplus a_{i+1},$ если $b_{L-1}=0,$

$sh(b)\oplus p\oplus a_{i+1},$ если $b_{L-1}=1.$

Хеш является кольцевым. Пусть $b=h(a_1{a}_2\cdots a_n)$ и $b_{L-1}{b}_{L-2}\cdots b_0$ — это битовое представление $b$. Хеш $h(a_2{a}_3\cdots a_n{a}_{n+1})$ вычисляется следующим образомШаблон:Sfn:

$sh(b)\oplus a_n\oplus (a_1\cdot c),$ если $b_{L-1}=0,$

$sh(b)\oplus p\oplus a_n\oplus (a_1\cdot c),$ если $b_{L-1}=1,$

где $c$ — это $L$-битовое число, битовое представление которого соответствует многочлену $x^{n}modP(x)$. Число $c$ вычисляют заранее при инициализации хеша строки длины $n$.

Главная сложность — случайным образом выбрать неприводимый многочлен $P(x)$ степени $L$. РабинШаблон:Sfn описал эффективный алгоритм, позволяющий это сделать, и доказал, что вероятность коллизии хешей двух различных строк длины $n$ при случайном выборе $P(x)$ не превосходит $n/2^L$.

Отметим, что данный хеш часто путают с полиномиальным хешем из-за схожей области применения, рассмотрения многочленов и общего автора.

Ссылки

• ngramhashing — свободная C++-реализация нескольких кольцевых хеш-функций
• rollinghashjava  — Java-реализация кольцевых хеш-функций под лицензией Apache

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья