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 条
  • [21] A survey on tree edit distance and related problems
    Bille, P
    THEORETICAL COMPUTER SCIENCE, 2005, 337 (1-3) : 217 - 239
  • [22] RTED: A Robust Algorithm for the Tree Edit Distance
    Pawlik, Mateusz
    Augsten, Nikolaus
    PROCEEDINGS OF THE VLDB ENDOWMENT, 2011, 5 (04): : 334 - 345
  • [23] Analysis of tree edit distance on XML data
    Wu, Yu-Fang
    Lin, Shu-Fen
    Yen, Hsu-Chun
    PROCEEDINGS OF THE SIXTH IASTED INTERNATIONAL CONFERENCE ON COMMUNICATIONS, INTERNET, AND INFORMATION TECHNOLOGY, 2007, : 5 - 10
  • [24] Learning probabilistic models of tree edit distance
    Bernard, Marc
    Boyer, Laurent
    Habrard, Amaury
    Sebban, Marc
    PATTERN RECOGNITION, 2008, 41 (08) : 2611 - 2629
  • [25] Analyzing Edit Distance on Trees: Tree Swap Distance is Intractable
    Berglund, Martin
    PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2011, 2011, : 59 - 73
  • [26] Faster algorithms for guided tree edit distance
    Tsur, Dekel
    INFORMATION PROCESSING LETTERS, 2008, 108 (04) : 251 - 254
  • [27] Graph Similarity Using Tree Edit Distance
    Dwivedi, Shri Prakash
    Srivastava, Vishal
    Gupta, Umesh
    STRUCTURAL, SYNTACTIC, AND STATISTICAL PATTERN RECOGNITION, S+SSPR 2022, 2022, 13813 : 233 - 241
  • [28] Tree Edit Distance and Maximum Agreement Subtree
    Shin, Kilho
    INFORMATION PROCESSING LETTERS, 2015, 115 (01) : 69 - 73
  • [29] Neural String Edit Distance
    Libovicky, Jindrich
    Fraser, Alexander
    PROCEEDINGS OF THE SIXTH WORKSHOP ON STRUCTURED PREDICTION FOR NLP (SPNLP 2022), 2022, : 52 - 66
  • [30] XML Information Retrieval through Tree Edit Distance and Structural Summaries
    Laitang, Cyril
    Boughanem, Mohand
    Pinel-Sauvagnat, Karen
    INFORMATION RETRIEVAL TECHNOLOGY, 2011, 7097 : 73 - 83
12345