Abstract | ||
---|---|---|
In this paper, as variations of a Tai mapping between rooted labeled ordered trees (trees, for short), we introduce a segmental mapping to preserve the parent-children relationship as possible, and also top-down segmengal and bottom-up segmental mappings as the segmental mappings that contain the pair of the roots and the pair of the leaves, respectively. Then, we show that these mappings provide a new hierarchy for the variations of the Tai mapping in addition to a well-known one, in particular, the top-down segmental mapping coincides with a top-down mapping. Also we show that both segmental and bottom-up segmental distances as the minimum costs of segmental and bottom-up segmental mappings are metrics. Next, we design algorithms to compute the segmental and the bottom-up segmental distances in quadratic time and space. Finally, we give experimental results for the segmental distance. |
Year | DOI | Venue |
---|---|---|
2012 | 10.3233/FI-2014-1054 | Fundamenta Informaticae |
Keywords | DocType | Volume |
rooted labeled ordered trees,segmental distance,tai mapping,tree edit distance | Conference | 132 |
Issue | ISSN | Citations |
4 | 0169-2968 | 1 |
PageRank | References | Authors |
0.35 | 15 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tomohiro Kan | 1 | 4 | 1.10 |
Shoichi Higuchi | 2 | 4 | 2.79 |
Kouichi Hirata | 3 | 130 | 32.04 |