Русская Википедия:Скользящий хеш

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

<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 Но ввиду того, что алгоритм выбора случайного простого числа не такой простой, предпочитают использовать вариант хеша, в котором <math>q</math> является фиксированным простым числом, а <math>x</math> выбирается случайно из диапазона <math>\{0, 1, \ldots, q-1\}</math>. Дитзфелбингер и др.Шаблон:Sfn показали, что такой вариант хеша имеет те же теоретические характеристики, что и исходный. В частности, вероятность совпадения значений хешей двух различных строк <math>a_1 a_2 \cdots a_n</math> и <math>b_1 b_2 \cdots b_n</math> не превосходит <math>1 / n^c</math>, если <math>a_1, \ldots, a_n</math> и <math>b_1, \ldots, b_n</math> представляют собой целые числа из диапазона <math>[0,q)</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-битовых машинных слов (это так называемые простые числа Мерсенна). В таком случае операция взятия модуля может быть выполнена на многих компьютерах с помощью быстрых операций побитового сдвига и сложения. Другой возможный выбор — значения <math>q = 2^{32} - 5</math> или <math>q = 2^{64} - 59</math>, для которых тоже существуют быстрые алгоритмы взятия остатка от деления на <math>q</math> (при этом диапазон допустимых значений <math>x</math> немного сужают)Шаблон:Sfn. Частое заблуждение — полагать <math>q = 2^{32}</math>. Существуют семейства строк, на которых хеш с <math>q = 2^{L}</math> будет всегда давать множество коллизий, независимо от выбора <math>L</math>.Шаблон:Sfn Эти и другие дальнейшие детали реализации и теоретического анализ полиномиального хеша можно найти в статье об алгоритме Рабина — Карпа.

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

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

<math>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</math>,

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

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

Пусть <math>h'</math> — какой-то хеш, который отображает символы <math>a_1, \ldots, a_n</math> хешируемой строки в <math>L</math>-битовые числа (обычно <math>L = 32</math> или <math>L = 64</math>). Хеш циклическими полиномами определяется следующим образомШаблон:Sfn:

<math>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),</math>

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

<math>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}).</math>

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

Хеш Рабина

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

Результат хеширования строки <math>a_1 a_2 \cdots a_n</math> — это последовательность битов <math>b_{L-1} b_{L-2} \cdots b_0</math>. Число <math>L</math> выбирается простымШаблон:Sfn и достаточно большим, но так чтобы последовательность <math>b_{L-1} b_{L-2} \cdots b_0</math> умещалась в одно машинное слово (обычно берут <math>L = 31</math> или <math>L = 61</math>Шаблон:Sfn). Пусть <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>\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>s</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 p \oplus a_{i+1},</math> если <math>b_{L-1} = 1.</math>

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

<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>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 описал эффективный алгоритм, позволяющий это сделать, и доказал, что вероятность коллизии хешей двух различных строк длины <math>n</math> при случайном выборе <math>P(x)</math> не превосходит <math>n / 2^L</math>.

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

Ссылки

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

Литература

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