第1期 于世英，等：基于序列聚类的相似代码检测算法 ·55· toS)来进行初始过滤，如果它们的签名距离大于最 中的簇的相似关系，直到所有的序列S:都被处理， 大距离阈值，就直接判定这2个序列不相似；如果签 此时的相似关系可能为3种情况：1)如果簇列表中 名距离小于最大距离阈值，再计算其权重编辑距离 没有簇与序列S,相似，那么就新建一个簇存放该序 Dg(S1,S2)(wEditDisStoS)进行进一步判断.如算法 列，并且把新创建的簇添加到簇列表中；2)如果簇 1所述. 列表中有一个簇与该序列相似，就把它加人到这个 算法1判断序列与序列是否相似算法(8- 簇中，更新簇的特征值；3)如果簇列表中有多个簇 SandSSimilar). 与该序列相似，就把这几个簇合成一个新簇，再把序 输入：要判断相似性的2个序列S,和S2: 列S:加入到新簇中，并且在簇列表中移除合并了的 输出：布尔值(isSimilar). 那几个簇，添加新创建的簇.聚类过程如算法3 Begin 所述 1）boolean isSimilar; 算法3聚类算法(clustering) 2)int SandSMaxDis=getMaxDistance(S1,S2); 输入：存放序列的哈希表seriesMap. 3)int signDisStoS=calSignDisStoS(S1,S2); 输出：簇列表clusters. 4)If signDisStoS <=SandSMaxDis Begin 5) int wEditDisStoS =calWEditDisStoS(S,S2); 1)List clusters; 6) If wEditDisStoS <SandSMaxDis 2)For each series s in seriesMap 7) isSimilar =true; 3) List simCluNotoSList:/clusters in List clus- 8) Else ters which are similar to series s 9) isSimilar false; 4) List removeCluList; 10) End if 11)End if 5) For each cluster c in clusters If isSandCSimilar(s,c) End 6) 2.3.2判断序列与簇是否相似 7) simCluNotoSList.add(c); 有了判断序列与序列是否相似的算法作为支 8) End if 撑，判断序列与簇是否相似就很容易了.只需要把簇 9) End for 中的所有序列依次与该序列进行相似性判断，如果 10) If simCluNotoSList.size()==0 簇中有任意一个序列与该序列相似，就判定为该序 11) Create a new cluster c'to put series s and 列与该簇相似.如算法2所述. put c'into clusters; 算法2判断序列与序列是否相似算法(8 12) Else if simCluNotoSList.size()==1 SandCSimilar). 13) Put s in cluster c and update the feature of c; 输人：要判断相似性的序列ser和簇cluster. 14) Else 输出：布尔值(isSimilar). 15) Merging clusters in simCluNotoSList into a Begin new cluster c'and put c'into clusters; 1)boolean isSimilar; 16) Remove clusters in simCluNotoSList from 2)For each series s in cluster clusters; 3) isSimilar =isSandCSimilar (ser,s); 17)End if 4) If isSimilar 18)End for 5) break; End 6) End if 算法3给出了改进的基于密度的序列聚类过 7)End for 程.其中，步骤5)~9)是判断簇列表中有几个簇与 End 序列是相似的，可能出现上面给出的3种情况.步骤 2.3.3符号序列的聚类 10)~11)对应情况1)，即簇列表中没有簇与序列相 本文采用改进的基于密度的聚类算法对序列聚 似；步骤12)~13)对应情况2)，簇列表中有一个簇 类，首先创建一个簇列表来存放聚类结果簇，对于存 与该序列相似；步骤14)~16)对应情况3)，簇列表 放在m即中任意一个序列S:,判断序列S:与簇列表 中有多个簇与该序列相似