Using a simple function of the sizes of two trees and the edit distance between them, this paper presents a normalized tree edit distance, which not only satisfies the triangle inequality, but also is a genuine metric valued in [ 0, 1 ] under the condition that the weight function is a metric over the set of elementary edit operations with all costs of insertions/deletions of the same weight. Moreover, the distance can be directly computed through tree edit distances and it has the same computing time complexity with the tree edit distance. Handwritten digits recognition experiments show that the metric normalization can reach 91.6％ , which is 0. 2％ and 0. 8％ better than that of the other two existing methods respectively when the AESA is used.%利用树大小和树编辑距离的简单函数提出了一种归一化树编辑距离,在权重函数具有度量性质且所有插入和删除操作的权重都相等时,不仅能完全满足三角不等式,而且是一种取值在[0,1]的度量.这种距离可以由树编辑距离直接计算得到,其计算时间复杂度与树编辑距离相同.通过手写数字识别实验说明,AESA算法利用该距离获得的识别率为91.6%,比其他2种归一化树编辑距离分别高0.2%和0.8%.
展开▼
