IEICE TRANSACTIONS on Fundamentals
Distance between Rooted and Unordered Trees Based on Vertex and Edge Mappings
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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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://global.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 -
English
