Определение разницы между двумя файлами

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

Вместе со студией (любой, похоже, до .NET) есть программка windiff, которая сравнивает текстовые файлы, судя по всему, тот же алгоритм используется и source safe-ом. К WinDiff-у есть исходники, надо поискать в мсдн "WinDiff: Graphical File Comparison Tool". :shuffle:

Здравствуйте Аноним, Вы писали:

Текстовых или бинарных?

Здравствуйте DarkGray, Вы писали:

DG>Здравствуйте Аноним, Вы писали:

DG>Текстовых или бинарных?

А что, это принцыпиально меняет дело?

Здравствуйте yogi, Вы писали:

DG>>Текстовых или бинарных?

Y>А что, это принцыпиально меняет дело?

Текстовые обычно сравнивают по строкам, а бинарные не по строкам.

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

Здравствуйте DarkGray, Вы писали:

DG>Здравствуйте Аноним, Вы писали:

DG>Текстовых или бинарных?

Бинарных. Предпологаеться что файлы могут быть любыми.

Здравствуйте Аноним, Вы писали:

DG>>Текстовых или бинарных?

А>Бинарных. Предпологаеться что файлы могут быть любыми.

Как насчет зарегистрироваться?
Это не больно — как будто уснешь

Теперь по теме.

Если побайтное сравнение — т.е. файлы условно одинаковой длины, отличаются байтами на некоторых местах — решение простое.

На выходе — серия "патчей":

с позиции i по j - заменить на b[i..j]

Сравнение по цепочкам. Т.е.

файл a = ab1[0..i1) a2[0..i2) ab3[0..i3) ...
файл b = ab1[0..i1) b2[0..j2) ab3[0..i3) ...

На выходе — патчи вида

заменить [i1..i2] на b[j1..j2]

Так работает windiff (правда, он оперирует не байтами, а строками).

Уже зарегестрировался. И правда — совсем не страшно :)
А за ответ спасибо, буду думать.

Здравствуйте Кодт, Вы писали:


К>Теперь по теме.

К>Если побайтное сравнение — т.е. файлы условно одинаковой длины, отличаются байтами на некоторых местах — решение простое.

К>На выходе — серия "патчей":
К>

К>с позиции i по j - заменить на b[i..j]
К>

К>Сравнение по цепочкам. Т.е.
К>

К>файл a = ab1[0..i1) a2[0..i2) ab3[0..i3) ...
К>файл b = ab1[0..i1) b2[0..j2) ab3[0..i3) ...
К>

К>На выходе — патчи вида
К>

К>заменить [i1..i2] на b[j1..j2]
К>

К>Так работает windiff (правда, он оперирует не байтами, а строками).


Мне кажеться что вот здесь:
К>Сравнение по цепочкам. Т.е.
К>

К>файл a = ab1[0..i1) a2[0..i2) ab3[0..i3) ...
К>файл b = ab1[0..i1) b2[0..j2) ab3[0..i3) ...
К>

что то не так. Хотя как должно быть сказать пока не могу.

Здравствуйте Аноним, Вы писали:

АА>Мне кажеться что вот здесь:
К>>Сравнение по цепочкам. Т.е.
К>>

К>>файл a = ab1[0..i1) a2[0..i2) ab3[0..i3) ...
К>>файл b = ab1[0..i1) b2[0..j2) ab3[0..i3) ...
К>>

А>что то не так. Хотя как должно быть сказать пока не могу.

Зависит от природы файлов и операций над ними.

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

a: abc|defghijklm|nopqrs|tuvw|xyz
b: abc|XYZ|nop|ABCD|qrs||xyz

Мультимедийные потоки — то же, но там, в отличие от текста, изменяются серии кадров (звуковых или видео). (Монтаж)
А в масштабе двух смежных кадров идет побайтная или попиксельная разница. (Коллаж)

Кстати, хорошие термины:
коллаж — побайтная разница
монтаж — нарезка, иногда (для пущей сложности) перестановка.

Алгоритм обнаружения монтажа, конечно, гораздо сложнее, чем коллажа.
Приходится искать совпадающие цепочки, устранять неоднозначность за счет оценок и/или эвристик.
В общем, см. windiff. Они эту задачу как-то решили.

Всем спасибо. Решение найдено