A Computing Algorithm for the Tree Metric Based on the Structure Preserving Mapping

Eiichi TANAKA  

IEICE TRANSACTIONS (1976-1990)   Vol.E68   No.5   pp.317-324
Publication Date: 1985/05/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Automata and Languages

Full Text: PDF(419.8KB)>>
Buy this Article

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.