前段时间公司里有需求需要一个文本对比工具,我在网上也收集到了一些资料,找到了一些对比 DEMO,仔细考虑之后恍然大悟,这东西不就是最长公共子序列算法吗?

所谓的 diff,就是寻找两个文本中的最长公共子序列,子序列的任意部分都是正确的部分,而在这个序列之外的字符就是错误字符,抱着这个思路我开发了一个基于 Web 的校对工具,当然虽然可能有些粗糙,但还是非常宝贵的实践体验啊,因为这是我学习一些算法来第一次真正意义上的用到,并且如果不知道这个算法的话,可能真的写不出来这个工具(只能用循环判断来进行对比,一但某个字符错误,接下来全错)

在这里放出核心的代码。

const LCS_TABLE = (s1, s2) => {
  s1 = s1.slice()
  s2 = s2.slice()
  let x = s1.length
  let y = s2.length
  // 需要保证表格的便利与数组的访问同意 也就是从1 开始
  // 所以需要在前面将数组踮起 并且为了避免越界 需要在获取长度之后进行
  s1.unshift(null)
  s2.unshift(null)
  // 以下两个循环都是为了打出一个边界 也就是表格的最顶层和最左层都是0
  let table = []
  for (let i = 0; i <= x; i++) {
    table[i] = []
    table[i][0] = {
      val: 0
    }
  }
  for (let i = 0; i <= y; i++) {
    table[0][i] = {
      val: 0
    }
  }
  // 正式开始
  for (let i = 1; i <= x; i++) {
    for (let j = 1; j <= y; j++) {
      // 找到匹配 填入左上箭头
      if (s1[i] === s2[j]) {
        table[i][j] = {
          val: table[i - 1][j - 1].val + 1,
          lt: true,
          t2Index: j - 1
        }
      } else if (table[i - 1][j].val >= table[i][j - 1].val) {
        table[i][j] = {
          val: table[i - 1][j].val,
          top: true,
          t2Index: j - 1
        }
      } else {
        table[i][j] = {
          left: true,
          val: table[i][j - 1].val,
          t2Index: j - 1
        }
      }
    }
  }
  return table
}

const printLCS = (table, X, i, j) => {
  if (i === 0 || j === 0) return
  if (table[i][j].lt) {
    return printLCS(table, X, i - 1, j - 1)
  }
  if (table[i][j].top) {
    return printLCS(table, X, i - 1, j)
  }
  return printLCS(table, X, i, j - 1)
}

// 返回一个包含 text2Index 下标的数组
// 所有匹配的文本
const processTextLCSDiff = table => {
  let i = table.length - 1
  let j = table[0].length - 1
  function _inner(table, i, j) {
    if (i === 0 || j === 0) return []
    if (table[i][j].lt) {
      return [table[i][j].t2Index].concat(_inner(table, i - 1, j - 1))
    }
    if (table[i][j].top) {
      return [].concat(_inner(table, i - 1, j))
    }
    return [].concat(_inner(table, i, j - 1))
  }
  return _inner(table, i, j)
}

const getDiffTextArray = (diffIndexArray, textArray) => {
  return textArray.map((v, i) => {
    // 检测该字符是否匹配
    let findex = diffIndexArray.findIndex(v => v === i)
    if (findex > -1) {
      return {
        mathed: true,
        val: v
      }
    }
    return {
      mathed: false,
      val: v
    }
  })
}

// 接收主文本和副文本 返回已副文本为基准的一个数组,其内部为对象,标记该单个字符和正确情况。
function textDiffCore(mainText, assistantText) {
  mainText = mainText.split('')
  assistantText = assistantText.split('')
  console.time('search')
  const table = LCS_TABLE(mainText, assistantText)
  console.timeEnd('search')
  console.time('LCS')
  const LCSArray = processTextLCSDiff(table)
  console.timeEnd('LCS')
  return getDiffTextArray(LCSArray, assistantText)
}

// 接收两段文本 和一个元素以便插入结果
function startDiff(text1, text2, content) {
  // 已1为基准 进行前置处理
  // 文本处理的内容是用正则删除所有空格换行 业务需要
  text1 = textProcess(text1)
  text2 = textProcess(text2)
  let diffResult = textDiffCore(text1, text2)
  let htmlText = diffResult.map(v => {
    return (
      '<span ' +
      (v.mathed ? 'class="corrent" ' : 'class="fail" ') +
      '>' +
      v.val +
      '</span>'
    )
  })
  content.html(htmlText)
}

求最长公共子序列是一个NPHard问题,她的效率是O(n ^ 2),还是比较慢的,还有一点我这个东西因为业务需要是删除所有换行的,这样的话所有文本都处于一行上。

如果能分行对比,性能会有大幅度的提升。