Affiliations: Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan. kan@dumbo.ai.kyutech.ac.jp; syou_hig@dumbo.ai.kyutech.ac.jp | Department of Artificial Intelligence & Biomedical Informatics R&D Center, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan. hirata@ai.kyutech.ac.jp
Note: [] Current affiliation: Kyushu Electric Power, Co., Inc.
Note: [] Current affiliation: Honest Kyushu, Co., Ltd.
Note: [] The author would like to experss thanks for support by the Grant-in-Aid for Scientific Research 22240010, 24240021, 24300060 and 25540137 from the Ministry of Education, Culture, Sports, Science and Technology, Japan. Address for correspondence: Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan
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.
Keywords: tree edit distance, segmental distance, Tai mapping, rooted labeled ordered trees
