Прокручивающийся хеш - Rolling hash

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

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

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

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

Полиномиальный скользящий хеш

В Алгоритм поиска строки Рабина – Карпа часто объясняется с помощью скользящей хеш-функции, которая использует только умножения и сложения:

${displaystyle H=c_{1}a^{k-1}+c_{2}a^{k-2}+c_{3}a^{k-3}+...+c_{k}a^{0},}$

куда ${displaystyle a}$ константа, а ${displaystyle c_{1},...,c_{k}}$ являются входными символами (но эта функция не Отпечаток пальца рабина, Смотри ниже).

Во избежание манипулирования огромными ${displaystyle H}$ значения, вся математика сделана по модулю ${displaystyle n}$. Выбор ${displaystyle a}$ и ${displaystyle n}$ критически важно для хорошего хеширования; видеть линейный конгруэнтный генератор для дальнейшего обсуждения.

Удаление и добавление символов просто включает добавление или вычитание первого или последнего члена. Для сдвига всех символов на одну позицию влево необходимо умножить всю сумму ${displaystyle H}$ к ${displaystyle a}$. Сдвиг всех символов на одну позицию вправо требует деления всей суммы ${displaystyle H}$ к ${displaystyle a}$. Обратите внимание, что в арифметике по модулю ${displaystyle a}$ можно выбрать мультипликативный обратный ${displaystyle a^{-1}}$ по которому ${displaystyle H}$ можно умножить, чтобы получить результат деления без фактического выполнения деления.

Отпечаток пальца рабина

В Отпечаток пальца рабина это еще один хеш, который также интерпретирует ввод как полином, но по Поле Галуа GF (2). Вместо того, чтобы рассматривать ввод как полином из байтов, он рассматривается как полином из битов, и вся арифметика выполняется в GF (2) (аналогично CRC32 ). Хеш - это результат деления этого многочлена на неприводимый многочлен над GF (2). Можно обновить отпечаток Рабина, используя только входной и выходной байты, что фактически делает его скользящим хешем.

Поскольку он имеет того же автора, что и алгоритм поиска строки Рабина – Карпа, который часто объясняется другим, более простым скользящим хешем, и поскольку этот более простой скользящий хеш также является многочленом, оба скользящих хеш-значения часто ошибочно принимают друг за друга. Программное обеспечение для резервного копирования отдыхать использует отпечаток Рабина для разделения файлов с размером BLOB-объекта от 512 байт до 8 МБ.^[2]

Циклический полином

Хеширование циклическим полиномом^[3]- иногда называемый Бужаш - также прост, но он позволяет избежать умножения, используя бочки вместо. Это форма хеширование таблиц: предполагается, что есть какая-то хеш-функция ${displaystyle h}$ от символов к целым числам в интервале ${displaystyle [0,2^{L})}$. Эта хеш-функция может быть просто массивом или хеш-таблица отображение символов на случайные целые числа. Пусть функция ${displaystyle s}$ - циклическое двоичное вращение (или круговой сдвиг ): он поворачивает биты на 1 влево, помещая последний бит в первую позицию. Например., ${displaystyle s(10011)=00111}$. Позволять ${displaystyle oplus }$ быть побитовым Эксклюзивный или. Хеш-значения определены как

${displaystyle H=s^{k-1}(h(c_{1}))oplus s^{k-2}(h(c_{2}))oplus ldots oplus s(h(c_{k-1}))oplus h(c_{k}),}$

где умножение на степень двойки может быть реализовано двоичным сдвигом. Результат - число в ${displaystyle [0,2^{L})}$.

Вычисление хеш-значений в скользящем режиме выполняется следующим образом. Позволять ${displaystyle H}$ быть предыдущим значением хеш-функции. Повернуть ${displaystyle H}$ однажды: ${displaystyle Hleftarrow s(H)}$. Если ${displaystyle c_{1}}$ это персонаж, который нужно удалить, поверните его ${displaystyle k}$ раз: ${displaystyle s^{k}(h(c_{1}))}$. Затем просто установите

${displaystyle Hleftarrow s(H)oplus s^{k}(h(c_{1}))oplus h(c_{k+1}),}$

куда ${displaystyle c_{k+1}}$ это новый персонаж.

Хеширование с помощью циклических многочленов является строго универсальным или попарно независимым: просто оставьте первое ${displaystyle L-k+1}$ биты. То есть взять результат ${displaystyle H}$ и уволить любой ${displaystyle k-1}$ последовательные биты.^[1] На практике это достигается целочисленным делением ${displaystyle Hightarrow Hdiv 2^{k-1}}$.

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

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

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

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

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

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

${displaystyle S(n)=sum _{i=n-8195}^{n}c_{i},}$

${displaystyle H(n)=S(n)mod 4096,}$

куда

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

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

Для каждого ${displaystyle n}$ куда ${displaystyle H(n)==0}$эти программы разрезают файл между ${displaystyle n}$ и ${displaystyle n+1}$Такой подход гарантирует, что любое изменение файла повлияет только на его текущий и, возможно, следующий фрагмент, но не на другой фрагмент.

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

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

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

алгоритм FastCDC Вход: буфер данных src, длина данных п,     выход: точка разреза я        MinSize ← 2 КБ // минимальный размер фрагмента 2 КБ MaxSize ← 64 КБ // максимальный размер фрагмента - 64 КБ fp ← 0    я ← MinSize    Маска ← 0x0000d93003530000LL        // размер буфера меньше минимального размера блока если п ≤ MinSize тогда        возвращаться п    если п ≥ MaxSize тогда        п ← MaxSize         пока я < п делать        fp ← (fp << 1 ) + Механизм[src[я]]        если !(fp & Маска) тогда            возвращаться я       возвращаться я

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

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

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

Программного обеспечения

• Rollinghashcpp это бесплатно программное обеспечение C ++ реализация нескольких скользящих хэш-функций
• Rollinghashjava представляет собой лицензированную Apache реализацию Java скользящих хеш-функций

Смотрите также

• MinHash
• шинглинг

внешняя ссылка

• MIT 6.006: Введение в алгоритмы 2011 - Конспект лекций - скользящий хеш

Сноски

1. Дэниел Лемир, Оуэн Касер: Рекурсивный пХеширование -граммы в лучшем случае попарно независимое, Computer Speech & Language 24 (4), страницы 698–710, 2010. arXiv: 0705.4676.
2. «Ссылки - документация restic 0.9.0». restic.readthedocs.io. Получено 2018-05-24.
3. Джонатан Д. Коэн, Рекурсивные функции хеширования для п-Граммы, ACM Trans. Инф. Syst. 15 (3), 1997.
4. Хорват, Адам (24 октября 2012 г.). "Скользящий хеш Рабина Карпа - блоки динамического размера на основе хешированного содержимого".
5. «Структуры данных и форматы файлов - документация Borg - Deduplicating Archiver 1.1.5». borgbackup.readthedocs.io. Получено 2018-05-24.
6. «Алгоритм Rsyncrypto».
7. Ся, Вэнь; Чжоу, Юкунь; Цзян, Хун; Фэн, Дэн; Хуа, Ю; Ху Юйчун; Лю, Цин; Чжан, Юйчэн. «FastCDC: быстрый и эффективный подход к разделению на блоки с определением содержимого для дедупликации данных». USENIX. Получено 2020-07-24.
8. Ся, Вэнь; Цзян, Хун; Фэн, Дэн; Тиан, Лэй; Фу, Мин; Чжоу, Юкун (2014). «Ddelta: основанный на дедупликации подход быстрого дельта-сжатия». Оценка эффективности. 79: 258–272. Дои:10.1016 / j.peva.2014.07.016. ISSN  0166-5316.
9. Ся, Вэнь; Цзоу, Сянъюй; Цзян, Хун; Чжоу, Юкунь; Лю, Чуаньи; Фэн, Дэн; Хуа, Ю; Ху Юйчун; Чжан, Юйчэн (16.06.2020). «Проектирование быстрого группирования с определением содержимого для систем хранения на основе дедупликации данных». Транзакции IEEE в параллельных и распределенных системах. 31 (9): 2017–2031. Дои:10.1109 / TPDS.2020.2984632. S2CID  215817722. Получено 2020-07-22.
10. М. Фюрер, Ускоренное умножение целых чисел, в: STOC ’07, 2007, стр. 57–66.