Алгоритм сравнения файлов, кто понял, растолкуйте мне

Какое количество байт дешевле всего (в плане производительности) сравнивать за один присест коду, который ты пишешь?
Например, 4, 8 или даже 16. Вот и сделай условный цикл сравнения двух буферов, состоящий из элементов такого размера. Всё равно, в итоге, самый оптимальный алгоритм, например, для i686, сведётся к чему-то подобному, только с соответствующим размером слова.

Я пытаюсь замутить построчное сравнение файлов. Нашёл вот этот алгоритм. Закодировать два текста в два массива, закодировал, а как идти и сравнивать массивы не могу понять, может как-то не так написано. Сейчас смотрю на реализацию сравнения, написанную на C#, взял с codeproject.com: http://www.codeproject.com/Articles/13326/An-O-ND-Difference-Algorithm-for-C. Буду разбирать её.

Скорее всего, описание алгоритма кривое.

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

ну а дальше - сравниваеться 1 ое значение из первого и второга массива
если равные - то переходят ко 2ому

если неравны - то счетчик второго увеличиваеться на 1 - и опят ьсравниваеться
как достигли конца массива - то +1 делаеться для первого счетчика - и опять проверяеться

тут только важно помнить - что равенство хешей двух строк означает что они могут быть равны и неравны - неоднозначная ситуация - надо для точности сравнить сами строки
а вот отличие хешей - означает что строки ТОЧНО неравны - и строки сравнивать бесмысленно

А зачем делать хеши?

ну - это делалось в описании - к ним вопрос

(4 байта сравнить быстрее чем полную строку)

если неравны - то счетчик второго увеличиваеться на 1 - и опят ьсравниваеться как достигли конца массива - то +1 делаеться для первого счетчика - и опять проверяеться

Кстати, это и есть тот момент который я не понял. Т.е если два элемента не равны, то мы индекс элемента во втором массиве инкрементируем и снова сравниваем с первым массивом. И вот здесь загвоздка: сравниваем с тем же самым элементом в первом массиве, или со следующим(в статье ведь сказано что сравниваем с элементом, следующим за текущим, но в этом случае теряется смысл такого сравнения, можно просто пройтись и каждое с каждым сравнить). Теперь ещё один момент: при сравнении, если элементы не равны, индекс во втором массиве мы увеличили, снова сравнили. Предположим что они опять не равны, что тогда? Снова во втором увеличиваем? Но тогда опять же нарушается условие сравнения(оно описано в конце), когда сравниваются индексы последних совпавших элементов, типа если в правом массиве больше на единицу, то типа вставка, если меньше то удаление, если равны, то просто изменение. Но если следовать алгоритму, то получается, что этот индекс будет всегда больше во втором массиве, и при этом он будет больше чем на 1. Вроде так, если я не запутался :)

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

Мне кажется, что автор статьи предложил довольно неплохой способ перевода строки в число. Если попадутся одинаковые, то это однозначное соответствие.

сущность хеша - в том и заключаеться что большое множество ставиться в соответствии меньшее множество
и всегда хеш - если он меньше чем сам обьект - несет меньше информации

в примере - делается что то вроде хеша из строки в double - а у него всего 8 байт (64 бита)
поэтому обязательно будут строки у которых равен хеш
если это неважно так неважно - но забывать про это не стоит

можно просто пройтись и каждое с каждым сравнить

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

Да все просто. Это банальный diff.

Например:

Текст1 = «почему-то мама мыла раму»
Текст2 = «мама мылом мыла раму утром»
Будем считать разницу по словам (хотя можно и по символам и по строкам и ваще как угодно)

вычислением разницы бедет
ОбщийТекст = ["",          «мама»,"",      «мыла», «раму»,«»]
Разница1    = [«почему-то», "",    "",      "",     "",    «„]
Разница2    = [“»,          "",    «мылом», "",     "",    «утром»]
Причем Length(Общий Текст) = Lenght(Разница1) = Length(Разница2)

Сначала находим матрицу набольшей общей последовательности НОП(i,j). 
Описание в педивикии http://ru.wikipedia.org/wiki/Наибольшая_общая_подпоследовательность)

l1 = length(текст1)
l2 = length(текст2)

Для i=l1-1 До 0 Шаг -1 Цикл	
	Для j=l2-1 До 0 Шаг -1 Цикл		
		Если Текст1 = Тектс2[j] То
			НОП[j] =  1 + НОП[i+1][j+1]	
		Иначе
			НОП[j] = max(НОП[i+1][j], НОП[j+1])
		Конец Если
	Конец Цикла
Конец Цикла
		
затем заполняем 3 массива 
ОбщийТекст - тут общие элементы для Текст1 и Текст2
Разница1 - разница м-ду общим текстом и Текст1
Разница2 - то же для Текст2
примерно так:
i = 0  // счетчик по массиву текст1
j = 0  // по массиву текст2
w = 0  // по массивам ОбщийТекст, Разница1 и Разница2
l1 = length(текст1)
l2 = length(текст2)
// Сначала крутим цикл по матрице НОП, заполняя ОбщийТекст и Раницы1 и 2
Пока НОП[j] != 0 и i < l1 и i < l2 цикл
	ОбщийТекст[w] = «»
	Разница1[w] = «»
	Разница2[w] = «»
	
	Если Текст1 = Текст2 то
		ОбщийТекст[w]  = Текст1
		i = i + 1
		j = j + 1
	Иначе
		Если НОП[j] = НОП[i+1][j] То
			Разница1[w]  = Текст1
			i = i + 1
		Иначе
			Разница2[w]  = Текст2[j]
			j = j + 1
		Конец Если
		
	Конец Если
	w = w + 1
конец цикла
// Текст за рамками общего 
// для текст1 (слово «почему-то»)
Для k=i до l1-1 цикл
	ОбщийТекст[w] = «»
	Разница1[w] = Текст1[k]
	Разница2[w] = «»
	w = w + 1	
Конец цикла
// для текст2 (слово «утром»)
Для l=i до l2-1 цикл
	ОбщийТекст[w] = «»
	Разница1[w] = «»
	Разница2[w] = Текст2[l]
	w = w + 1	
Конец цикла
Имеем 3 массива: ОбщийТекст - с общим текстом + 2 разницы.
Теперь, например, можно вывести куда нить все это, пройдясь в цикле от i=1 до w по 3 массивам, рисуя ОбщийТекст черным, Разницу1  к примеру зеленым ну а Разницу2 каким-нить красным.
Алгорим списан с рельной либы на LotusScript, написаной давным давно на коленке как часть самописной СЭД.
Объяснил конечно сумбурно. Но надеюсь что получше чем в статье. 
 
PS 
cм исходники diff 
 

ГАВНО ЭТОТ ВАШ LORCODE!!!!!!!

Текст1 = "почему-то мама мыла раму"
Текст2 = "мама мылом мыла раму утром"
Будем считать разницу по словам (хотя можно и по символам и по строкам и ваще как угодно)

вычислением разницы бедет
Общий текст = ["",          "мама","",      "мыла", "раму",""]
Разница1    = ["почему-то", "",    "",      "",     "",    ""]
Разница2    = ["",          "",    "мылом", "",     "",    "утром"]
Причем Length(Общий Текст) = Lenght(Разница1) = Length(Разница2)

Сначала находим матрицу набольшей общей последовательности НОП(i,j). 
Описание в педивикии http://ru.wikipedia.org/wiki/Наибольшая_общая_подпоследовательность)

l1 = length(текст1)
l2 = length(текст2)

Для i=l1-1 До 0 Шаг -1 Цикл	
	Для j=l2-1 До 0 Шаг -1 Цикл		
		Если Текст1[i] = Тектс2[j] То
			НОП[i][j] =  1 + НОП[i+1][j+1]	
		Иначе
			НОП[i][j] = max(НОП[i+1][j], НОП[i][j+1])
		Конец Если
	Конец Цикла
Конец Цикла
		
затем заполняем 3 массива 
ОбщийТекст - тут общие элементы для Текст1 и Текст2
Разница1 - разница м-ду общим текстом и Текст1
Разница2 - то же для Текст2

примерно так:
i = 0  // счетчик по массиву текст1
j = 0  // по массиву текст2
w = 0  // по массивам ОбщийТекст, Разница1 и Разница2

l1 = length(текст1)
l2 = length(текст2)

// Сначала крутим цикл по матрице НОП, заполняя ОбщийТекст и Раницы1 и 2
Пока НОП[i][j] != 0 и i < l1 и i < l2 цикл
	ОбщийТекст[w] = ""
	Разница1[w] = ""
	Разница2[w] = ""
	
	Если Текст1[i] = Текст2[i] то
		ОбщийТекст[w]  = Текст1[i]
		i = i + 1
		j = j + 1
	Иначе
		Если НОП[i][j] = НОП[i+1][j] То
			Разница1[w]  = Текст1[i]
			i = i + 1
		Иначе
			Разница2[w]  = Текст2[j]
			j = j + 1
		Конец Если
		
	Конец Если
	w = w + 1
конец цикла

// Текст за рамками общего 
// для текст1 (слово "почему-то")
Для k=i до l1-1 цикл
	ОбщийТекст[w] = ""
	Разница1[w] = Текст1[k]
	Разница2[w] = ""
	w = w + 1	
Конец цикла

// для текст2 (слово "утром")
Для l=i до l2-1 цикл
	ОбщийТекст[w] = ""
	Разница1[w] = ""
	Разница2[w] = Текст2[l]
	w = w + 1	
Конец цикла

Имеем 3 массива: ОбщийТекст - с общим текстом + 2 разницы.
Теперь, например, можно вывести куда нить все это, пройдясь в цикле от i=1 до w по 3 массивам, рисуя ОбщийТекст[i] черным, Разницу1[i]  к примеру зеленым ну а Разницу2[i] каким-нить красным.
Алгорим списан с рельной либы на LotusScript, написаной давным давно на коленке как часть самописной СЭД.
Объяснил конечно сумбурно. Но надеюсь что получше чем в статье. 

 

Спасибо. Тут я как понял идёт прогон по всему тексту. Я думал сделать так: 1. Каждую строчку в число(хеш) 2. Проходи по ассивам и сравниваем их хеши, для тогочтобы выяснить, в какие строчки вставлялся текст, из каких удалялся, а в каких просто изменялся. Эти изменения пишем в два массива(массив из структур, описывающих разницу в одном блоке. т.е с какой по какую строку, с какого по какой символ, тип изменения). 3. Затем, за второй проход, проходим по этим массивам «отличий» и к отличающимся строкам применяем алгоритм нахождения наибольшей общей последовательности, чтобы найти отличий непосредственно в этих блоках. 3. Дальше все найденные отличия раскрашиваем. )

Ну можно и с хэшами работать. Т.е. в приведенном алгоритме меняем текст на хэши

Общий текст = [хэш (""),          хэш ("мама"),хэш (""),      хэш ("мыла"), хэш ("раму"),хэш ("")]
Разница1    = [хэш ("почему-то"), хэш (""),    хэш (""),      хэш (""),     хэш (""),    хэш ("")]
Разница2    = [хэш (""),          хэш (""),    хэш ("мылом"), хэш (""),     хэш (""),    хэш ("утром")]

После сравнения нужно привести обратно к читаемому виду т.е. заменить хэши на исходные слова (или др элементы), а так как вычисление хэша - операция необратимая, нужен словарь с привязкой текста (строк, слов, букв или на каком уровне мы там разницу ищем) к хэшам. Для ускоряйзинга поиска в словаре его неплохо было бы отсортировать. Кароче в итоге получили индекс в чистом виде. Тут и до собственной СУБД недалеко ;) К тому же получем доп тормоза при преобразовании исходника в хэш (что не так страшно) и обратном сопоставлении (а вот тут в лучшем случае сложность О(n*log(n) а если не сортировать словарь то и O(n*n))

Вообще на скорость diff более всего влияет то, как мелко мы подробим текст. При увеличении кол-ва элементов катастрофически растет матрица НОП. т.к. с каждым новым элементом добавляется 1 строка и один столбец т.е. сравнение по строкам радикально быстрее сравнения по словам и уж тем более по буквам.

Кароче, хэши тут реально нужны при сравнении какой нить ацкой графомании типа «Воины и Мира» с «Тихим Доном».

В плане ускорения я бы подумал над адаптивным алгоритмом, когда сначала ищем разницу по большим кускам и для несовпадающих больших кусков детализируем разницу на меньшем уровне. Типа нашли разницу по абзацам и для несовпадающих абзацев нашли разницу по словам.