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). Дальнейшая оптимизация возможна при переходе на отображаемые в память файлы и использовании предварительного поиска коротких совпадений, но мне это уже не понадобилось.

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: