关于文本对比方案的实现与思考

在原创开发作者相关功能的时候，遇到了一个文本对比的功能，需要向作者展示章节内容修改前后的差异：作者会对章节内容进行修改，后台审核过程中，也会对章节内容做一定的调整，这些调整的细节，需要告知作者。

实现一个 的功能，这需要解决两个问题，核心问题是如何寻找出两段给定文本的差异，次要问题是如何保存数据。

首先，如何找出两段文本的差异？ 当时调研后发现有个现成的 扩展，可以实现这一功能，但无法很好的解决问题，会有以下不足：

• 扩展依赖底层库 ，默认是按行对比。我们对小说章节文本内容进行存储时，会带上 标签来进行分段，而不是系统换行符，那么整个章节的 内容都会被视为一行，对比结果会退化为两段文本是否一致，无法体现修改的细节。而修改分段方式会涉及到业务的调整，引入更多的不确定性。
• 扩展非官方扩展，以扩展的方式使用，需要自己编译安装，影响运行环境的标准化，引入额外的不确定性。

因此决定这部分自己来实现。

其次，关于如何保存数据？ 方案一：保存每次修改前后的完整内容。优势在于处理起来方便，对原有流程的入侵比较少；缺点在于冗余内容比较多，每次修改都要保存一个完整的历史备份， 而且每次展示差异，都需要重新执行一次对比。

方案二：在每次修改时找出修改前后的差异细节，仅对差异的细节与最后一次的内容做保存，那么章节的历史版本内容都可以根据最新内容加上差异的细节反推出来。 优势在于冗余数据少。但有个比较明显的缺陷，需要保存连续的差异记录，如果中间某次差异记录的丢失，会导致往前所有的记录无效。

我们选择的是方案二。

最长公共子序列算法 是实现文本对比的手段之一，他的原理就是找出两段给定文本的公共子序列中长度最长的序列，也就是相同的部分， 那么剩下的就是两段文本间的不同部分。想要找出这个最长的序列，可以通过动态规划的方法，如果把要对比的两串文本表示为，他们的最长公共子序列为 ：

则可以将这个过程表示为 ，假设对于各有一个子串,他们的公共子序列表示为

那么当 各自再增加一个字符的长度时， 如何取值呢？

• 如果 ，说明 和 相比，新增了一个相同的字符，所以
• 如果 ，那么 就是 和 中比较大的那一个， 即

上面的描述，就是通过动态规划解决这个题时，所要找出的状态转移方程，用代码表示，就是：

其实，怀着优化性能的心态，我也尝试过自己来解决这个问题：既然对过长的内容做 性能不佳，那我们试着去控制比较的规模不就可以了？

• 这样获得的结果，"正确性"会低上很多，因为搜索的过程中，相同区域可能会命中两个，而我们没有额外的信息，来支撑我们判断哪个更正确。
• 如何确定这个"固定长度"？这个固定长度取太长则会降低命中率，达不到缩小规模的目的；取得太短，命中率变高，取到最优解的概率低，降低准确率。

• https://github.com/google/diff-match-patch
• https://github.com/sergi/go-diff

较长字符串的半长

• 如果两段文本存在一个公共字串，且这个公共字串的长度，大于较长字符的一半，那么这个子串必然是唯一的，他一定是的"最长公共子序列"的一部分。
• 一段文本的半长，必然包含四等分后的第二段或第三段

将这推导反过来，我们优先检查片段2、3是否在另一个文本中存在，如果不是，那么就不存在这样的半长子串；如果是，则需要进一步检查这两个 片段中，加上他们前后相同的部分后，是否超过一半。这样就可以快速且准确的找到最长公共子序列的大部分。而剩下的部分，也可以通过循环这个过程来找全，而且运算规模是不断缩小的。这就是google关于"最长公共子序列"优化的实现。

在解决两段文本进行对比的问题后，我们来着手解决第二个问题，如何进行数据的保存。如果是保存修改前后的完整内容，仅仅需要注意区分各个版本内容的顺序即可。 如果是只保存差异部分，那么还需要定义一下具体需要保存的内容与格式。

当进行完对比后，可以将对比结果分为三种类型的文本：

• 存在于两段文本的相同部分，标记为
• 仅存在于修改前的文本，标记为
• 仅存在于修改后的文本，标记为

由于我们本来就需要保存修改后的完整内容，而标记为 的部分，肯定存在，所以这部分的数据属于重复内容，不需要额外保存。 此外，标记为 add 的文本也存在于修改后的文本中，但依然需要特殊标记；最后，标记为 的文本，在修改后的文本中已经不存在了， 所以必须保存。我们将修改前后的内容分别记录为 ， 之间的差异记录为 ，可以表示为：

第一个公式表示的是计算出 的过程；第二个公式表示的是通过 和 ，推导出 内容的过程，在进行这个计算的过程中，除了 已知的内容 之外，还需要知道 中的 片段，在 中的位置； 第三个公式表示的是通过 和 ，反推出 内容的过程， 同样，这个过程需要知道 中的 片段，在 中的位置信息，所以 的数据结构可以记录如下：

有了这些信息之后，就可以完成反推还原的过程，但仍然需要一个校验位来确保数据的正确性，用于验证 是否真的是 与 的差异。 由于我们的方案是保存最新版本的内容，也就是 ， 因此在使用中，首先需要考虑用到的是公式3 ， 需要验证这个步骤的正确性， 就需要在 与 之间建立联系，比如将 的 值随 一起保存，在执行公式3前，先比较 的 值与保存的是否一致，如果不一致，说明 与 至少有一个是错误的， 也就不能得到正确的 ，那么最终diff的结构就是：

在讨论数据保存方案时，通过以 数据保存为主，历史版本为辅的方案可能更优秀。保存 数据的主要优势在于内容小，节省存储。然而如果出现换章的情况，整个 章节的内容都被替换掉了，那么 实际上保存的是修改前后的内容和。在这种情况下，仅保存历史版本反而会更节省存储。