RTED: A Robust Algorithm for the Tree Edit Distance
RTED: A Robust Algorithm for the Tree Edit Distance
复制标题
DOI：
10.14778/2095686.2095692
复制
发表时间：
2011-12-01
影响因子：
2.5
通讯作者：
Augsten, Nikolaus
中科院分区：
文献类型：
--
作者：
Pawlik, Mateusz;Augsten, Nikolaus
我们考虑有序标记树之间的经典树编辑距离，它被定义为将一棵树转换为另一棵树的节点编辑操作的最小代价序列。树编辑距离的最新解决方案并不令人满意。该领域的主要竞争者要么具有最优的最坏情况复杂性，但最坏情况经常发生，要么它们对某些树的形状非常有效，但对其他树的形状却退化了。这将导致不可预测且常常不可行的运行时。在两种算法之间没有明显的选择方法。本文提出了一种鲁棒的树编辑距离算法RTED。对于任何输入实例，RTED的渐近复杂度小于或等于最佳竞争者的复杂度，即RTED既是有效的又是最坏情况下的最优的。我们介绍了一类LRH（左-右-重）算法，其中包括RTED和文献中最快的树编辑距离算法。我们证明了RTED在运行时复杂度方面优于所有先前提出的LRH算法。在我们对合成和真实世界数据的实验中，我们经验地评估我们的解决方案，并将其与最先进的技术进行比较。
We consider the classical tree edit distance between ordered labeled trees, which is defined as the minimum-cost sequence of node edit operations that transform one tree into another. The state-of-the-art solutions for the tree edit distance are not satisfactory. The main competitors in the field either have optimal worst-case complexity, but the worst case happens frequently, or they are very efficient for some tree shapes, but degenerate for others. This leads to unpredictable and often infeasible runtimes. There is no obvious way to choose between the algorithms.In this paper we present RTED, a robust tree edit distance algorithm. The asymptotic complexity of RTED is smaller or equal to the complexity of the best competitors for any input instance, i.e., RTED is both efficient and worst -case optimal. We introduce the class of LRH (Left -Right -Heavy) algorithms, which includes RTED and the fastest tree edit distance algorithms presented in literature. We prove that RTED outperforms all previously proposed LRH algorithms in terms of runtime complexity. In our experiments on synthetic and real world data we empirically evaluate our solution and compare it to the state-of-the-art.