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

Graphtage 是一个命令行实用程序及底层库，用于语义比较和合并树状结构，例如 JSON、JSON5、XML、HTML、YAML 和 TOML 文件。其名称是“graph”（图）和“graftage”（嫁接，即园艺中将两棵树连接成一棵的实践）的组合词。继续阅读了解：

Graphtage 的不同之处和优势
我们开发它的原因
它的工作原理
作为库使用的指南

各种优势

Graphtage 让您快速轻松地查看两个文件之间的差异，但它不是像 diff 那样的标准面向行的比较工具。Graphtage 具有语义感知能力，可以跨无序结构（如 JSON 字典和 XML 元素标签）映射差异。您甚至可以比较两种不同格式的文件！当与我们的 PolyFile 工具结合使用时，您可以对任意文件格式进行语义差异比较。

树状文件格式作为传输和存储数据的手段正变得越来越常见。如果您曾经处理过复杂的 REST API、解析过模板生成的网页输出，或编写过配置文件（随后需要找出哪个具体更改使事情正常工作），您可能已经对当前开源语义差异工具的现状感到失望。

Graphtage 解决了这些问题。它现已可用。要安装该实用程序，请运行：

1

pip3 install graphtage

在此处获取源代码。

现有差异工具的不足

树中的有序节点（例如 JSON 列表）以及特别是映射（例如 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"]
}

现有工具有效地规范化 JSON（例如，按键对字典元素排序并将列表格式化为每行一个项目），然后执行传统的 diff。我们不需要花哨的工具！以下是它们实际所做的：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


$ cat original.json | jq -M --sort-keys > original.canonical.json
$ cat modified.json | jq -M --sort-keys > modified.canonical.json
$ diff -u original.canonical.json modified.canonical.json
    {
    -  "bar": "testing",
       "foo": [
    -    1,
         2,
         3,
    -    4
    -  ]
    +    4,
    +    5
    +  ],
    +  "woo": [
    +    "foobar"
    +  ],
    +  "zab": "testing"
    }

这个结果不太有用，特别是当输入文件很大时。问题是更改字典键会破坏差异：由于“bar”被更改为“zab”，规范表示发生了变化，传统差异算法将它们视为单独的编辑（差异的第 2 行和第 15 行）。

相比之下，以下是 Graphtage 对同一对文件的输出：

为什么以前没有做到这一点？

一般来说，将一个图最优映射到另一个图无法在多项式时间内执行，因此对于任何有用大小的图来说都是不可行的（除非 P=NP）。即使对于像 DAG 这样的受限图类也是如此。然而，树和森林是特殊情况，可以在多项式时间内映射，并对可能的编辑类型施加合理的约束。Graphtage 利用了这一点。

它是如何知道的？

Graphtage 的差异算法在中间表示上操作，而不是在原始文件格式的数据结构上操作。这使得 Graphtage 拥有可以处理任何输入文件类型的通用比较算法。因此，要添加对新文件类型的支持，只需将其“提升”到中间表示即可。同样，只需一次实现对新编辑类型的支持，它将立即可用于所有支持的文件类型。使用中间表示还有一个额外的好处，即允许跨格式比较和格式转换：Graphtage 可以愉快地将 JSON 文件与 YAML 文件进行差异比较，并以 TOML 语法格式化差异输出。

Graphtage 使用 Levenshtein 距离度量的“在线”“构造性”实现来匹配有序序列（如列表），类似于 Wagner–Fischer 算法。该算法从一个无界映射开始，并迭代改进它，直到边界收敛，此时发现最优编辑序列。

通过解决从源字典中的键/值对到目标字典中的键/值对的完全二分图上的最小权重匹配问题来匹配字典。

Graphtage 是一个命令行实用程序，但它也可以轻松用作库。可以直接从 Python 与 Graphtage 交互，并扩展它以支持新的文件格式和编辑类型。

Graphtage 的下一步计划

我们认为 Graphtage 非常巧妙。您还可以将 Graphtage 与我们的 PolyFile 工具结合使用，以语义差异比较任意文件格式，即使它们本身不是基于树的。试试看，并告诉我们您如何使用它。

我们还计划扩展 Graphtage 以处理抽象语法树，这将使您的源代码差异能够告诉您哪些变量被更改以及代码块是否被重新排序等信息。如果您对新功能有类似巧妙的想法，请与我们分享！

注意：此工具的部分开发由国防高级研究计划局（DARPA）在 SafeDocs 项目上资助。所表达的观点、意见和/或发现是作者的观点，不应解释为代表国防部或美国政府的官方观点或政策。

如果您喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News

页面内容各种优势现有差异工具的不足为什么以前没有做到这一点？它是如何知道的？ Graphtage 的下一步计划最近的帖子构建安全消息传递很难：对 Bitchat 安全辩论的细致看法使用 Deptective 调查您的依赖项系好安全带，Buttercup，AIxCC 的评分回合正在进行中！使您的智能合约超越私钥风险 Go 解析器中意外的安全陷阱 © 2025 Trail of Bits。使用 Hugo 和 Mainroad 主题生成。

Graphtage：革命性的语义差异比较工具，轻松处理JSON、XML等结构化数据

Graphtage是一款创新的命令行工具和库，专为语义比较和合并树状结构文件（如JSON、XML、HTML等）设计。它解决了传统diff工具在处理无序结构时的不足，支持跨格式比较，甚至能与PolyFile结合分析任意文件格式。