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

摘要

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