SIMPLE FAST ALGORITHMS FOR THE EDITING DISTANCE BETWEEN TREES AND RELATED PROBLEMS
SIMPLE FAST ALGORITHMS FOR THE EDITING DISTANCE BETWEEN TREES AND RELATED PROBLEMS
复制标题
DOI：
10.1137/0218082
复制
发表时间：
1989-12-01
影响因子：
1.6
通讯作者：
SHASHA, D
中科院分区：
文献类型：
--
作者：
ZHANG, KZ;SHASHA, D
Ordered labeled trees are trees in which the left-to-right order among siblings is significant. The distance between two ordered trees is considered to be the weighted number of edit operations (insert, delete, and modify) to transform one tree to another. The problem of approximate tree matching is also considered. Specifically, algorithms are designed to answer the following kinds of questions:1. What is the distance between two trees? 2. What is the minimum distance betweenandwhen zero or more subtrees can be removed from? 3. Let the pruning of a tree at nodenmean removing all the descendants of noden. The analogous question for prunings as for subtrees is answered.A dynamic programming algorithm is presented to solve the three questions in sequential time $O(|T_1 | \times |T_2 | \times \min ({\textit{depth}}(T_1 ),{\textit{leaves}}(T_1 )) \times \min ({\textit{depth}}(T_2 ),{\textit{leaves}}(T_2 )))$ and spacecompared with $O(|T_1 | \times |T_2 | \times ({\textit{depth}}(T_1 ))^2 \times ({\textit{depth}}(T_2 ))^2 )$ for the best previous published algorithm due to Tai [J. Assoc. Comput. Mach., 26 (1979), pp, 422-433]. Further, the algorithm presented here can be parallelized to give time.
Ordered labeled trees are trees in which the left-to-right order among siblings is significant. The distance between two ordered trees is considered to be the weighted number of edit operations (insert, delete, and modify) to transform one tree to another. The problem of approximate tree matching is also considered. Specifically, algorithms are designed to answer the following kinds of questions:1. What is the distance between two trees? 2. What is the minimum distance betweenandwhen zero or more subtrees can be removed from? 3. Let the pruning of a tree at nodenmean removing all the descendants of noden. The analogous question for prunings as for subtrees is answered.A dynamic programming algorithm is presented to solve the three questions in sequential time $O(|T_1 | \times |T_2 | \times \min ({\textit{depth}}(T_1 ),{\textit{leaves}}(T_1 )) \times \min ({\textit{depth}}(T_2 ),{\textit{leaves}}(T_2 )))$ and spacecompared with $O(|T_1 | \times |T_2 | \times ({\textit{depth}}(T_1 ))^2 \times ({\textit{depth}}(T_2 ))^2 )$ for the best previous published algorithm due to Tai [J. Assoc. Comput. Mach., 26 (1979), pp, 422-433]. Further, the algorithm presented here can be parallelized to give time.