11

是否有任何既定或现有的格式或约定来表示两个 JSON 文档之间的差异？

假设两个远程节点（或服务器/客户端）都有一些表示为潜在复杂 JSON 的数据，其结构在运行前是未知的。一个人想向另一个人发送更新，但不想将整个状态作为一个大的 JSON 发送。相反，只是三角洲。表示任何两个 JSON 文档之间的差异（或差异）的好方法是什么？它们可能非常相似（一个小的变化），但可能不是。

4

2 回答 2

9

JSON 文档本质上是树，叶子包含名称/值对。

您要做的是传输最小的树增量：将一棵树转换为另一棵树的最小编辑集。

计算树增量是一门艺术，部分原因是它取决于您允许的增量类型（只是插入/删除叶子？交换子树？移动子树？重复子树？重命名？替换值？）。您还需要考虑语义等价性；如果你交换两个子树的位置，结果在语义上是否不同？（您的 delta 检测器可能会看到这样的树交换；语义身份检查可能会因为不感兴趣而将其排除）。如果复制子树，答案在语义上是否不同？（我认为对于 JSON，有效的答案是“否”）。

您需要动态编程算法之类的东西来确定这样的最小增量；您可以从Levenshtein 距离上的弦乐中汲取灵感。

这是程序员对源代码感兴趣的一个常见问题。将 JSON 文档视为源代码，并在https://stackoverflow.com/q/5779160/120163上查看答案以进行进一步讨论。

于 2013-03-24T02:28:32.223 回答
6

正如 Ira 指出的那样，有一些类似于 Levenshtein 的选项，但是您会考虑序列化您的对象并按字典顺序比较它，正如 Ira 提到的那样，这不会考虑您正在寻找的特定于 JSON 的语言差异（两棵树可能是相同的 JSON，但在 Levenshtein 距离上却大不相同）。你想要的绝对是树编辑距离。

因此，为了添加一些关于树编辑距离艺术的细节，这个领域中使用的已知算法通常是 Zhang & Shasha 或 Klein，例如，您可以找到 Zhang & Shasha 的 python 实现。这些算法将获得将一棵树转换为另一棵树的最少编辑次数，从而提供您的差异​​。但是，它们在绝对最好的情况下有点慢 O(n^2)，所以如果你正在比较大量 JSON 对象或文件，你会发现自己正在完善你的高尔夫游戏、洗碗、洗衣服、给宠物洗澡和其他家庭杂项。

这就是 Ira 所说的艺术的真正所在，因为这类算法很困难，而且计算成本很高。所以你可以做的就是发挥创造力。一种方法是缩小必须比较的对象的数量。例如，为什么要计算两个 JSON 对象之间的编辑距离，这两个对象显然更类似于中间而不是彼此？不要通过字典比较来计算相同对象的编辑距离，如果两个对象有些或显着不同，也许会忘记差异，只是说需要彻底替换。

为了应用树编辑距离的“艺术”，即为自己节省不必要的 CPU 周期，您需要一种方法来提供围绕“有些相似”或“显着不同”的含义的指标。

为此，我编写了 PQ-Gram 树编辑距离近似算法 ( http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf ) 的实现，您可以在 github 上找到它以用于Node.js 或在浏览器中 ( https://github.com/hoonto/jqgram.git ) 基于现有的 PyGram Python 代码 ( https://github.com/Sycondaman/PyGram )。

PQ-Gram 比在 O(n log n) 时间和 O(n) 空间中运行的真正编辑距离算法快得多，其中 n 是节点数。

因此，我的建议是使用 jqgram 快速了解您正在查看的 JSON 对象编辑距离指标。确定应该比较哪些 JSON 对象，而不是只替换哪些 JSON 对象，然后当您想要获取 diff 的真实距离时，请使用 Klein 或 Zhang & Shasha 获取实际 diff。

这是直接从 GitHub 上 jqgram 实现的 README 中提取的 jqgram JSON 对象树编辑距离近似示例：

var jq = require("jqgram").jqgram;
var root1 = {
    "thelabel": "a",
    "thekids": [
        { "thelabel": "b",
        "thekids": [
            { "thelabel": "c" },
            { "thelabel": "d" }
        ]},
        { "thelabel": "e" },
        { "thelabel": "f" }
    ]
}

var root2 = {
    "name": "a",
    "kiddos": [
        { "name": "b",
        "kiddos": [
            { "name": "c" },
            { "name": "d" },
            { "name": "y" }
        ]},
        { "name": "e" },
        { "name": "x" }
    ]
}

jq.distance({
    root: root1,
    lfn: function(node){ return node.thelabel; },
    cfn: function(node){ return node.thekids; }
},{
    root: root2,
    lfn: function(node){ return node.name; },
    cfn: function(node){ return node.kiddos; }
},{ p:2, q:3, depth:10 },
function(result) {
    console.log(result.distance);
});

lfn 和 cfn 参数指定每个 JSON 树应如何独立确定每个树根的节点标签名称和子数组，以便您可以做一些有趣的事情，例如比较来自不同来源的 JSON 对象。您需要做的就是提供这些函数以及每个根，而 jqgram 将完成其余的工作，调用您提供的 lfn 和 cfn 函数来构建树。

于 2013-06-15T17:18:21.227 回答