基于词嵌入的源码相似度研究

钱 程，谢春丽，王梦琦，权 雷

（1.江苏师范大学智慧教育学院；2.江苏师范大学计算机科学与技术学院，江苏徐州 221116）

0 引言

随着Github、StackOverflow 等开源代码平台的开放，这些开源代码的直接获取不可避免地引发了代码剽窃，无形中增加了程序漏洞的传播。高校各种在线判题系统（On⁃line Judge，OJ）使用过程中，学生作业以源代码形式提交到OJ 平台，平台在线自动完成评测，这种方式使得学生抄袭他人代码现象泛滥［1］。事实上，商用软件领域抄袭的现象也愈演愈烈［1］，造成了维护程序编写者知识产权日渐困难的局面。因此，研究代码克隆并评测代码剽窃这一问题很有必要。文本相似度度量是解决该类问题的基础手段，它也适用于其他领域，如文本分类［2］、信息检索、自动代码补充［3］等。相关文本相似度计算方法不断被设计研究出来，比较常见的有N-gram、TF-IDF、LSA 等。

N-gram 模型注重词数量特征，缺乏对语义的检测［4］。武永亮等［5］提出的TF-IDF 模型通过计算词频权重来比较词的重要性，但这种方法仅仅只针对文本统计信息，缺乏对词义、结构的计算。一些其他基于关键词典的方法受词典大小限制，需要大量词汇；而基于编辑距离的方法由于应用场景受限制，对长句的检测、计算存在较大误差［6］。

针对上述问题，本文选择基于向量空间的模型，通过TF-IDF 和Word2vec 构建模型。将该模型与基于N-Gram的模型进行对比，以期尽可能考虑到文本相似度的语义因素，并对其计算结果进行比较和分析。实验结果表明，基于向量空间的模型在检测C++源码相似情况的效果要优于基于词的N-gram 模型。

1 相关工作

1.1 关键词匹配方法

N-gram 是一种语言模型思想，广泛应用于语音识别、手写体识别、拼写纠错等领域。这种思想基于一个假设：在一个句子中下一个词的出现仅依赖于前面的一个或几个词，而与其他任何词不相关（即隐含马尔可夫模型中的假设）［7］。以“好好学习，天天”为例，当出现该句子后，大部分人很容易就会接出之后的“向上”一词，而不是其他的词，这表明“向上”一词的出现依赖于“好好学习，天天”的出现。

在N-gram 模型中，N 表示分解的句子中词的数量，其中第N 个词的出现只与前N-1 个词有关，而与其他词无关［8］。常用的N-gram模型有Bi-gram模型和Tri-gram模型。

（1）Bi-gram。即N=2 时的N-gram 模型（二元模型），指一个词的出现只依赖于它前面出现的那一个词，使用该模型对“我爱学习”这句话进行分解可得：｛我，爱｝、｛爱，学｝、｛学，习｝。

（2）Tri-gram。即N=3 时的N-gram 模型（三元模型），指一个词的出现只依赖于它前面出现的那两个词，使用该模型对“我爱学习”这句话进行分解可得：｛我，爱，学｝、｛爱，学，习｝。

如何使用N-gram 模型对代码进行相似度计算就要引入N-gram 距离概念。N-gram 距离通过衡量两个句子之间的差异来实现相似度计算。按长度N 对原句进行分词处理，得到所有长度为N（单词数量为N）的字符串。对于两个句子S 和T，通过计算他们公共子串的数量得到两者的相似度。N-gram 距离计算公式如下：

1.2 向量空间方法

本文的向量空间指将源码文本向量化，一般通过对文本分词、去停用词、编码、向量化这几个步骤完成对文本中词的向量化，再通过权重叠加法或模型法获取文本（句子、段落、文章）的向量，这实际上是一种将源码文本表示成低维、稠密、实数向量的方法。

1.2.1 TF-IDF 方法

TF-IDF 是一种统计方法，用以评估某个字词对于一个文件集或一个文件的重要程度，其思想是：在一篇文章中，某个词的重要性与该词在这篇文章中出现的次数正相关，与语料库中出现该词的文章数负相关。

TF（Term Frequency）：词频，指一个词在文章中出现的频率，表示这个词与该文章的相关性。这个数字是对词数的归一化，以防止它偏向长文件。TF 值计算公式如下：

IDF（Inverse Document Frequency）：逆向文件词频，表示一个词语出现的普遍程度。一个词的IDF 值可以通过文章总数除以包含该词的文章数，再将得到的商取以10 为底的对数。但是可能存在没有任何一篇文章包含这个词的情况，这会导致分母为0，为了防止该情况发生，分母通常会加上1。最终的IDF 值计算公式如下：

一篇文章中某个词的重要程度，可以标记为词频和逆向文件词频的乘积，某个词对文章的重要性越高，它的TFIDF 值也就越大，就认为其具有很好的类别区分能力。TFIDF 值计算公式如下：

余弦相似度通过测量两个向量夹角的余弦值确定两个向量大致指向是否相同从而来度量它们之间的相似性，该结果与向量的长度无关，与向量的指向相关。余弦相似度常用于高维正空间，例如在信息检索中，每个词项被赋予不同的维度，而一个维度由一个向量表示，其各个维度上的值对应于该词项在文档中出现的频率。余弦相似度因此可以给出两篇文档在其主题方面的相似度，计算公式如下：

1.2.2 基于Word2vec 的代码相似性

Word2vec 是2013 年Google 研发的一款用于训练词向量的工具，它将词语用向量表示，然后映射到向量空间进行处理，其核心架构主要有CBOW 模型和Skip-gram 模型［9-10］。本文采用CBOW 模型，该模型特点是可以通过上下文来预测当前单词，如图1 所示。

2 模型构建

2.1 基于TF-IDF 的模型

本文结合TF-IDF 模型构建基于词向量的模型。模型通过数据预处理器，将送入的源码集处理成一个文本矩阵，矩阵每一行代表一篇源码，一行中任一元素代表一个词。随后将文本矩阵送入TF-IDF 生成器，输出一个TFIDF 矩阵，其中每一行同样代表一篇源码，一行中的每一个元素为词的TF-IDF 值。最后送入相似度矩阵生成器得到一个相似度矩阵，每一行即为一篇源码的文本向量。模型结构如图2 所示。

Fig.1 CBOW model图1 CBOW 模型

Fig.2 TF-IDF model图2 TF-IDF 模型

2.2 基于Word2vec 的模型

Word2Vec 将每一个词都映射成向量，同时不断训练向量，从而提取出词与词之间的语义特征［11］，最后根据某些规则计算出词向量的文本向量。本文将数据集送入gensim库中的Word2vec 模型，获取所有词的词向量。通过对每一篇源码进行分词、去停用词处理后对所有词的词向量求和取平均，从而获得每一篇代码的向量，最后通过计算向量间的余弦值获得源码与源码之间的相似度（即余弦相似度）。模型结构如图3 所示。

Fig.3 Word2vec model图3 Word2vec 模型

3 实验结果与分析

3.1 数据集

本文将江苏师范大学教学科研辅助平台（http：//cstlab.jsnu.edu.cn）学生提交的课程作业作为数据集，包括35 个种类共905 篇C++源码，每个种类都代表一种功能实现（包含但不止于计算最大公约数、欧几里得算法、冒泡排序），每个种类的文件夹内包含数量不等的源代码文件。

3.2 实验过程

3.2.1 TF-IDF 实验过程

图4 为该实验的实验过程，第一个步骤是数据预处理，首先对所有C++源码使用jieba 库进行分词处理，然后保留需要的词，本文使用两种方法选择需要保留的词。实际上，这两种方法正好是相反的：

Fig.4 Experiment process of TF-IDF图4 TF-IDF 实验过程

（1）去停用词，去除如‘return’、‘define’、‘include’、‘main’、‘int’、‘bool’、‘｛’、‘｝’、‘；’等这类词，保留以外的词。

（2）在闭区间内选择需要保留下来的词，仅保留以下词，而去除其他词：

步骤（2）生成的文本向量，将每一篇源码TF-IDF 值相应设置为特征值，其余位置设置为0，这样形成一种类似于one-hot 编码的编码方式，为每一篇源码生成专属向量。

（3）将已生成的文本向量利用余弦相似度计算出任何两篇源码的相似度。

该实验的向量矩阵生成的部分伪代码如下：

3.2.2 Word2vec 实验过程

该实验步骤分为：数据准备、模型构建和模型评估三大步骤，如图5 所示。

Fig.5 Experiment process of Word2vec图5 Word2vec 实验过程

读取数据集中所有的数据，然后将其存入一个列表，随后将这个列表送入第二个过程中——模型构建，首先设置好模型训练的参数，然后开始构建模型。在第三个过程中，读取测试数据的源码内容进行分词处理，并通过模型获取分词后词的向量，将这些向量求和取平均处理后得到源码的特征向量，最后计算源码向量间的相似度并计算模型的F1-score。完成一次上述操作后，返回第二个过程，对模型构建的参数进行修改，重新构建模型，计算F1-score值。

计算两篇源码之间相似度的部分伪代码，输入值的前5 项皆为模型参数，最后两项为需要计算相似度的两篇源码，输出内容即为两者的相似度。

3.3 模型评判

阈值是一个分界线，用于判断两篇源码是否可以判定为相似：

（1）在N-gram 方法下，源码间的相似程度与N-gram 距离反相关，所以当相似度小于或等于阈值时，两篇源码相似；反之则两者不相似。

（2）在TF-IDF 和Word2vec 方法下，源码间的相似程度与余弦相似度正相关，因此当相似度大于或等于阈值时，认为两篇源码相似；反之则认为两者不相似。

确定任意两篇源码是否为相似的标记，选择实现同一功能（即在同一文件夹下的）源码标记为相似，标记为1；实现不同功能（即在不同文件夹下的）源码标记为不相似，标记为0。

每一篇源码与数据集中所有源码一一进行相似度计算，得到一个由相似度构成的二维矩阵。通过计算不同阈值下的F1-score 值并获取其中最大的F1-score 值然后根据该值来衡量一个模型相似度计算效果的优劣。F1-score 值取值范围为0 到1，数值越大认为模型的计算效果越佳。

F1-score 计算公式如下：

3.4 实验结果

表1 为N-gram 模型不同N 值的情况，它显示了模型在何阈值下能得到最大F1-score 值以及最大F1-score 值的具体数值。结果显示当N=2 时，该模型可以得到最大的准确值、召回值以及F1-score 值，具体数值分别为56.06%、69.67%和62.12%。

Tabel 1 Experimental result of N-gram model表1 N-gram 模型试验结果

表2 为选择保留词的两种不同方式下TF-IDF 模型的实验结果，结果表明在闭区间内选择保留词能够得到更高的F1-score 值和更高的准确度、召回值。从原理上分析可知，选择闭区间保留了源码的结构信息，而开区间仅保留语义、单词，并没有保留结构信息。

Table 2 Experimental result of TF-IDF model表2 TF-IDF 模型试验结果

图6 展示了Word2vec 模型不同参数下的实验结果，其参数数值从左往右分别是workers、size、sample 参数。在实验中，将参数min_count 和参数window 分别设置为1 和10除需要测试的参数和指定的参数之外，其他参数均为默认值，实验得到最高的F1-score 值为0.658 8。

Fig.6 Results of Word2vec models with different parameters图6 Word2vec 模型参数下的数据值

根据以上数据，可以得到N-gram、TF-IDF、Word2vec三个模型的最大F1-score 分别为0.621 2、0.775 9、0.658 8。

从方法原理上看，N-gram 方法只考虑到了词数量上的关系，而Word2vec 和TF-IDF 在考虑词数量的基础上还考虑到了结构、语义。因此基于空间向量的方法能够考虑的范围更广，对于C++代码相似检测更有效。实验结果表明，基于空间向量的方法在检测相似度方面效果确实比基于关键词的方法好。

4 结语

本文采用基于关键词的N-gram 方法、基于向量空间并通过结合TF-IDF 和Word2vec 的方法完成对C++源码的相似度计算。反复实验后的结果表明，基于空间向量的方法可以更加全面、准确反映代码之间的结构关系、语义关系。但实验还存在以下缺陷：①模型准确度不是很高；②各模型整体结构单一；③在识别粒度更小的结构上存在不足。

对于相似度计算，后续将在关键词、语义、语法、结构等方面设计更全面的检测方法。同时，使用基于CNN 的方法对C++源码进行相似度计算，以期解决相应不足并取得更好的效果。