Скользящий хеш: различия между версиями
[непроверенная версия] | [непроверенная версия] |
Дополнил дискуссию о полиномиальном хеше. Добавил литературу. |
Добавил раздел о полиномиальном хеше над полями размера 2^L. Добавил ещё одну ссылку на операции в этом хеше. |
||
Строка 1: | Строка 1: | ||
'''Кольцевой хеш''' ({{lang-en|rolling hash}}) — хеш-функция, обрабатывающая вход в рамках некоторого окна. Получение значения хеш-функции для сдвинутого окна в таких функциях является дешевой операцией. Для пересчета значения требуется знать лишь предыдущее значение хеша, значение входных данных, которые остались за пределами окна, и значение данных, которые попали в окно. Другими словами, если <math>x = h(a_1 a_2 \cdots a_n)</math> представляет собой хеш последовательности <math>a_1 a_2 \cdots a_n</math>, то хеш <math>h(a_2 a_3 \cdots a_n a_{n+1})</math> для «сдвинутой» последовательности <math>a_2 a_3 \cdots a_n a_{n+1}</math> может быть получен с помощью легко вычислимой функции <math>f(x, a_1, a_{n+1})</math>. |
'''Кольцевой хеш''' ({{lang-en|rolling hash}}) — хеш-функция, обрабатывающая вход в рамках некоторого окна. Получение значения хеш-функции для сдвинутого окна в таких функциях является дешевой операцией. Для пересчета значения требуется знать лишь предыдущее значение хеша, значение входных данных, которые остались за пределами окна, и значение данных, которые попали в окно. Другими словами, если <math>x = h(a_1 a_2 \cdots a_n)</math> представляет собой хеш последовательности <math>a_1 a_2 \cdots a_n</math>, то хеш <math>h(a_2 a_3 \cdots a_n a_{n+1})</math> для «сдвинутой» последовательности <math>a_2 a_3 \cdots a_n a_{n+1}</math> может быть получен с помощью легко вычислимой функции <math>f(x, a_1, a_{n+1})</math>. |
||
Возможность быстрого «сдвига» хеша накладывает некоторые ограничения на теоретические гарантии. В частности, показано{{sfn|Lemire, Kaser|2010}}, что семейства кольцевых хешей не могут быть {{iw|k-независимое хеширование|3-независимыми|en|k-independent hashing}}; максимум |
Возможность быстрого «сдвига» хеша накладывает некоторые ограничения на теоретические гарантии. В частности, показано{{sfn|Lemire, Kaser|2010}}, что семейства кольцевых хешей не могут быть {{iw|k-независимое хеширование|3-независимыми|en|k-independent hashing}}; максимум — [[Универсальное хеширование|универсальными]] или {{iw|k-независимое хеширование|2-независимыми|en|k-independent hashing}}. Впрочем, для большинства приложений достаточно универсальности (даже приблизительной). |
||
Кольцевой хеш применяется для поиска подстроки в алгоритме [[Алгоритм Рабина — Карпа|Рабина — Карпа]], для вычисления хешей [[N-грамма|N-грамм]] в тексте{{sfn|Cohen|1997}}, а также в программе [[rsync]] для сравнения двоичных файлов (используется кольцевая версия [[adler-32]]). |
Кольцевой хеш применяется для поиска подстроки в алгоритме [[Алгоритм Рабина — Карпа|Рабина — Карпа]], для вычисления хешей [[N-грамма|N-грамм]] в тексте{{sfn|Cohen|1997}}, а также в программе [[rsync]] для сравнения двоичных файлов (используется кольцевая версия [[adler-32]]). |
||
== Полиномиальный хеш |
== Полиномиальный хеш == |
||
В [[алгоритм Рабина — Карпа|алгоритме Рабина — Карпа]] часто используется простой полиномиальный кольцевой хеш, построенный на операциях умножения и сложения{{sfn|Rabin, Karp|1987}}{{sfn|Dietzfelbinger, Gil, Matias, Pippinger|1992}}: |
В [[алгоритм Рабина — Карпа|алгоритме Рабина — Карпа]] часто используется простой полиномиальный кольцевой хеш, построенный на операциях умножения и сложения{{sfn|Rabin, Karp|1987}}{{sfn|Dietzfelbinger, Gil, Matias, Pippinger|1992}}: |
||
: <math>h(a_1 a_2 \cdots a_n) = (a_1 x^{n-1} + a_2 x^{n-2} + a_3 x^{n-3} + |
: <math>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</math>. |
||
Чтобы избежать использования целочисленной арифметики произвольной точности, используется арифметика в [[кольцо вычетов|кольце вычетов]] по модулю <math>q</math>, умещающемуся в одно машинное слово. Выбор констант <math>x</math> и <math>q</math> очень важен для получения качественного хеша. В исходном варианте хеша предполагалось, что <math>q</math> должно быть случайно выбранным простым число, а <math>x = 2</math>.{{sfn|Rabin, Karp|1987}} Но ввиду того, что алгоритм выбора случайного простого числа не такой простой, предпочитают использовать вариант хеша, в котором <math>q</math> является фиксированным простым числом, а <math>x</math> выбирается случайно из диапазона <math>\{0, 1, \ldots, q-1\}</math>. Дитзфелбингер и др.{{sfn|Dietzfelbinger, Gil, Matias, Pippinger|1992}} показали, что такой вариант хеша имеет те же теоретические характеристики, что и исходный. В частности, вероятность совпадения значений хешей двух различных строк длины <math>\leq n</math> не превосходит <math>1 / n^c</math>, если <math>q > n^{c+1}</math> и <math>x</math> выбирается действительно случайно. |
Чтобы избежать использования целочисленной арифметики произвольной точности, используется арифметика в [[кольцо вычетов|кольце вычетов]] по модулю <math>q</math>, умещающемуся в одно машинное слово. Выбор констант <math>x</math> и <math>q</math> очень важен для получения качественного хеша. В исходном варианте хеша предполагалось, что <math>q</math> должно быть случайно выбранным простым число, а <math>x = 2</math>.{{sfn|Rabin, Karp|1987}} Но ввиду того, что алгоритм выбора случайного простого числа не такой простой, предпочитают использовать вариант хеша, в котором <math>q</math> является фиксированным простым числом, а <math>x</math> выбирается случайно из диапазона <math>\{0, 1, \ldots, q-1\}</math>. Дитзфелбингер и др.{{sfn|Dietzfelbinger, Gil, Matias, Pippinger|1992}} показали, что такой вариант хеша имеет те же теоретические характеристики, что и исходный. В частности, вероятность совпадения значений хешей двух различных строк длины <math>\leq n</math> не превосходит <math>1 / n^c</math>, если <math>q > n^{c+1}</math> и <math>x</math> выбирается действительно случайно. |
||
Удаление старых входных символов и добавление новых производится путём прибавления или вычитания первого или последнего члена формулы (по модулю <math>q</math>). Для удаления члена <math>a_1 x^{n-1}</math> хранят заранее посчитанное значение <math>x^{n-1} \bmod q</math>. Сдвиг окна производится путём домножения всего многочлена <math>h(a_1 a_2 \cdots a_n)</math> на <math>x</math> либо делением на <math>x</math> (если <math>q</math> простое, то в кольце вычетов возможно вместо деления производить умножение на обратную величину). На практике удобнее всего полагать <math>q = 2^{31} - 1</math> или <math>q = 2^{61} - 1</math> для, соответственно, 32-х и 64-х битовых машинных слов (это так называемые [[Число Мерсенна|простые числа Мерсенна]]). В таком случае операция взятия модуля может быть выполнена на многих компьютерах с помощью быстрых операций побитового сдвига и сложения<ref name="Bit">S. E. Anderson. [https://graphics.stanford.edu/~seander/bithacks.html Bit twiddling hacks.]</ref>. Другой возможный выбор |
Удаление старых входных символов и добавление новых производится путём прибавления или вычитания первого или последнего члена формулы (по модулю <math>q</math>). Для удаления члена <math>a_1 x^{n-1}</math> хранят заранее посчитанное значение <math>x^{n-1} \bmod q</math>. Сдвиг окна производится путём домножения всего многочлена <math>h(a_1 a_2 \cdots a_n)</math> на <math>x</math> либо делением на <math>x</math> (если <math>q</math> простое, то в кольце вычетов возможно вместо деления производить умножение на обратную величину). На практике удобнее всего полагать <math>q = 2^{31} - 1</math> или <math>q = 2^{61} - 1</math> для, соответственно, 32-х и 64-х битовых машинных слов (это так называемые [[Число Мерсенна|простые числа Мерсенна]]). В таком случае операция взятия модуля может быть выполнена на многих компьютерах с помощью быстрых операций побитового сдвига и сложения<ref name="Bit">S. E. Anderson. [https://graphics.stanford.edu/~seander/bithacks.html Bit twiddling hacks.]</ref>. Другой возможный выбор — значения <math>q = 2^{32} - 5</math> или <math>q = 2^{64} - 59</math>, для которых тоже существуют быстрые алгоритмы взятия остатка от деления на <math>q</math> (при этом диапазон допустимых значений <math>x</math> немного сужают){{sfn|Krovetz, Rogaway|2000}}. Частое заблуждение — полагать <math>q = 2^{32}</math>. Существуют семейства строк, на которых хеш с <math>q = 2^{L}</math> будет всегда давать множество [[Коллизия хеш-функции|коллизий]], независимо от выбора <math>L</math>.{{sfn|Pachocki, Radoszewski|2013}} Эти и другие дальнейшие детали реализации и теоретического анализ полиномиального хеша можно найти в статье об [[Алгоритм Рабина — Карпа#Используемая хеш-функция|алгоритме Рабина — Карпа]]. |
||
== Полиномиальный хеш над полем GF(2<sup>L</sup>) == |
|||
Данный хеш похож на обычный полиномиальный хеш, но все вычисления в нём производятся в [[Конечное поле|конечном поле]] <math>\mathrm{GF}(2^L)</math>. Обычно <math>L</math> выбирается равным 64. Элементы поля — это числа <math>0, 1, \ldots, 2^L - 1</math>. Сложение в поле реализуется с помощью операции [[Сложение по модулю 2|побитового исключающего «или»]] <math>\oplus</math>, а умножение выполняется с помощью операции {{iw|Беспереносное уножение|беспереносного умножения|en|Carry-less pdroduct}} и последующего взятия остатка от «беспереносного» деления (беспереносным делением здесь названа операция обратная беспереносному умножению) на некоторый выбранный элемент <math>q</math>, соответствующий неприводимому многочлену над полем (на поле <math>\mathrm{GF}(2^L)</math> можно смотреть как на множество многочленом над полем <math>\mathrm{GF}(2)</math>). Например, можно положить <math>q = 2^{64} + 2^4 + 2^3 + 2 + 1</math>{{sfn|Lemire, Kaser|2016}}. Тогда хеш вычисляется следующим образом: |
|||
: <math>h(a_1 a_2 \cdots a_n) = a_1 \star x^{n-1} \oplus a_2 \star x^{n-2} \oplus a_3 x^{n-3} \oplus \cdots \oplus a_n x^{0}</math>. |
|||
Показано{{sfn|Lemire, Kaser|2016}}, что на современных процессорах [[Intel]] и [[AMD]] такой хеш можно эффективно вычислить с помощью инструкций из расширения {{iw|Набор инструкций CLMUL|CLMUL |en|CLMUL instruction set}}. |
|||
== Хеш циклическими полиномами (Buzhash) == |
== Хеш циклическими полиномами (Buzhash) == |
||
Строка 21: | Строка 26: | ||
== Хеш Рабина == |
== Хеш Рабина == |
||
Данный хеш применим только в специальном случае, когда символы хешируемой строки <math>a_1 a_2 \cdots a_n</math> суть числа 0 и 1. Идея хеша в том, чтобы смотреть на последовательность битов <math>b_{L-1} b_{L-2} \cdots b_0</math>, представляющую <math>L</math>-битовое число-хеш, как на многочлен <math>b_{L-1} x^{L-1} \oplus b_{L-2} x^{L-2} \oplus \cdots \oplus b_1 x \oplus b_0</math> над [[Кольцо вычетов|полем вычетов по модулю 2 |
Данный хеш применим только в специальном случае, когда символы хешируемой строки <math>a_1 a_2 \cdots a_n</math> суть числа 0 и 1. Идея хеша в том, чтобы смотреть на последовательность битов <math>b_{L-1} b_{L-2} \cdots b_0</math>, представляющую <math>L</math>-битовое число-хеш, как на многочлен <math>b_{L-1} x^{L-1} \oplus b_{L-2} x^{L-2} \oplus \cdots \oplus b_1 x \oplus b_0</math> над [[Кольцо вычетов|полем вычетов по модулю 2 <math>\mathrm{GF}(2)</math>]]. Число <math>L</math> выбирается простым и достаточно большим, но так чтобы последовательность <math>b_{L-1} b_{L-2} \cdots b_0</math> умещалась в одно машинное слово (обычно берут <math>L = 31</math> или <math>L = 61</math>{{sfn|Rabin|1981}}). Пусть <math>P(x) = p_{L} x^L \oplus p_{L-1} x^{L-1} \oplus \cdots \oplus p_1 x \oplus p_0</math> представляет собой некоторый [[неприводимый многочлен]] степени <math>L</math> (то есть <math>p_L \ne 0</math>) над полем <math>\mathrm{GF}(2)</math> и обозначим через <math>p</math> соответствующее число с битовым представлением <math>p_{L} p_{L-1} \cdots p_0</math>. Хеш-функция <math>h(a_1 a_2 \cdots a_n)</math> определяется как число с битовым представлением <math>b_{L-1} b_{L-2} \cdots b_0,</math> таким что многочлен <math>B(x) = b_{L-1} x^{L-1} \oplus b_{L-2} x^{L-2} \oplus \cdots \oplus b_1 x \oplus b_0</math> является остатком от деления многочлена <math>A(x) = a_{1} x^{n-1} \oplus a_{2} x^{n-2} \oplus \cdots \oplus a_{n-1} x \oplus a_n</math> на многочлен <math>P(x)</math>, то есть <math>B(x) = A(x) \bmod P(x)</math>. |
||
Несмотря на весьма запутанное определение, хеш Рабина довольно просто реализуем (если неприводимый многочлен <math>P(x)</math> уже найден). Вычисления опираются на такое несложное наблюдение: если число <math>b</math> с битовым представлением <math>b_{L-1} b_{L-2} \cdots b_0</math> кодирует многочлен <math>B(x) = b_{L-1} x^{L-1} \oplus b_{L-2} x^{L-2} \oplus \cdots \oplus b_1 x \oplus b_0</math>, то число <math>\mathop{sh}(b)</math> кодирует многочлен <math>x\cdot B(x)</math>, где <math>\mathop{sh}(b)</math> обозначает операцию [[Битовый сдвиг|побитового сдвига]] числа <math>b</math> на один бит влево (с замещением младшего бита нулём). Пусть <math>b = h(a_1 a_2 \cdots a_i)</math> и <math>b_{L-1} b_{L-2} \cdots b_0</math> |
Несмотря на весьма запутанное определение, хеш Рабина довольно просто реализуем (если неприводимый многочлен <math>P(x)</math> уже найден). Вычисления опираются на такое несложное наблюдение: если число <math>b</math> с битовым представлением <math>b_{L-1} b_{L-2} \cdots b_0</math> кодирует многочлен <math>B(x) = b_{L-1} x^{L-1} \oplus b_{L-2} x^{L-2} \oplus \cdots \oplus b_1 x \oplus b_0</math>, то число <math>\mathop{sh}(b)</math> кодирует многочлен <math>x\cdot B(x)</math>, где <math>\mathop{sh}(b)</math> обозначает операцию [[Битовый сдвиг|побитового сдвига]] числа <math>b</math> на один бит влево (с замещением младшего бита нулём). Пусть <math>b = h(a_1 a_2 \cdots a_i)</math> и <math>b_{L-1} b_{L-2} \cdots b_0</math> — это битовое представление <math>b</math>. Тогда <math>h(a_1 a_2 \cdots a_{i} a_{i+1})</math> вычисляется следующим образом: |
||
: <math>\mathop{sh}(b) \oplus a_{i+1},</math> если <math>b_{L-1} = 0,</math> |
: <math>\mathop{sh}(b) \oplus a_{i+1},</math> если <math>b_{L-1} = 0,</math> |
||
: <math>\mathop{sh}(b) \oplus p \oplus a_{i+1},</math> если <math>b_{L-1} = 1.</math> |
: <math>\mathop{sh}(b) \oplus p \oplus a_{i+1},</math> если <math>b_{L-1} = 1.</math> |
||
Строка 30: | Строка 35: | ||
: <math>\mathop{sh}(b) \oplus a_n \oplus (a_1\cdot c),</math> если <math>b_{L-1} = 0,</math> |
: <math>\mathop{sh}(b) \oplus a_n \oplus (a_1\cdot c),</math> если <math>b_{L-1} = 0,</math> |
||
: <math>\mathop{sh}(b) \oplus p \oplus a_n \oplus (a_1\cdot c),</math> если <math>b_{L-1} = 1,</math> |
: <math>\mathop{sh}(b) \oplus p \oplus a_n \oplus (a_1\cdot c),</math> если <math>b_{L-1} = 1,</math> |
||
где <math>c</math> |
где <math>c</math> — это <math>L</math>-битовое число, битовое представление которого соответствует многочлену <math>x^{n} \bmod P(x)</math>. Число <math>c</math> вычисляют заранее при инициализации хеша строки длины <math>n</math>. |
||
Главная сложность |
Главная сложность — случайным образом выбрать неприводимый многочлен <math>P(x)</math> степени <math>L</math>. Рабин{{sfn|Rabin|1981}} описал эффективный алгоритм, позволяющий это сделать, и доказал, что вероятность коллизии хешей двух различных строк длины <math>n</math> при случайном выборе <math>P(x)</math> не превосходит <math>n / 2^L</math>. |
||
Отметим, что данный хеш часто путают с полиномиальным хешем |
Отметим, что данный хеш часто путают с полиномиальным хешем из-за схожей области применения, рассмотрения многочленов и общего автора. |
||
== Ссылки == |
== Ссылки == |
||
Строка 91: | Строка 96: | ||
|ref=Lemire, Kaser |
|ref=Lemire, Kaser |
||
|doi=10.1016/j.csl.2009.12.001 |
|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 |
|||
|издательство= Springer-Verlag |
|||
|номер=3 |
|||
|том=6 |
|||
|место= Berlin, Germany |
|||
|страницы=171–185 |
|||
|год=2016 |
|||
|ref=Lemire, Kaser |
|||
|doi=10.1007/s13389-015-0110-5 |
|||
}} |
}} |
||
* {{статья |
* {{статья |
Версия от 16:01, 30 марта 2018
Кольцевой хеш (англ. rolling hash) — хеш-функция, обрабатывающая вход в рамках некоторого окна. Получение значения хеш-функции для сдвинутого окна в таких функциях является дешевой операцией. Для пересчета значения требуется знать лишь предыдущее значение хеша, значение входных данных, которые остались за пределами окна, и значение данных, которые попали в окно. Другими словами, если представляет собой хеш последовательности , то хеш для «сдвинутой» последовательности может быть получен с помощью легко вычислимой функции .
Возможность быстрого «сдвига» хеша накладывает некоторые ограничения на теоретические гарантии. В частности, показано[1], что семейства кольцевых хешей не могут быть 3-независимыми[англ.]; максимум — универсальными или 2-независимыми[англ.]. Впрочем, для большинства приложений достаточно универсальности (даже приблизительной).
Кольцевой хеш применяется для поиска подстроки в алгоритме Рабина — Карпа, для вычисления хешей N-грамм в тексте[2], а также в программе rsync для сравнения двоичных файлов (используется кольцевая версия adler-32).
Полиномиальный хеш
В алгоритме Рабина — Карпа часто используется простой полиномиальный кольцевой хеш, построенный на операциях умножения и сложения[3][4]:
- .
Чтобы избежать использования целочисленной арифметики произвольной точности, используется арифметика в кольце вычетов по модулю , умещающемуся в одно машинное слово. Выбор констант и очень важен для получения качественного хеша. В исходном варианте хеша предполагалось, что должно быть случайно выбранным простым число, а .[3] Но ввиду того, что алгоритм выбора случайного простого числа не такой простой, предпочитают использовать вариант хеша, в котором является фиксированным простым числом, а выбирается случайно из диапазона . Дитзфелбингер и др.[4] показали, что такой вариант хеша имеет те же теоретические характеристики, что и исходный. В частности, вероятность совпадения значений хешей двух различных строк длины не превосходит , если и выбирается действительно случайно.
Удаление старых входных символов и добавление новых производится путём прибавления или вычитания первого или последнего члена формулы (по модулю ). Для удаления члена хранят заранее посчитанное значение . Сдвиг окна производится путём домножения всего многочлена на либо делением на (если простое, то в кольце вычетов возможно вместо деления производить умножение на обратную величину). На практике удобнее всего полагать или для, соответственно, 32-х и 64-х битовых машинных слов (это так называемые простые числа Мерсенна). В таком случае операция взятия модуля может быть выполнена на многих компьютерах с помощью быстрых операций побитового сдвига и сложения[5]. Другой возможный выбор — значения или , для которых тоже существуют быстрые алгоритмы взятия остатка от деления на (при этом диапазон допустимых значений немного сужают)[6]. Частое заблуждение — полагать . Существуют семейства строк, на которых хеш с будет всегда давать множество коллизий, независимо от выбора .[7] Эти и другие дальнейшие детали реализации и теоретического анализ полиномиального хеша можно найти в статье об алгоритме Рабина — Карпа.
Полиномиальный хеш над полем GF(2L)
Данный хеш похож на обычный полиномиальный хеш, но все вычисления в нём производятся в конечном поле . Обычно выбирается равным 64. Элементы поля — это числа . Сложение в поле реализуется с помощью операции побитового исключающего «или» , а умножение выполняется с помощью операции беспереносного умножения[англ.] и последующего взятия остатка от «беспереносного» деления (беспереносным делением здесь названа операция обратная беспереносному умножению) на некоторый выбранный элемент , соответствующий неприводимому многочлену над полем (на поле можно смотреть как на множество многочленом над полем ). Например, можно положить [8]. Тогда хеш вычисляется следующим образом:
- .
Показано[8], что на современных процессорах Intel и AMD такой хеш можно эффективно вычислить с помощью инструкций из расширения CLMUL[англ.].
Хеш циклическими полиномами (Buzhash)
Пусть — какой-то хеш, который отображает символы хешируемой строки в -битовые числа (обычно или ). Хеш циклическими полиномами определяется следующим образом[2]:
где — это операция побитового исключающего «или», а — это операция циклического сдвига -битового числа на битов влево. Несложно показать, что данный хеш кольцевой:
Главное преимущество этого хеша в том, что он использует только быстрые побитовые операции доступные на многих современных компьютерах. Качество хеша напрямую зависит от выбора функции . Лемире и Касер[1] доказали, что если функция выбирается случайно из семейства независимых хеш-функций[англ.], то вероятность совпадения хешей двух различных строк длины не превосходит . Это накладывает определённые ограничения на диапазон задач, в которых данный хеш может использоваться. Во-первых, длина хешируемых строк должна быть меньше . Для алгоритмов хеширования общего назначения это условие может быть проблемой, но, например, для хеширования -грамм, где обычно не превосходит 16, такое ограничение является естественным (в случае -грамм роль символов играют отдельные лексемы текста). Во-вторых, выбор семейства независимых функций в некоторых случаях тоже может быть проблемой. Для байтового алфавита свойством независимости обладает семейство функций , закодированных таблицей из 256-и различных случайных -битовых чисел (выбор функции — это заполнение таблицы). Для хеширования -грамм можно присваивать различные случайные -битовые числа различным лексемам (обычно число разных лексем в таких задачах относительно невелико) и такое семейство хеш-функций тоже имеет свойство независимости.
Хеш Рабина
Данный хеш применим только в специальном случае, когда символы хешируемой строки суть числа 0 и 1. Идея хеша в том, чтобы смотреть на последовательность битов , представляющую -битовое число-хеш, как на многочлен над полем вычетов по модулю 2 . Число выбирается простым и достаточно большим, но так чтобы последовательность умещалась в одно машинное слово (обычно берут или [9]). Пусть представляет собой некоторый неприводимый многочлен степени (то есть ) над полем и обозначим через соответствующее число с битовым представлением . Хеш-функция определяется как число с битовым представлением таким что многочлен является остатком от деления многочлена на многочлен , то есть .
Несмотря на весьма запутанное определение, хеш Рабина довольно просто реализуем (если неприводимый многочлен уже найден). Вычисления опираются на такое несложное наблюдение: если число с битовым представлением кодирует многочлен , то число кодирует многочлен , где обозначает операцию побитового сдвига числа на один бит влево (с замещением младшего бита нулём). Пусть и — это битовое представление . Тогда вычисляется следующим образом:
- если
- если
Хеш является кольцевым. Пусть и — это битовое представление . Хеш вычисляется следующим образом[9]:
- если
- если
где — это -битовое число, битовое представление которого соответствует многочлену . Число вычисляют заранее при инициализации хеша строки длины .
Главная сложность — случайным образом выбрать неприводимый многочлен степени . Рабин[9] описал эффективный алгоритм, позволяющий это сделать, и доказал, что вероятность коллизии хешей двух различных строк длины при случайном выборе не превосходит .
Отметим, что данный хеш часто путают с полиномиальным хешем из-за схожей области применения, рассмотрения многочленов и общего автора.
Ссылки
- ngramhashing — свободная C++ реализация нескольких кольцевых хеш-функций
- rollinghashjava — Java реализация кольцевых хеш-функций под лицензией Apache
Примечания
- ↑ 1 2 Lemire, Kaser, 2010.
- ↑ 1 2 Cohen, 1997.
- ↑ 1 2 Rabin, Karp, 1987.
- ↑ 1 2 Dietzfelbinger, Gil, Matias, Pippinger, 1992.
- ↑ S. E. Anderson. Bit twiddling hacks.
- ↑ Krovetz, Rogaway, 2000.
- ↑ Pachocki, Radoszewski, 2013.
- ↑ 1 2 Lemire, Kaser, 2016.
- ↑ 1 2 3 Rabin, 1981.
Литература
- 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.