Torsello Andrea, Hidović-Rowe Dzena, Pelillo Marcello
Dipartimento di Informatica, Università Ca' Foscari di Venezia, Via Torino 155, 30172 Venezia Mestre, Italy.
IEEE Trans Pattern Anal Mach Intell. 2005 Jul;27(7):1087-99. doi: 10.1109/tpami.2005.146.
We address the problem of comparing attributed trees and propose four novel distance measures centered around the notion of a maximal similarity common subtree. The proposed measures are general and defined on trees endowed with either symbolic or continuous-valued attributes and can be applied to rooted as well as unrooted trees. We prove that our measures satisfy the metric constraints and provide a polynomial-time algorithm to compute them. This is a remarkable and attractive property, since the computation of traditional edit-distance-based metrics is, in general, NP-complete, at least in the unordered case. We experimentally validate the usefulness of our metrics on shape matching tasks and compare them with (an approximation of) edit-distance.
我们解决了比较属性树的问题，并围绕最大相似公共子树的概念提出了四种新颖的距离度量。所提出的度量具有通用性，适用于赋予符号或连续值属性的树，并且可应用于有根树和无根树。我们证明了我们的度量满足度量约束，并提供了一种多项式时间算法来计算它们。这是一个显著且有吸引力的特性，因为基于传统编辑距离的度量计算通常是NP完全问题，至少在无序情况下是这样。我们通过实验验证了我们的度量在形状匹配任务中的有用性，并将它们与编辑距离（的一种近似）进行了比较。
