如何計算樹編輯距離？

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 
'''