Кто-нибудь знает или знает о реализации алгоритма генерации двоичных патчей в C #?
По сути, сравните два файла (обозначенные old и new ) и создайте файл исправления, который можно использовать для обновления файла old , чтобы получить такое же содержимое, как у нового файла.
Реализация должна быть относительно быстрой и работать с огромными файлами. Он должен демонстрировать O (n) или O (logn) время выполнения.
Мои собственные алгоритмы обычно бывают паршивыми (быстрыми, но производят огромные исправления) или медленными (производят небольшие исправления, но имеют время выполнения O (n ^ 2)).
Любой совет или указатели для реализации были бы хорошими.
В частности, реализация будет использоваться для синхронизации серверов для различных больших файлов данных, для которых у нас есть один главный сервер. При изменении файлов данных главного сервера нам также необходимо обновить несколько внешних серверов.
Самый наивный алгоритм, который я сделал, который работает только для файлов, которые могут храниться в памяти, выглядит следующим образом:
- Получите первые четыре байта из старого файла, назовите его ключом
- Добавьте эти байты в словарь, где key -> position , где position - это позиция, где я взял эти 4 байта, 0 для начала
- Пропустите первый из этих четырех байтов, возьмите еще 4 (3 перекрытия, 1 один) и добавьте в словарь таким же образом
- Повторите шаги 1-3 для всех 4-байтовых блоков в старом файле
- С самого начала нового файла захватите 4 байта и попытайтесь найти его в словаре
- Если найдено, найдите самое длинное совпадение, если их несколько, сравнив байты из двух файлов
- Кодируйте ссылку на это местоположение в старом файле и пропустите соответствующий блок в новом файле
- Если не найден, закодируйте 1 байт из нового файла и пропустите его
- Повторите шаги 5-8 для остальной части нового файла
Это похоже на сжатие без окон, поэтому оно будет использовать много памяти. Это, однако, довольно быстро, и производит довольно маленькие патчи, пока я пытаюсь сделать вывод кода минимальным.
Более эффективный в использовании алгоритм использует оконное управление, но создает гораздо большие файлы исправлений.
В приведенном выше алгоритме есть больше нюансов, которые я пропустил в этом сообщении, но я могу опубликовать более подробную информацию, если это необходимо. Я, однако, чувствую, что мне нужен совсем другой алгоритм, поэтому улучшение этого алгоритма, вероятно, не приведет меня достаточно далеко.
Редактировать # 1 : Вот более подробное описание вышеприведенного алгоритма.
Сначала объедините два файла, чтобы у вас был один большой файл. Запомните точку между двумя файлами.
Во-вторых, сделайте это , захватите 4 байта и добавьте их позицию в словарь шаг для всего во всем файле.
В-третьих, откуда начинается файл new , выполните цикл, пытаясь найти существующую комбинацию из 4 байтов и найти самое длинное совпадение. Убедитесь, что мы рассматриваем только позиции из старого файла или из ранее в новом файле, чем мы в настоящее время на . Это гарантирует, что мы можем повторно использовать материал как в старом, так и в новом файле во время применения патча.
Edit # 2 : Исходный код для вышеуказанного алгоритма
Вы можете получить предупреждение о проблемах с сертификатом. Я не знаю, как решить эту проблему, поэтому в настоящее время просто примите сертификат.
Источник использует множество других типов из остальной части моей библиотеки, так что файл - это не все, что нужно, но это реализация алгоритма.
@ lomaxx, я попытался найти хорошую документацию для алгоритма, используемого в subversion, под названием xdelta, но если вы уже не знаете, как работает алгоритм, найденные мной документы не могут сказать мне, что мне нужно знать.
Или, может быть, я просто плотный ...:)
Я быстро взглянул на алгоритм с того сайта, который вы дали, и, к сожалению, его нельзя использовать. Комментарий из бинарного файла diff гласит:
Для нахождения оптимального набора различий требуется квадратичное время относительно размера ввода, поэтому оно очень быстро становится непригодным для использования.
Хотя мои потребности не оптимальны, поэтому я ищу более практичное решение.
Спасибо за ответ, добавил закладку в его утилиты, если они мне когда-нибудь понадобятся.
Редактировать # 1 : Обратите внимание, я посмотрю на его код, чтобы узнать, смогу ли я найти какие-то идеи, и позже отправлю ему письмо с вопросами, но я прочитал эту книгу. он ссылается и, хотя решение подходит для поиска оптимальных решений, оно нецелесообразно в использовании из-за временных требований.
Редактировать # 2 : Я обязательно поищу реализацию xdelta на python.