JS 文本差异对比算法 - 实现类似 Git Diff 的行级比较功能-js教程-PHP中文网

JS 文本差异对比算法 - 实现类似 Git Diff 的行级比较功能

夢幻星辰

发布： 2025-09-18 19:37:01

原创

800人浏览过

答案是使用Myers差分算法实现行级文本对比，该算法通过计算最短编辑距离找出两文本差异，JavaScript中可基于动态规划实现路径追踪，将每行视为独立元素进行比较，最终输出包含插入、删除、相同行的差异序列，并可通过高亮、并排显示或HTML报告等方式可视化结果。

js 文本差异对比算法 - 实现类似 git diff 的行级比较功能

JS 文本差异对比算法，目标是实现类似 Git Diff 的行级比较功能，简单来说，就是找出两个文本版本之间的差异，并以易于理解的方式呈现出来。

实现类似 Git Diff 的行级比较功能，通常需要用到文本差异对比算法。这里主要介绍一种常见的算法：Myers 差分算法，以及如何用 JavaScript 实现它。

Myers 算法的核心思想是找到两个文本之间的最短编辑距离。编辑距离是指将一个文本转换为另一个文本所需的最少操作次数，这些操作包括插入、删除和替换。在行级比较中，我们将每一行文本视为一个独立的元素。

如何选择合适的文本差异对比算法？

选择算法时，需要考虑几个因素：性能、准确性和易用性。Myers 算法在性能和准确性之间取得了较好的平衡，并且相对容易理解和实现。还有一些其他的算法，例如 LCS（最长公共子序列）算法，但 Myers 算法通常更适合行级比较。

在实际应用中，如果文本量非常大，可以考虑使用一些优化过的 Myers 算法变种，例如使用启发式搜索或并行计算来提高性能。此外，一些现成的 JavaScript 库也提供了文本差异对比功能，例如

diff

登录后复制

库。这些库通常已经对算法进行了优化，并且提供了更丰富的功能，例如高亮显示差异、生成 HTML 格式的差异报告等。

如果对性能要求不高，或者只是想了解算法的原理，可以自己实现 Myers 算法。下面是一个简单的 JavaScript 实现示例：

Calliper 文档对比神器

文档内容对比神器

查看详情

function diff(a, b) {
  const n = a.length;
  const m = b.length;
  const max = n + m;
  const v = new Array(2 * max + 1).fill(0);
  const prev = new Array();

  for (let d = 0; d <= max; d++) {
    for (let k = -d; k <= d; k += 2) {
      let x = (k === -d || (k !== d && v[max + k - 1] < v[max + k + 1])) ?
        v[max + k + 1] :
        v[max + k - 1] + 1;
      let y = x - k;

      while (x < n && y < m && a[x] === b[y]) {
        x++;
        y++;
      }

      v[max + k] = x;

      if (x === n && y === m) {
          // 找到了最短路径
          let path = [];
          let curX = x, curY = y, curK = k, curD = d;
          while (curD > 0) {
              let prevK;
              if (curK === -curD || (curK !== curD && prev[curD-1][max + curK - 1] < prev[curD-1][max + curK + 1])) {
                  prevK = curK + 1;
              } else {
                  prevK = curK - 1;
              }
              let prevX = prev[curD-1][max + prevK];
              let prevY = prevX - prevK;

              while (curX > prevX && curY > prevY) {
                  path.push({type: 'equal', value: a[curX-1]});
                  curX--;
                  curY--;
              }
              if(prevK > curK){
                path.push({type: 'insert', value: b[curY-1]});
              } else {
                path.push({type: 'delete', value: a[curX-1]});
              }
              curK = prevK;
              curD--;
          }
          return path.reverse();
      }
    }
    prev[d] = [...v]; // 记录当前v的状态
  }

  return null; // 没有找到差异
}

// 示例用法
const a = ['line1', 'line2', 'line3', 'line4'];
const b = ['line1', 'line2', 'line5', 'line4', 'line6'];

const differences = diff(a, b);

if (differences) {
  differences.forEach(d => {
    console.log(d.type, d.value);
  });
} else {
  console.log('No differences found.');
}

登录后复制

这个代码示例只是一个简单的实现，没有进行任何优化。在实际应用中，需要根据具体的需求进行调整和优化。