Modifizierung von Myers diff durch Identifizierung von zusammengesetzten Einheiten und Behandlung als 1 einzelne Einfügu ⇐ JavaScript

[Guest]

Myers Difff-Algorithmus funktioniert auf Charakterebene und identifiziert bei jedem Schritt Einfügung, Entfernung oder No-Operation. Zum Beispiel führt der Vergleich von pqrsxrsrsz (alte Zeichenfolge, die horizontal dargestellt) und pqrsarsxrsy (neu präsentiert vertikal dargestellt) zur Entfernung von x, die Einführung von A, Entfernung von y, Einfügung von x, Entfernung von Z und Einfügung von y. < /p>

Code: Select all

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

Aber wenn ich RS in beiden Zeichenfolgen ersetze, wird die alte Zeichenfolge zu pqxyz und neu wird zu pqaxy , erstellen:

Code: Select all

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

wobei nur ein entfernt und z eingefügt wird.
Hier ist das o ((m+n) D) Version von Myers Diff-Algorithmus. Snippet-Code-Js Lang-Js PrettyPrint-Override ">

Code: Select all

        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