Многие библиотеки или приложения дедупликации применяют алгоритм скользящего хеширования Рабина Карпа для быстрого хеширования, чтобы вырезать фрагмент из двоичного файла.
Мой вопрос: почему алгоритм Рабина Карпа часто используется для вырезания фрагмента?
Я знаю, что он быстрый. алгоритм скользящего хеширования, но мой вопрос более фундаментален.
Было бы много способов вырезать кусок.
Например, сравнение одного байта (без операции модификации) со значением для вырезания куска приведет к фрагменту размером 256 байт. в среднем.
Сравнение 9 битов даст в среднем 512 байтов и т. д.
Разве простое сравнение последних нескольких битов без хеширования не приведет к результату, аналогичному алгоритму скользящего хеширования, такому как Рабин Карп, но быстрее?
Связь между алгоритмом Рабина-Карпа и дедупликацией
Ответы (1)
Для дедупликации блоков переменного размера у нас есть два шага:
- Чанкинг
- Индексация
Скользящий хэш Рабина Карпа — это алгоритм фрагментации, который разрезает файл на части разного размера. Затем нам нужно проиндексировать/запросить фрагменты данных, так как мы делаем дедупликацию. Общий метод заключается в вычислении хеш-значения чанка и сохранении чанка с хешем в качестве ключа. С алгоритмом Рабина Карпа все просто, поскольку мы одновременно получаем хэш и блок данных.
Вы упомянули метод, который сравнивает последние несколько битов, может помочь разрезать файл на части, но если вы хотите проиндексировать эти куски, как мы можем получить ключ? Итак, вы должны вычислить хэш.
Надеюсь, это поможет.
person
zhangyuting
schedule
16.05.2017
