Narrow Results

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.

In the previous paper on a tree-to-tree editing problem some errors were included. This letter describes the corrected definition of a structure preserving mapping between rooted and ordered trees and a computing method of the tree distance based on the mapping.