检测树结构之间的差异

Question

这更像是一个CS问题,但却是一个有趣的问题:

假设我们有2个树结构,其中重组的节点或多或少相同.你怎么找到的

1. 任何
2. 在某种意义上是最小的

操作顺序

• MOVE(A, B) - 在节点B下移动节点A(使用整个子树)
• INSERT(N, B)- 在节点B下插入新节点N.
• DELETE (A) - 删除节点A(使用整个子树)

将一棵树转换为另一棵树.

显然可能存在这样的转变是不可能的情况,小孩子是带有孩子B的根A到带有孩子A的根B等等.在这种情况下,算法将简单地传递" 不可能 " 的结果.

更为壮观的版本是网络的概括,即当我们假设一个节点可以在树中多次出现(实际上有多个"父")时,禁止循环.

免责声明:这不是一个功课,实际上它来自一个真正的业务问题,我发现很有趣,想知道是否有人可能知道一个解决方案.

Answer 1

不仅有关于图同构的维基百科文章(如Space_C0wb0y指出的那样),还有一篇关于图同构问题的专门文章.它有一个Solved special cases已知多项式时间解的部分.树木就是其中之一,它引用了以下两个参考:

• PJ Kelly,"树木的同余定理"Pacific J. Math.,7(1957)pp.961-968
• Aho,Alfred V.; 霍普克罗夫特,约翰; Ullman,Jeffrey D.(1974),计算机算法设计与分析,阅读,MA:Addison-Wesley.

Answer 2

您不清楚是否要比较源代码的抽象语法树,解释为树的XML文档或其他类型的树.

有很多论文讨论比较语法树和通过各种方法计算最小距离.这些想法应该是相关的.

一篇好文章是Change Distilling,它试图比较两个抽象语法树的源代码并报告最小的差异.本文讨论了一种特定的方法,并且还简要地提及(并提供了参考)各种类似的技术.

在用于比较源文本的可用工具中实际上实现了这些算法中的很少一部分.我们的智能差异器就是其中之一.

Answer 3

虽然这个问题很老,但我会在下面添加更多参考和算法:

1. X-Diff:一种有效的XML文档变更检测算法,Yuan Wang,David J. DeWitt,Jin-Yi Cai
2. KF-Diff +:XML文档的高效变更检测算法
3. diffX:一种检测多版本XML文档中的更改的算法
4. XML树中的变化检测:一项调查,Luuk Peters
5. 树数据结构中的相似性

此外,GitHub上的库和框架(在javascript中)实现了树状结构的差异,例如处理JSON数据或XML树的应用程序(例如,用于客户端MVC/MVVM):

1. React.js
2. JSON-补丁
3. jsondiffpatch
4. objectDiff

Answer 4

如果人们发现这个问题并且需要为Node.js或浏览器实现一些东西,我将为我编写的一个实现提供一个链接和代码示例,您可以在github上找到它:(https://github.com /hoonto/jqgram.git)基于现有的PyGram Python代码(https://github.com/Sycondaman/PyGram).

这是树编辑距离近似算法,但它比尝试找到真正的编辑距离快得多.近似在O(n log n)时间和O(n)空间中执行,而真正的编辑距离通常是O(n ^ 3)或O(n ^ 2),使用已知算法用于真正的编辑距离.参见PQ-Gram算法所来自的学术论文:(http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf)

所以使用jqgram:

例:

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 },
function(result) {
    console.log(result.distance);
});

这会给你一个介于0和1之间的数字.越接近零,两棵树看起来越接近jqgram.一种方法可能是使用jqgram在许多树中根据其速度缩小几个密切相关的树,然后利用剩余的少量树上的真实编辑距离,你需要仔细检查,为此你可以找到python例如,Zhang和Shasha算法的参考或端口的实现.

请注意,lfn和cfn参数指定每个树应如何独立地确定每个树根的节点标签名称和子数组,以便您可以执行诸如将对象与浏览器DOM进行比较等时髦的事情.您需要做的就是提供这些函数以及每个根,jqgram将完成其余的工作,调用您的lfn和cfn提供的函数来构建树.所以从这个意义上来说,(在我看来)它比PyGram更容易使用.另外,它的Javascript,所以使用它客户端或服务器端!

另外,为了回答循环检测,检查jqgram里面的克隆方法,那里有循环检测,但是归功于节点克隆的作者,从那里稍微修改并包含了该片段.