一种基于结构特征的树相似度计算方法

来源：计算机工程杂志2018年第11期北京时间：

作者：陈彦桦,李剑

单位：北京邮电大学 计算机学院,北京 100876

摘要：为高效计算树的相似度,提出基于树结构特征的相似度计算方法。通过构造K个节点的所有非同构形态子树,计算其同构个数并作为特征向量进行树的相似度计算。该方法摒弃了直接计算相似度的方式,利用树的结构特征间接表示树的相似度,可有效应用于大规模数据集的相似度计算。实验结果显示:在特征向量提取方面,随着树的节点规模增大,算法时间复杂度呈线性增加;在相似度计算方面,同类数据相似度0.7以上占比74%,不同类数据相似度不超过0.2,表明提取的特征向量能够较好地表征原程序

关键词：子树同构, 结构特征, 相似度计算, 编辑距离,聚类

基金资助：国家自然科学基金(U1636106,61472048)