Скользящий (прокручивающий, кольцевой ) хеш rolling hash

Привет, Вы узнаете о том , что такое скользящий хеш, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое скользящий хеш, rolling hash, прокручивающий хеш , кольцевой хеш , настоятельно рекомендую прочитать все из категории Шифры в криптографии.

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

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

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

Еще одно популярное приложение - это программа rsync , которая использует контрольную сумму на основе adler-32 Марка Адлера в качестве скользящего хеша. Сетевая файловая система с низкой пропускной способностью (LBFS) использует отпечаток Рабина в качестве скользящего хэша. FastCDC (Fast Content-Defined Chunking) использует эффективный с точки зрения вычислений отпечаток Gear в качестве скользящего хэша.

В лучшем случае скользящие хеш-значения попарно независимы или строго универсальны . Например, они не могут быть 3-мя независимыми .

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

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

.

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

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

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

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

,

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

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

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

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

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

Хеш Рабина

Данный хеш применим только в специальном случае, когда символы хешируемой строки суть числа 0 и 1. Идея хеша в том, чтобы смотреть на входную строку как на многочлен над полем , а сам хеш представляет собой взятие остатка от деления на случайно выбранный на этапе инициализации хеша неприводимый многочлен степени над полем . По существу это та же процедура, что используется в CRC. Рассмотрим ее более подробно.

Результат хеширования строки — это последовательность битов . Число выбирается простым и достаточно большим, но так чтобы последовательность умещалась в одно машинное слово (обычно берут или ). Пусть представляет собой некоторый неприводимый многочлен степени над полем . Обозначим через соответствующее число с битовым представлением . Хеш-функция определяется как число с битовым представлением таким что многочлен является остатком от деления многочлена на многочлен , то есть .

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

если

если

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

если

если

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

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

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

Нарезка на основе содержимого с использованием скользящего хеша [ править ]

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

Самый простой подход к вычислению динамических фрагментов - это вычисление скользящего хеша, и если он соответствует шаблону (например, все младшие N бит - нули), то это граница фрагмента. Такой подход гарантирует, что любое изменение файла повлияет только на его текущий и, возможно, следующий фрагмент, но ни на что другое.

Когда границы известны, блоки необходимо сравнить по их хеш-значениям, чтобы определить, какой из них был изменен и нуждается в передаче по сети. Программа резервного копирования Attic использует алгоритм Buzhash с настраиваемым диапазоном размера блока для разделения потоков файлов.

Нарезка на основе содержимого с использованием скользящей суммы

Несколько программ, включая gzip (с --rsyncableопцией) и rsyncrypto, выполняют нарезку на основе содержимого на основе этой конкретной (невзвешенной) скользящей суммы:

где

• это сумма 8196 последовательных байтов, заканчивающихся байтом (требуется 21 бит памяти),
• это байт файла,
• "хеш-значение", состоящее из нижних 12 битов .

Сдвиг окна на один байт просто включает добавление нового символа к сумме и вычитание самого старого символа (уже не находящегося в окне) из суммы.

Для каждого где эти программы разрезают файл между и . Такой подход гарантирует, что любое изменение файла повлияет только на его текущий и, возможно, следующий фрагмент, но не на другой фрагмент.

Отпечаток устройства Gear и алгоритм фрагментации на основе контента FastCDC

Алгоритм Content-Defined Chunking (CDC) должен вычислять хэш-значение потока данных побайтно и разбивать поток данных на фрагменты, когда хеш-значение соответствует заранее заданному значению. Однако побайтовое сравнение строки приведет к значительным накладным расходам на вычисления. FastCDC предлагает новый и эффективный подход Content-Defined Chunking. Он использует быстрый алгоритм хеширования Gear , пропускающий минимальную длину, нормализуя распределение размеров фрагментов и, наконец, что не менее важно, каждый раз прокручивая два байта для ускорения алгоритма CDC, что позволяет достичь примерно в 10 раз большей пропускной способности. чем подход CDC, основанный на Рабине.

Псевдокод базовой версии представлен следующим образом:

Где Gear array - это предварительно рассчитанный массив хеширования. Здесь FastCDC использует алгоритм хеширования Gear, который может быстро вычислить результаты скользящего хеширования и сохранить равномерное распределение результатов хеширования, как у Рабина. По сравнению с традиционным алгоритмом хеширования Рабина, он обеспечивает гораздо более высокую скорость. Эксперименты показывают, что при сегментировании потока данных он может генерировать почти такое же распределение размеров фрагментов за гораздо более короткое время (около 1/10 фрагментов на основе рабина ).

Вычислительная сложность

Все скользящие хеш-функции линейны по количеству символов, но их сложность зависит от длины окна () варьируется. Скользящий хеш Рабина – Карпа требует умножения двух -битные числа, целочисленное умножение в . ^[10] Хеширование диаграмм циклическими полиномами может выполняться за линейное время.

Вау!! 😲 Ты еще не читал? Это зря!

• Хеш- функция
• w-shingling шинглинг

Исследование, описанное в статье про скользящий хеш, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое скользящий хеш, rolling hash, прокручивающий хеш , кольцевой хеш и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Шифры в криптографии