Сравнение файлов

[Jin X]

Нужно произвести сравнение двух двоичных файлов (старой и новой версии) и результат выдать в виде списка, состоящего из возможных пунктов:
[*] *По смещению XXX изменено YYY байт на "ZZZZZZZZ"
[*] *По смещению XXX вставлен блок "ZZZZZZZZZ" размером YYY
[*] *По смещению XXX удалён размером YYY
[*] Блок скопирован из смещения XXX по смещению YYY
[*] Блок перемещён из смещения XXX по смещению YYY (ну, это, в принципе, может быть как комбинация двух предыдущих пунктов)
* - самые важные пункты (должны поддерживаться алгоритмом обязательно)
Желательно бы ещё иметь возможность определять такие изменения, как перемещение с заменой (т.е. блок перемещён, но в нём заменены несколько байт), но это, конечно, уже в последнюю очередь, т.к. ИМХО самое сложное.

Интересует теория, но если есть уже готовые программы, интересно было бы посмотреть... (сам я знаю только проги для работы с текстовыми файлами)

- Спасибо!

Сообщение отредактировано: 7in - 24.08.03, 12:34

[Black Star]

Ну и мечты у тебя? Задача выполнима, и даже легко, но никогда этим не страдал и тебе не советую. Одна простая причина - нафига это ?
Достаточно просто узнать дату 1го и 2го файла, их размер и воооо как достаточно, а то блоки искать  :...

[Clane]

Цитата Black_Star, 24.08.03, 23:18:24

Ну и мечты у тебя? Задача выполнима, и даже легко, но никогда этим не страдал и тебе не советую. Одна простая причина - нафига это ?
Достаточно просто узнать дату 1го и 2го файла, их размер и воооо как достаточно, а то блоки искать  :...

Для того, чтобы кряки писать, или я не прав, а JinX ?

[Jin X]

Цитата

Достаточно просто узнать дату 1го и 2го файла, их размер и воооо как достаточно, а то блоки искать

И что это даст? Ты б для начала спросил для чего это. И если это легко решается, то лучше подскажи, а не рассуждай - нужно мне это или нет.

2 Clane: Нет, совсем не кряки, а патчи и обновления (для кряков обычно достаточно просто заменить пару байт без всяческих передвижений).

Сообщение отредактировано: 7in - 24.08.03, 21:16

[GrAnd]

У Microsoft есть прога одна WinDiff... тем более с вижуалом она поставляется и в виде исходника... Вот ее за основу и возьми... ;D

[zx1024]

Покумекал я над этим вопросом. И вот к каким выводам пришёл.
1) *По смещению XXX изменено YYY байт на "ZZZZZZZZ" является по сути комбинацией из двух последующих пунктов. Только ты можешь знать как поступить в этой ситуации:
ABCDEFG  и ABEFG. Здесь удален CD или CDEFG заменён на EFG (ну здесь может и очевидно, но наверняка будут и посложнее ситуации)?
2) То, что для первого файла будет "вставлено" - для второго будет "удалено".
Следовательно, можно рассматривать только удаления (или вставки) сначала для одного файла, потом для другого. А это почти тривиальная задача, если не считать время её выполнения. Затем, если удаление и вставка появились с одним смещением (?) сказано конечно не совсем корректно) можно подумать и о замене.
Если один из вставленных блоков совпадёт с удалённым, то это уже перемещение (можно рассматривать частичное совпадение). Копирование - поиск подстроки (вставленного блока) во втором "исправленном" файле (не рассматриваются вставленные блоки).

[Jin X]

Цитата zx1024, 26.08.03, 00:12:25

Только ты можешь знать как поступить в этой ситуации:
ABCDEFG  и ABEFG. Здесь удален CD или CDEFG заменён на EFG (ну здесь может и очевидно, но наверняка будут и посложнее ситуации)?

Если это в конце файла, то да (можно выбрать любой, но очевидно, что удаление предпочтительнее, т.к. его описать легче (меньше памяти надо)). А если где-то в середине, то никаких вопросов не может быть: если это удаление, то все последующие байты будут смещены.

Цитата

2) То, что для первого файла будет "вставлено" - для второго будет "удалено". Следовательно, можно рассматривать только удаления (или вставки) сначала для одного файла, потом для другого.

Ну я ж говорю: патчи, обновления (обратная операция мало интересует). Значит, нужно сравнивать один файл относительно другого.

Цитата

А это почти тривиальная задача, если не считать время её выполнения.

Ты знаешь, мне бы хотелось, чтобы всё выполнялось быстро, иначе это уже кривизна алгоритма. К тому же, это кажется только тривиальной задачей, т.к. кроме вставки/удаления есть ещё и замена.

Цитата

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

Ты знаешь, кажется всё так просто... пока за реализацию не возмёшься.
И мне не надо, чтобы алгоритм работал целый час.

2 GrAnd: Прогу скачал, посмотрю (вот только исходников я не нашёл ).
Может, подскажешь, в каком направлении идти (какие алгоритмы почитать и т.д).

Сообщение отредактировано: 7in - 26.08.03, 13:59

[deil]

малость далеко от исходной задачи, но, имхо, для начала может и подойдёт -
алгоритм поиска максимального совпадения двух строк (и взять за алфавит все аски символы)
причём взять не вариант из динамического программирования. а использовать метод поиска максимальной подпоследовательности:
пусть есть две строки - s1 & s2
выпишем все символы из s1 и рядом с ними - позиции, где они встречаются
отсортируем их (позиции) по убыванию (а: 177 20 2, ж: 12 1 и т,д,)
затем для каждого символа из s2 (сначала первый, потом второй и т.д.) выпишем эти последовательности (которые мы записали ранее) (если нужно - пишем пустые строки)
в итоге получим некоторую последовательность позиций
найдём в ней наибольшую возрастающую подпоследовательность
(идём справа-налево. для каждого символа будем в "ответ" записывать наибольшую позицию, не превосходящую выписанную позицию предыдущего символа)
в итоге полученная последовательность позиций - общая максимальная подпоследовательность двух строк...

надеюсь хоть как-то поможет

[GrAnd]

Исходники WinDiff - http://skyriver.ru/grand/ftp/download/windiff.zip

[deil]

p.s.
поразмыслил..
в результате получения общей последовательности, и тупо проанализировав несовпадающие участки, можно легко найти те места, где:
# *По смещению XXX изменено YYY байт на "ZZZZZZZZ"
# *По смещению XXX вставлен блок "ZZZZZZZZZ" размером YYY
# *По смещению XXX удалён размером YYY

имхо

pp.s. правда это будет довольно ресурсоёмко..

[Jin X]

2 DEiL: В твоём примере (про совпадающие участки) есть одна ресурсоёмкая процедура. А именно поиск наибольшей возрастающей последовательности. Вот смотри, допустим у меня получилась такая последовательность:

1 8, -, 2 3, 4 5 6, 4 5 6, 4 5 6, 7, 9, 10, 1 8

Теперь, чтобы мне найти максимумальную последовательность (3 4 5 6 7), мне нужно сделать два вложенных цикла:
[*] перебор всех списков (разделённых здесь запятыми)
[*] перебор всех чисел в списке
Затем для каждого из этих чисел мне нужно организовать ещё два вложенных цикла:
[*] перебор всех списков, начиная со следующего относительно того, в котором исходное число встретилось (правда, до тех пор, пока ни будет найдено НЕсовпадение, см. следующий пункт)
[*] поск в списке следующего числа относительно исходного (и увеличение исходного на единицу)


А что там у нас с поиском совпадений с помощью хэш-функций, интересно?
Набо б про них почитать... сейчас займёмся

Сообщение отредактировано: 7in - 29.08.03, 18:12

[Jin X]

Я тут подумал... Ведь по сути дела, моя задача - это архивация LZ77-алгоритмом! Только в качестве окна будет браться первый файл (и это окно будет не скользящим, а фиксированным и равным размеру этого файла), а в качестве сжимаемых данных - второй файл!

Поправьте меня, если я не прав. Блин, оказывается как всё просто!
Осталось только найти быстрый алгоритм поиска (с помощью хэш-функций, конечно)
Ыыыыыы!!!... (p.s. это я так радуюсь)

Сообщение отредактировано: 7in - 29.08.03, 18:20

[Jin X]

Единственная проблема осталась: замена одного символа будет дорого обходиться...
Представьте: изменён 1 байт в середине файла. Нужно закодировать информацию о том, что начиная с позиции 0 совпадает туева хуча байт, затем 1 байт другой, а затем опять совпадает туева хуча байт (начиная со следующей позиции).

Давайте думать, как решить эту проблему... :

И надо ещё придумать, как кодировать вставленные символы (т.е. если брать LZSS, то вставленные символы будут занимать в 1.125 больше, чем надо).

p.s. Надо мне всё-таки дочитать книжку по сжатию данных... там ещё BWT какой-то есть, может он подойдёт
p.p.s. Впервые, наверное, создал аж три сообщения подряд...

Сообщение отредактировано: 7in - 29.08.03, 18:32

[deil]

Цитата Jin X, 29.08.03, 22:09:04

2 DEiL: В твоём примере (про совпадающие участки) есть одна ресурсоёмкая процедура. А именно поиск наибольшей возрастающей последовательности. Вот смотри, допустим у меня получилась такая последовательность:

1 8, -, 2 3, 4 5 6, 4 5 6, 4 5 6, 7, 9, 10, 1 8

Теперь, чтобы мне найти максимумальную последовательность (3 4 5 6 7), мне нужно сделать два вложенных цикла:
[*] перебор всех списков (разделённых здесь запятыми)
[*] перебор всех чисел в списке
Затем для каждого из этих чисел мне нужно организовать ещё два вложенных цикла:
[*] перебор всех списков, начиная со следующего относительно того, в котором исходное число встретилось (правда, до тех пор, пока ни будет найдено НЕсовпадение, см. следующий пункт)
[*] поск в списке следующего числа относительно исходного (и увеличение исходного на единицу)


А что там у нас с поиском совпадений с помощью хэш-функций, интересно?
Набо б про них почитать... сейчас займёмся

ээээ
читай вдумчиво :-)
для начала - наибольшая возрастающая последовательность - 1 3 4 5 6 7 8 :-)
и поясняю ещё раз, как нужно её искать :-)

1 8, -, 2 3, 4 5 6, 4 5 6, 4 5 6, 7, 9, 10, 1 8
эту строку нужно анализировать справа налево:
рассмотрим "кусок": 1 8
максимум здесь - "8"
выписываем в ответ
смотри левее - 10
не подходит. ответ "8"
смотри левее: 9
аналогично
далее - 7
7 меньше 8, значит ответ - "7 8"
левее - 4 5 6
берём отсюда максимальное число, меньшее 7-ке - 6
ответ - "6 7 8"
имхо это самая простая и нересурсоёмкая процедура из всего алгоритма :-)
самое ресурсоёмкое - поиск и запоминание позиций вхождения..

[deil]

хм
к сожалению не знаю LZ77, знаю только LZ & LZW..
из этой "оперы" единственное, что приходит в голову - из 1-го файла составить суффиксное дерево, и использовать его как словарь для 2-го файла, сжимая его по LZW.. имхо это будет самый эффективный для поставленной задачи алгоритм. в плане поиска различий :-)
но есть одно но - при длине 1-го файла в 1кб, суффиксное дерево будет занимать... мм.. как минимум (1024!)! байт.. а это..  и гига наверное не хватит  :

[Jin X]

LZ77 (LZSS - одна из разновидностей) и LZ88 (LZW - одна из разновидностей) отличаются тем, что в первом просто ищутся совпадения и кодируются смещениями и размерами (если совпали) или выводятся сами байты, если ничего не найдено, т.е. словарём является всё множество возможных сочетаний символов из уже просмотренной части файла (а если словарь - это весь файл, как мне нужно сделать, то из всего файла). Скользящее окно - это когда берутся не все байты от начала до текущей позиции, а N последних. А во втором методе в словарь помещаются только определённые фразы, а в вывод заносятся индексы (если брать конкретно LZW). LZ77 гораздо быстрее декодируется.

[deil]

ух
нет
это не для моих мозгов :-)
в общем.. удачи

p.s. я облажался в алгоритме поиска наибольшей возрастающей подпоследовательности ) всё-таки целое лето дискретку не повторял :-))
в твоём примере  
1 8, -, 2 3, 4 5 6, 4 5 6, 4 5 6, 7, 9, 10, 1 8 она будет 1 2(3) 4 5 6 7 9 10 )

ззы.
8 1, -, 3 2, 6 5 4, 6 5 4, 6 5 4. 7, 9, 10, 8 1
8 1
          3 2                                                      1
                  6 5 4                                        
                            6 5 4
                                       6 5 4
                                                 7
                                                      9          8
                                                           10
и вот теперь идём справа на лево, сравнивая числа...

:

[Jin X]

Что-то я тогда логики этого метода не пойму...
Во второй строке цифры должны возрастать на единицу, причём обязательно в каждой следующей позиции.

Возмём тот же ряд...

1 8, -, 2 3, 4 5 6, 4 5 6, 4 5 6, 7, 9, 10, 1 8

...и строки...

аббнннраеп<br>агбнннрепа

Что совпадает? "бнннр", т.е. 3,4,5,6,7

Так что, не гони

[Demo_S]

есть стандартные программы
fc /b для винды и diff для линукса.

есть всякие программы коммерчиские, что-то вроде xdiff но я наверняка не помню.

есть работа группы исследователей, которые предложили 4 алгоритма для решения такой задачи. Мы (4 человека и я в том числе) когда-то писали такую прогу, даже для продажи, и она вроде делала какой-то западный аналог. Но счас она утеряна (писали еще давно, потом винт полетел и все.) так что счас к сожалению ни доки ни исходников.

Но мы доки нашли в инете. нечт типа "алгоритм diff" или "аналог xdiff"
лучше искать в гугле в групах usenet (aka fido).

Есть какая-то коммерческая программа,которая бесплатна для частного пользования, но стоит около 7килобасов, если хочешь сделать ее частью проги, которую будешь сам продавать. Если вспомню, напишу.

[deil]

Цитата Jin X, 30.08.03, 17:21:13

Что-то я тогда логики этого метода не пойму...
Во второй строке цифры должны возрастать на единицу, причём обязательно в каждой следующей позиции.

Возмём тот же ряд...

1 8, -, 2 3, 4 5 6, 4 5 6, 4 5 6, 7, 9, 10, 1 8

...и строки...

аббнннраеп<br>агбнннрепа

Что совпадает? "бнннр", т.е. 3,4,5,6,7

Так что, не гони

тьфу ты
ну ты и чучело :-))
приведённый алгоритм ищёт маскимально длинну/ совпадающиую подпоследовательность, а не блок!
поэтому ответ 1 2 4 5 6 7 9 10 выдаст тебе:
аббнннраеп
агбнннрепа
жирным как раз и выделен совпадающий участок
и тогда становится ясно, что чтоб, допустим, из второй строчки получить первую, нужно:
на 2-й позиции вставить "б"
на 3-й позиции удалить "г"
на 8-й позиции вставить "а"
удалить последнюю "а"

разве тебе не это нужно?  :D

[Jin X]

Аааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааа!!!!!!!....... Кипяток! Тьфу, т.е. эврика! ;D
Ясно, спасибо, тоже может пригодиться

Сообщение отредактировано: 7in - 31.08.03, 19:47

[deil]

ура

я понял: моя дорога - прямиков в Микрософт... я на днях реализовал этот алгоритм.. мм.. эээ,,, на вход поустил 2 50-тиколбайтных файла (разные версии сервака ЧП :-)).,
считав 1-й файл, программа откушала полтора мега оперативки.. считав второй - 150.. а когда начала сравнивать - я грохнул её, когда использование свопоа дошло до 2Гб  ;D ;D ;D

[Black Star]

Не, не то...
Я бы делал так:
Открываешь 2 файла, читаешь в каждом, например 50 символов (байтов)...
Слаживаешь их методом XOR... нули пошли - текст одинаковый...
Ну, коль нет, - ищите более оригинальный способ

[Demo_S]

обобщенный алгоритм:
предполагается знание принципов работы хешей

i=0
j=0
считываем с первого файла 16 байт с i-той позиции. считаем хеш, записываем в хеш-таблицу.
считываем со второго файла 16 байт с j-той позиции, считаем хеш. если в хеш-таблице по этому хешу есть запись, то сравниваем эти 16 байт побайтно, если совпали, то проверяем на совпадение следующие мабйты после этих 16 .
Таким образом определяем кусок совпадающих байт. записываем в результирующий файл адрес начала цепочки совпадающих байтов и ее длину.
j+=длина совпадающего участка
i++;//да да, именно ++

Если же для хеша сделанного из 16 байт второго файла нет значения в хещ таблице, либо значения есть, а байты не совпадают, то записываем 1 байт в результ-файл. и j++.
делаем пока не закончаться файлы.

в этом алгоритме есть некоторые моменты. над которыми надо подумать (как реализовывать запись в рез-файл, чтобы отличать запись о совпадающих байтах от записи несовпадающих байт), есть вещи, которые можно оптимизировать (мы считываем с первого файла 16 байт с 0, потом 16 с 1, то есть перечитываем заново 15 байт. это можно обойти, ведь мы их считали на пред итерации, проще всего это обходится с использвоанием file mapping)

можно делать разные модификации, например сначала считать весь первый файл и построить таблицу хешей, а потом брать второй, и сверять.

и еще парочка оптимизаций, которые долго описывать:)

Сообщение отредактировано: Demo_S - 03.09.03, 21:16

[Jin X]

Кстати, про хэш...

Пока практически ничего не читал про хэши, но прочёл 1 коротенькую статью и не понял, почему хэш увеличивает скорость в данном случае. Сейчас поясню...
Описывается усовершенствование алгоритма сравнения строк.
Есть две строки s1 и s2. Нужно найти подстроку, т.е. s2 в s1.

Алгоритм (допустим, хэш-функция - это обычное сложение кодов символов):
0. i=0 (отсчёт символов в строках начинаем с нуля)
1. Считаем хэш-функцию s2 (h1 - значение функции).
2. Считаем хэш-функцию length(s2) первых символов s1 (h2 - значение функции).
3. Сравниваем h1 и h2. Если совпадают, то сравниваем s1 с куском s2. Если совпадают, значит задача решена!
4. Если нет, прибавляем к h2 код следующего (т.е. (i+length(s1))-го) символа s1 и вычитаем i-й символ s1; i++
5. goto 3

Почему этот алгоритм быстрее, чем (без хэша):
0. i=0; Ch=первый_символ_s2;
1. Сравниваем i-й символ s1 с Ch. Если совпадают, то сравниваем s1 с куском s2. Если совпадают, значит задача решена!
2. Если нет, то i++
3. goto 1

Ведь в первой задаче на каждом шаге нужно выполнить 3 операции: прибавить, вычесть и сравнить, когда во второй - только сравнить?! Где ж обещанное ускорение?!

Сообщение отредактировано: 7in - 03.09.03, 23:01

[Demo_S]

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

пусть с1 - 100 символов, с2 10 символов.
во втором алгме на каждом шаге будет 10 сравнений, а шагов будет 90 (в худшем случае)

с хешем на каждой итерации 1 сложение, 1 вычитание и одно сравнение.
и только если хеши совпали, проводится посимвольное сравнение. если же хеши не совпали, то сравнения не прводится.

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

[Jin X]

Посмотри внимательно второй мой алгоритм.

Да и вообще, ни один нормальный человек не будет продолжать сравнение, если найдено хотя бы одно несовпадение. Т.е. если первый символ не совпадает, то второй уже сравниваться не будет.
Это ли не быстрее?

Сообщение отредактировано: 7in - 04.09.03, 20:51

[Demo_S]

твой второй алгоритм - тоже использует хеш-функцию:)
просто твоя хеш-функция такая:
для строки вернуть ее первый элемент.

в этом случае твой вопрос сводится к тому, какая хеш-фукнция лучше:)