diff算法原理与前端应用详解

diff算法原理与前端应用详解

引用

CSDN

1.

https://m.blog.csdn.net/weixin_41697143/article/details/142916725

diff算法是一种用于比较两个数据（如字符串、对象）差异的算法，在版本控制（如Git）、代码对比、数据同步等场景中有着广泛的应用。本文将介绍diff算法的基本原理、实现方法及其在前端开发中的应用。

diff算法原理

diff算法的核心是找出两个数据之间的差异，例如字符串的差异、对象的差异。在版本控制中，diff算法常用于展示代码的修改历史，如下图所示：

绿色部分表示添加，红色部分表示删除。diff算法可以处理整行的删除和增加，也可以处理行内的字符变化。

LCS算法

LCS（最长公共子序列）算法是diff算法中最常用的一种实现方式，时间复杂度为O(n²)，本质上是动态规划算法的扩展。

最长公共子序列与最长公共子串

• 最长公共子串：两个字符串中的最长公共子串，要求子串一定连续。
• 最长公共子序列：两个字符串中的最长公共子序列，不要求子序列连续。

例如，两个字符串abcde和ace的最长公共子序列如下图所示：

其核心递推式如下：

• 如果str1[i - 1]等于str2[j - 1]，则当前值为左上角值加1，即D[i][j] = D[i - 1][j - 1] + 1。
• 如果str1[i - 1]不等于str2[j - 1]，则当前值为上方和左方值的最大值，即D[i][j] = Max(D[i - 1][j], D[i][j - 1])。

查分算法

基于Myers在1986年提出的算法，核心思想可以概括为以下三个步骤：

1. 将两个文本拆分为“标记”数组，标记的构成各不相同；在diffChar中，每个字符都是一个标记，而在diffLines中，每一行都是标记。
2. 找到将第一个token数组转换为第二个token数组所需的最小单token插入和删除集合。
3. 返回一个数组，将上一步中计算的变换表示为一系列变化对象。

其他改进的diff算法

基于基本的diff算法，很多学者提出了“最长公共子数组”算法，或者优化了虚拟DOM的diff算法。这些改进算法的思想值得学习，但由于篇幅限制，这里不进行展开。

diff算法在前端中的应用

JavaScript第三方库实现

jsdiff是一个常用的diff算法库，使用人数很多，项目中可以放心使用。以下是一个在Node.js中的使用示例：

// jsdiff demo, reference: https://github.com/kpdecker/jsdiff
// nodejs
// "colors": "^1.4.0",
// "diff": "^7.0.0"
require('colors');
const Diff = require('diff');
// 核心：比较两个字符串的差异 Diff.diffChars(s1, s2)
const diffList = Diff.diffChars('Hello Michael Blog', 'Hello Tom Blog');
// 返回值是一个列表，然后循环用不同颜色展示
diffList.forEach((part) => {
  let text = part.value;
  // green for additions
  if (part.added) {
    text = part.value.bgGreen;
  }
  // red for deletions
  if (part.removed) {
    text = part.value.bgRed;
  }
  process.stderr.write(text);
});

React第三方库实现

diff-viewer是diff库在React框架中进一步的应用，可以直接将代码传入组件中展示差异。以下是一个使用示例：

// react-diff-viewer demo, reference: https://github.com/praneshr/react-diff-viewer
import React, { PureComponent } from 'react';
import ReactDiffViewer from 'react-diff-viewer';
// 两端代码（字符串）
const oldCode = `
const a = 10
const b = 10
const c = () => console.log('foo')
if(a > 10) {
  console.log('bar')
}
console.log('done')
`;
const newCode = `
const a = 10
const boo = 10
if(a === 10) {
  console.log('bar')
}
`;
// 直接把代码传入组件中，即可展示。其他的属性和配置详见官方网站。
class Diff extends PureComponent {
  render = () => {
    return (
      <ReactDiffViewer oldValue={oldCode} newValue={newCode} splitView={true} />
    );
  };
}
export default Diff;

Python库实现

Python内置函数也实现了diff效果，以下是一个使用示例：

import difflib
# https://blog.csdn.net/molangmolang/article/details/138093020
text1 = '一次性执行\nJS\nPY\nTS\n的单元测试'
text2 = '一次性执行\njavascript\npython\ntypescript\n的单元测试'
# 创建Differ对象
differ = difflib.Differ()
# 使用Differ对象生成差异报告
# diff = differ.compare(text1.splitlines(' '), text2.splitlines(' '))
diff = differ.compare(text1.splitlines(keepends=True), text2.splitlines(keepends=True))
# 打印差异报告
print(''.join(diff))

手写diff算法实现

在某些场景下，可能需要自己实现diff算法。以下是一个基于LCS算法的diff实现示例：

function LcsFn(str1, str2) {
  const n1 = str1.length;
  const n2 = str2.length;
  // 建立空的二维数组，填充0，行列分别是两个字符串的长度
  const lcsArr = new Array(n1 + 1).fill(null).map((_, index) => new Array(n2 + 1).fill(0));
  // 使用动态规划存储子串长度
  // 遍历矩阵
  for (let i = 1; i < n1 + 1; i++) {
    for (let j = 1; j < n2 + 1; j++) {
      // 如果字符串的两个值相等，那么当前的值等于左上角的值 + 1
      if (str1[i - 1] === str2[j - 1]) {
        lcsArr[i][j] = lcsArr[i - 1][j - 1] + 1;
      }
      // 如果字符串的两个值不等，那么当前值等于上面的值和左边的值的最大值。
      else {
        lcsArr[i][j] = Math.max(lcsArr[i][j - 1], lcsArr[i - 1][j]);
      }
    }
  }
  const sameStr = getStr(str1, str2, lcsArr);
  return { str1, str2, lcsArr, sameStr }
}
// 根据二维数组，输出子串具体字符
function getStr(str1, str2, lcsArr) {
  const result = []
  let i = str1.length;
  let j = str2.length;
  // 使用双指针获取矩阵的索引
  while (i > 0 && j > 0) {
    // 如果索引对应的字符串一样，那么把相同的字符，放到结束数组中（就是公共字符）
    // 如果索引对应的字符串不一样，比较矩阵的值，那么一个指针减少1
    if (str1[i - 1] === str2[j - 1]) {
      result.unshift(str1[i - 1])
      i--
      j--
    } else if (lcsArr[i][j - 1] > lcsArr[i - 1][j]) {
      j--
    } else {
      i--
    }
  }
  return result;
}
let str1 = 'hello-Mike-Hi';      //  最长相同子串为：'e,l,o,b,g'   -- 长度9
let str2 = 'hello-Tom-Hi'; // -- 长度14
console.log(LcsFn(str1, str2));

参考链接

• jsdiff: https://github.com/kpdecker/jsdiff
• An O(ND) Difference Algorithm and Its Variations: http://www.xmailserver.org/diff2.pdf
• https://xueshu.baidu.com/usercenter/paper/show?paperid=1b0039833a74422f1de7e4286d40f30f
• https://download.csdn.net/blog/column/8019278/88798916
• https://www.cnblogs.com/wp-leonard/p/17888780.html
• https://blog.csdn.net/m0_74931837/article/details/142443789