jsdiff

定义

jsdiff 是一个用 JavaScript 编写的文本差异比较实现，其名称来自项目仓库名 kpdecker/jsdiff，而在 npm 上的包名则是 diff^[3]。它接收一段旧文本和一段新文本，计算出把前者变为后者所需的最小插入与删除操作集合，并以「变更对象」数组的形式返回结果。

该库的自述文件把它定位为「一种 JavaScript 文本差异实现」，并说明其算法依据是 Myers 在 1986 年发表的论文^[1]。除基本的文本比较外，它还提供生成、解析和套用补丁的接口，因此既能用于界面上的差异高亮，也能用于程序化的文件更新^[4]。

原理

jsdiff 的计算过程分为三步：先把新旧两段文本各自切分成「词元」（token）数组，再找出把第一组词元变换成第二组所需的最少单次插入与删除，最后把该变换表示为按文本顺序排列的变更对象数组。什么算一个词元取决于所选函数，例如按字符比较时每个字符是一个词元，按行比较时每一行是一个词元。

词元是否「相等」由比较方式决定，默认使用严格相等运算，部分函数提供可配置的等价判断，例如忽略大小写时大小写不同的字符被视为相同。底层算法来自 Myers 的论文，该论文把求最长公共子序列与求最短编辑脚本这两个问题归结为在编辑图中寻找最短路径，并给出时间复杂度为 O(ND) 的算法，其中 N 是两序列长度之和，D 是最小编辑脚本的大小^[5]。该算法在两段文本较为相似、差异较小时表现良好^[5]。

jsdiff 与论文所描述的原算法存在若干不影响结果、只影响性能的差异。它用每条对角线上的变更对象链表来记录已算出的差异，而不是论文第 8 页所设想的、保存各对角线最远可达 D 路径的数组；同时它会跳过那些最远可达路径会越出编辑图边缘的对角线，在新文本只是接在旧文本末尾或在末尾截断的情况下，可把时间开销由平方级降低到线性级。

返回的变更对象包含 value、added、removed 等字段：value 是该变更所覆盖文本的内容，added 为真表示这段内容被插入新文本，removed 为真表示它从旧文本中删除，两个标记都不成立时代表新旧文本共有的部分^[1]。较新版本的变更对象还提供 count 字段，表示该对象所包含的词元数量，例如按字符比较时即为字符个数^[3]。

发展历程

jsdiff 的早期版本版权声明覆盖 2009 年至 2011 年，作者署名为 Kevin Decker，许可证为 BSD 许可^[6]。在早期版本中，库只提供按字符、单词、行和 CSS 词元比较的函数，以及生成统一差异格式补丁的 createPatch 和套用补丁的 applyPatch 等接口^[7]。

随着版本演进，库陆续补充了更多比较函数，包括区分空白的按词比较、忽略行首行尾空白的按行比较、按句子比较、JSON 对象比较和数组比较，并增加了解析补丁、反向补丁等能力^[1]。安装方式也从早期的 npm 与 git 克隆，扩展到通过 bower 安装以及直接在网页中引入脚本文件^[1]。

据 npm 包页面记录，diff 包已发布 9.0.0 等在内的多个大版本，仓库由 kpdecker/jsdiff 维护，最新发布的版本号已到 9 系列^[8]。该包在生态中的使用规模较大，第三方统计显示其被依赖的软件仓库数量约 155 万个，依赖包约 4153 个^[2]。自版本 8 起，jsdiff 自带类型定义，使用者不再需要单独依赖 @types/diff 包。

应用

最直接的用法是在页面上显示文本差异。官方示例调用按字符比较的函数取得变更对象，再根据 added 与 removed 标记为不同部分赋予不同颜色，从而把增删内容渲染出来^[1]。

在补丁处理方面，较新版本提供了与 Unix 命令行工具相当的能力：用 createTwoFilesPatch 生成补丁，用 applyPatch 把补丁套用到指定文件，用 applyPatches 处理包含多个文件的补丁，后者的用法与命令行中直接把补丁输入给 patch 命令相近。这些接口使其可以嵌入版本控制、变更审阅一类的工具中。

该库也被其他库作为基础组件使用。例如 diff-text 这一网页组件在说明中写明其使用 kpdecker/jsdiff 来渲染单词、字符、行、句子、CSS、JSON 或数组之间的差异，并把选项直接透传给 jsdiff^[9]。

局限

jsdiff 的比较结果依赖词元的切分方式与相等判断，本身并不理解语义。官方文档指出，若需要语义相关的比较，例如对代码做语义差异分析，需要使用者自行借助某门语言的解析器切分，再把词元数组交给数组比较函数处理。

在处理体量大且差异极多的文本时，该算法的时间开销会显著上升，因为 O(ND) 中的 D 正是编辑脚本的大小^[5]。为此库提供了 maxEditLength 与 timeout 两项限制：前者设定允许考虑的最大编辑距离，超出即放弃；后者设定毫秒数，到时就中止算法，两种情况都返回 undefined 而不返回差异结果^[3]。这两个选项适用于返回变更对象的函数以及 structuredPatch 等部分补丁生成函数，并不适用于所有补丁生成接口。

套用补丁并非总能成功。若补丁中的某些片段无法与源文本对应上，applyPatch 会返回假值而不是修补后的文本，使用者需要自行处理失败情形。此外，环境兼容性随版本变化：早期版本虽支持所有 ES3 环境，但在 IE8 及更早浏览器上，按词比较等算法可能因 split 操作不支持捕获组而失败^[4]；版本 8 支持 ES5 环境，而从版本 9 起，各次发布以当时最新的 Node 长期支持版本以及至少已发布 30 个月的浏览器核心版本为支持基准^[10]。

参见

• Myers 差异算法 —— jsdiff 所采用的底层文本差异算法，由 Eugene W. Myers 于 1986 年提出。

• npm —— jsdiff 以 diff 为包名发布的 JavaScript 包管理平台。

• JavaScript —— jsdiff 所使用的编程语言。

• 统一差异格式 —— jsdiff 生成与套用补丁时采用的文本格式。

• 最长公共子序列 —— 与最短编辑脚本互为对偶、与差异算法密切相关的经典问题。

• 版本控制 —— jsdiff 的典型应用场景之一，用于呈现文件版本之间的变化。