如何计算树编辑距离?
下面是一些java source code(gzip压缩包,位于底部),用于树编辑距离算法,可能对您有用。
该页面包含参考文献和一些幻灯片,通过“张和莎莎”算法一步一步和其他有用的链接,让您了解速度。
编辑︰虽然这个答案被接受,因为它指向张沙沙算法,链接中的代码有错误。史蒂夫约翰逊和tim.tadh提供了working Python code。有关更多详细信息,请参阅Steve Johnson's comment。
我想你只是寻找两个顶点之间的最短路径。如果是这样,你可以使用Dijkstra's algorithm。 (*页面上有伪代码供您参考。)
树编辑距离是与“编辑脚本”相关的成本(系列的编辑操作)将一棵树变成另一棵。我不认为你可以直接使用Dijkstra的算法。 – Naaff 2009-06-30 19:21:26
@Naaff:其实你可以使用Dijkstra的算法(我不会推荐它)。图的节点将是OP的问题的树,并且它们将具有编辑距离为1的树的边缘。此图是无限的,因此您不会将其存储在内存中,而是会在您随时计算它。对于不太接近这个算法的树来说,它的性能和内存消耗会非常糟糕。 – yairchu 2009-07-01 10:11:00
@yairchu:谢谢你的见解。有趣的是,如果一个人能*使用Dijkstra的算法,即使一个人不应该*。 :) – Naaff 2009-07-01 20:38:45
您提到的ICALP2007论文的期刊版本是http://www.wisdom.weizmann.ac.il/~oweimann/Publications/TEDinTALG.pdf 此版本也有一个伪代码。
树编辑距离有许多变化。如果您可以使用自上而下的树编辑距离(限制插入和删除树叶),我建议您尝试使用以下纸张:http://portal.acm.org/citation.cfm?id=671669&dl=GUIDE&coll=GUIDE&CFID=68408627&CFTOKEN=54202965。实现是一个简单的动态编程矩阵,具有O(n2)成本。
(编辑这个答案链接到当前版本的执行由tim.tadh给出)
这个Python库实现了章杀杀算法正确:https://github.com/timtadh/zhang-shasha
它开始作为一个直接端口在当前接受的答案(使用tarball链接的答案)中列出的Java源代码,但该实现是不正确,几乎不可能运行。
感谢您的回馈 - 很高兴您能够正确实施Zhang-Shasha算法。抱歉,我链接的代码无法正常工作。 – Naaff 2010-11-24 18:27:26
这里你可以找到的树编辑距离算法的Java实现:
http://www.inf.unibz.it/dis/projects/tree-edit-distance
除了1989张&傻傻的算法,也有比较近的算法,包括1998年克莱恩,Demaine树编辑距离实现等人。 2009年,由Pawlik & Augsten乐百氏树编辑距离(RTED)算法,2011年
我写了一个基于现有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来缩小选择的范围。
希望代码可以帮助一些人。
我做了一个简单的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
'''
这里链接的实现是不正确的。 (请参阅我的答案。)我通过移植它开始实施,但是当我最终找到它所参考的论文时,发现原始论文的一些偏离导致其无法对称,三角不等的基本测试等。 – 2010-11-24 17:32:04