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

[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]

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

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