图形：一种新的语义区分工具

Graphage是一个命令行实用程序和基础库，用于语义上比较和合并树状结构，如JSON、JSON5、XML、HTML、YAML和TOML文件。它的名字是“图形”和“嫁接”的混合词(即，将两棵树连接在一起以使它们生长为一棵树的园艺实践)。请继续阅读以下内容：

Graphage使您可以快速、轻松地看到两个文件之间的不同之处，但它不是像Diff那样的面向行的标准比较工具。Graphage是语义感知的，这允许它在无序结构(如JSON字典和XML元素标记)之间映射差异。您甚至可以比较两种不同格式的文件！当与我们的PolyFile工具配合使用时，您可以在语义上区分任意文件格式。

树状文件格式作为传输和存储数据的手段正变得越来越普遍。如果您曾经争论过粗糙的REST API，理清了模板生成的网页的输出，或者虚构了一个配置文件(随后需要找出哪个特定的更改才是让事情运行的那个)，那么您可能已经与开源语义差异工具的当前状态作过斗争，并对此感到失望。

树中的有序节点(例如，JSON列表)，特别是映射(例如，JSON字典)是具有挑战性的。大多数现有的差分算法和实用程序都假定结构是有序的。以此JSON为例：

现有工具有效地规范了JSON(例如，按键和格式列表对字典元素进行排序，每行一项)，然后执行传统的比较。我们不需要任何花哨的工具来做这件事！他们实际上是这样做的：

该结果不是很有用，特别是在输入文件很大的情况下。问题是更改Dict键打破了差异：由于“bar”被更改为“zab”，规范表示也发生了变化，传统的diff算法将它们视为单独的编辑(diff的第2行和第15行)。

通常，最优地将一个图映射到另一个图不能在多项式时间内执行，因此对于任何有用大小的图(除非P=NP)来说都不容易处理。即使对于像DAG这样的有限类图形也是如此。但是，树和森林是特殊情况，可以在多项式时间内映射，并对可能的编辑类型进行合理的约束。图形利用了这一点。

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

Graphage使用Levenshtein距离度量的“在线”“构造性”实现(类似于Wagner-Fischer算法)来匹配有序序列(如列表)。该算法从一个无界映射开始，迭代地改进它，直到边界收敛，在这一点上发现最优的编辑序列。

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

Graphage是一个命令行实用程序，但它可以像库一样轻松使用。用户可以直接从Python与Graphage交互，并对其进行扩展以支持新的文件格式和编辑类型。

我们认为Graphage相当不错。您还可以将Graphage与我们的PolyFile工具结合使用，在语义上区分任意文件格式，即使它们本身不是基于树的。试一试，让我们知道你是如何使用它的。

我们还计划将Graphage扩展到抽象语法树上，这将允许您的源代码差异告诉您诸如哪些变量被更改以及代码块是否被重新排序之类的事情。如果您对新功能有类似的好主意，请与我们分享！

注意：该工具的部分开发资金来自国防高级研究计划局(DARPA)的SafeDocs项目。所表达的观点、观点和/或调查结果是作者的观点，不应解释为代表国防部或美国政府的官方观点或政策。