For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Computing Algorithm for the Tree Metric Based on the Structure Preserving Mapping
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1985/05/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Automata and Languages
Full Text: PDF(419.8KB)>>
This paper describes a computing algorithm 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 the 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. The proposed algorithm computes the distance between Tα and Tβ in time OT( mβ Nα Nβ) and in space OS( Nα Nβ), where Nα, Nβ, mα and mβ are the number of vertices of Tα, that of Tβ, the maximum number of children of a vertex in Tα and that in Tβ, respectively. Possible applications are to pattern recognition, syntactic error detection and correction for natural and artificial languages, and information retrieval for tree-structure data.