Analysis of tree edit distance algorithms

被引：0
作者：
Dulucq, S [1 ]
Touzet, H
机构：
[1] Univ Bordeaux 1, LaBRI, F-33405 Talence, France
[2] Univ Lille 1, LIFL, F-59655 Villeneuve Dascq, France
来源：
COMBINATORIAL PATTERN MATCHING, PROCEEDINGS | 2003年 / 2676卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this article; we study the behaviour of dynamic programming methods for the tree edit distance problem, such as [4] and [2]. We show that those two algorithms may: be described in a more general framework of cover strategies. This analysis allows us to; define a new tree edit distance algorithm, that is optimal for cover strategies.
引用
收藏
页码：83 / 95
页数：13
相关论文
共 50 条
  • [31] 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
  • [32] Exploiting Spatial Architectures for Edit Distance Algorithms
    Tithi, Jesmin Jahan
    Crago, Neal C.
    Emer, Joel S.
    2014 IEEE INTERNATIONAL SYMPOSIUM ON PERFORMANCE ANALYSIS OF SYSTEMS AND SOFTWARE (ISPASS), 2014, : 23 - 34
  • [33] Tree Edit Distance and Maximum Agreement Subtree
    Shin, Kilho
    INFORMATION PROCESSING LETTERS, 2015, 115 (01) : 69 - 73
  • [34] Optimal Algorithms for Bounded Weighted Edit Distance
    Cassis, Alejandro
    Kociumaka, Tomasz
    Wellnitz, Philip
    2023 IEEE 64TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, FOCS, 2023, : 2177 - 2187
  • [35] Computing Text Similarity using Tree Edit Distance
    Sidorov, Grigori
    Gomez-Adorno, Helena
    Markov, Ilia
    Pinto, David
    Loya, Nahun
    2015 ANNUAL MEETING OF THE NORTH AMERICAN FUZZY INFORMATION PROCESSING SOCIETY DIGIPEN NAFIPS 2015, 2015,
  • [36] Clustering of Synthetic Routes Using Tree Edit Distance
    Genheden, Samuel
    Engkvist, Ola
    Bjerrum, Esben
    JOURNAL OF CHEMICAL INFORMATION AND MODELING, 2021, 61 (08) : 3899 - 3907
  • [37] Phylogenetic tree reconstruction based on normalized edit distance
    Li, Yu-Jian
    Wang, Fang-Yuan
    Beijing Gongye Daxue Xuebao / Journal of Beijing University of Technology, 2008, 34 (11): : 1211 - 1215
  • [38] Extend tree edit distance for effective object identification
    Wang, Yue
    Wang, Hongzhi
    Zhang, Liyan
    Wang, Yang
    Li, Jianzhong
    Gao, Hong
    KNOWLEDGE AND INFORMATION SYSTEMS, 2016, 46 (03) : 629 - 656
  • [39] Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance
    Mao, Xiao
    2021 IEEE 62ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2021), 2022, : 792 - 803
  • [40] Tree Edit Distance as a Baseline Approach for Paraphrase Representation
    Vila, Marta
    Dras, Mark
    PROCESAMIENTO DEL LENGUAJE NATURAL, 2012, (48): : 89 - 95
12345