(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210654436.7 (22)申请日 2022.06.10 (71)申请人 北京矩道优达网络科技有限公司 地址 100080 北京市海淀区上地 东路35号 院1号楼2层1-202-212 (72)发明人 杨博洋　傅得强　俞昊然　 (74)专利代理 机构 北京世誉鑫诚专利代理有限 公司 11368 专利代理师 刘秀珍 (51)Int.Cl. G06F 40/194(2020.01) G06F 40/216(2020.01) G06F 40/253(2020.01) G06F 40/30(2020.01) G06F 8/41(2018.01) (54)发明名称 一种基于加权抽象语法树的代码抄袭检测 方法 (57)摘要 本发明提供的一种基于加权抽象语法树的 代码抄袭检测方法包括： 获取两份代码； WASTK通 过词法解析和语法解析生成所述两份代码各自 对应的抽象语法树， 获得两棵抽象语法树； 调整 所述抽象语 法树的结构； 采用TF ‑IDE技术给所述 抽象语法树上节点赋权值； 计算所述两棵抽象语 法树的树核函数； 根据所述树核函数进行数据标 准化及相似度计算。 根据每个代码段出现的频 率， 给代码抽象语法树上对应的节点赋予权重， 以达到区分代码段重要性的目的， 从而精确判定 两份代码的抽象语法树的相似度。 权利要求书2页 说明书8页 附图2页 CN 115062600 A 2022.09.16 CN 115062600 A 1.一种基于加权抽象语法树的代码抄袭检测方法， 其特 征在于， 所述检测方法包括： 获取两份代码； WASTK通过词法解析和语法解析生成所述两份代码各自对应的抽象语法树， 获得两棵 抽象语法树； 调整所述抽象语法树的结构； 采用TF‑IDE技术给所述抽象语法树上节点赋权值； 计算所述两棵抽象语法树的树核函数； 根据所述 树核函数进行 数据标准 化及相似度计算。 2.根据权利要求1所述的一种基于加权抽象语法树的代码抄袭检测方法， 其特征在于， 所述调整所述抽象语法树的结构具体包括： 对冗余节点进行处理， 以简化所述抽象语法树的结构， 并对节点存储的信息进行标准 化处理。 3.根据权利要求1所述的一种基于加权抽象语法树的代码抄袭检测方法， 其特征在于， 所述采用TF ‑IDE技术给所述抽象语法树上节点赋权值具体包括： 根据以节点为根的子树在整棵抽象语法树上出现的频率， 利用了信 息检索领域中常用 的TF‑IDF技术， 给每个节点赋予权值。 4.根据权利要求1所述的一种基于加权抽象语法树的代码抄袭检测方法， 其特征在于， 所述计算所述两棵抽象语法树的树核函数 具体包括： WASTK将对两棵调整后的抽象语法树进行树核函数的求 解； 树核函数是一种基于树结构的计算相似度的方法， 两棵抽象语法树T1和T2的相似度通 过计算树核函数值K(T1,T2)得到： 在求解函数C(s1,s2)时需要考虑每 个节点的权值； 求解函数C(s1,s2)的方法： 其中λtree是一个衰减参数； 随着树 的高度增长， 子树 的树核函数值将会受到( λtree)size 的影响， size是指子树的高度， wor ds表示的是中序遍历以节点s为根的子树上所有叶子结 点得到的代码片段； dist(a,b)表示两个字符串a和b的相似度， 具体定义如下： 其中leva,b是指字符串a和b的编辑距离(edit  distance)； 函数max用于求出两个参数的最大值， 两个表达式之间的相似度不等于0， 而由表达式 之间的编辑距离决定； 加上两个字 符串a和b的相似度dist(a,b)后， 表达式级别的修改将会 被WASTK检测出来； 如果子树s1的根节点 不同于子树s2的根节点， 那么： C(s1,s2)＝0权　利　要　求　书 1/2 页 2 CN 115062600 A 2否则如果子树s1和子树s2的根节点都是叶子结点， 那么： 否则就进行递归求 解： 其中ns(s)是指 子树s的根结点roots的孩子节点总个数， st(s,i)表示的是以节点roots 的第i个孩 子节点为根的子树； 在否则就进行递归求解的情况中， 由于子树s1和子树s2的根节点是相同的， 则 有ns(s1) ＝ns(s2)。 5.根据权利要求1所述的一种基于加权抽象语法树的代码抄袭检测方法， 其特征在于， 所述根据所述 树核函数进行 数据标准 化及相似度计算具体包括： 计算出两棵抽象语法树T1和T2的树核函数值K(T1,T2)后， 为了方便结果比较分析， 需要 对数据进行 标准化； 数据标准 化方法公式： 其中， K'(T1,T2)为两个向量h(T1)和h(T2)的余弦相似度， 结果在区间[0,1]内， 在ASTK和 WASTK里， K'(T1,T2)为两份代码的相似度， 相似度越接近0， 则表示两份代码的差异性越大， 反之相似度越接 近1， 则表示两份代码越相似。权　利　要　求　书 2/2 页 3 CN 115062600 A 3