做个文本对比工具，高亮出两段文字哪里不一样

想做个小工具：两段文字贴进去，高亮标出哪里改了。

第一反应是逐字符比对，做出来发现结果一团糟——改一个字，后面所有字符的对应关系全错位了，满屏都是"不同"。正确做法是先按行比对，再在行内找差异。核心算法是 LCS。

一、为什么按字符比对不行

假设原文是 abcdef，改了一个字符变成 abXdef。

按位置逐个比：第 3 位 c vs X，不同；第 4 位 d vs d……等等，实际上因为插入/删除了一个字符，后面的位置全错开了。

真实的 diff 算法要能识别：哪些是"没变的"，哪些是"新增的/删掉的"。这就是 LCS 要解决的问题。

二、最长公共子序列（LCS）

子序列的意思是：从原序列里去掉一些元素、但不改变剩下元素的相对顺序。

比如 abcde 和 ace 的最长公共子序列是 ace，长度 3。

用在 diff 上：LCS 里的行就是"没变的行"，其余的就是新增或删除的。

不同比对粒度适合不同场景，先对号入座再写代码：

实际工具里普遍用"行级为主、行内为辅"这条路线。

动态规划实现：

function lcsMatrix(a, b) {
  const m = a.length, n = b.length
  // dp[i][j] = a 的前 i 个和 b 的前 j 个的 LCS 长度
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0))

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
      }
    }
  }
  return dp
}

function diffLines(oldLines, newLines) {
  const dp = lcsMatrix(oldLines, newLines)
  const result = []

  let i = oldLines.length, j = newLines.length
  while (i > 0 || j > 0) {
    if (i > 0 && j > 0 && oldLines[i - 1] === newLines[j - 1]) {
      result.unshift({ type: 'same', text: oldLines[i - 1] })
      i--; j--
    } else if (j > 0 && (i === 0 || dp[i][j - 1] >= dp[i - 1][j])) {
      result.unshift({ type: 'add', text: newLines[j - 1] })
      j--
    } else {
      result.unshift({ type: 'del', text: oldLines[i - 1] })
      i--
    }
  }
  return result
}

得到的结果是三种类型的行：same（没变）、add（新增）、del（删除）。渲染时给不同背景色就完事了。

三、O(n×m) 是真会卡

这是做这个工具最大的坑。

LCS 的复杂度是 O(n×m)——两段各 1000 行，就要算一百万次，还要开一个 1000×1000 的二维数组（存一百万个数字）。

实测：各 2000 行的时候，页面会明显卡住一两秒，鼠标都动不了。各 5000 行基本就卡死了。

几个优化方向：

第一，先去掉公共的前缀和后缀。 大多数时候改动在中间，头和尾是一样的：

function trimCommon(oldLines, newLines) {
  let start = 0
  while (start < oldLines.length && start < newLines.length
         && oldLines[start] === newLines[start]) {
    start++
  }

  let endOld = oldLines.length - 1
  let endNew = newLines.length - 1
  while (endOld >= start && endNew >= start
         && oldLines[endOld] === newLines[endNew]) {
    endOld--; endNew--
  }

  return {
    head: oldLines.slice(0, start),
    midOld: oldLines.slice(start, endOld + 1),
    midNew: newLines.slice(start, endNew + 1),
    tail: oldLines.slice(endOld + 1),
  }
}

只对中间那段跑 LCS，头尾直接标记为相同。改动集中在中间时，这一刀能砍掉 90% 的计算量。

第二，按行哈希降维。 比较长字符串慢，先转成数字：

function toHashes(lines) {
  const map = new Map()
  return lines.map(line => {
    let h = 0
    for (let i = 0; i < line.length; i++) {
      h = (h * 31 + line.charCodeAt(i)) >>> 0      // 简单字符串哈希
    }
    if (!map.has(h)) map.set(h, line)
    return h
  })
}

之后比对的是数字，快很多。（注意哈希可能碰撞，业务上可接受；严谨的话碰撞时用原字符串再比一次。）

第三，超过阈值就降级。 给个上限，超了就提示用户"内容太长，只显示前 N 行的差异"，别死等：

const MAX_LINES = 1500
if (oldLines.length > MAX_LINES || newLines.length > MAX_LINES) {
  return { tooLong: true }
}

四、行内高亮

行级 diff 做完，还能再细一层：在一对"删除行 + 新增行"里，标出具体哪几个字符变了。

function diffWords(oldStr, newStr) {
  // 先找公共前缀
  let start = 0
  while (start < oldStr.length && start < newStr.length
         && oldStr[start] === newStr[start]) {
    start++
  }
  // 再找公共后缀
  let endOld = oldStr.length - 1
  let endNew = newStr.length - 1
  while (endOld >= start && endNew >= start
         && oldStr[endOld] === newStr[endNew]) {
    endOld--; endNew--
  }

  return {
    prefix: oldStr.slice(0, start),
    removed: oldStr.slice(start, endOld + 1),
    added: newStr.slice(start, endNew + 1),
    suffix: oldStr.slice(endOld + 1),
  }
}

这个简化版只处理"中间改了一块"的情况，对付绝大多数改动够了。要处理多处改动就得再上完整的字符级 LCS。

五、渲染

function render(diff) {
  const html = diff.map(item => {
    const cls = item.type                    // same / add / del
    return `<div class="line ${cls}">${escapeHtml(item.text)}</div>`
  }).join('')
  container.innerHTML = html
}

escapeHtml 必须加。用户粘贴的内容可能有 <、& 这些字符，不转义的话会破坏 HTML 结构，严重的还会 XSS。

.line.same { color: #5b6b82; }
.line.add  { background: #e6f4ea; color: #1e6b3a; }
.line.del  { background: #fce8e6; color: #a32d2d; }

几个容易忽略的点

• 空行和空格。用户从编辑器复制过来的文本，行尾可能有空格，a 和 a 会被判成不同。可以先 trimEnd() 归一化，或者提供"忽略空白"开关。

• 换行符。Windows 是 \r\n，Mac/Linux 是 \n，不统一处理会出现满屏"差异"。split 之前先统一：

  const lines = text.replace(/\r\n/g, '\n').split('\n')
  

• 结尾的空行。"a\nb\n".split('\n') 会得到 ['a', 'b', '']，多一个空元素。一般要去掉最后一个空行再比对。

• 别在输入框变化时就立刻算。用防抖，等用户停手 300 毫秒再跑 diff，不然输入过程中会一直卡。

• 大文本考虑放 Web Worker。把 diff 计算丢到后台线程，主线程不卡。代码复杂度会上一个台阶，看需求决定。

• 左右并排还是上下统一显示。并排更直观，但窄屏上放不下。可以宽屏并排、窄屏自动切上下。

小结

文本 diff 的核心就是 LCS——公共子序列里的行是没变的，其余是增删。实现不难，难在性能：它是 O(n×m) 的，两千行就能让页面卡住。所以实际用的时候必须做三件事：先削掉公共的头尾、按行哈希降维、超过阈值降级提示。还有两个容易翻车的小细节——换行符要统一、innerHTML 渲染前必须转义 HTML。做好这些，一个几百行的文本对比工具就足够好用了。