Сравнение двух текстов

[tsigel]

Здравствуйте! Помогите пожалуйста с алгоритмом сравнения двух текстов.

Есть 2 текста, по идее эти тексты должны не сильно отличаться друг от друга. Задача найти изменения в этом тексте и выделить цветом.

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

Первое что пришло в голову - разбить строки на массивы и сравнивать элементы массива.

Вялые попытки.. (выделяет дописанное в конец слово не учитывая что слово можно дописать и в начало )

var text1 = "мама мыла раму";
var text2 = "мама мыла раму долго";

var arr1 = text1.split(' ');
var arr2 = text2.split(' ');

if (arr2.length > arr1.length) {
  for (var i = arr1.length; i < arr2.length; i++) {
    arr2[i] = "<span class='changedText'>" + arr2[i] + "</span>";
  }
}

alert(arr1.join(' '));
alert(arr2.join(' '));

[tsigel]

По идее - надо при сравнении массивов при нахождении первого отличия - сравнивать также со всеми последующими элементами, но это будет подходить только для добавления слова.

Неработающие наброски...

if (arr1.length >= arr2.length) {
  for (var i = 0; i < arr1.length; i++) {
    if (arr1[i] != arr2[i]){
      arr2[i] += "<span class='changedText'>"
      for (var j = i; j < arr2.length; j++) {
        if (arr1[i] == arr2[j]) {
          arr2[j] = "</span>" + arr2[j]
          break;
        }
      }
    }    
  }
}

[tsigel]

Другой подход, который так же работает не корректно:

var text2 = "мама мыла раму долго";
        var text1 = "мама мыла кривую раму";
        var result = [];
        var a1 = text1.split(' ');
        var a2 = text2.split(' ');

        var changes = false;
        for (var i = 0; i < Math.min(a1.length,a2.length); i++) {
            var text = a1[i];
            if (!a2[i] || text != a2[i]) {
                if (!changes) {
                    changes = true;
                    result.push('<span class="changedText">');
                }
            } else {
                if (changes) {
                    changes = false;
                    result.push('</span>');
                }
            }
            result.push(text);
        }
        if (changes) result.push("</span>");
        alert(result.join(' '));

Если добавляем слово в начало 0 он считает измененным весь текст.

[Demath]

tsigel, нужно найти все слова во 2-ом массиве, которых нет в 1-ом массиве?

function DiffArrays(A,B)
{
    var M = A.length, N = B.length, C = [];
    for (var i=0; i<M; i++)
     { var j = 0;
       while (B[j]!==A[i] && j<N) j++;
       if (j==N) C[C.length] = A[i];
     }
   return C;
}

var text1 = "мама мыла кривую раму";
var text2 = "мама мыла раму долго";

var arr1 = text1.split(' ');
var arr2 = text2.split(' ');

alert( DiffArrays(arr2, arr1) );

[keen]

ну это вопрос не языка (подфорум "Общие вопросы Javascript"), а алгоритмизации.

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

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

[Demath]

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

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

[keen]

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

а нахрена нам их упорядочивать??
мы ж тогда получим равенство текстов 'a b c' и 'c a b'

одним циклом идём по первому "эталонному" массиву, сравниваем элементы со 2м, если не совпадают, делаем пару-тройку дополнительных шагов "в стороны". если совпадений нет, значит у нас во 2м тексте появились/пропали слова.

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

ну говорю ж, от задачи надо идти.

[Serg_pnz]

Имхо нужен метод шинглов http://ru.wikipedia.org/wiki/%D0%90%...BB%D0%BE%D0%B2
Но это уже потянет за собой серверное решение.

[keen]

Имхо нужен метод шинглов http://ru.wikipedia.org/wiki/%D0%90%...BB%D0%BE%D0%B2
Но это уже потянет за собой серверное решение.

перечитай формулировку задачи, нафига ему такой фундаментальный метод?)

[tsigel]

Всем большое спасибо, сейчас изучу все вышеописанное.