Использование расстояния Levenshtein для вычисления HTML Diff ⇐ Javascript

[Anonymous]

Я использую расстояние Levenshtein, чтобы вычислить различия между 2 html Strings. Учитывая 2 строки HTML: < /p>

[*] Они сначала преобразуются в объекты DOM < /li>
Оба объекта DOM сгладиваются в 2 отдельных массивы < /li>
Он подается в алгоритм расстояния Левенштейна. < /li>
< /ol>
Но проблема в том, что это не всегда Вычислить наиболее оптимальную дифференциацию. Под оптимальным я имею в виду тот, который визуально более правильный. Например: < /p>

Код: Выделить всё

const oldHTML = `

[list]
x
[/list]

`;
< /code>
и < /p>
 const newHTML = `

[list]
[*]x
[/list]

[list]
[*]xy
[/list]

`;
< /code>
Должен создать Diff: < /p>

 < Br /> 
        

[list]
[*]xy
[/list]

[list]
[*]x
[/list]

< /code>
< /div>
< /div>
< /p>
, а скорее, он производит: < /p>


        

[list]
[*]xyx
[/list]

[list]
[*]x
[/list]

, что не является неверным, но не самым оптимальным. Вот как происходит строительство матрицы и ее обход: < /p>


var
diff = [],
row = old.length + 1,
column = current.length + 1,
offset = 1

function createMatrix() {
matrix = new Array(row);
for (var i = 0; i < row; i++) {
matrix = new Array(column);
}
//fill the 0th row and column
for (var i = 0; i < row; i++) {
matrix[0] = i;
}
for (var j = 0; j < column; j += 1) {
matrix[0][j] = j;
}
//calculate min operations
for (var i = 1; i < row; i++) {
for (var j = 1; j < column; j++) {
var a = old;
var b = current[j - offset];
var subDistance = (a.hashVal == b.hashVal) ? 0 : 10e6;
var costReplace = matrix[j - 1] + subDistance * a.elementCount + subDistance * b.elementCount;
var costRemoved = matrix[j] + a.elementCount;
var costInserted = matrix[j - 1] + b.elementCount;
matrix[j] = Math.min(costReplace, costRemoved, costInserted);
}
}
}

function traceBack() {
var i, j;

for (i = row - 1, j = column - 1; i > 0 && j > 0;) {
var top = matrix[j];
var topLeft = matrix[j - 1];
var left = matrix[j - 1];
if (topLeft == matrix[i][j] && topLeft 0) {
(current[j - offset]).status = 'inserted';
diff.unshift(current[j - offset]);
j--;
}
}< /code>
< /div>
< /div>
< /p>
Я ищу решение и перспективу, чтобы посмотреть на эту проблему. Что я наблюдал, так это: < /p>

Алгоритм Levenshtein в его следах выбора пути, который не является неверным. Но в той же матрице существует путь, который даст лучший результат, как я показал выше. Как к этому можно подходить? Пожалуйста, дайте мне знать, если я пропустил добавление дополнительной информации.


Подробнее здесь: https://stackoverflow.com/questions/793 ... -html-diff