ツリーの編集距離を計算するにはどうすればよいですか？

Question

私の個人的なプロジェクトのツリー間の編集距離を計算する必要があります。 This論文はアルゴリズムを記述していますが、頭や尾を作ることはできません。あなたは、より親しみやすい方法で適用可能なアルゴリズムを記述するリソースを認識していますか？擬似コードまたはコードも役立ちます。

Answer 1

便利なツリー編集距離アルゴリズムの場合、java source code（下部にgzipped tarball）があります。

このページには、「Zhang and Shasha」アルゴリズムを順を追って説明している参考文献やスライドや、その他の役に立つリンクがあり、スピードアップを図ります。

編集：この回答はZhang-Shashaアルゴリズムを指していたので受け入れられましたが、リンク内のコードにバグがあります。 Steve Johnsonとtim.tadhはworking Python codeを提供しています。詳細はSteve Johnson's commentを参照してください。

Answer 2

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実装を見つける：1989年の張&シャシャのアルゴリズムに加えて

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

を、クライン1998、Demaineを含むより最近のアルゴリズムの木の編集距離の実装もありますet al。私は木の編集を使用したい人のために、既存のPyGram Pythonコード（https://github.com/Sycondaman/PyGram）に基づいて実装（https://github.com/hoonto/jqgram.git）を書いた2011年

Answer 7

2009、およびPawlik & Augstenによるロバスト木の編集距離（RTED）アルゴリズム、ブラウザおよび/または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らによる真の編集距離の取得よりもはるかに高速です。すべて最小のO（n^2）時間を実行する真の編集距離アルゴリズムを提供するので、しばしば不適切である。

多くの場合、実際のアプリケーションでは、既知の標準に対する複数のツリーの相対的な近似が得られれば真の編集距離を知る必要はありません。 Javascript、ブラウザ、そして現在はNode.jsの出現によりサーバ上で頻繁にツリー構造とエンドユーザのパフォーマンスを処理することは、アルゴリズムの実装と設計において重要です。従ってjqgram。

例：LFNとCFNパラメータは、オブジェクトを比較するようなファンキーなものを行うことができるように、各ツリーは、それぞれ独立して、ツリーのルートのノードラベル名と子供の配列を決定する方法を指定すること

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); 
}); 

注意例えば、ブラウザDOMに送る。必要なのは、これらの関数を各ルートとともに提供することと、jqgramは残りの作業を行い、lfnとcfnの提供関数を呼び出してツリーを構築するだけです。その意味で、（とにかく私の意見では）PyGramよりもはるかに使いやすいです。プラス、そのJavascriptは、クライアントまたはサーバー側で使用してください！

ここでは、jqgramまたはPyGramを使用していくつかのツリーを閉じた後、実際の編集距離アルゴリズムを使用してより小さなツリーセットを使用する方法を説明します。すでに容易に決定することができますか、またはその逆です。したがって、jqgramを使用して選択肢を絞り込むこともできます。

コードがいくつかの人々を助けることを願っています。

Answer 8

誰もが興味を持っている場合、私はjpypeを使用してAPTEDアルゴリズムの簡単なPythonラッパー（apted.py）を作っ：

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