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.
Distance between Rooted and Unordered Trees Based on Vertex and Edge Mappings
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2004/05/01
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
tree, graph, structure, pattern, distance, similarity, mapping, algorithm, pattern matching,
Full Text: PDF(275.5KB)>>
The issues of comparing the similarity or dissimilarity (distance) between structures have been studied. Especially, several distances between trees and their efficient algorithms have been proposed. However, all of the tree distances are defined based on mapping between vertices only, and they are helpless to compare the tree structures whose vertices and edges hold information. In this paper, we will propose a mapping between rooted and unordered trees based on vertex translation and edge translation, and then define a distance based on proposed mapping, and develop an efficient algorithm for computing proposed distance. Proposed distance can be used to compare the similarity or distance between two natural language sentences.