Graphtage：新型语义差异比较工具

Graphtage 是一个命令行工具及底层库，用于语义化比较和合并树形结构文件，如 JSON、JSON5、XML、HTML、YAML 和 TOML。其名称结合了“graph”（图）和“graftage”（园艺中的嫁接技术），寓意将两棵树合并为一。本文将介绍：

Graphtage 的独特优势
开发动机
工作原理
作为库的使用方法

现有差异工具的不足

树形结构中的有序节点（如 JSON 列表）和映射（如 JSON 字典）是传统工具的难点。大多数现有差异算法假设结构有序，导致输出结果不直观。例如：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


# original.json
{
    "foo": [1, 2, 3, 4],
    "bar": "testing"
}
# modified.json
{
    "foo": [2, 3, 4, 5],
    "zab": "testing",
    "woo": ["foobar"]
}

传统工具通过规范化（如按键排序字典、逐行格式化列表）后执行标准差异比较，结果混乱且难以理解。Graphtage 通过语义感知能力，跨无序结构映射差异，甚至支持不同格式文件的比较。

技术实现原理

多项式时间映射优化

一般图到图的优化映射无法在多项式时间内完成，但树和森林结构在合理编辑约束下可实现多项式时间映射。Graphtage 利用这一特性实现高效处理。

中间表示层

Graphtage 的差异算法基于中间表示而非原始文件格式的数据结构，这使得：

通用比较算法支持任意输入文件类型
添加新文件类型只需将其“提升”到中间表示
新编辑类型实现一次即可应用于所有支持格式
支持跨格式比较和输出格式转换（如 JSON 与 YAML 差异以 TOML 语法输出）

算法细节

列表匹配：采用 Levenshtein 距离度量的“在线”构造性实现，类似 Wagner–Fischer 算法，通过迭代优化无界映射直至收敛，发现最优编辑序列。
字典匹配：通过求解源字典与目标字典键值对完全二分图的最小权重匹配问题实现。

库集成与扩展

Graphtage 不仅可作为命令行工具，还能作为 Python 库直接集成和扩展，支持新文件格式和编辑类型。

未来计划

Graphtage 将与 PolyFile 工具结合，支持任意文件格式的语义差异比较，即使非树形结构。下一步计划扩展至抽象语法树（AST），实现源代码变量变更和代码块重排等高级差异分析。

注：此工具部分由美国国防高级研究计划局（DARPA）SafeDocs 项目资助开发。观点仅代表作者，不代表美国国防部或美国政府立场。

Graphtage：革命性的语义差异比较工具，轻松处理JSON、XML等树形结构文件

Graphtage是一款创新的命令行工具和库，专为语义比较和合并JSON、XML、HTML等树形结构文件而设计。它突破传统行级差异工具限制，支持无序结构和跨格式比较，采用多项式时间算法优化映射效率。