Làm cách nào để tính khoảng cách chỉnh sửa cây?

Question

Tôi cần tính khoảng cách chỉnh sửa giữa các cây cho một dự án cá nhân của tôi. This giấy mô tả một thuật toán, nhưng tôi không thể làm cho người đứng đầu hoặc đuôi ra khỏi nó. Bạn có biết bất kỳ tài nguyên nào mô tả thuật toán có thể áp dụng theo cách dễ tiếp cận hơn không? Mã giả hoặc mã cũng sẽ hữu ích.

Answer 1

Dưới đây là một số java source code (gzipped tarball ở phía dưới) cho thuật toán Tree Edit Distance có thể hữu ích cho bạn.

Trang bao gồm các tham chiếu và một số trang trình bày đi qua thuật toán "Zhang và Shasha" từng bước và các liên kết hữu ích khác giúp bạn tăng tốc.

Chỉnh sửa: Trong khi câu trả lời này được chấp nhận vì nó chỉ ra thuật toán Zhang-Shasha, mã trong liên kết có lỗi. Steve Johnson và tim.tadh đã cung cấp working Python code. Xem Steve Johnson's comment để biết thêm chi tiết.

Answer 2

Tôi nghĩ bạn chỉ đang tìm đường đi ngắn nhất giữa hai đỉnh. Nếu có, bạn có thể sử dụng Dijkstra's algorithm. (Trang wikipedia có mã giả trên đó để bạn tham khảo.)

Answer 3

Có phiên bản tạp chí của giấy ICALP2007 mà bạn tham chiếu tại http://www.wisdom.weizmann.ac.il/~oweimann/Publications/TEDinTALG.pdf Phiên bản này cũng có mã giả.

Answer 4

Có nhiều biến thể của khoảng cách chỉnh sửa cây. Nếu bạn có thể đi với khoảng cách chỉnh sửa cây từ trên xuống, điều này giới hạn việc chèn và xóa các lá, tôi khuyên bạn nên thử loại giấy sau đây: http://portal.acm.org/citation.cfm?id=671669&dl=GUIDE&coll=GUIDE&CFID=68408627&CFTOKEN=54202965. Việc triển khai thực hiện là một ma trận lập trình động đơn giản với chi phí O (n2).

Answer 5

(Edited câu trả lời này để liên kết đến phiên bản hiện tại của việc thực hiện do tim.tadh)

thư viện

Python này thực hiện các thuật toán Zhang-Shasha đúng: https://github.com/timtadh/zhang-shasha

Nó bắt đầu như là một cổng trực tiếp của nguồn Java được liệt kê trong câu trả lời hiện đang được chấp nhận (câu trả lời có liên kết tarball), nhưng việc thực hiện đó là không chính xác và gần như không thể chạy được.

Answer 6

Ở đây bạn tìm thấy triển khai Java khoảng cách thuật toán cây chỉnh sửa:

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

Ngoài thuật toán năm 1989 Zhang & Shasha của, cũng có triển khai cây chỉnh sửa khoảng cách của các thuật toán gần đây bao gồm Klein năm 1998, Demaine et al. 2009, và Tree Sửa cách (rted) thuật toán mạnh mẽ bởi Pawlik & Augsten, 2011.

Answer 7

tôi đã viết một thực hiện (https://github.com/hoonto/jqgram.git) dựa trên mã PyGram Python hiện có (https://github.com/Sycondaman/PyGram) cho những người bạn của những người muốn sử dụng cây chỉnh sửa khoảng cách xấp xỉ bằng cách sử dụng thuật toán PQ-Gram trong trình duyệt và/hoặc trong Node.js.

Mô đun xấp xỉ khoảng cách chỉnh sửa cây jqgram thực hiện thuật toán PQ-Gram cho cả ứng dụng phía máy chủ và trình duyệt; O (n log n) thời gian và O (n) không gian performant trong đó n là số lượng các nút.Xem tài liệu học thuật mà từ đó thuật toán đến: (http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf)

Ước lượng PQ-Gram nhanh hơn nhiều so với khoảng cách chỉnh sửa thực sự qua Zhang & Shasha, Klein, hoặc Guha et. al, người cung cấp các thuật toán khoảng cách chỉnh sửa thực sự mà tất cả thực hiện tối thiểu O (n^2) thời gian và do đó thường không phù hợp.

Thường trong các ứng dụng trong thế giới thực, không cần phải biết khoảng cách chỉnh sửa thực nếu có thể đạt được xấp xỉ tương đối của nhiều cây với một tiêu chuẩn đã biết. Javascript, trong trình duyệt và bây giờ trên máy chủ với sự ra đời của Node.js đối phó thường xuyên với cấu trúc cây và hiệu suất người dùng cuối thường là quan trọng trong việc thực hiện và thiết kế thuật toán; do đó jqgram.

Ví dụ:

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

Lưu ý rằng các thông số lfn và CFN chỉ định cách mỗi cây nên xác định tên nhãn nút và các mảng trẻ em cho mỗi gốc cây một cách độc lập để bạn có thể làm những việc sôi nổi như so sánh một đối tượng cho một DOM trình duyệt chẳng hạn. Tất cả những gì bạn cần làm là cung cấp các chức năng đó cùng với mỗi gốc và jqgram sẽ làm phần còn lại, gọi hàm lfn và cfn của bạn để cung cấp các cây. Vì vậy, trong ý nghĩa đó là (theo ý kiến ​​của tôi anyway) dễ dàng hơn nhiều để sử dụng hơn PyGram. Plus, Javascript của nó, do đó, sử dụng nó khách hàng hoặc phía máy chủ! Bây giờ, một cách tiếp cận bạn có thể sử dụng là sử dụng jqgram hoặc PyGram để lấy một vài cây gần và sau đó sử dụng thuật toán chỉnh sửa khoảng cách thực sự đối với một nhóm cây nhỏ hơn, tại sao lại sử dụng tất cả tính toán trên cây có thể dễ dàng xác định là rất xa, hoặc ngược lại. Vì vậy, bạn có thể sử dụng jqgram để thu hẹp lựa chọn quá.

Hy vọng mã giúp một số người dùng.

Answer 8

tôi đã thực hiện một wrapper python đơn giản (apted.py) cho các thuật toán APTED sử dụng jpype nếu có ai quan tâm:

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