Page 331 - 《软件学报》2021年第7期

李玫 等:面向代码相似性检测的相似哈希改进方法 2249

采用将这些常见行直接筛除的策略,仅保留那些有文件特色的行参与指纹的计算.
由此,本文在行粒度相似哈希算法的基础上进行了改进,结合代码文件的结构特点引入了常见行筛选列表
以消除一些频繁出现且包含语义较少的行,如图 4 所示.从上述 10 种常见语言的行统计结果中对每种语言各取
前 20 000 行作为该语言行筛选器的筛选内容,不同语言的行筛选器一起组成常见行列表.对于一个待测源代码
文件,首先进行去空行、去注释、去空格、全部大写转换为小写的预处理过程,并将代码文件分行;其次根据文
件的后缀名判断所属语言,从常见行列表中选取对应语言的常见行筛选器,并将文件中包含在筛选器中的对应
行全部筛除,剩下的每一行作为该代码文件的特征;然后通过 MurMur Hash [25] 方法对这些特征依次进行哈希计
算,并将得到的结果逐位映射为一串由 1、–1 组成的序列;最后将这些序列经过累加和降维得到最终的指纹结
果.使用本文提出的方法对图 3 中的例子进行指纹计算,两者的海明距离由 7 变为了 27,可见改进后的算法很好
地体现了两段代码的差异.

Fig.3 Examples of meaningless repeating lines
图 3 无意义重复行示例

Fig.4 Enhanced simhash algorithm with line granularity
图 4 改进后的行粒度相似哈希方法