一個新的樹編輯距離之演算法

Abstract

在1989年，Zhang和Shasha提出了傳統型樹編輯距離的演算法，其時間複雜度為O(|S||T|min(Ls,Ds)min(Lt,Dt)) 其中|S|和|T| 分別為第一、第二顆樹的節點個數，Ls和Ds為第一顆樹的葉節點個數和第一顆樹的深度，Lt和Dt為第二顆樹的葉節點個數和第二顆樹的深度。在1995年Zhang提出了限制型樹編輯距離的演算法，其時間複雜度為O(|S||T|)。本篇論文提出了一個混合型編輯距離的問題。這樣的一個編輯距離的規範可應用於XML文件的比對、HTML/XHTML文件的比對、圖樣的辨識等應用。我們也提出了一個時間為O(dsmax*dtmax*|S|*|T|)的演算法來解決此問題，其中dsmax為樹S中所有不符合限制型節點之路徑的最大值，dtmax為樹T中所有不符合限制型節點之路徑的最大值。