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

摘要：

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

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

所属期刊栏目：44

分类号：TP18(自动化基础理论)

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

在线出版日期：2019-01-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：197-201,208