An O(n^3)-Time Algorithm for Tree Edit Distance
An O(n^3)-Time Algorithm for Tree Edit Distance
复制标题
树编辑距离的 O(n^3) 时间算法
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Oren Weimann
中科院分区：
文献类型：
--
作者：
E. Demaine;S. Mozes;Benjamin Rossman;Oren Weimann
带有顶点标签的两个有序树之间的编辑距离是将一棵树转换为另一棵树的最低成本，该树由一系列基本操作，包括删除和重新标记现有节点，以及在本文中插入新的节点。 o（n） - 用于此问题的时间算法，改善先前的o（n log n）时间算法[6]。子问题（这本身就是有趣的），加上对问题的更深入的了解，我们还证明了我们以前的算法的最佳性。已知的下限（n log n）[4]与ω（n），与我们的算法的运行时间相匹配。当两棵树具有不同尺寸的M和N时，其中m <n。
The edit distance between two ordered trees with vertex labels is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. In this paper, we present a worstcase O(n)-time algorithm for this problem, improving the previous best O(n log n)time algorithm [6]. Our result requires a novel adaptive strategy for deciding how a dynamic program divides into subproblems (which is interesting in its own right), together with a deeper understanding of the previous algorithms for the problem. We also prove the optimality of our algorithm among the family of decomposition strategy algorithms—which also includes the previous fastest algorithms—by tightening the known lower bound of Ω(n log n) [4] to Ω(n), matching our algorithm’s running time. Furthermore, we obtain matching upper and lower bounds of Θ(nm(1+log n m )) when the two trees have different sizes m and n, where m < n.