两个JSON之间的区别是否有既定的表示？

Question

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

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

Answer 1

JSON文档本质上是树,其中包含名称/值对.

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

计算树的增量是一种艺术,部分原因在于它取决于你允许的增量种类(只需插入/删除叶子？交换子树？移动子树？重复子树？重命名名称？替换值？).您还需要考虑语义等价; 如果你通勤两个子树的位置,结果在语义上是不同的？(您的delta检测器可能会看到这样的树交换;语义身份检查可能会将其消除为不感兴趣).如果你复制一个子树,答案在语义上是不同的？(我认为对于JSON来说,有效的答案是"不").

你需要像动态编程算法这样的东西来确定这样一个最小的delta; 你可以从Levenshtein距离上获取灵感.

这是程序员对源代码感兴趣的常见问题.将JSON文档视为源代码,并在/sf/ask/404541231/上查看答案以供进一步讨论.

Answer 2

正如Ira指出的那样,Levenshtein有一些选择,但是你会看到序列化你的对象并按字典顺序进行比较,正如Ira提到的那样,你不会考虑你正在寻找的JSON特定的语言差异(两棵树可能是相同的JSON,但Levenshtein距离非常不同).你想要的绝对是树编辑距离.

因此,为了增加树编辑距离艺术的一些细节,这个空间中使用的已知算法通常是Zhang&Shasha或Klein,你可以找到Zhang和Shasha的python实现.这些算法将获得将一棵树转换为另一棵树的最小编辑次数,从而提供差异.但是,它们在绝对最好的情况下有点慢O(n ^ 2),所以如果你要比较大量的JSON对象或文件,你会发现自己完善了你的高尔夫游戏,做菜,洗衣,给你的宠物洗澡等等.家庭杂物.

而这正是Ira所说的艺术真正的地方,因为这些算法很难并且计算成本很高.所以你可能会做的是创造性.一种方法是缩小的对象的数量都进行比较.例如,为什么要计算两个JSON对象之间的编辑距离,这两个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对象,而不是仅仅替换,然后当你想要真正的距离来获得差异时,利用Klein或Zhang&Shasha来获得实际差异.

这是jithgram JSON对象树编辑距离近似示例直接取自github上jqgram实现的README:

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提供的函数来构建树.