摘要
利用树大小和树编辑距离的简单函数提出了一种归一化树编辑距离,在权重函数具有度量性质且所有插入和删除操作的权重都相等时,不仅能完全满足三角不等式,而且是一种取值在[0,1]的度量.这种距离可以由树编辑距离直接计算得到,其计算时间复杂度与树编辑距离相同.通过手写数字识别实验说明,AESA算法利用该距离获得的识别率为91.6%,比其他2种归一化树编辑距离分别高0.2%和0.8%.
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 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.
出处
《北京工业大学学报》
EI
CAS
CSCD
北大核心
2011年第4期576-582,共7页
Journal of Beijing University of Technology
基金
国家自然科学基金资助项目(60775010)
北京市自然科学基金资助项目(4112009)
北京工业大学高层次人才培养资助项目
北京市属市管高等学校'中青年骨干教师培养计划'资助项目PHR(IHLB)
关键词
度量
树编辑距离
三角不等式
逼近排除算法
metric
tree edit distance
triangle inequality
approximating and eliminating search algorithm（AESA）
