Distance between Rooted and Unordered Trees Based on Vertex and Edge Mappings

Shaoming LIU  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E87-A   No.5   pp.1034-1041
Publication Date: 2004/05/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
tree,  graph,  structure,  pattern,  distance,  similarity,  mapping,  algorithm,  pattern matching,  

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




Summary: 
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.