Page 74 - 《软件学报》2021年第9期

2698 Journal of Software 软件学报 Vol.32, No.9, September 2021

共子串为“public,int,for,if”.字符串 S 和 T 分别为快速排序和冒泡排序关键字流图节点存储信息组合而成.根据
字符串 S 和 T 的最大公共子串构建关键字流图最大公共子图.
Table 2 Finding common keywords using dynamic programming algorithm
表 2 动态规划法查找公共关键字
S
T public int if null for if null
public public “⋅” “⋅” “⋅” “⋅” “⋅” “⋅”
int “⋅” Public,int “⋅” “⋅” “⋅” “⋅” “⋅”
for “⋅” “⋅” “⋅” “⋅” for “⋅” “⋅”
for “⋅” “⋅” “⋅” “⋅” for “⋅” “⋅”
if “⋅” “⋅” “⋅” “⋅” “⋅” for,if “⋅”
null “⋅” “⋅” “⋅” “⋅” “⋅” “⋅” “⋅”
图 6 是冒泡排序和快速排序关键字流图的最大公共子图(灰色部分).灰色部分节点存储了字符串 S 和 T 公
共子串中的关键字,关键字流图的最大正是由 S 和 T 公共子串的关键字所在的节点构成.

public public
int int

if for

for null for

if
if
null null
null
null null

(a) 快速排序关键字流图 (b) 冒泡排序关键字流图
Fig.6 Maximum common sub-graph of keyword flow graph (in gray)
图 6 关键字流图的最大公共子图(灰色部分)
2.4 程序相似性的判定

待测程序快速排序与冒泡排序的关键字流图最大公共子图已经生成,本节利用最大公共子图距离算法(见
定义 5)计算程序相似程度.最大公共子图距离公式(公式(1))中,|G 1 |和|G 2 |分别表示程序快速排序和冒泡排序的
节点数,mcs|G 1 ,G 2 |表示最大公共子图的节点数.由图 6 知:冒泡排序与快速排序存储关键字的节点都为 5,关键字
流图最大公共子图的节点为 4,故 max(|G 1 |,|G 2 |)=5,mcs|G 1 ,G 2 |=4,将具体数值带入公式,可得最大公共子图距离
D(G 1 ,G 2 )=0.2.公式(2)将程序相似度定义为 1−D(G 1 ,G 2 ),已知冒泡排序和快速排序的最大公共子图距离 0.2,故两
程序的相似度 S(G 1 ,G 2 )=(1−D(G 1 ,G 2 ))×100%=80%.
基于关键字流图判定程序相似度的伪代码见算法 1.
算法 1. 程序相似度的判定.
输入:待测程序 program1,program2;
输出:待测程序相似度 similarity.