Сравнение двух текстов
Здравствуйте! Помогите пожалуйста с алгоритмом сравнения двух текстов.
Есть 2 текста, по идее эти тексты должны не сильно отличаться друг от друга. Задача найти изменения в этом тексте и выделить цветом. Для чего это нужно: Делаем что-то типа просмотра версий документа (на странице 2 десятка разных элементов форм, необходимо сравнить значения элементов форм старого документа и нового и выделить цветом). Для того чтобы можно было делать выделение цветом сделал что элементы форм, содержимое которых различно заменяются на дивы, выглядящие как инпуты, текстари.. Осталось только подсветить слова. Первое что пришло в голову - разбить строки на массивы и сравнивать элементы массива. Вялые попытки.. (выделяет дописанное в конец слово не учитывая что слово можно дописать и в начало :cray: )
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(' '));
|
По идее - надо при сравнении массивов при нахождении первого отличия - сравнивать также со всеми последующими элементами, но это будет подходить только для добавления слова.
Неработающие наброски...
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;
}
}
}
}
}
|
Другой подход, который так же работает не корректно:
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 он считает измененным весь текст. |
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) );
|
ну это вопрос не языка (подфорум "Общие вопросы Javascript"), а алгоритмизации.
если уж делать через массивы (которые, вообще говоря, лучше разбивать ещё знаками препинания), то можно сделать всё буквально за один проход, сравнивая поэлементно; плюс забегая вперёд/назад, проверяя наличие/отсутствие дополнительных элементов. ну и вообще плясать надо от задачи - реализация зависит от того насколько точным должно быть сравнение (достаточно ли просто найти отличающиеся слова, или надо проверять посимвольно, особым образом отмечая различающиеся/добавленные/вырезанные куски). |
Цитата:
|
Цитата:
мы ж тогда получим равенство текстов 'a b c' и 'c a b' одним циклом идём по первому "эталонному" массиву, сравниваем элементы со 2м, если не совпадают, делаем пару-тройку дополнительных шагов "в стороны". если совпадений нет, значит у нас во 2м тексте появились/пропали слова. у такого подхода есть минус в том что если много повторящихся подряд идущих слов, алгоритм будет косячить. ну говорю ж, от задачи надо идти. |
Имхо нужен метод шинглов http://ru.wikipedia.org/wiki/%D0%90%...BB%D0%BE%D0%B2
Но это уже потянет за собой серверное решение. |
Цитата:
перечитай формулировку задачи, нафига ему такой фундаментальный метод?) |
Всем большое спасибо, сейчас изучу все вышеописанное.
|
var text1 = "Мама мыла очень кривую раму";
var text2 = "Мама долго мыла кривую раму";
var arr1 = text1.split(' ');
var arr2 = text2.split(' ');
var result1 = [], result2 = [];
for (var i = 0; i < arr1.length; i++) {
if (arr2[i] == undefined) {
for (var j = i; j < arr1.length; j++) {
arr1[j] = "<span class='changedText'>" + arr1[j] + "</span>";
}
break;
}
if (arr1[i] != arr2[i]) {
if (findInArray(arr1[i], arr2)) {
arr1.splice(i, 0, arr1[i]);
arr2[i] = "<span class='changedText'>" + arr2[i] + "</span>";
if (result1[result1.length - 1] != arr1[i])
result1.push(arr1[i]);
result2.push(arr2[i]);
} else {
arr2.splice(i, 0, arr2[i]);
arr1[i] = "<span class='changedText'>" + arr1[i] + "</span>";
result1.push(arr1[i]);
}
} else {
if (result1[result1.length - 1] != arr1[i])
result1.push(arr1[i]);
result2.push(arr2[i]);
}
}
function findInArray (element, array) {
var find = false;
for (var i = 0; i < array.length; i++) {
if (array[i] == element)
find = true;
}
return find;
}
alert(result1.join(' '));
alert(result2.join(' '));
Вроде работает, но есть косяки: Не придумал что делать если новый текст длиннее исходного (я пробегаюсь только по исходному массиву). keen, Как Вы и говорили косяки со знаками препинания. Вроде это можно сделать регулярными выражениями, но в них я не силен, как бы мне выделить в отдельные элементы массива знаки препинания так, чтобы потом оно нормально склеилось в строку и не потерять при этом знаки? И ещё, мой алгоритм не выводит в первом массиве 2 одинаковых слова :( |
Цитата:
____________ Цитата:
Приведите примеры. |
Не совсем. На странице представлены 2 версии документа. text1 текст данного поля из более старой версии, text2 - соответственно более новой. Необходимо цветом выделить изменения в обоих документах. И в старом и в новом. Чтобы оператор при работе с ними не искал читая одинаковые документы.
|
У документов есть поля для редактирования, так что функция не должна быть рассчитана на обработку больших количеств текста за 1 заход.
Оптимизация и скорость работы тоже не волнует, т.к. Функция запускается однократно при загрузке страницы. |
Например, для
var text1 = "Мама мыла очень кривую раму"; var text2 = "Мама долго мыла кривую раму"; какие слова нужно вывести? |
Demath,
Для данных текстов: text1 = "Мама мыла <span class='changedText'>очень</span> кривую раму" text2 = "Мама <span class='changedText'>долго</span> мыла кривую раму" И из первого исчезло "очень", мы его выделяем, а во втором добавилось "долго", его мы тоже выделяем. Удивительно, но скрипт выше правильно отрабатывает данные тексты :blink: :) По идее, если бы тексты были такие: var text1 = "Мама мыла кривую раму"; var text2 = "Мама мыла раму"; То необходимо было бы в первом тексте выделить "кривую", а второй оставить неизменным. |
Цитата:
Цитата:
|
Прошу прощения если непонятно объясняю.
|
Почитайте перед сном симметрическая разность :)
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;
}
function SymmDiffArrays(A,B)
{
return DiffArrays(A,B).concat( DiffArrays(B,A) );
}
var text1 = "Мама мыла очень кривую раму",
text2 = "Мама долго мыла кривую раму",
arr1 = text1.split(' '),
arr2 = text2.split(' ');
alert( SymmDiffArrays(arr1, arr2) );
|
Demath,
Спасибо за ответ, учу матчасть! :write: |
function difference(a, b) {
a = a.split(' ');
b = b.split(' ');
var d1 = a.filter(function(i) {return !(b.indexOf(i) > -1);});
var d2 = b.filter(function(i) {return !(a.indexOf(i) > -1);});
return d1.concat(d2);
}
alert(difference("Мама мыла очень кривую раму", "Мама долго мыла кривую раму"));
|
Началось, кто короче) Я только-только 1-й вариант прожевал)
Спасибо :) Вы не подскажете, как знаки препинания тоже в отдельные элементы массива положить? Потому что иначе с ними тоже косяк. С регулярками, увы, не дружу совсем. :( |
function difference(a, b) {
var re = /([~!$%^&*()_+|`\-=\\\[\]{};':",\.\/<>?@#])/g;
a = a.replace(re, ' $1').split(' ');
b = b.replace(re, ' $1').split(' ');
var d1 = a.filter(function(i) {return !(b.indexOf(i) > -1);});
var d2 = b.filter(function(i) {return !(a.indexOf(i) > -1);});
return d1.concat(d2);
}
alert(difference("Мама! мыла очень кривую раму", "Мама? долго мыла кривую раму"));
|
devote,
Спасибо большое! |
tsigel,
Обратите внимание indexOf и filter не доступны в IE до IE9. |
вот полифил filter:
if (!Array.prototype.filter) {
Array.prototype.filter = function(fun /*, thisp*/) {
'use strict';
if (!this) {
throw new TypeError();
}
var objects = Object(this);
var len = objects.length >>> 0;
if (typeof fun !== 'function') {
throw new TypeError();
}
var res = [];
var thisp = arguments[1];
for (var i in objects) {
if (objects.hasOwnProperty(i)) {
if (fun.call(thisp, objects[i], i, objects)) {
res.push(objects[i]);
}
}
}
return res;
};
}
И соответственно indexOf:
if (!Array.prototype.indexOf) {
Array.prototype.indexOf = function (searchElement /*, fromIndex */ ) {
'use strict';
if (this == null) {
throw new TypeError();
}
var n, k, t = Object(this),
len = t.length >>> 0;
if (len === 0) {
return -1;
}
n = 0;
if (arguments.length > 1) {
n = Number(arguments[1]);
if (n != n) { // shortcut for verifying if it's NaN
n = 0;
} else if (n != 0 && n != Infinity && n != -Infinity) {
n = (n > 0 || -1) * Math.floor(Math.abs(n));
}
}
if (n >= len) {
return -1;
}
for (k = n >= 0 ? n : Math.max(len - Math.abs(n), 0); k < len; k++) {
if (k in t && t[k] === searchElement) {
return k;
}
}
return -1;
};
}
|
Цитата:
|
оффтоп: winmerge изобретаем, понятно...
|
| Часовой пояс GMT +3, время: 01:47. |