The Tree-to-Tree Editing Problem

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.