Скользящий хеш: различия между версиями
[непроверенная версия] | [непроверенная версия] |
м союз "а" |
Дополнил дискуссию о полиномиальном хеше. Добавил литературу. |
||
Строка 10: | Строка 10: | ||
Чтобы избежать использования целочисленной арифметики произвольной точности, используется арифметика в [[кольцо вычетов|кольце вычетов]] по модулю <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>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}</math>. Существуют семейства строк, на которых хеш с <math>q = 2^{L}</math> будет всегда давать множество [[Коллизия хеш-функции|коллизий]], независимо от выбора <math>L</math>.{{sfn|Pachocki, Radoszewski|2013}} Эти и другие дальнейшие детали реализации и теоретического анализ полиномиального хеша можно найти в статье об [[Алгоритм Рабина — Карпа#Используемая хеш-функция|алгоритме Рабина — Карпа]]. |
Удаление старых входных символов и добавление новых производится путём прибавления или вычитания первого или последнего члена формулы (по модулю <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}} Эти и другие дальнейшие детали реализации и теоретического анализ полиномиального хеша можно найти в статье об [[Алгоритм Рабина — Карпа#Используемая хеш-функция|алгоритме Рабина — Карпа]]. |
||
== Хеш циклическими полиномами (Buzhash) == |
== Хеш циклическими полиномами (Buzhash) == |
||
Строка 67: | Строка 67: | ||
|ref=Dietzfelbinger, Gil, Matias, Pippinger |
|ref=Dietzfelbinger, Gil, Matias, Pippinger |
||
|doi=10.1007/3-540-55719-9_77 |
|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 |
|||
|издательство= Springer-Verlag |
|||
|место= Berlin, Germany |
|||
|страницы=73–89 |
|||
|год=2000 |
|||
|ref=Krovetz, Rogaway |
|||
|doi=10.1007/3-540-45247-8_7 |
|||
}} |
}} |
||
* {{статья |
* {{статья |
Версия от 15:18, 30 марта 2018
Кольцевой хеш (англ. rolling hash) — хеш-функция, обрабатывающая вход в рамках некоторого окна. Получение значения хеш-функции для сдвинутого окна в таких функциях является дешевой операцией. Для пересчета значения требуется знать лишь предыдущее значение хеша, значение входных данных, которые остались за пределами окна, и значение данных, которые попали в окно. Другими словами, если представляет собой хеш последовательности , то хеш для «сдвинутой» последовательности может быть получен с помощью легко вычислимой функции .
Возможность быстрого «сдвига» хеша накладывает некоторые ограничения на теоретические гарантии. В частности, показано[1], что семейства кольцевых хешей не могут быть 3-независимыми[англ.]; максимум — универсальными или 2-независимыми[англ.]. Впрочем, для большинства приложений достаточно универсальности (даже приблизительной).
Кольцевой хеш применяется для поиска подстроки в алгоритме Рабина — Карпа, для вычисления хешей N-грамм в тексте[2], а также в программе rsync для сравнения двоичных файлов (используется кольцевая версия adler-32).
Полиномиальный хеш Рабина — Карпа
В алгоритме Рабина — Карпа часто используется простой полиномиальный кольцевой хеш, построенный на операциях умножения и сложения[3][4]:
- .
Чтобы избежать использования целочисленной арифметики произвольной точности, используется арифметика в кольце вычетов по модулю , умещающемуся в одно машинное слово. Выбор констант и очень важен для получения качественного хеша. В исходном варианте хеша предполагалось, что должно быть случайно выбранным простым число, а .[3] Но ввиду того, что алгоритм выбора случайного простого числа не такой простой, предпочитают использовать вариант хеша, в котором является фиксированным простым числом, а выбирается случайно из диапазона . Дитзфелбингер и др.[4] показали, что такой вариант хеша имеет те же теоретические характеристики, что и исходный. В частности, вероятность совпадения значений хешей двух различных строк длины не превосходит , если и выбирается действительно случайно.
Удаление старых входных символов и добавление новых производится путём прибавления или вычитания первого или последнего члена формулы (по модулю ). Для удаления члена хранят заранее посчитанное значение . Сдвиг окна производится путём домножения всего многочлена на либо делением на (если простое, то в кольце вычетов возможно вместо деления производить умножение на обратную величину). На практике удобнее всего полагать или для, соответственно, 32-х и 64-х битовых машинных слов (это так называемые простые числа Мерсенна). В таком случае операция взятия модуля может быть выполнена на многих компьютерах с помощью быстрых операций побитового сдвига и сложения[5]. Другой возможный выбор — значения или , для которых тоже существуют быстрые алгоритмы взятия остатка от деления на (при этом диапазон допустимых значений немного сужают)[6]. Частое заблуждение — полагать . Существуют семейства строк, на которых хеш с будет всегда давать множество коллизий, независимо от выбора .[7] Эти и другие дальнейшие детали реализации и теоретического анализ полиномиального хеша можно найти в статье об алгоритме Рабина — Карпа.
Хеш циклическими полиномами (Buzhash)
Пусть — какой-то хеш, который отображает символы хешируемой строки в -битовые числа (обычно или ). Хеш циклическими полиномами определяется следующим образом[2]:
где — это операция побитового исключающего «или», а — это операция циклического сдвига -битового числа на битов влево. Несложно показать, что данный хеш кольцевой:
Главное преимущество этого хеша в том, что он использует только быстрые побитовые операции доступные на многих современных компьютерах. Качество хеша напрямую зависит от выбора функции . Лемире и Касер[1] доказали, что если функция выбирается случайно из семейства независимых хеш-функций[англ.], то вероятность совпадения хешей двух различных строк длины не превосходит . Это накладывает определённые ограничения на диапазон задач, в которых данный хеш может использоваться. Во-первых, длина хешируемых строк должна быть меньше . Для алгоритмов хеширования общего назначения это условие может быть проблемой, но, например, для хеширования -грамм, где обычно не превосходит 16, такое ограничение является естественным (в случае -грамм роль символов играют отдельные лексемы текста). Во-вторых, выбор семейства независимых функций в некоторых случаях тоже может быть проблемой. Для байтового алфавита свойством независимости обладает семейство функций , закодированных таблицей из 256-и различных случайных -битовых чисел (выбор функции — это заполнение таблицы). Для хеширования -грамм можно присваивать различные случайные -битовые числа различным лексемам (обычно число разных лексем в таких задачах относительно невелико) и такое семейство хеш-функций тоже имеет свойство независимости.
Хеш Рабина
Данный хеш применим только в специальном случае, когда символы хешируемой строки суть числа 0 и 1. Идея хеша в том, чтобы смотреть на последовательность битов , представляющую -битовое число-хеш, как на многочлен над полем вычетов по модулю 2 (). Число выбирается простым и достаточно большим, но так чтобы последовательность умещалась в одно машинное слово (обычно берут или [8]). Пусть представляет собой некоторый неприводимый многочлен степени (то есть ) над полем и обозначим через соответствующее число с битовым представлением . Хеш-функция определяется как число с битовым представлением таким что многочлен является остатком от деления многочлена на многочлен , то есть .
Несмотря на весьма запутанное определение, хеш Рабина довольно просто реализуем (если неприводимый многочлен уже найден). Вычисления опираются на такое несложное наблюдение: если число с битовым представлением кодирует многочлен , то число кодирует многочлен , где обозначает операцию побитового сдвига числа на один бит влево (с замещением младшего бита нулём). Пусть и — это битовое представление . Тогда вычисляется следующим образом:
- если
- если
Хеш является кольцевым. Пусть и — это битовое представление . Хеш вычисляется следующим образом[8]:
- если
- если
где — это -битовое число, битовое представление которого соответствует многочлену . Число вычисляют заранее при инициализации хеша строки длины .
Главная сложность — случайным образом выбрать неприводимый многочлен степени . Рабин[8] описал эффективный алгоритм, позволяющий это сделать, и доказал, что вероятность коллизии хешей двух различных строк длины при случайном выборе не превосходит .
Отметим, что данный хеш часто путают с полиномиальным хешем Рабина — Карпа из-за схожей области применения, рассмотрения многочленов и общего автора.
Ссылки
- 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 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.
- Рабин М. О. 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.