如何计算树编辑距离？

Question

我需要为我的个人项目计算树之间的编辑距离. 该论文描述了一种算法,但我不能做正面或反面出来.您是否了解以更平易近人的方式描述适用算法的任何资源？伪代码或代码也会有所帮助.

Answer 1

(编辑此答案以链接到tim.tadh给出的当前版本的实现)

这个Python库正确实现了Zhang-Shasha算法:https://github.com/timtadh/zhang-shasha

它最初是作为当前接受的答案(带有tarball链接的答案)中列出的Java源的直接端口,但该实现不正确,几乎不可能运行.

Answer 2

下面是一些可能对您有用的Tree Edit Distance算法的java源代码(底部是gzipped tarball).

该页面包括参考资料和一些幻灯片,这些幻灯片分步介绍了"张和沙莎"算法以及其他有用的链接,以帮助您加快速度.

编辑:虽然这个答案被接受了,因为它指向了Zhang-Shasha算法,但链接中的代码存在错误.Steve Johnson和tim.tadh提供了可用的Python代码.有关详细信息,请参阅Steve Johnson的评论.

Answer 3

我根据现有的PyGram Python代码(https://github.com/Sycondaman/PyGram)编写了一个实现(https://github.com/hoonto/jqgram.git)给那些希望使用树编辑距离的人在浏览器和/或Node.js中使用PQ-Gram算法进行近似.

jqgram树编辑距离近似模块为服务器端和浏览器端应用程序实现PQ-Gram算法; O(n log n)时间和O(n)空间性能,其中n是节点数.请参阅算法所来自的学术论文:(http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf)

PQ-Gram近似比通过Zhang&Shasha,Klein或Guha等获得真正的编辑距离快得多.al,提供真正的编辑距离算法,所有这些算法都执行最少的O(n ^ 2)时间,因此通常是不合适的.

通常在现实世界的应用中,如果可以获得多个树与已知标准的相对近似,则不必知道真正的编辑距离.Javascript,在浏览器中,现在在服务器上,随着Node.js的出现经常处理树结构和最终用户性能,这在算法实现和设计中通常是至关重要的; 因此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, depth:10 },
function(result) {
    console.log(result.distance);
});

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

现在你可以使用的一种方法是使用jqgram或PyGram来获取一些接近的树,然后继续对一小组树使用真正的编辑距离算法,为什么要在树上花费所有计算你已经很容易确定非常遥远,反之亦然.所以你也可以使用jqgram来缩小选择范围.

希望代码可以帮助一些人.