WikiSort.ru - Не сортированное

Кольцевой хеш (англ. rolling hash) — хеш-функция, обрабатывающая вход в рамках некоторого окна. Получение значения хеш-функции для сдвинутого окна в таких функциях является дешевой операцией. Для пересчета значения требуется знать лишь предыдущее значение хеша, значение входных данных, которые остались за пределами окна, и значение данных, которые попали в окно. Другими словами, если ${\displaystyle x=h(a_{1}a_{2}\cdots a_{n})}$ представляет собой хеш последовательности ${\displaystyle a_{1}a_{2}\cdots a_{n}}$ , то хеш ${\displaystyle h(a_{2}a_{3}\cdots a_{n}a_{n+1})}$ для «сдвинутой» последовательности ${\displaystyle a_{2}a_{3}\cdots a_{n}a_{n+1}}$ может быть получен с помощью легко вычислимой функции ${\displaystyle f(x,a_{1},a_{n+1})}$ .

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

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

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

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

${\displaystyle 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}}}$ .

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

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

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

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

${\displaystyle 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}}$ ,

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

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

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

${\displaystyle 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}),}$

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

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

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

Хеш Рабина

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

Результат хеширования строки ${\displaystyle a_{1}a_{2}\cdots a_{n}}$ — это последовательность битов ${\displaystyle b_{L-1}b_{L-2}\cdots b_{0}}$ . Число ${\displaystyle L}$ выбирается простым^[9] и достаточно большим, но так чтобы последовательность ${\displaystyle b_{L-1}b_{L-2}\cdots b_{0}}$ умещалась в одно машинное слово (обычно берут ${\displaystyle L=31}$ или ${\displaystyle L=61}$ ^[9]). Пусть ${\displaystyle P(x)=p_{L}x^{L}\oplus p_{L-1}x^{L-1}\oplus \cdots \oplus p_{1}x\oplus p_{0}}$ представляет собой некоторый неприводимый многочлен степени ${\displaystyle L}$ над полем ${\displaystyle \mathrm {GF} (2)}$ . Обозначим через ${\displaystyle p}$ соответствующее число с битовым представлением ${\displaystyle p_{L}p_{L-1}\cdots p_{0}}$ . Хеш-функция ${\displaystyle h(a_{1}a_{2}\cdots a_{n})}$ определяется как число с битовым представлением ${\displaystyle b_{L-1}b_{L-2}\cdots b_{0},}$ таким что многочлен ${\displaystyle B(x)=b_{L-1}x^{L-1}\oplus b_{L-2}x^{L-2}\oplus \cdots \oplus b_{1}x\oplus b_{0}}$ является остатком от деления многочлена ${\displaystyle A(x)=a_{1}x^{n-1}\oplus a_{2}x^{n-2}\oplus \cdots \oplus a_{n-1}x\oplus a_{n}}$ на многочлен ${\displaystyle P(x)}$ , то есть ${\displaystyle B(x)=A(x){\bmod {P}}(x)}$ .

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

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

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

Хеш является кольцевым. Пусть ${\displaystyle b=h(a_{1}a_{2}\cdots a_{n})}$ и ${\displaystyle b_{L-1}b_{L-2}\cdots b_{0}}$  — это битовое представление ${\displaystyle b}$ . Хеш ${\displaystyle h(a_{2}a_{3}\cdots a_{n}a_{n+1})}$ вычисляется следующим образом^[9]:

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

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

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

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

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

Ссылки

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

Примечания

Литература

• Cohen J. D. Recursive hashing functions for n-grams // ACM Transactions on Information Systems^[en]. — New York, USA: ACM, 1997. — Т. 15, № 3. — С. 291–320. — DOI:10.1145/256163.256168.
• Dietzfelbinger M., Gil J., Matias Y., Pippenger N.^[en]. Polynomial hash functions are reliable // Proceedings of the 19th International Colloquium on Automata, Languages and Programming^[en] (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^[en]. — 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.