Бинарная генерация патчей на C#
https://stackoverflow.com/questions/5831
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У кого-нибудь есть или известно о реализации алгоритма генерации двоичных исправлений в C #?
В принципе, сравните два файла (обозначенных Старый и новое), и создать файл исправления, который можно использовать для обновления Старый файл должен иметь то же содержимое, что и новое файл.
Реализация должна быть относительно быстрой и работать с огромными файлами.Он должен показывать время выполнения O (n) или O (logn).
Мои собственные алгоритмы, как правило, либо паршивые (быстрые, но выдают огромные исправления), либо медленные (выдают небольшие исправления, но имеют время выполнения O (n ^ 2)).
Любые советы или указания по реализации были бы приятными.
В частности, реализация будет использоваться для синхронизации серверов для различных больших файлов данных, для которых у нас есть один главный сервер.Когда файлы данных главного сервера изменяются, нам также необходимо обновить несколько внешних серверов.
Самый наивный алгоритм, который я создал, который работает только для файлов, которые могут храниться в памяти, заключается в следующем:
- Возьмите первые четыре байта из Старый файл, назовем это Клавиша
- Добавьте эти байты в словарь, где клавиша -> положение, где положение это позиция, в которой я захватил эти 4 байта, 0 для начала
- Пропустите первый из этих четырех байтов, возьмите еще 4 (3 перекрываются, 1 один) и добавьте в словарь таким же образом
- Повторите шаги 1-3 для всех 4-байтовых блоков в Старый файл
- С самого начала новое файл, возьмите 4 байта и попытайтесь найти его в словаре
- Если найдено, найдите самое длинное совпадение, если их несколько, путем сравнения байтов из двух файлов
- Закодируйте ссылку на это местоположение в Старый файл, и пропустите соответствующий блок в новое файл
- Если не найден, закодируйте 1 байт из новое файл, и пропустите его
- Повторите шаги 5-8 для остальной части новое файл
Это чем-то похоже на сжатие, без управления окнами, поэтому будет использоваться много памяти.Это, однако, довольно быстро и выдает довольно небольшие исправления, пока я стараюсь сделать выводимые коды минимальными.
Более экономичный по объему памяти алгоритм использует управление окнами, но создает гораздо большие файлы исправлений.
В приведенном выше алгоритме есть еще несколько нюансов, которые я пропустил в этом посте, но при необходимости я могу опубликовать более подробную информацию.Однако я чувствую, что мне нужен совершенно другой алгоритм, поэтому улучшение приведенного выше алгоритма, вероятно, не продвинет меня достаточно далеко.
Правка №1:Вот более подробное описание приведенного выше алгоритма.
Сначала объедините два файла, чтобы у вас получился один большой файл.Запомните точку разреза между двумя файлами.
Во-вторых, сделайте это возьмите 4 байта и добавьте их позицию в словарь выполните действия для всего файла целиком.
В-третьих, откуда взялся новое запускается файл, выполните цикл с попыткой найти существующую комбинацию из 4 байт и найдите самое длинное совпадение.Убедитесь, что мы рассматриваем только позиции из старого файла или из ранее в новом файле, чем мы сейчас находимся.Это гарантирует, что мы сможем повторно использовать материал как в старом, так и в новом файле во время применения исправления.
Правка №2: Исходный код к приведенному выше алгоритму
Вы можете получить предупреждение о том, что с сертификатом возникли некоторые проблемы.Я не знаю, как это решить, поэтому на данный момент просто примите сертификат.
Исходный код использует множество других типов из остальной части моей библиотеки, так что этот файл - это не все, что требуется, но это реализация алгоритма.
@lomaxx, я пытался найти хорошую документацию по алгоритму, используемому в subversion, под названием xdelta, но если вы еще не знаете, как работает алгоритм, документы, которые я нашел, не сообщают мне того, что мне нужно знать.
Или, возможно, я просто тупица...:)
Я быстро просмотрел алгоритм с того сайта, который вы предоставили, и он, к сожалению, непригоден для использования.В комментарии из двоичного файла diff говорится:
Поиск оптимального набора различий требует квадратичного времени относительно размера входных данных, поэтому он очень быстро становится непригодным для использования.
Однако мои потребности не являются оптимальными, поэтому я ищу более практичное решение.
Спасибо за ответ, хотя добавил закладку в свои утилиты, если они мне когда-нибудь понадобятся.
Правка №1:Обратите внимание, я посмотрю на его код, чтобы посмотреть, смогу ли я найти какие-нибудь идеи, и я также позже отправлю ему электронное письмо с вопросами, но я прочитал книгу, на которую он ссылается, и, хотя решение хорошо подходит для поиска оптимальных решений, оно непрактично в использовании из-за требований времени.
Правка №2:Я обязательно поищу реализацию python xdelta.
Решение
Извини, что я не смог больше помочь.Я бы определенно продолжал смотреть на xdelta, потому что я использовал его несколько раз для создания качественных различий в ISO-файлах размером более 600 МБ, которые мы сгенерировали для распространения наших продуктов, и он работает очень хорошо.
Другие советы
bsdiff был разработан для создания очень маленьких исправлений для двоичных файлов.Как указано на его странице, для этого требуется max(17*n,9*n+m)+O(1) байт памяти и выполняется в O((n+m) log n) время (где n это размер старого файла и m это размер нового файла).
Исходная реализация написана на C, но описан порт C # здесь и доступный здесь.
Вы видели VCDiff?Это часть библиотеки Misc, которая, похоже, довольно активна (последний выпуск r259, 23 апреля 2008).Я им не пользовался, но подумал, что об этом стоит упомянуть.
Возможно, стоит проверить, что делают некоторые другие ребята в этом пространстве, и не обязательно на арене C #.
Это библиотека, написанная на c#
В SVN также есть алгоритм двоичного разделения, и я знаю, что есть реализация на python, хотя я не смог найти ее с помощью быстрого поиска.Они могут дать вам несколько идей о том, как улучшить ваш собственный алгоритм
Если это предназначено для установки или распространения, рассматривали ли вы возможность использования пакета SDK установщика Windows?У него есть возможность исправлять двоичные файлы.
http://msdn.microsoft.com/en-us/library/aa370578 (ПРОТИВ 85).aspx
Это приблизительное руководство, но ниже приведен алгоритм rsync, который может быть использован для создания ваших двоичных исправлений.
