Кольцевой хеш

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Кольцевой хэш»)
Перейти к: навигация, поиск

Кольцевой хеш (англ. rolling hash) — хеш-функция, обрабатывающая вход в рамках некоторого окна. Получение значения хеш-функции для сдвинутого окна в таких функциях является дешевой операцией. Для пересчета значения требуется знать лишь предыдущее значение хеша, значение входных данных, которые остались за пределами окна, и значение данных, которые попали в окно. Другими словами, если представляет собой хеш последовательности , то хеш для «сдвинутой» последовательности может быть получен с помощью легко вычислимой функции .

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

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

Полиномиальный хеш[править | править код]

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

.

Чтобы избежать использования целочисленной арифметики произвольной точности, используется арифметика в кольце вычетов по модулю , умещающемуся в одно машинное слово. Выбор констант и очень важен для получения качественного хеша. В исходном варианте хеша предполагалось, что должно быть случайно выбранным простым число, а .[3] Но ввиду того, что алгоритм выбора случайного простого числа не такой простой, предпочитают использовать вариант хеша, в котором является фиксированным простым числом, а выбирается случайно из диапазона . Дитзфелбингер и др.[4] показали, что такой вариант хеша имеет те же теоретические характеристики, что и исходный. В частности, вероятность совпадения значений хешей двух различных строк длины не превосходит , если и выбирается действительно случайно.

Удаление старых входных символов и добавление новых производится путём прибавления или вычитания первого или последнего члена формулы (по модулю ). Для удаления члена хранят заранее посчитанное значение . Сдвиг окна производится путём домножения всего многочлена на либо делением на (если простое, то в кольце вычетов возможно вместо деления производить умножение на обратную величину). На практике удобнее всего полагать или для, соответственно, 32-х и 64-х битовых машинных слов (это так называемые простые числа Мерсенна). В таком случае операция взятия модуля может быть выполнена на многих компьютерах с помощью быстрых операций побитового сдвига и сложения[5]. Другой возможный выбор — значения или , для которых тоже существуют быстрые алгоритмы взятия остатка от деления на (при этом диапазон допустимых значений немного сужают)[6]. Частое заблуждение — полагать . Существуют семейства строк, на которых хеш с будет всегда давать множество коллизий, независимо от выбора .[7] Эти и другие дальнейшие детали реализации и теоретического анализ полиномиального хеша можно найти в статье об алгоритме Рабина — Карпа.

Полиномиальный хеш над полем GF(2L)[править | править код]

Данный хеш похож на обычный полиномиальный хеш, но все вычисления в нём производятся в конечном поле . Обычно выбирается равным 64. Элементы поля — это числа . Сложение в поле реализуется с помощью операции побитового исключающего «или» , а умножение выполняется с помощью операции , которая сначала беспереносно умножает[en] на , а потом берёт остаток от «беспереносного» деления результата на некоторый выбранный элемент (беспереносным делением здесь названа операция обратная беспереносному умножению). Элемент должен быть выбран так, что и — это неприводимый многочлен над полем (на поле часто смотрят как на множество многочленом над полем по модулю некоторого неприводимого многочлена степени ). Например, можно положить [8]. Тогда хеш вычисляется следующим образом[4]:

,

где — это случайно выбранное на этапе инициализации хеша число из диапазона , а — это короткая запись для , где повторён раз. С помощью основной теоремы алгебры можно показать, что вероятность коллизии хешей двух различных строк длины не превосходит . Показано[8], что на современных процессорах Intel и AMD вся необходимая для хеша арифметика над полем может быть эффективно вычислена с помощью инструкций из расширения CLMUL[en].

Хеш циклическими полиномами (Buzhash)[править | править код]

Пусть  — какой-то хеш, который отображает символы хешируемой строки в -битовые числа (обычно или ). Хеш циклическими полиномами определяется следующим образом[2]:

где  — это операция побитового исключающего «или», а  — это операция циклического сдвига -битового числа на битов влево. Несложно показать, что данный хеш кольцевой:

Главное преимущество этого хеша в том, что он использует только быстрые побитовые операции доступные на многих современных компьютерах. Качество хеша напрямую зависит от выбора функции . Лемире и Касер[1] доказали, что если функция выбирается случайно из семейства независимых хеш-функций[en], то вероятность совпадения хешей двух различных строк длины не превосходит . Это накладывает определённые ограничения на диапазон задач, в которых данный хеш может использоваться. Во-первых, длина хешируемых строк должна быть меньше . Для алгоритмов хеширования общего назначения это условие может быть проблемой, но, например, для хеширования -грамм, где обычно не превосходит 16, такое ограничение является естественным (в случае -грамм роль символов играют отдельные лексемы текста). Во-вторых, выбор семейства независимых функций в некоторых случаях тоже может быть проблемой. Для байтового алфавита свойством независимости обладает семейство функций , закодированных таблицей из 256-и различных случайных -битовых чисел (выбор функции — это заполнение таблицы). Для хеширования -грамм можно присваивать различные случайные -битовые числа различным лексемам (обычно число разных лексем в таких задачах относительно невелико) и такое семейство хеш-функций тоже имеет свойство независимости.

Хеш Рабина[править | править код]

Данный хеш применим только в специальном случае, когда символы хешируемой строки суть числа 0 и 1. Идея хеша в том, чтобы смотреть на последовательность битов , представляющую -битовое число-хеш, как на многочлен над полем вычетов по модулю 2 . Число выбирается простым и достаточно большим, но так чтобы последовательность умещалась в одно машинное слово (обычно берут или [9]). Пусть представляет собой некоторый неприводимый многочлен степени (то есть ) над полем и обозначим через соответствующее число с битовым представлением . Хеш-функция определяется как число с битовым представлением таким что многочлен является остатком от деления многочлена на многочлен , то есть .

Несмотря на весьма запутанное определение, хеш Рабина довольно просто реализуем (если неприводимый многочлен уже найден). Вычисления опираются на такое несложное наблюдение: если число с битовым представлением кодирует многочлен , то число кодирует многочлен , где обозначает операцию побитового сдвига числа на один бит влево (с замещением младшего бита нулём). Пусть и  — это битовое представление . Тогда вычисляется следующим образом:

если
если

Хеш является кольцевым. Пусть и  — это битовое представление . Хеш вычисляется следующим образом[9]:

если
если

где  — это -битовое число, битовое представление которого соответствует многочлену . Число вычисляют заранее при инициализации хеша строки длины .

Главная сложность — случайным образом выбрать неприводимый многочлен степени . Рабин[9] описал эффективный алгоритм, позволяющий это сделать, и доказал, что вероятность коллизии хешей двух различных строк длины при случайном выборе не превосходит .

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

Ссылки[править | править код]

Примечания[править | править код]

Литература[править | править код]