如何计算树编辑距离？

Question

我需要为我的个人项目计算树之间的编辑距离。论文描述了一种算法，但是我无法从中找出头或尾。您是否知道以更易于理解的方式描述适用算法的资源？伪代码或代码也会有帮助。

Answer 1

下面是一些java source code（gzip压缩包，位于底部），用于树编辑距离算法，可能对您有用。

该页面包含参考文献和一些幻灯片，通过“张和莎莎”算法一步一步和其他有用的链接，让您了解速度。

编辑︰虽然这个答案被接受，因为它指向张沙沙算法，链接中的代码有错误。史蒂夫约翰逊和tim.tadh提供了working Python code。有关更多详细信息，请参阅Steve Johnson's comment。

Answer 2

我想你只是寻找两个顶点之间的最短路径。如果是这样，你可以使用Dijkstra's algorithm。 （维基百科页面上有伪代码供您参考。）

Answer 3

您提到的ICALP2007论文的期刊版本是http://www.wisdom.weizmann.ac.il/~oweimann/Publications/TEDinTALG.pdf 此版本也有一个伪代码。

Answer 4

树编辑距离有许多变化。如果您可以使用自上而下的树编辑距离（限制插入和删除树叶），我建议您尝试使用以下纸张：http://portal.acm.org/citation.cfm?id=671669&dl=GUIDE&coll=GUIDE&CFID=68408627&CFTOKEN=54202965。实现是一个简单的动态编程矩阵，具有O（n2）成本。

Answer 5

（编辑这个答案链接到当前版本的执行由tim.tadh给出）

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

它开始作为一个直接端口在当前接受的答案（使用tarball链接的答案）中列出的Java源代码，但该实现是不正确，几乎不可能运行。

Answer 6

这里你可以找到的树编辑距离算法的Java实现：

http://www.inf.unibz.it/dis/projects/tree-edit-distance

除了1989张&傻傻的算法，也有比较近的算法，包括1998年克莱恩，Demaine树编辑距离实现等人。 2009年，由Pawlik & Augsten乐百氏树编辑距离（RTED）算法，2011年

Answer 7

我写了一个基于现有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近似比通过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来缩小选择的范围。

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

Answer 8

我做了一个简单的Python包装（apted.py）使用jpype如果有人有兴趣的APTED算法：

# To use, create a folder named lib next to apted.py, then put APTED.jar into it 

import os, os.path, jpype 

global distancePackage 
distancePackage = None 

global utilPackage 
utilPackage = None 

def StartJVM(): 
    # from http://www.gossamer-threads.com/lists/python/python/379020 
    root = os.path.abspath(os.path.dirname(__file__)) 
    jpype.startJVM(jpype.getDefaultJVMPath(), 
    "-Djava.ext.dirs=%s%slib" % (root, os.sep)) 
    global distancePackage 
    distancePackage = jpype.JPackage("distance") 
    global utilPackage 
    utilPackage = jpype.JPackage("util") 


def StopJVM(): 
    jpype.shutdownJVM() 


class APTED: 
    def __init__(self, delCost, insCost, matchCost): 
    global distancePackage 
    if distancePackage is None: 
     raise Exception("Need to call apted.StartJVM() first") 
    self.myApted = distancePackage.APTED(float(delCost), float(insCost), float(matchCost)) 

    def nonNormalizedTreeDist(self, lblTreeA, lblTreeB): 
    return self.myApted.nonNormalizedTreeDist(lblTreeA.myLblTree, lblTreeB.myLblTree) 


class LblTree: 
    def __init__(self, treeString): 
    global utilPackage 
    if utilPackage is None: 
     raise Exception("Need to call apted.StartJVM() first") 

    self.myLblTree = utilPackage.LblTree.fromString(treeString) 

''' 
# Example usage: 

import apted 
apted.StartJVM() 
aptedDist = apted.APTED(delCost=1, insCost=1, matchCost=1) 
treeA = apted.LblTree('{a}') 
treeB = apted.LblTree('{b{c}}') 
dist = aptedDist.nonNormalizedTreeDist(treeA, treeB) 
print dist 


# When you are done using apted 
apted.StopJVM() 
# For some reason it doesn't usually let me start it again and crashes python upon exit when I do this so call only as needed 
'''