New Algorithm for Ordered Tree-to-Tree Correction Problem
New Algorithm for Ordered Tree-to-Tree Correction Problem
复制标题
有序树到树校正问题的新算法
DOI：
10.1006/jagm.2001.1170
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Weimin Chen
中科院分区：
文献类型：
--
作者：
Weimin Chen
有序的树对树校正问题是计算将一个有序树转换为另一个问题的最低编辑成本。 s || t |+min {l2s | t |+l2.5slt，l2t | s | s |+l2.5tls）时间，其中ls表示s和ds的叶子的数量表示S的深度S。这个问题在o（| s || t | min {ls，ds} min {lt，dt}）时间（K. Zhang和D. Shasha，Siam J. Comput.18，No. 6（1989），1245？1262）和在o（min {| s | 2 | t | log2 | t |，| t | 2 | 2 | s | log2 | s | s |}）时间（P. N. Klein，在“算法？ （G Bilardi，G。F。Italiano，A。Pietracaprina和G. Pucci编辑），计算机科学中的讲义，第1461卷，第91页？102，Springer-Verlag，柏林/纽约，1998年）。
The ordered tree-to-tree correction problem is to compute the minimum edit cost of transforming one ordered tree to another one. This paper presents a new algorithm for this problem. Given two ordered trees S and T, our algorithm runs in O(|S||T|+min{L2S|T|+L2.5SLT,L2T|S|+L2.5TLS) time, where LS denotes the number of leaves of S and DS denotes the depth of S. The previous best algorithms for this problem run in O(|S||T|min{LS,DS}min{LT,DT}) time (K. Zhang and D. Shasha, SIAM J. Comput.18, No. 6 (1989), 1245?1262) and in O(min{|S|2|T|log2|T|,|T|2|S|log2|S|}) time (P. N. Klein, in “Algorithms?ESA'98, 6th Annual European Symposium” (G. Bilardi, G. F. Italiano, A. Pietracaprina, and G. Pucci, Eds.), Lecture Notes in Computer Science, Vol. 1461, pp. 91?102, Springer-Verlag, Berlin/New York, 1998). As a comparison, our algorithm is asymptotically faster for certain kind of trees.