diff 在计算什么:最长公共子序列(LCS)
找出两段文本的差异,就是回答“把原文改成修改稿,最少要删掉哪些行、插入哪些行”。这和求两个列表的最长公共子序列(LCS,Longest Common Subsequence)是同一个问题:在保持顺序的前提下,两边都能取出的最长序列。 属于 LCS 的内容是“没有变化的部分”,其余的内容,只在原文中出现就是删除,只在修改稿中出现就是新增。 因此编辑次数(删除 + 新增)等于 原文长度 + 修改稿长度 − 2 × LCS 长度。
本工具采用经典的动态规划:先填好 LCS 长度表,再从表中回溯读出编辑操作。时间和内存都与两个长度的乘积成正比, 所以先去掉两段文本开头和结尾相同的部分,只对中间不同的区段建表;若乘积仍然过大,就给出提示而不是让页面卡死(上限见下文)。 Git 默认使用的 diff 基于 Eugene Myers 在 1986 年发表的另一种算法,两个版本越相似运行越快。两者都以最小编辑为目标, 但存在多个同样短的解时,选择的解可能不同,所以删除行和新增行的排布可能略有差别。
可以手工跟着算的例子
下面是算法讲解中的经典字符串 ABCABBA(原文)和 CBABAC(修改稿)。每个格子表示“从该位置到末尾的 LCS 长度”,左上角的格子就是整体的 LCS 长度。 这些数字是生成本页时用和工具相同的递推公式算出来的。
| 原文＼修改稿 | C | B | A | B | A | C | 末尾 |
|---|---|---|---|---|---|---|---|
| A | 4 | 4 | 3 | 2 | 2 | 1 | 0 |
| B | 4 | 4 | 3 | 2 | 1 | 1 | 0 |
| C | 4 | 3 | 3 | 2 | 1 | 1 | 0 |
| A | 3 | 3 | 3 | 2 | 1 | 0 | 0 |
| B | 3 | 3 | 2 | 2 | 1 | 0 | 0 |
| B | 2 | 2 | 2 | 2 | 1 | 0 | 0 |
| A | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 末尾 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
结果:LCS 长度为 4。原文 7 项、修改稿 6 项,所以最少编辑数为 7 + 6 − 2×4 = 5。 换成按行的例子更直观:原文为“苹果 / 香蕉 / 葡萄”,修改稿为“苹果 / 草莓 / 葡萄 / 橙子”,LCS 是“苹果、葡萄”,长度 2, 编辑数为 3 + 4 − 2×2 = 3,即删除“香蕉”1 行,新增“草莓”和“橙子”2 行。把这几行直接放进上面的输入框,就能看到同样的结果。
按行、按词、按字符有什么区别
按行适合以行为意义单位的文本,如源代码、配置文件、清单和合同条款。速度快、结果简洁,但行内哪怕只改了一个词,整行也会显示为删除加新增。 为此,当一条删除行和一条新增行相邻时,工具会把这两行再按词比较一次,把真正改动的词着色标出。按词适合写成长长一行的报告、文章初稿, 用来看哪个短语被改了。按字符适合核对错别字、数字差一位,以及账号、网址这类一个字符出错就出问题的内容;但文本很长时处理会明显变慢, 碰巧相同的字符也会让结果碎成难读的小片段,请只用于较短的片段。需要注意:本工具“按词”是以空白分隔的,中文句子里没有空格, 所以一段不含空格的中文会被当作一个词,整段只要有一个字不同就会整体显示为改动。要细看中文句子内部的差异,请用“按字符”。
| 单位 | 适合的文本 | 优点 | 注意 |
|---|---|---|---|
| 行 | 代码、配置、清单、条款 | 快,结果短 | 改一个词整行也会显示改动(行内高亮可弥补) |
| 词 | 英文长句、报告 | 能看到改动的短语 | 以空白分隔,不含空格的中文整句算一个词 |
| 字符 | 数字、姓名、网址核对 | 连一个字符的差别也能发现 | 长文本慢,结果容易碎 |
空白和大小写选项什么时候用
内容相同,只是缩进变了,或行尾多了空格,导致每一行都显示为“不同”时,选择“忽略首尾空白”,只会留下真正的改动。 从文字处理软件复制来的文本常有连续两个空格,这时选“连续空白合并为一个”更合适。“忽略大小写”适用于只改了英文大小写的普通文章, 但在 userId 与 userID 是不同名字的代码对比中请关闭。这些选项只影响比较过程,屏幕上仍显示原文。 Windows(CRLF)与 Unix(LF)换行符不同会让每一行都看起来不一样,本工具在输入时就统一了换行,避免了这个问题。
如何阅读结果、用在哪里
绿色表示只在修改稿中出现(新增),红色表示只在原文中出现(删除)。比较合同或服务条款的修订前后,可以先按行通览, 再把改动过的行用按词方式复查。代码和配置文件建议按行并忽略空白,只看有意义的改动。要对比 JSON,可先用JSON 格式化把两边的缩进和排版统一,无谓的差异就会消失。改写完自荐信或论文后, 可以用字数统计查看篇幅变化。看起来相同却被判为不同时,请切换到按字符, 常见原因是全角空格、零宽字符这类看不见的字符,或同一个字符以不同编码形式保存。若发现规律后想批量替换名称, 可先在正则表达式测试器里试验表达式。
隐私、上限与不适用的情况
粘贴的内容全部在浏览器内处理,不会上传,也不会保存。实际的限制是内存:LCS 表每格存一个 32 位数字,去掉开头和结尾相同部分后, 如果需要比较的区段格子数超过 25,000,000,工具就不再建表而是显示提示。这大约相当于 100 MB,每一侧约 5,000 项。按行时是几千行, 按字符时则是几千个字符,所以长文档请改用按行或拆分后分别比较。
diff 不理解“移动”:把一段文字剪切后粘贴到别处,会显示为一处删除、另一处新增。工具只对比纯文本,不能发现 Word 或 PDF 中的格式、表格、图片的变化。 行内高亮是把相邻的删除行与新增行按顺序配对比较,如果行的顺序被大幅打乱,配对可能不准确。不支持三方合并和版本管理, 团队协作的代码请使用 Git 之类的版本控制工具。具有法律效力的文件,最终核对必须由人对照原件完成。
常见问题
一行里只改了一个词,为什么整行都显示红/绿?
这是按行对比的基本行为。删除行和新增行配对后,其中真正改动的词会用更深的颜色标出,请看颜色更深的部分。如果只想看短语,请把对比单位改成按词。
“忽略首尾空白”和“连续空白合并为一个”有什么区别?
前者只去掉每个比较项两端的空白;后者还会把项内部连续的空格或制表符当作一个空格,所以连按两次空格造成的差异也会被忽略。
内容看起来一样,为什么显示不同?
常见原因有看不见的空白(全角空格、零宽字符)、行尾空格、Unicode 规范化形式不同,以及大小写差异。可以试着切换选项,并用按字符方式找出具体不同的字符。
能检测出被移动的行吗?
不能。位置改变的行会显示为一处删除、另一处新增,这是基于 LCS 的 diff 的普遍特点。
结果会和 Git 的 diff 不一样吗?
可能略有不同。存在多种同样少的编辑方案时,不同算法选择的路径不同,即使编辑数相同,删除行和新增行的位置也可能稍有差别。Git 使用 Myers 系列算法,还可选择其他方式。
“复制差异”按什么格式复制?
按行时,未改动的行前加两个空格,删除行前加“- ”,新增行前加“+ ”。按词和按字符时,删除内容用 [-…-] 包起来,新增内容用 [+…+] 包起来。