相似度算法在源程序比较中的应用

朱利龙

"

摘要：在计算机程序课的教学过程中，时常需要对学生所提交的源程序进行检查，特别是源程序的重复率检查。纯人工对比不但花费时间长，而且效率低下。因此，本文提出利用文本相似度算法解决源程序对比的方法，并设计出相应的源程序比较系统，来帮助老师从繁重的工作中解脱出来。

关键词： 相似度；距离编辑算法；源程序对比

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）21-0214-01

源程序对比分析是一个复杂的过程，不仅需要考虑实用性和考虑准确性，而且还要兼顾运行效率等问题。在程序上机课的过程性考核中，很多同学提交的程序源代码之间重复率很高。本文借助计算机实现源程序的自动对比，不但可以降低劳动强度，提高工作效率，而且可以减少误判的可能性，进一步保证源程序对比结果的正确性。

1 特征提取

要获取源程序重复率，判断是否抄袭程度，可以通过计算源程序的相似率来代替。相似率越高说明源程序重复部分越多，学生抄袭的可能性越高。要计算代码的相似率，就得提取源代码的有关特征参数。

根据源程序块粒度大小不同，可以利用源程序中诸如换行符之类的分割符来分解成程序语句，分解得到的每一部分称为一个程序块。源程序块的选择将在很大程度上影响程序的效率，要比较源程序部分复制，就必须减少源程序块的长度。本文将每一个语句看成一个源程序块，即粒度大小为一条语句。于是，源程序就被分解为语句集合，源程序的相似程度便可以由语句的相似率来计算。因此，对于源程序的对比，选择程序语句作为源程序的对比粒度块是具有可行性的。

本文系统采用的是距离编辑算法，利用字符串的模式匹配实现对源程序相似度进行判断。把两篇源程序进行全文对比得出相似度；得出相似度后，根据源程序分隔符把两源程序分割成逐条语句的，然后对这些语句进行一一对比，得出语句的相似度；比较出来的超过语句的相似度的语句称为相似句，把相似句对应的原句进行红色标记；统计出相似句对应原句占原源程序的比例，在比较中可以通过红色显示相同。

2 距离编辑算法

距离编辑算法，简称为LD算法。该方法主要从源程序中选取一些源程序块，利用LD算法比较两源程序块字符串的相似性，由此得出比较子串相似度（即子串间的距离）。两个字符串距离就是一个字符串转换成另一个字符串过程中，进行添加、删除、修改等基本操作的次数，将源程序的语句作为字符串，借助LD算法对比代码间的距离，然后计算取其占代码长度的比例作为判断代码重复率，从而即可得到学生源程序的抄袭程度。如果两个源程序字符串的距离越大，就说明他们越不同。

该算法对两个字符串（句子或整篇源程序）进行对比，得出两个字符串之间的“距离”，然后根据相似度计算公式计算出两个字符串之间的相似度。下面给出了在Visual Basic编程环境下，利用递归法实现的算法代码。

Dim mA（） As Byte，mB（） As Byte 模块级变量，存放语句单元

计算编辑距离函数LD

Public Function LD（ByVal A As String，ByVal B As String） As Integer

mA = StrConv（A，vbFromUnicode） ：mB = StrConv（B，vbFromUnicode）

ReDim L（Len（A），Len（B）） As Integer

For i = 1 To Len（A）

L（i， 0） = i

Next

For j = 1 To Len（B）

L（0， j） = j

Next

For I = 1 To Len（A）

For j = 1 To Len（B）

If mA（I - 1） = mB（j - 1） Then

L（I， j） = L（I - 1， j - 1）

Else

L（I， j） = Min（L（I - 1， j - 1）， L（I - 1， j）， L（I， j - 1）） + 1

End If

Next

Next

LD = L（Len（A）， Len（B））

End Function

计算最小值函数Min

Public Function Min（ByVal A As Integer，ByVal B As Integer，ByVal C As Integer） As Integer

Min = IIF（A > B，A，B） ：Min = IIF（Min < C，Min，C）

End Function

3 源程序比较过程

在上述算法的基础上，本文所设计的源程序比较系统主要有三个步骤，该系统所对应的流程图见图1。

1）从存放源程序的数据库里取出程序代码，构成源程序集合。学生提交的程序代码都会被提炼出主要部分汇总到程序数据库中。在后期进行代码对比时，就可以直接从数据库中读取学生提交的源代码，甚至可以用于年级之间学生编程能力的纵向比较。

2）分割源程序并从中提取特征参数。本文使用语句结束标记或其他代码间隔符（如“空格”“换行”等）作为语句的天然分割符，刨除源程序中影响对比操作的无用代码，即程序通用框架部分，例如集成开发工具产生的代码，只保留学生自己编写的主要代码，然后借助系统提取相关的特征参数。

3）计算源程序相似度。从上一步分割得到的语句集合，计算出语句之间的编辑距离，其占语句长度的百分比即为语句相似度；将所有语句间的编辑距离累加作为源程序间的编辑距离，其占源程序代码长度的百分比就是源程序间的相似度；若相似度量值大于教师所给定的临界值，说明程序代码间的重复率过高，学生存在复制抄袭的可能，并通过颜色标示出重复部分，从而达到系统自动对比源程序的目的，而且可以提高学生的自律性和积极性。

4 总结

本文所设计的源程序比较系统，在程序类课程的教学过程中，已经作为该类课程过程考核手段之一，不仅帮助老师从繁重的工作中解脱出来，而且提高了学生的学习积极性。在今后将逐步引入数据挖掘的处理过程，以便可以实现程序类课程教学效果的纵向对比，从而更好促进程序类教学。

参考文献：

[1] 李俊民，赵东. 零基础学Visual Basic[M].北京：机械工业出版社，2010.

[2] 刘宏哲. 文本语义相似度计算[M]. 北京：电子工业出版，2014.

[3] 张宪超. 数据结构、算法及应用[M].北京：科学出版社，2012.

[4] 程海涛，王俏，卢亮，等.探索Visual Basic教学方法改革[J].科技信息，2011（12）：225.