Tag Archives: кольцевой хэш

Xprer

Недавно возникла забавная задачка. Предположим, некий софт накапливает данные в файле. Иногда происходят сбои, и данные начинают записываться повторно в конец файла так, что результирующую структуру файла можно представить в виде трёх участков alpha alpha beta, где alpha — дублирующаяся последовательность байт (префикс). Корректный файл выглядит как alpha beta. Итак, задача: отбросить максимальный дублирующийся префикс в заданном файле за приемлемое время (файл может быть размером в десяток гигабайт).

Для решения данной задачи я написал небольшую консольную утилиту xprer «maXimal PREfix Reduction» (сборка под Windows x86-64, Microsoft Visual C++ 2013 runtime), принимающую один или два параметра командной строки: имя исходного файла и необязательное имя результирующего файла. Если имя результирующего файла не задано, то результат записывается в файл xprer.out.имя исходного файла.

Реализация утилиты использует стандартную библиотеку C++. Исходный код доступен здесь. Для поиска совпадения префикса используется подход, аналогичный алгоритму поиска подстроки Рабина-Карпа. Используется кольцевой хэш на основе суммы и суммы сумм (похож на Adler32, но имеет длину 64 бита и вычисляется по модулю 232).

Поиск совпадения начинается со сравнения половин файла (случай alpha alpha приводится к alpha). Далее префикс уменьшается на один байт до тех пор, пока не будет найдено совпадение, либо не будет достигнуто начало файла. Для получения хорошего быстродействия понадобилось выполнять буферизацию вручную (при чтении назад стандартная буферизация только мешает, для решения этой задачи написан класс StreamBackBuffer). Дальнейшая оптимизация возможна при переходе на отображаемые в память файлы и использовании предварительного поиска коротких совпадений, но мне это уже не понадобилось.

Реклама