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

[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!)! байт.. а это..  и гига наверное не хватит  :