Изменение различий Myers путем выявления составных единиц и обработки их как 1 отдельную вставку или удаление ⇐ Javascript

[Anonymous]

Алгоритм Diff Myers работает на уровне символов и идентифицирует вставку, удаление или отсутствие операции на каждом этапе. Так, например, сравнение PQRSXRSYRSZ (старая строка представлена ​​горизонтально) и PQRSARSXRSY (новая строка, представленная вертикально) приводит к удалению x, вставку a, удаление y, вставка x, удаление z и z и z и Вставка y. < /p>

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

      P Q R S X R S Y R S Z
P ↘ · · · · · · · · · ·
Q · ↘ · · · · · · · · ·
R · · ↘ · · · · · · · ·
S · · · ↘ → · · · · · ·
A · · · · ↓ · · · · · ·
R · · · · · ↘ · · · · ·
S · · · · · · ↘ → · · ·
X · · · · · · · ↓ · · ·
R · · · · · · · · ↘ · ·
S · · · · · · · · · ↘ →
Y · · · · · · · · · · ↓

Но если я заменяю Rs в обеих строках, старая строка становится pqxyz , а новый становится pqaxy , создание:

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

  P Q X Y Z
P ↘ · · · ·
Q · ↘ · · ·
A · ↓ · · ·
X · · ↘ · ·
Y · · · ↘ →

, где удаляется только и z вставлен.
Вот o ((m+n) D) Версия алгоритма Myers Diff. Сплык-кодек-д-дж Ланг-JS PrettyPrint-Override ">

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

        class Keep {
constructor(line) {
this.type = 'Keep';
this.line = line;
}
}

class Insert {
constructor(line) {
this.type = 'Insert';
this.line = line;
}
}

class Remove {
constructor(line) {
this.type = 'Remove';
this.line = line;
}
}

// Represents a point on the frontier with its history
class Frontier {
constructor(x, history) {
this.x = x;        // x-coordinate in edit graph
this.history = history;  // sequence of operations to reach this point
}
}

function myersDiff(old, current) {
// Initialize the frontier with starting point
// K=1 diagonal starts at (0,0) with empty history
const frontier = { 1: new Frontier(0, []) };

// Convert from 1-based to 0-based indexing
// Algorithm uses 1-based indexing, but JavaScript uses 0-based
function one(idx) {
return idx - 1;
}

const aMax = old.length;  // horizontal size of edit graph
const bMax = current.length;  // vertical size of edit graph

// Main loop: try increasing numbers of edits
for (let d = 0; d  x.hashVal));
return {
elements: sequence1.slice(pos1, pos1 + 3),
size: 3,
isCompound: true
};
}
}

console.log('Returning single unit:', sequence1[pos1].hashVal);
return {
elements: [sequence1[pos1]],
size: 1,
isCompound: false
};
}

function unitsMatch(unit1, unit2) {
if (!unit1 || !unit2) return false;
if (unit1.elements.length !== unit2.elements.length) return false;

return unit1.elements.every((elem, i) =>
elem.hashVal === unit2.elements[i].hashVal
);
}

function visualizePath(old, current, finalPath) {
const matrix = [];
const headerRow = [' '];
for (let char of old) {
headerRow.push(char.hashVal);
}
matrix.push(headerRow);

for (let i = 0; i < current.length; i++) {
const row = [current[i].hashVal];
for (let j = 0; j < old.length; j++) {
row.push('·');
}
matrix.push(row);
}

let prevX = 0, prevY = 0;
for (const [x, y] of finalPath) {
if (y >= 0 && y < matrix.length && x >= 0 && x < matrix[0].length) {
if (x === prevX && y > prevY) {
matrix[y][x] = '↓';
} else if (x > prevX && y === prevY) {
matrix[y][x] = '→';
} else if (x > prevX && y >  prevY) {
matrix[y][x] = '↘';
}
}
prevX = x;
prevY = y;
}

console.log('\nPath Visualization:');
for (const row of matrix) {
console.log(row.join(' '));
}
}

function addPathPoints(path, startX, startY, endX, endY, isDiagonal = false) {
if (isDiagonal) {
for (let i = 0; i  x.hashVal).join(''));
console.log('Current:', current.map(x => x.hashVal).join(''));
console.log('Max D:', maxD);

for (let d = 0; d 

Подробнее здесь: [url]https://stackoverflow.com/questions/79426058/modifying-myers-diff-by-identifying-compound-units-and-treating-them-as-1-single[/url]