Graphtage：新一代语义差异分析工具

Graphtage 是一个命令行工具及底层库，专为语义化比较和合并树形结构文件而设计，支持 JSON、JSON5、XML、HTML、YAML 和 TOML 等多种格式。其名称结合了“图”（graph）和“嫁接术”（graftage）的含义，寓意将两棵树合并为一棵。

现有差异工具的不足

传统差异工具（如 diff）在处理无序结构（如 JSON 字典）时存在局限。它们通常通过规范化（如按键排序字典元素）后进行行级对比，导致关键变更被误判为多个独立编辑。例如：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


# original.json
{
    "foo": [1, 2, 3, 4],
    "bar": "testing"
}

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

传统工具会错误地将 "bar" 到 "zab" 的键名变更识别为删除和添加操作，而非单一语义编辑。

技术实现原理

多项式时间算法突破

虽然图到图的优化映射通常无法在多项式时间内完成，但 Graphtage 针对树和森林结构实现了多项式时间映射算法，通过合理约束编辑类型实现高效计算。

中间表示层架构

Graphtage 在中间表示层而非原始文件数据结构上运行差异算法，这使得：

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

核心算法细节

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

应用扩展能力

Graphtage 既可作为命令行工具使用，也可作为 Python 库直接集成和扩展。未来计划包括：

与 PolyFile 工具结合，支持任意文件格式的语义差异分析
扩展至抽象语法树（AST）分析，实现源代码变量变更和代码块重排检测

开发背景

该工具部分由美国国防高级研究计划局（DARPA）SafeDocs 项目资助开发，观点和发现仅代表作者立场。

通过 pip3 install graphtage 安装工具，源代码已开放提供。

语义差异分析新利器：Graphtage 技术解析

Graphtage是一款创新的语义差异分析工具，支持JSON、XML、YAML等多种树形结构文件的智能对比与合并。它突破传统行级对比限制，采用中间表示层和多项式时间算法，实现跨格式语义映射和最小化编辑距离计算。