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

← →
DevilDevil © (2007-01-25 01:34) [0]

Вопрос: существует ли какой-нибудь быстрый способ сравнения файлов... точнее нахождения всех общих цепочек байт?

по моему естественно:
1) оба файла надо сначала занести в память
2)
function EqualBytes(P1, P2 : pointer; MaxLength : DWORD) : DWORD; asm push esi push edi mov esi, eax mov edi, edx {} mov edx, ecx shr ecx, 2 jz @normecx Repe cmpsd je @normecx mov ecx, 3 sub esi, 4 sub edi, 4 jmp @cmpbytes @normecx: mov ecx, edx and ecx, 3 jz @Exit @cmpbytes: Repe cmpsb je @exit dec esi @Exit: sub eax, esi neg eax pop edi pop esi end;

← →
Германн © (2007-01-25 01:45) [1]

>
> DevilDevil © (25.01.07 01:34)
>
> Вопрос: существует ли какой-нибудь быстрый способ сравнения
> файлов... точнее нахождения всех общих цепочек байт?

Тут обязательно нужно ограничиться какими-то "осмысленными" критериями. нахождения всех общих цепочек байт слишком общо и практически не подлежит алгоритмизации.
Даже TotalCommander -> "Сравнить файлы по содержимому" от весьма уважаемого мною Christian Gisler не всегда работает так, как это мне нужно.

← →
DevilDevil © (2007-01-25 10:19) [2]

← →
Сергей М. © (2007-01-25 10:31) [3]

> 1) оба файла надо сначала занести в память

Хорошо когда эти файлы небольшие, а если не полезут ?

Решение тут напрашивается само собой - некэширующий файл-маппинг небольших фиксированных по размеру (кратному 64к) фрагментов обоих файлов.

← →
DevilDevil © (2007-01-25 11:16) [4]

> Сергей М. © (25.01.07 10:31) [3]

В моём случае файлы не привысят 600кб.
Ну так есть какой-нибудь алгоритм?

← →
Сергей М. © (2007-01-25 11:39) [5]

> DevilDevil © (25.01.07 11:16) [4]

А что в результате нужно получить ?
Список записей вида "смещение начала цепочки"+"длина цепочки" ?

← →
Sinys © (2007-01-25 11:57) [6]

Что-то типа not(P1 and P2) не покатит? если больше нуля то баста

← →
DevilDevil © (2007-01-25 12:41) [7]

> Сергей М. © (25.01.07 11:39) [5]

Смещение в первом файле, смещение во втором файле, длина цепочки

← →
Сергей М. © (2007-01-25 12:48) [8]

> Смещение в первом файле, смещение во втором файле

Эдак ты далеко зайдешь.

Пусть есть два файла с одинаковым содержимым: ХХХ

Приведи результирующий список для данного примера, как ты себе его представляешь ...

← →
novill © (2007-01-25 12:59) [9]

> [7] DevilDevil © (25.01.07 12:41)

а что вот стаким алогритм должен делать?

файл1 "1234 12345 1234"

файл2 "12345 1234 12345"

← →
DevilDevil © (2007-01-25 13:06) [10]

для начала:

Смещение в первом файле, смещение во втором файле, длина цепочки

0, 0, 4
5, 6, 4
11, 11, 4

P.S. но в идеале:
0, 0, 4
5, 0, 5
11, 0, 4

дело в том, что я хочу уметь написать что то типа патчера + архиватора... для Delphi приложений (и уж тем более тематических приложений (БД, игры, ДВИЖКИ)) должно дать хорошую степень сжатия....... с учётом того, что программа-распаковщик знает, откуда брать исходный файл, чтобы получить результирующий ;)

← →
Игорь Шевченко © (2007-01-25 13:15) [11]

Умные люди ищут в сети исходники программы diff (они есть) и вдумчиво их изучают. Там очень хороший алгоритм применен.

← →
Сергей М. © (2007-01-25 13:20) [12]

> DevilDevil © (25.01.07 13:06) [10]

А куда у тебя делись , к примеру, записи:

0,0,1
0,6,1
0,11,1
..
?

Моль съела ?)
Они ведь точно так же удовлетворяют заданному тобой условию поиска ..

← →
novill © (2007-01-25 13:21) [13]

а может сначала разберешь алгоритмы архивации?

← →
DevilDevil © (2007-01-25 13:30) [14]

2Сергей М. © (25.01.07 13:20) [12]

а они должны отсеиваться

← →
Сергей М. © (2007-01-25 13:40) [15]

> они должны отсеиваться

Чтой-то вдруг ?
Где это фигурирует в условиях задачи ?

В точном соответствии с твоими условиями записи 0,0,1 0,6,1 0,11,1 означают:
при поиске и сравнении цепочек длиной в один элемент обнаружено, что
в первом файле элемент "1" по смещению 0 встречается во втором файле по смещениям 0, 6, 11.

Что здесь противоречит условиям задачи ?

> Сергей М. © (25.01.07 13:40) [15]

Вопрос: существует ли какой-нибудь быстрый способ сравнения файлов... точнее нахождения всех общих цепочек байт, максимальной длинны?

К этой формулировке придраться можно ещё больше. Вопрос тем не менее остаётся открытым; надеюсь, приведённый мной пример расставил все точки над "и", и Вы поняли мою задачу.

Кстати о diff, погуглил ничего вразумительного пока не нашёл (исходники всмысле), буду рад любой помощи, в том числе и предоставление ссылки на исходники diff.

P.S. меня интересует именно быстрый алгоритм. Метод полного перебора очень долгий, предположительно 15-60 минут для файлов в 400кб.

Доп вопрос: как определить смещение в exe файле, с которого начинается код? Если учесть, что код выровнен по 4-х байтной границе (по крайней мере в Delphi), есть смысл проверять код по 4 байта за раз, начиная с этих точек. Такой подход может потерять до 3-х байт в каждой цепочке байт, зато увеличит скорость обработки на пару порядков.

> Вопрос: существует ли какой-нибудь быстрый способ сравнения
> файлов

см. тот же diff.

Вполне эффективно сравнивает файлы и выводит протокол совпадений/несовпадений .

Только он, diff, не решает поставленную тобой задачу, ибо она и значально не корректна в своей постановке.

> как определить смещение в exe файле, с которого начинается
> код?

А никак.

Потому что сама постановка вопроса лишена смысла.
Гугли по "структура PE-модуля" - и да посетит тебе откровение.

> способ сравнения файлов

> приведённый мной пример расставил все точки над "и"

Этот пример не имеет ни малейшего отношения к файлам.

> Кстати о diff, погуглил ничего вразумительного пока не нашёл
> (исходники всмысле), буду рад любой помощи, в том числе
> и предоставление ссылки на исходники diff.

Например:
http://www.codeproject.com/tools/difftool.asp
http://www.thefreecountry.com/programming/filecomparison.shtml

DevilDevil © (25.01.07 17:09) [20]

> спасибо, Diff я уже нашёл...
> только exe он не сравнивает...

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

Алгоритм сравнения файлов. Найти похожие ветки