Двоичная генерация патчей в C #

Кто-нибудь имеет или знает о реализации алгоритма генерации двоичных патчей в C #?

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

Реализация должна быть относительно быстрой и работать с огромными файлами. Он должен демонстрировать O (n) или O (logn) время выполнения.

Мои собственные алгоритмы обычно бывают паршивыми (быстрыми, но производят огромные исправления) или медленными (производят небольшие исправления, но имеют время выполнения O (n ^ 2)).

Любой совет или указатели для реализации были бы хорошими.

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

Самый наивный алгоритм, который я сделал, который работает только для файлов, которые могут храниться в памяти, заключается в следующем:

  1. Возьмите первые четыре байта из старого файла, назовите этот ключ
  2. Добавьте эти байты в словарь, где ключ -> позиция , где позиция - это позиция, где я взял эти 4 байта, 0 для начала
  3. Пропустите первый из этих четырех байтов, возьмите еще 4 (3 перекрытия, 1 один) и добавьте в словарь таким же образом
  4. Повторите шаги 1-3 для всех 4-байтовых блоков в старом файле.
  5. С самого начала нового файла возьмите 4 байта и попытайтесь найти его в словаре.
  6. Если найдено, найдите самое длинное совпадение, если их несколько, сравнив байты из двух файлов.
  7. Кодируйте ссылку на это местоположение в старом файле и пропустите соответствующий блок в новом файле.
  8. Если не найден, закодируйте 1 байт из нового файла и пропустите его
  9. Повторите шаги 5-8 для остальной части нового файла

Это похоже на сжатие без окон, поэтому оно будет использовать много памяти. Это, однако, довольно быстро, и производит довольно маленькие патчи, пока я пытаюсь сделать вывод кода минимальным.

Более эффективный в использовании алгоритм использует оконное управление, но производит гораздо большие файлы патчей.

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


Редактирование # 1 : Вот более подробное описание вышеприведенного алгоритма.

Сначала объедините два файла, чтобы у вас был один большой файл. Запомните точку отсечения между двумя файлами.

Во-вторых, захватите 4 байта и добавьте их позицию к шагу словаря для всего файла.

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


Редактирование # 2 : Исходный код для вышеуказанного алгоритма

Вы можете получить предупреждение о проблемах с сертификатом. Я не знаю, как решить это, так что пока просто принимаю сертификат.

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


@lomaxx, я попытался найти хорошую документацию для алгоритма, используемого в subversion, под названием xdelta, но если вы уже не знаете, как работает алгоритм, найденные документы не могут сказать мне, что мне нужно знать.

А может я просто дремучий ... :)

Я быстро взглянул на алгоритм с того сайта, который вы дали, и, к сожалению, его нельзя использовать. Комментарий из двоичного файла diff говорит:

Поиск оптимального набора различий требует квадратичного времени относительно размера ввода, поэтому он очень быстро становится непригодным для использования.

Хотя мои потребности не оптимальны, поэтому я ищу более практичное решение.

Спасибо за ответ, добавил закладку в его утилиты, если они мне когда-нибудь понадобятся.

Редактирование № 1 : Обратите внимание, я посмотрю на его код, чтобы узнать, смогу ли я найти какие-то идеи, и позже я пришлю ему письмо с вопросами, но я прочитал ту книгу, на которую он ссылается, и хотя решение хорошо для находя оптимальные решения, он нецелесообразен в использовании из-за временных требований.

Редактирование # 2 : Я определенно буду охотиться за реализацией Python Xdelta.

8.08.2008 12:22:07
Ссылка на исходный код не работает. Можете ли вы обновить его, пожалуйста?
lasseschou 7.04.2014 12:28:13
Этот конкретный фрагмент кода является post, вот моя текущая версия, хотя я давно не поддерживал эту библиотеку: lassevk.kilnhg.com/Code/LVK-for-NET/net-40/trunk/Files/…
Lasse V. Karlsen 7.04.2014 16:32:35
6 ОТВЕТОВ
РЕШЕНИЕ

Извините, я не могу помочь. Я бы определенно продолжал смотреть на xdelta, потому что я использовал его несколько раз для создания качественных различий для файлов размером 600 МБ + ISO, которые мы сгенерировали для распространения наших продуктов, и он работает очень хорошо.

5
8.08.2008 13:03:06
Да, xdelta это хорошо. Однако он работает на относительно небольших окнах (100 КБ, если я не ошибаюсь), но с его работающей реализацией я мог бы легко настроить это для наших данных. Размер окна был выбран для скорости для subversion, если я не ошибаюсь, но наш код может легко работать немного дольше, если он не должен занимать всю ночь (что делает моя текущая реализация).
Lasse V. Karlsen 8.08.2008 13:04:57

Возможно, стоит проверить, что другие парни делают в этом пространстве, и не обязательно на арене C #.

Это библиотека, написанная на C #

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

1
8.08.2008 12:48:09
SVN использует алгоритм xdelta (по крайней мере из взгляда на источник)
Simon Buchan 30.01.2009 07:07:28

Если это для установки или распространения, рассматривалось ли использование пакета установщика Windows SDK? Имеет возможность исправлять двоичные файлы.

http://msdn.microsoft.com/en-us/library/aa370578(VS.85).aspx

1
8.08.2008 18:26:45

Вы видели VCDiff ? Это часть библиотеки Misc, которая выглядит довольно активной (последний выпуск r259, 23 апреля 2008 г.). Я не использовал это, но думал, что стоит упомянуть.

3
6.09.2008 21:10:09

Это грубое руководство, но ниже приведен алгоритм rsync, который можно использовать для создания ваших двоичных патчей.

http://rsync.samba.org/tech_report/tech_report.html

0
4.05.2009 20:40:18

bsdiff был разработан для создания очень маленьких патчей для двоичных файлов. Как указано на его странице, он требует max(17*n,9*n+m)+O(1)байтов памяти и работает во O((n+m) log n)времени (где nразмер старого файла и mразмер нового файла).

Исходная реализация находится на C, но порт C # описан здесь и доступен здесь .

4
30.12.2010 00:07:06