Скользящий хеш (Vtkl,[xpnw ]yo)

Скользящий хеш (англ. rolling hash, также кольцевой хеш) — хеш-функция, обрабатывающая вход в рамках некоторого окна. Получение значения хеш-функции для сдвинутого окна в таких функциях является дешевой операцией. Для пересчета значения требуется знать лишь предыдущее значение хеша, значение входных данных, которые остались за пределами окна, и значение данных, которые попали в окно. Другими словами, если $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})$.

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

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

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

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

$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}){\bmod {q}}$.

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

Удаление старых входных символов и добавление новых производится путём прибавления или вычитания первого или последнего члена формулы (по модулю $q$). Для удаления члена $a_{1}x^{n-1}$ хранят заранее посчитанное значение $x^{n-1}{\bmod {q}}$. Сдвиг окна производится путём домножения всего многочлена $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$ немного сужают). Частое заблуждение — полагать $q=2^{32}$. Существуют семейства строк, на которых хеш с $q=2^{L}$ будет всегда давать множество коллизий, независимо от выбора $L$. Эти и другие дальнейшие детали реализации и теоретического анализ полиномиального хеша можно найти в статье об алгоритме Рабина — Карпа.

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

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

$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,\ldots ,2^{L}-1\}$, а $x^{m}$ — это короткая запись для $x\star x\star \cdots \star x$, где $x$ повторён $m$ раз. С помощью основной теоремы алгебры можно показать, что вероятность коллизии хешей двух различных строк длины $n$ не превосходит $n/2^{L}$. Показано, что на современных процессорах Intel и AMD вся необходимая для хеша арифметика над полем $\mathrm {GF} (2^{L})$ может быть эффективно вычислена с помощью инструкций из расширения CLMUL.

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

Пусть $h'$ — какой-то хеш, который отображает символы $a_{1},\ldots ,a_{n}$ хешируемой строки в $L$-битовые числа (обычно $L=32$ или $L=64$). Хеш циклическими полиномами определяется следующим образом:

$h(a_{1}a_{2}\cdots a_{n})=s^{n-1}(h'(a_{1}))\oplus s^{n-2}(h'(a_{2}))\oplus \cdots \oplus s(h'(a_{n-1}))\oplus h'(a_{n}),$

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

$h(a_{2}a_{3}\ldots a_{n+1})=s(h(a_{1}a_{2}\ldots a_{n}))\oplus s^{n}(h'(a_{1}))\oplus h'(a_{n+1}).$

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

Хеш Рабина

Данный хеш применим только в специальном случае, когда символы хешируемой строки $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 {GF} (2)$, а сам хеш представляет собой взятие остатка от деления $A(x)$ на случайно выбранный на этапе инициализации хеша неприводимый многочлен $P(x)$ степени $L$ над полем $\mathrm {GF} (2)$. По существу это та же процедура, что используется в CRC. Рассмотрим её более подробно.

Результат хеширования строки $a_{1}a_{2}\cdots a_{n}$ — это последовательность битов $b_{L-1}b_{L-2}\cdots b_{0}$. Число $L$ выбирается простым и достаточно большим, но так чтобы последовательность $b_{L-1}b_{L-2}\cdots b_{0}$ умещалась в одно машинное слово (обычно берут $L=31$ или $L=61$). Пусть $P(x)=p_{L}x^{L}\oplus p_{L-1}x^{L-1}\oplus \cdots \oplus p_{1}x\oplus p_{0}$ представляет собой некоторый неприводимый многочлен степени $L$ над полем $\mathrm {GF} (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){\bmod {P}}(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}$, то число $\mathop {sh} (b)$ кодирует многочлен $x\cdot B(x)$, где $\mathop {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})$ вычисляется следующим образом:

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

$\mathop {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})$ вычисляется следующим образом:

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

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

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

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

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

Ссылки

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

Литература

• Cohen J. D. Recursive hashing functions for n-grams // ACM Transactions on Information Systems. — New York, USA: ACM, 1997. — Т. 15, № 3. — С. 291–320. — doi:10.1145/256163.256168.
• Dietzfelbinger M., Gil J., Matias Y., Pippenger N.. Polynomial hash functions are reliable // Proceedings of the 19th International Colloquium on Automata, Languages and Programming (ICALP'92). — Berlin, Germany: Springer-Verlag, 1992. — С. 235–246. — doi:10.1007/3-540-55719-9_77.
• Krovetz T., Rogaway P. Fast universal hashing with small keys and no preprocessing: the PolyR construction // Proceedings of the International Conference on Information Security and Cryptology. — Berlin, Germany: Springer-Verlag, 2000. — С. 73–89. — doi:10.1007/3-540-45247-8_7.
• Lemire D., Kaser O. Recursive n-gram hashing is pairwise independent, at best // Journal Computer Speech and Language. — London, UK: Academic Press Ltd., 2010. — Т. 24, № 4. — С. 698–710. — doi:10.1016/j.csl.2009.12.001.
• Lemire D., Kaser O. Faster 64-bit universal hashing using carry-less multiplications // Journal of Cryptographic Engineering. — Berlin, Germany: Springer-Verlag, 2016. — Т. 6, № 3. — С. 171–185. — doi:10.1007/s13389-015-0110-5.
• Рабин М. О. Fingerprinting by random polynomials // Tech Report TR-CSE-03-01. — Center for Research in Computing Technology, Harvard University, 1981. — С. 1–14. Архивировано 29 апреля 2018 года.
• Рабин М. О., Карп Р. М. Efficient randomized pattern-matching algorithms // IBM Journal of Research and Development. — IBM, 1987. — Т. 31, № 2. — С. 249–260. — doi:10.1147/rd.312.0249.
• Pachocki J., Radoszewski J. Where to use and how not to use polynomial string hashing // Olympiads in Informatics. — Vilnus, Lithuania: Vilnus University, 2013. — Т. 7. — С. 90–100.