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

Shaoming LIU

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

Shaoming LIU

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E87-A No.5 pp.1034-1041

Publication Date: 2004/05/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Shaoming LIU, "Distance between Rooted and Unordered Trees Based on Vertex and Edge Mappings" in IEICE TRANSACTIONS on Fundamentals, vol. E87-A, no. 5, pp. 1034-1041, May 2004, doi: .
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e87-a_5_1034/_p

Copy

@ARTICLE{e87-a_5_1034,
author={Shaoming LIU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Distance between Rooted and Unordered Trees Based on Vertex and Edge Mappings},
year={2004},
volume={E87-A},
number={5},
pages={1034-1041},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - Distance between Rooted and Unordered Trees Based on Vertex and Edge Mappings
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1034
EP - 1041
AU - Shaoming LIU
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E87-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2004
AB - 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.
ER -