Генерация бинарных патчей на 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 гласит:

Finding an optimal set of differences requires quadratic time relative to the input size, so it becomes unusable very quickly.

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

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

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

Редактировать # 2: Я обязательно найду реализацию python xdelta.