Кто-нибудь знает или знает о реализации алгоритма генерации двоичных патчей в С#?
В принципе, сравните два файла (назначенные старым и новым) и создайте файл исправлений, который можно использовать для обновления старого файла, чтобы иметь такое же содержимое, что и новый файл.
Реализация должна быть относительно быстрой и работать с огромными файлами. Он должен демонстрировать время работы O (n) или O (logn).
Мои собственные алгоритмы имеют тенденцию либо быть паршивыми (быстрыми, но производят огромные исправления), либо медленными (производят небольшие патчи, но имеют O (n ^ 2) время выполнения).
Любые советы или указатели для реализации будут приятными.
В частности, реализация будет использоваться для синхронизации серверов для различных больших файлов данных, для которых у нас есть один главный сервер. Когда файлы данных главного сервера меняются, нам также необходимо обновить несколько серверов вне сайта.
Самый наивный алгоритм, который я сделал, который работает только для файлов, которые могут храниться в памяти, выглядит следующим образом:
Это похоже на сжатие, без окон, поэтому он будет использовать много памяти. Это, однако, довольно быстро и создает довольно маленькие исправления, если я пытаюсь сделать минимальные коды.
Более эффективный с точки зрения памяти алгоритм использует окно, но создает гораздо большие файлы патчей.
Есть больше нюансов к вышеуказанному алгоритму, который я пропустил в этом сообщении, но при необходимости могу опубликовать более подробную информацию. Тем не менее, я считаю, что мне нужен совсем другой алгоритм, поэтому улучшение по вышеуказанному алгоритму, вероятно, не приведет меня достаточно далеко.
Изменить # 1. Ниже приведено более подробное описание алгоритма.
Сначала объедините два файла, чтобы у вас был один большой файл. Помните точку пересечения между двумя файлами.
Во-вторых, сделайте это, захватите 4 байта и добавьте их позицию на шаг словаря для всего, что находится во всем файле.
В-третьих, начиная с того места, где начинается новый файл, выполните цикл с попыткой найти существующую комбинацию из 4 байтов и найдите самое длинное совпадение. Удостоверьтесь, что мы рассматриваем только позиции из старого файла или ранее в новом файле, чем в настоящее время. Это гарантирует, что мы можем повторно использовать материал как в старом, так и в новом файле во время применения патча.
Изменить # 2: Исходный код для вышеуказанного алгоритма
Вы можете получить предупреждение о наличии каких-либо проблем с сертификатом. Я не знаю, как разрешить это, поэтому пока просто принимаем сертификат.
Источник использует множество других типов из остальной части моей библиотеки, поэтому файл не все, что требуется, но это реализация алгоритма.
@lomaxx, я попытался найти хорошую документацию для алгоритма, используемого в subversion, называемого xdelta, но если вы уже не знаете, как работает алгоритм, документы, которые я нашел, не могут сказать мне, что мне нужно знать.
Или, может быть, я просто плотный...:)
Я быстро взглянул на алгоритм с того сайта, который вы дали, и, к сожалению, он неприменим. Комментарий от двоичного файла diff говорит:
Поиск оптимального набора различий требует квадратичного времени относительно размера ввода, поэтому он становится непригодным для использования очень быстро.
Мои потребности не оптимальны, поэтому я ищу более практичное решение.
Спасибо за ответ, хотя добавили закладку в его утилиты, если они мне понадобятся.
Изменить # 1: Заметьте, я посмотрю на его код, чтобы узнать, могу ли я найти некоторые идеи, и я также отправлю ему электронное письмо позже с вопросами, но я прочитал эту книгу, которую он ссылается, и хотя решение хорошо подходит для поиска оптимальных решений, это нецелесообразно в использовании из-за требований времени.
Изменить # 2. Я определенно выслежу реализацию python xdelta.
Жаль, что больше не помогала. Я бы определенно продолжал смотреть на xdelta, потому что я использовал его несколько раз, чтобы произвести качественные различия с файлами 600MB + ISO, которые мы создали для распространения наших продуктов, и он работает очень хорошо.
bsdiff был разработан для создания очень маленьких патчей для двоичных файлов. Как указано на его странице, для этого требуется max(17*n,9*n+m)+O(1) байт памяти и работает в O((n+m) log n) времени (где n - размер старого файла, а m - размер нового файла).
Исходная реализация находится на C, но порт С# описывается здесь и доступен .
Вы видели VCDiff? Это часть библиотеки Misc, которая выглядит довольно активной (последний выпуск r259, 23 апреля 2008 г.). Я не использовал его, но думал, что стоит упомянуть.
Возможно, стоит проверить, что делают некоторые из других парней в этом пространстве, а не обязательно на арене С#.
Это библиотека, написанная в С#
SVN также имеет бинарный алгоритм diff, и я знаю, что реализация в python, хотя я не смог найти его с помощью быстрого поиска. Они могут дать вам несколько идей о том, где можно улучшить собственный алгоритм.
Если это касается установки или распространения, рассмотрели ли вы использование SDK установщика Windows? Он имеет возможность исправлять двоичные файлы.
http://msdn.microsoft.com/en-us/library/aa370578(VS.85).aspx
Это приблизительная рекомендация, но для алгоритма rsync можно использовать следующие алгоритмы, которые можно использовать для создания ваших двоичных патчей.