Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes

被引：0
|
作者：
Aratsu, Taku [1 ]
Hirata, Kouichi [1 ]
Kuboyama, Tetsuji [2 ]
机构：
[1] Kyushu Inst Technol, Dept Artificial Intelligence, Kawazu 680-4, Iizuka, Fukuoka 8208502, Japan
[2] Gakushuin Univ, Ctr Comp, Toshima Ku, Tokyo, Japan
来源：
SOFSEM 2009-THEORY AND PRACTICE OF COMPUTER SCIENCE, PROCEEDINGS | 2009年 / 5404卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this paper, we give an approximation of the tree edit distance through the string edit distance for binary tree. codes, instead of one for Euler strings introduced by Akutsu (2006). Here, a binary tree code is a string obtained by traversing a binary tree representation with two kinds of dummy nodes of a tree in preorder. Then, we show that sigma/2 <= tau <= (h + 1)sigma + h, where tau is the tree edit distance between trees, sigma is the string edit distance between their binary tree codes and It is the minimum height of the trees.
引用
收藏
页码：93 / +
页数：3
相关论文
共 50 条
  • [1] Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes
    Aratsu, Taku
    Hirata, Kouichi
    Kuboyama, Tetsuji
    FUNDAMENTA INFORMATICAE, 2010, 101 (03) : 157 - 171
  • [2] Approximating tree edit distance through string edit distance
    Akutsu, Tatsuya
    Fukagawa, Daiji
    Takasu, Atsuhiro
    ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2006, 4288 : 90 - +
  • [3] Approximating Tree Edit Distance through String Edit Distance
    Akutsu, Tatsuya
    Fukagawa, Daiji
    Takasu, Atsuhiro
    ALGORITHMICA, 2010, 57 (02) : 325 - 348
  • [4] Approximating Tree Edit Distance through String Edit Distance
    Tatsuya Akutsu
    Daiji Fukagawa
    Atsuhiro Takasu
    Algorithmica, 2010, 57 : 325 - 348
  • [5] Tree edit distance with gaps
    Touzet, H
    INFORMATION PROCESSING LETTERS, 2003, 85 (03) : 123 - 129
  • [6] A New Perspective on the Tree Edit Distance
    Schwarz, Stefan
    Pawlik, Mateusz
    Augsten, Nikolaus
    SIMILARITY SEARCH AND APPLICATIONS, SISAP 2017, 2017, 10609 : 156 - 170
  • [7] Analysis of tree edit distance algorithms
    Dulucq, S
    Touzet, H
    COMBINATORIAL PATTERN MATCHING, PROCEEDINGS, 2003, 2676 : 83 - 95
  • [8] Learning stochastic tree edit distance
    Bernard, Marc
    Habrard, Amaury
    Sebban, Marc
    MACHINE LEARNING: ECML 2006, PROCEEDINGS, 2006, 4212 : 42 - 53
  • [9] A metric normalization of tree edit distance
    Yujian Li
    Zhang Chenguang
    Frontiers of Computer Science in China, 2011, 5 : 119 - 125
  • [10] Efficient Computation of the Tree Edit Distance
    Pawlik, Mateusz
    Augsten, Nikolaus
    ACM TRANSACTIONS ON DATABASE SYSTEMS, 2015, 40 (01):
12345