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 条
  • [41] An A*-algorithm for the Unordered Tree Edit Distance with Custom Costs
    Paassen, Benjamin
    [J]. SIMILARITY SEARCH AND APPLICATIONS, SISAP 2021, 2021, 13058 : 364 - 371
  • [42] A New String Edit Distance and Applications
    Petty, Taylor
    Hannig, Jan
    Huszar, Tunde, I
    Iyer, Hari
    [J]. ALGORITHMS, 2022, 15 (07)
  • [43] String reconciliation with unknown edit distance
    Kontorovich, Aryeh
    Trachtenberg, Ari
    [J]. 2012 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS (ISIT), 2012,
  • [44] Top-down tree edit-distance of regular tree languages
    Ko, Sang-Ki
    Han, Yo-Sub
    Salomaa, Kai
    [J]. INTERNATIONAL JOURNAL OF ADVANCES IN ENGINEERING SCIENCES AND APPLIED MATHEMATICS, 2019, 11 (01) : 2 - 10
  • [45] Top-Down Tree Edit-Distance of Regular Tree Languages
    Ko, Sang-Ki
    Han, Yo-Sub
    Salomaa, Kai
    [J]. LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS (LATA 2014), 2014, 8370 : 466 - 477
  • [46] Top-down tree edit-distance of regular tree languages
    Sang-Ki Ko
    Yo-Sub Han
    Kai Salomaa
    [J]. International Journal of Advances in Engineering Sciences and Applied Mathematics, 2019, 11 : 2 - 10
  • [47] Learning string-edit distance
    Ristad, ES
    Yianilos, PN
    [J]. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1998, 20 (05) : 522 - 532
  • [48] Dependency Tree Matching with Extended Tree Edit Distance with Subtrees for Textual Entailment
    Alabbas, Maytham
    Ramsay, Allan
    [J]. 2012 FEDERATED CONFERENCE ON COMPUTER SCIENCE AND INFORMATION SYSTEMS (FEDCSIS), 2012, : 11 - 18
  • [49] Approximating Edit Distance in the Fully Dynamic Model
    Kociumaka, Tomasz
    Mukherjee, Anish
    Saha, Barna
    [J]. 2023 IEEE 64TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, FOCS, 2023, : 1628 - 1638
  • [50] Bounded Occurrence Edit Distance: A New Metric for String Similarity Joins with Edit Distance Constraints
    Komatsu, Tomoki
    Okuta, Ryosuke
    Narisawa, Kazuyuki
    Shinohara, Ayumi
    [J]. SOFSEM 2014: THEORY AND PRACTICE OF COMPUTER SCIENCE, 2014, 8327 : 363 - 374
12345