'use strict';
function loop(src, dst) {
const n = src.length;
const m = dst.length;
let d; // d-path
const V = []; // 用于存储所有d-path的可能的k线的最佳落点
for (d = 0; d <= n + m; d++) {
const currentDTrace = {};
let x;
let y;
V.push(currentDTrace);
// 0-path能到达的最远点
if (d === 0) {
let t = 0;
while (n > t && m > t && src[t] === dst[t]) {
t++;
}
currentDTrace[d] = t;
if (t === n && t === m) {
return { V, n, m, d };
}
continue;
}
// (d-1)-path的所有落点集合
const lastDPath = V[d - 1];
for (let k = -d; k <= d; k += 2) {
if (k === -d || (k !== d && lastDPath[k - 1] < lastDPath[k + 1])) { // 从(d-1)-path向下,insert操作
x = lastDPath[k + 1];
} else { // 从(d-1)-path向右,delete操作
x = lastDPath[k - 1] + 1;
}
y = x - k;
while (x < n && y < m && src[x] === dst[y]) {
x++;
y++;
}
currentDTrace[k] = x;
if (x === n && y === m) {
return { V, n, m, d };
}
}
}
}
// 回溯生成路径
function getTrace(V, n, m, d) {
const trace = [];
let currX = n;
let currY = m;
for (let dCopy = d; dCopy > 0; dCopy--) {
const prevDTrace = V[dCopy - 1];
const k = currX - currY;
const prevK = k === -dCopy || (k !== dCopy && prevDTrace[k - 1] < prevDTrace[k + 1]) ? k + 1 : k - 1;
const prevX = prevDTrace[prevK];
const prevY = prevX - prevK;
while (currX > prevX && currY > prevY) {
trace.unshift({ type: 'MOVE', x1: currX - 1, y1: currY - 1, x2: currX, y2: currY });
currX -= 1;
currY -= 1;
}
trace.unshift({ type: currX === prevX ? 'INSERT' : 'DELETE', x1: prevX, y1: prevY, x2: currX, y2: currY });
currX = prevX;
currY = prevY;
}
const zeroPathDotX = V[0]['0']; // 0-path最后的落点的x值
const zeroPathDotY = zeroPathDotX - 0;
if (zeroPathDotX !== 0) {
for (let i = 0; i < zeroPathDotX; i++) {
trace.unshift({
type: 'MOVE',
x1: zeroPathDotX - (i + 1),
y1: zeroPathDotY - (i + 1),
x2: zeroPathDotX - i,
y2: zeroPathDotY - i,
});
}
}
return trace;
}
const myers = (src, dst) => {
const { V, n, m, d: minEditDistance } = loop(src, dst);
const trace = getTrace(V, n, m, minEditDistance);
const lcsLength = trace.length - minEditDistance;
return { trace, minEditDistance, lcsLength };
};
module.exports = {
myers,
};
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.