一、背景简介

最近有一个项目使用富文本编辑器来编写带格式的文章，每次保存内容时都能生成历史记录，并且可以查看历史版本与当前版本的差异。这是一个典型的Diff视图功能，常见的代码编辑器、git、beyond compare都有类似的功能。

大部分diff工具或开源库都是基于纯文本的，市面上主流的富文本编辑器（TinyMCE、FCKEditor、TipTap）虽然也有提供diff插件，但无一例外都是收费功能，其它一些专门提供富文本diff的网站，也只提供商业化的付费功能。

考虑到项目对富文本Diff视图有比较多定制化的视觉和交互需求，同时市面上缺少能较好满足需求的开源项目，我们打算自己实现一个基于富文本的差异对比视图。

二、需求分析

我们的项目有几个特点：

1. 文章内容有排版和格式，而非纯文本。
2. 用户非技术人员，对于内容要所见即所得，无法使用markdown这样基于纯文本标记语言来写文章。
3. 富文本编辑器已经确定使用TipTap，方案设计时要考虑与TipTap的集成。

对应到技术实现上：

1. 内容是树状结构（比如一部分文字被加粗、斜体等修饰）。
2. diff视图中内容的排版和格式必须与编辑时一致，所以diff视图也需要渲染在富文本编辑器中，保证最大程度的所见即所得。

三、技术分析

1. 核心模块

无论是纯文本还是富文本，大部分diff视图按职责划分都会包含这三个核心模块

1. Differ 差异对比的核心算法，返回所有差异点的数据。
2. Renderer 负责渲染新、旧内容视图。
3. Highlighter 负责将Differ返回的差异数据在Renderer视图中可视化的显示出来。

2. 关键差异

我们看看富文本diff在这三个模块上分别有什么差异

2.1 Differ

纯文本

1. 对于一个纯文本，数据是二维结构，第一个维度是行，第二个维度便是一行中的单词或字符。
2. 通过对比字符的相同与否就可获得确定的差异。

富文本

1. 数据是树型结构，层次不确定，需要递归的对比节点、子节点。
2. 节点是个复杂对象，通常有属性、样式、内容等等，不同节点要根据展现和功能考虑不同的对比方式。

2.2 Renderer

纯文本

1. 按行渲染，每行所占高度一致。
2. 所有字符同等对待，渲染结果只包含文本内容。
3. 布局方式简单。

富文本

1. 不同节点的渲染结果有比较大的差异。
2. 渲染结果包含样式、布局，文本内容只是其中一部分。

2.3 Highlighter

纯文本

高亮索引位置即是字符在文中的位置，无需复杂计算。

富文本

高亮位置计算依赖Renderer的具体实现，需要综合考虑节点类型、渲染方式、节点层级等信息进行复杂计算。

3. 关键决策

在开始实现细节之前，通过对TipTap的调研，对几个关键技术点进行了选型和决策。

3.1 Differ

Differ算法是重中之重，Differ的输入参数数据结构会很大程度影响算法的复杂度和准确度。由于我们的内容是由TipTap这个富文本编辑器生成的，它导出的文档支持四种格式，分别是DOM、JSON、TipTap节点树以及markdown，分别评估一下它们的优缺点。

DOM

优点

1. 通用性好，所有的富文本最终最会渲染成DOM，不依赖特写的编辑器。
2. DOM有比较成熟的API，遍历、读取、操作节点方面比较方便。
3. 较低的学习成本。

缺点

1. DOM本身是一套庞大的系统，标签、属性非常繁多，想要考虑周全，会增加实现的复杂度。

JSON

TipTap把内容文档树导出为一个JSON格式的抽象语法树（AST）。

优点

1. 纯数据，不依赖渲染，没有任何副作用。
2. 具有TipTap的语义。

缺点

1. JSON缺少树的API，遍历、操作不方便，需要自己实现。

TipTap节点树

是对TipTap AST的树实现，可以理解为TipTap自己实现的虚拟DOM。

优点

1. 具有JSON的所有优点。
2. 封装了树节点操作的API。

缺点

1. 需要理解TipTap的节点API，有一定学习成本。

Markdown

优点

1. 纯文本，在diff阶段可以基于纯文本实现算法。

缺点

1. Markdown支持的标签有限，有一些格式无法转成对应的markdown标签。
2. 在Renderer和Highlighter中不能直接显示markdown，需求要求与编辑视图一样，具有排版和格式。
3. Markdown中有一些字符串是用于控制格式的，比如#、**，这些字符在渲染成富文本后并不会出现在UI上，如果这些字符发生变化，Highlighter模块需要理解哪些差异是控制格式，哪些是控制内容，在计算高亮区域时会非常复杂。

3.2 Renderer和Highlighter

Renderer即是在对比视图中如何渲染新/旧版本的内容，而Highlighter的实现很大程度依赖Renderer的实现，因此可以一起评估，这里主要考虑两个因素：

1. Renderer中渲染的内容是否与编辑视图一致
2. Highlighter能否高效、准确的定位到高亮区域

对于TipTap生成的内容，有两种常见渲染方式。

HTML

将TipTap中的内容导出为html，在Renderer中直接使用这份html进行渲染。

优点

1. 渲染原生dom，不需要额外处理。
2. 100%还原编辑时内容排版。

缺点

1. Highlighter只能用替换DOM的方式实现，而Highlighter替换DOM后，会导致原DOM树的结构发生变化，diff结果中的位置索引也可能需要重新计算，增加了Highlighter的复杂度。
2. 节点位置需要复杂的递归计算。

渲染到TipTap编辑器

为新/旧内容区域创建两个TipTap编辑器实例，将编辑视图保存的内容回显到编辑器中。

优点

1. 100%还原编辑时内容排版。
2. 可利用TipTap的NodePos对象快速获取节点位置，大大简化了diff结果的位置索引计算逻辑。[NodePos传送门]
3. 可通过Prosemirror（TipTap的底层）的Decoration机制实现高亮。（可在不更改树结构的情况下更改渲染）[Decoration传送门]

缺点

1. 需要创建两个TipTap编辑器实例，性能消耗相对较高。

综合考虑功能的完整性、复杂度以及实现成本等方面，用TipTap节点树作为Differ算法的输入，使用只读的TipTap编辑器来渲染对比视图，并用Decoration在编辑器中实现高亮。

四、技术实现

当关键决策确定后，就可以基于这几个技术点逐步实现整个diff视图功能。

Diff算法

树是一种多维的数据结构，直接设计树的diff算法有点不知从何下手，为了降低问题复杂度，我采用降维的方式来拆解问题，树 -> 仅一级节点 -> 纯文字 -> 一行文字 -> 单个字符，再用迭代的方式逐步逆向升维，最终实现完整的算法。

1. 基于逐个字符的diff

最简单的方式，对新旧字符串中相同索引位置的字符逐个比较。

上图的结果可以用下面的数据描述：

[
  { "type": "unchanged", "value": "A", "index": 0 },
  { "type": "modified", "newValue": "B", "oldValue": "X" "index": 1 }
  { "type": "added", "value": "C", "index": 2 }
]

再看一个删除的例子：

[
  { "type": "unchanged", "value": "A", "index": 0 },
  { "type": "modified", "newValue": "B", "oldValue": "X" "index": 1 }
  { "type": "removed", "value": "Y", "index": 2 }
]

问题

再看一个例子

• 新: “AXB123”
• 旧: “AB123”

如果用相同索引逐个字符diff，就会出现”X”、”B”、”1”、”2”都是修改，最后的”3”是新增。

但这显示不符合人脑的认知方式，下图更符合人的认知，把”B123”看成一个整体，新旧版本没有变化，只是新版本在”A”后面插入了一个”X”。

2. 基于LCS算法的字符diff

再看一个更复杂一点的例子

• 新：”AXB13B1”
• 旧：”AB123XB1”

人在识别两个字符串时，可以拆分为下面两步

1. 先找出所有相同的字符串模式

   1. 这里用模式是因为人是基于图形去识别，而不是逐个对比识别。比如这个例子中，人是一眼看出来”B1”这个整体同时出现在新、旧字符串中。
   2. 模式不仅仅是字符串相同，还和出现在整体中的位置有关，比如这个例子中，”B1”出现了两次，但我们会把两次”B1”识别为不同的模式，第一个”B1”前面的”X”是新增，第二个”B1”前的”X”是删除，而不会简单的把新的”XB1”旧的”XB1”看成相同的模式。

2. 在两个模式之间形成的区间内进行逐字符比对。

这样说比较抽象，结合下图，也就是说字符的比对并不是以绝对位置索引来比对的，而是以相同模式的位置为基准点，相同偏移位置的两个字符来比对。

那算法的关键就是找出相同模式的字符串，熟悉算法的同学可能已经看出来了，这就是典型的最长公共子序列（Longest Common Subsequence）算法，简称LCS。简单来说，就是找出多个序列中共有的最长子序列（不要求连续）。关于LCS算法的详细介绍，可参考下面两篇文章。

• LCS (from wiki)
• 动态规划之LCS

通过LCS算法+偏移索引，我们可以完美实现字符级别的diff。

3. 基于LCS算法的段落diff

满足了字符级别的diff，下一步就要把字符升成行或段落级别的diff。

先看一个例子 新版本

我是标题

我是新插入的段落。

我是原本就存在的段落。

旧版本

我是标题

我是原本就存在的段落。

当我们把每段看成一个整体，就可以用LCS算法计算出段落级别的diff。

问题

再看下面的例子

新版本

A’ -> 我是标题1

B -> 我是新插入的段落。

C’ -> 我是原本就存在的升级段落。

旧版本

A -> 我是标题

C -> 我是原本就存在的旧段落。

我对旧版本段落A和C中的部分内容做了微调，把段落看成整体的做法就是将A和A'识别为完全不同的节点，也就是LCS的长度为0，diff结果如下图：

这显然也是不符合人的认知的，虽然A和A'，C和C'不是完全相同，人脑依旧会把它们看作“相同的”段落，它们的LCS仍然是AC。

4. 引入相似度的LCS段落diff

因此在LCS算法中对段落做比对时，只要相似就可以认为是相同的段落，这里核心问题就是两段文字是相似度算法。

查了GPT，有很多算法，我就不全部列出来了，这里我复用了基于子符的LCS算法。简单来说，就是取两个段落中的LCS，然后算出这个LCS长度与整个段落字符长度的占比，超过一个阈值就认为是相似的。具体到上面的例子A和A'的最长公共子串是”我是标题”，计算出相似度为4 / 5 = 0.8，如果设置阈值为0.7，就可以认为是相同段落。

问题

再看两个例子

例子一

新版本

我是

旧版本

你是

相似度为1 / 2 = 0.5

例子二

新版本

我曾经喝过海水

旧版本

曾经沧海难为水

相似度为4 / 7 = 0.57

例子一比例子二的相似度低，但我们会认为例子一是相似的内容，只是将”你”改成了”我”，而例子二是完全不同的两句话。

5. 加权相似度

上面的例子说明不能用单一的阈值来判断，因为语义有连续性，当文字较多时，同样比例的LCS对整体语义的影响会降低，而文字较少时则反之，因此文字越多就要求阈值越高，我们可以引入加权的概念，随着文本长度的增加，对阈值乘以一个系数，要求更高的相似度。

问题

基于相似度的算法，虽然能识别出”相似的段落”，这样就能准确标识出非相似段落的增加或删除。但带来的问题，按之前的LCS算法，相同的段落会跳过对比，这样就无法准确标识到相似段落中的差异细节。

6. 结合段落与字符级别比对

这里可以对算法做个优化，非相似段落在上一步已经可以准确的识别到了，只需要在相似段落内部，再做一次字符级别的LCS，就可以精确到段落内部的字符差异。

7. 基于TipTapNode的LCS

在文章开始说过，我们要实现的是基于树结构的富文本diff，在之前的步骤一直都是基于纯文本，只需要对前面的步骤升维，就可以快速让算法适配TipTapNode。

1. 在第3步时，我们把段落整体看作一个LCS的节点，这里用同样的方式，把TipTapNode作为LCS的节点，并重新实现判断TipTapNode是否完全相同、相似的方法，让LCS算法能够对比TipTapNode。
2. 递归对每个子节点进行第3步，直到遇到纯文本节点。
3. 对纯文本节点执行第6步，做字符级别的diff。

经过上面7步迭代，已经可以比较精确的计算出两个TipTapNode树的差异，计算的结果用这样数据结构表示

interface DiffChange {
  /** 变化类型 */
  type: 'added' | 'removed' | 'modified';
  /** 节点索引路径，比如[0, 1]表示索引为0的节点的索引为1的子节点 */
  path: number[];
  /** 新版本中的对应node */
  newNode?: Node;
  /** 旧版本中的对应node */
  oldNode?: Node;
}
type DiffChanges = DiffChange[];

Highlighter

Highlighter的逻辑比较简单，拿到Differ计算出的DiffChanges结果，通过节点与路径信息，计算出TipTap的NodePos，再通过位置信息创建Decoration，TipTap就可以自动在对应位置创建高亮装饰器。

最终效果

对比某商业化的Diff产品，我们的算法可以做到更细颗粒度的对比，并且能够高亮出仅格式发生变化的内容。

超级合作者 — AI

实现这个Diff视图，所有的代码都是由AI编写，但AI编程并不是想像的那样，告诉AI一句话或一个指令，就能生成完整的功能。

不正确的使用姿势

起初，我只是告诉AI实现一个基于TipTap的富文本差异对比功能，它用了不到1分钟生成了核心逻辑模块和一个漂亮的调试demo页面，对初始数据的对比结果也是符合预期的，我心想这下稳了。

但当我满怀希望的修改了下初始数据，噩梦开始了。

1. 在后面新加一段 ❌
2. 在前面新加一段 ❌
3. 修改段落中的部分内容 ❌
4. 修改子节点中的内容 ❌
5. ……

每出现一个问题，我就告诉AI这里有什么问题，它每次都能在30秒内修复好，但整个程序就像有打不完的补丁，修完一个又有几个冒出来，后来甚至出现了下面的代码，是的！它为了让结果符合预期，开始在代码里hardcode。我也由满怀希望到渐渐绝望，想着还是放弃AI编程，老老实实自己来写。

正确的使用姿势

我暂停了让AI无休止的打补丁，花了半天时间review了AI写的代码，发现它实现了很多零散的功能，每一个都设计良好、代码规范、接口清晰，但感觉缺少一个系统层面的骨架，把这些零件有效的组织起来。我开始反思，如果从零开始，我会怎么实现这个功能，最后决定用由易到难，逐步迭代的策略，把AI当成另一个我，用合作的方式去实现这个功能。

1. 只实现第一层节点的diff，只要节点中的文字内容不同就认为不同。
2. 引入LCS算法，把节点整体当成LCS算法的单元。
3. 引入相似度，让LCS算法支持找出相似节点。
4. 引入加权相似度，让相似度阈值随内容长度变化。
5. 对子节点递归进行比对。
6. 对文本节点中的内容使用字符比对算法。
7. 增加识别仅格式变化的类型。
8. 生成复杂结构的文档，用于测试整个功能。

这8步是8次迭代，我确认每个迭代的功能符合预期后，会告诉AI当前的算法是正确的，接下来基于目前的算法做进一步优化，再告诉它下个迭代要实现的功能。生产过程由之前告诉AI一个大而模糊的功能，再不断打补丁修复问题；变成了一个渐进进化的过程，AI也因每一小步任务变的清晰，变的更加高效有序，并在每个迭代从我这里得到反馈，强化了正确的功能，减少了增量功能会影响已有功能的情况。

反思

AI和人应该是一种合作关系，有各自擅长处理的领域，很多问题的难点不是如何解决，而是问题不够清晰。迭代便是一种通过反馈让问题变的清晰的过程，AI的加入，可以让迭代的周期缩短到分钟级别，互相为对方提供反馈，最终使问题变的清晰并得以实现。

AI的优势

• AI在实现具体的功能时，非常高效且准确度较高，基本都能在分钟级别完成。
• 精通所有算法，各种API的调用，节省学习成本。
• 拥有海量的知识，可以参考信息，辅助分析。
• 可以快速构造各种测试数据，case覆盖率高（比如上面diff的测试文本）。

但AI要解决的是人的问题，因此只有人能反馈问题有没有解决，解决的程度如何，而能不能将模糊的问题看清、看透，才是人的核心优势。

我所做的事

虽然这个项目所有的代码是AI生成的，但我和AI其实也有分工

1. 前期调研了TipTap编辑器，了解TipTapNode的基本API能力和Decoration机制。
2. 通过学习和之前的经验，具备了Diff视图的三大核心模块的知识。
3. 结合需求和TipTap技术特点，在编码前做了核心决策。
4. 知道LCS算法的基础知识和其应用场景。
5. 有一定的抽象思维，能够将树简化为Node，将Node简化为段落，将段落简化为字符，为后面的迭代拆分做了铺垫。
6. 有迭代思维，知道如何将一个简单实现通过迭代的方式渐进升级。
7. 可以通过阅读AI的代码，间接学习AI的思考方式，最终改变与AI的协作方式。

过去程序员信奉

Talk is cheap, show me the code.

AI时代

Code is cheap, show me the talk.

但我认为未来也许

Talk and code are cheap, show me the thinking.