Алгоритм сравнения бинарных файлов

[Savant]

Если честно, то я не знаю как это правильно называется, поэтому поясню на примере.

Файл 1 - исходный:

aaabbbcccddd
eeeeeeeeefff

Файл 2 - конечный:

abababcdcdcd
eeeeefffe

После прогона программы генерируется "отчет" об отличиях (по сути же скриптовые команды), например:

Position 2, rewrite : baba
Position 8, rewrite : dcdc
Position 20, rewrite : fff
Position 24, delete : 3


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

Предполагаю, что найденные мною подобные алгоритмы для текстовых файлов не подойдут для бинарных (пока не пробовал). Зато попытался написать свой алгоритм, кстати не очень успешно - часто где-то зацикливается и умеет применять только 3 команды (заменить, вставить, удалить), хотелось бы иметь еще переместить, копировать, заполнить последовательность и т.д.

Жду комментариев по проблеме.

[ivank]

Кстати хорошая была бы олимпиадная задачка... Сделать генератор минимальных дифов. Тут можно много где проявиться...

Насколько я понимаю, теория лежащая в основе таких патчей будет та же самая, что и для текстовых патчеров (diff/patch). но т.к. я этой теории не знаю, то буду молчать :)

Вот что нашлось гуглом: http://www.xmailserver.org/xdiff-lib.html . Не знаю как оно работает, лень разбираться. Там же лежат две какие-то бумаги на эту тему, не смотрел.

[Savant]

ivank
Спасибо за ссылку, но гораздо больше ты мне помог тем, что подсказал правильный поисковый запрос для гугля. Итог - найден виндовый порт утилиты bsdiff/bspatch: http://sites.inka.de/tesla/download/bsdiff4.2-win32-src.zip (щас разбираемся, что к чему; к сожалению почти отсутствуют комментарии к тексту программ)

bsdiff and bspatch are tools for building and applying patches to binary files. By using suffix sorting (specifically, Larsson and Sadakane's qsufsort) and taking advantage of how executable files change, bsdiff routinely produces binary patches 50-80% smaller than those produced by Xdelta, and 15% smaller than those produced by .RTPatch (a $2750/seat commercial patch tool).