The Tree-to-Tree Editing Problem
The Tree-to-Tree Editing Problem
复制标题
树到树的编辑问题
DOI：
10.1142/s0218001488000157
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
Keiko Tanaka
中科院分区：
文献类型：
--
作者：
E. Tanaka;Keiko Tanaka
本文描述了基于结构保持映射的树距离计算算法。该距离被定义为在结构保持映射的限制下将树Tα变换为树Tβ所需的编辑操作权重的最小和。编辑操作允许将树的一个顶点替换为另一个树的顶点、删除树的顶点以及向树插入顶点。所提出的算法在时间 O(NαNβLα) 或 O(NαNβLβ) 和空间 O(NαNβ) 中确定 Tα 和 Tβ 之间的距离，其中 Nα、Nβ、Lα 和 Lβ 分别是 Tα、Tβ 的顶点数、Tα 和 Tβ 的叶子数。时间复杂度接近不可接近的最低界O(NαNβ)。提出了改进的算法。该树距离可以应用于任何问题，包括模式识别、句法树比较和分类，以及结构在结构保留映射中很重要的树比较。
This paper describes the computing alogrithms for the tree distance based on the structure preserving mapping. The distance is defined as the minimum sum of the weights of edit operations needed to transform tree Tα to tree Tβ under restriction of the structure preserving mapping. The edit operations allow substituting a vertex of a tree to another, deleting a vertex of a tree and inserting a vertex to a tree. Proposed algorithms determine the distance between Tα and Tβ in time O(NαNβLα) or O(NαNβLβ), and in space O(NαNβ), where Nα, Nβ, Lα and Lβ are the number of vertices of Tα, Tβ, the number of’ leaves of Tα and Tβ, respectively. The time complexity is close to the unapproachable lowest bound O(NαNβ). Improved algorithms are presented. This tree distance can be applied to any problems including pattern recognition, syntactic tree comparison and classification, and tree comparison whose structures are important in structure preserving mapping.