带回溯的编辑距离

功能说明

该示例计算两个字符串之间的 Levenshtein 编辑距离，并返回具体的插入、删除与替换步骤。距离可用于拼写纠错、模糊搜索、版本对比和输入相似度判断。函数使用 Array.from 拆分字符串，因此表情符号等由多个码元组成的字符会作为一个整体参与比较，不会把代理对拆坏。

关键代码

矩阵大小为 (左串长度 + 1) 乘 (右串长度 + 1)，第一行与第一列表示从空串转换的代价。填充时若当前字符相同则对角线代价为 0，否则取删除、插入、替换三种操作的最小值加一。回溯从右下角开始，优先走对角线，其次删除，最后插入，把操作压栈后反转，得到从源串到目标串的正向步骤。

使用注意

时间和空间复杂度都是 O(n 乘 m)，默认 maxLength 为 4000，超过会抛 RangeError，防止一次比较耗尽内存。替换操作不会展开成一次删除加一次插入，因此操作数量可能少于其他等价路径。该距离不包含换位操作，拼写检查场景可改用 Damerau-Levenshtein。矩阵使用 Uint32Array，超大输入仍应改用分块或带宽限制的近似算法。

验证方式

断言 kitten 与 sitting 的距离为 3，并检查操作序列包含两次替换与一次插入。测试空串到 abc 的距离为 3、完全相同的字符串距离为 0、单字符差异为 1。再用含表情符号的字符串验证按码点计数，并断言超过 maxLength 时抛 RangeError。

代码示例

export function editDistance(source, target, options = {}) {
  if (typeof source !== "string" || typeof target !== "string") {
    throw new TypeError("source and target must be strings");
  }
  const { maxLength = 4000 } = options;
  const left = Array.from(source);
  const right = Array.from(target);
  if (left.length > maxLength || right.length > maxLength) {
    throw new RangeError(`input exceeds maxLength of ${maxLength} code points`);
  }
  const rows = left.length + 1;
  const columns = right.length + 1;
  const matrix = Array.from({ length: rows }, () => new Uint32Array(columns));
  for (let row = 0; row < rows; row += 1) matrix[row][0] = row;
  for (let column = 0; column < columns; column += 1) matrix[0][column] = column;
  for (let row = 1; row < rows; row += 1) {
    for (let column = 1; column < columns; column += 1) {
      const cost = left[row - 1] === right[column - 1] ? 0 : 1;
      matrix[row][column] = Math.min(
        matrix[row - 1][column] + 1,
        matrix[row][column - 1] + 1,
        matrix[row - 1][column - 1] + cost,
      );
    }
  }
  return {
    distance: matrix[rows - 1][columns - 1],
    operations: backtrace(left, right, matrix),
  };
}

function backtrace(left, right, matrix) {
  const operations = [];
  let row = left.length;
  let column = right.length;
  while (row > 0 || column > 0) {
    const diagonalCost = row > 0 && column > 0 && left[row - 1] === right[column - 1] ? 0 : 1;
    if (row > 0 && column > 0 && matrix[row][column] === matrix[row - 1][column - 1] + diagonalCost) {
      if (diagonalCost === 1) {
        operations.push({ type: "substitute", from: left[row - 1], to: right[column - 1] });
      }
      row -= 1;
      column -= 1;
    } else if (row > 0 && matrix[row][column] === matrix[row - 1][column] + 1) {
      operations.push({ type: "delete", value: left[row - 1] });
      row -= 1;
    } else {
      operations.push({ type: "insert", value: right[column - 1] });
      column -= 1;
    }
  }
  return operations.reverse();
}

console.log(editDistance("kitten", "sitting"));
console.log(editDistance("book", "back"));
console.log(editDistance("", "abc"));