Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 26.08.2013, 16:58
Профессор
Отправить личное сообщение для tsigel Посмотреть профиль Найти все сообщения от tsigel
 
Регистрация: 12.12.2012
Сообщений: 1,398

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

Есть 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(' '));
Ответить с цитированием
  #2 (permalink)  
Старый 26.08.2013, 17:15
Профессор
Отправить личное сообщение для tsigel Посмотреть профиль Найти все сообщения от tsigel
 
Регистрация: 12.12.2012
Сообщений: 1,398

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

Неработающие наброски...
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;
        }
      }
    }    
  }
}
Ответить с цитированием
  #3 (permalink)  
Старый 26.08.2013, 17:20
Профессор
Отправить личное сообщение для tsigel Посмотреть профиль Найти все сообщения от tsigel
 
Регистрация: 12.12.2012
Сообщений: 1,398

Другой подход, который так же работает не корректно:
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 он считает измененным весь текст.
Ответить с цитированием
  #4 (permalink)  
Старый 26.08.2013, 19:20
Аватар для Demath
Профессор
Отправить личное сообщение для Demath Посмотреть профиль Найти все сообщения от Demath
 
Регистрация: 22.06.2012
Сообщений: 168

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) );

Последний раз редактировалось Demath, 26.08.2013 в 19:22.
Ответить с цитированием
  #5 (permalink)  
Старый 26.08.2013, 19:20
Аватар для keen
Профессор
Отправить личное сообщение для keen Посмотреть профиль Найти все сообщения от keen
 
Регистрация: 28.03.2012
Сообщений: 376

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

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

ну и вообще плясать надо от задачи - реализация зависит от того насколько точным должно быть сравнение (достаточно ли просто найти отличающиеся слова, или надо проверять посимвольно, особым образом отмечая различающиеся/добавленные/вырезанные куски).
Ответить с цитированием
  #6 (permalink)  
Старый 26.08.2013, 19:30
Аватар для Demath
Профессор
Отправить личное сообщение для Demath Посмотреть профиль Найти все сообщения от Demath
 
Регистрация: 22.06.2012
Сообщений: 168

Сообщение от keen
если уж делать через массивы (которые, вообще говоря, лучше разбивать ещё знаками препинания), то можно сделать всё буквально за один проход, сравнивая поэлементно; плюс забегая вперёд/назад, проверяя наличие/отсутствие дополнительных элементов.
Я думаю, если массивы не упорядочены, то буквально за один проход не получится.
Ответить с цитированием
  #7 (permalink)  
Старый 26.08.2013, 19:35
Аватар для keen
Профессор
Отправить личное сообщение для keen Посмотреть профиль Найти все сообщения от keen
 
Регистрация: 28.03.2012
Сообщений: 376

Сообщение от Demath Посмотреть сообщение
Я думаю, если массивы не упорядочены, то буквально за один проход не получится.
а нахрена нам их упорядочивать??
мы ж тогда получим равенство текстов 'a b c' и 'c a b'

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

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

ну говорю ж, от задачи надо идти.
Ответить с цитированием
  #8 (permalink)  
Старый 26.08.2013, 19:42
Аватар для Serg_pnz
Сам по себе
Отправить личное сообщение для Serg_pnz Посмотреть профиль Найти все сообщения от Serg_pnz
 
Регистрация: 09.06.2009
Сообщений: 963

Имхо нужен метод шинглов http://ru.wikipedia.org/wiki/%D0%90%...BB%D0%BE%D0%B2
Но это уже потянет за собой серверное решение.
Ответить с цитированием
  #9 (permalink)  
Старый 26.08.2013, 19:45
Аватар для keen
Профессор
Отправить личное сообщение для keen Посмотреть профиль Найти все сообщения от keen
 
Регистрация: 28.03.2012
Сообщений: 376

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

перечитай формулировку задачи, нафига ему такой фундаментальный метод?)
Ответить с цитированием
  #10 (permalink)  
Старый 27.08.2013, 10:29
Профессор
Отправить личное сообщение для tsigel Посмотреть профиль Найти все сообщения от tsigel
 
Регистрация: 12.12.2012
Сообщений: 1,398

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



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Пересечение и разность двух массивов harold Общие вопросы Javascript 9 18.12.2013 20:41
как сделдать меню из двух калонок как в bestchange.ru Андрей Лебедев Элементы интерфейса 2 21.01.2013 09:32
Сравнение двух дат fAmOus Элементы интерфейса 1 21.08.2012 16:27
Сравнение двух строк drac0Sha Общие вопросы Javascript 17 20.08.2012 19:45
MySQl дата между двух дат mycoding Серверные языки и технологии 8 14.02.2011 15:23