APP下载

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

2016-10-18朱利龙

电脑知识与技术 2016年21期
关键词:相似度

朱利龙

"

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

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

中图分类号: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.

猜你喜欢

相似度
改进的协同过滤推荐算法
模糊Petri网在油田开发设计领域的应用研究