原创《程序代码抄袭检测中串匹配算法》：此文是一篇程序代码论文范文,为你的毕业论文写作提供有价值的参考。
【 摘 要 】 为了保证程序设计课程实践教学质量,避免学生抄袭,可以检测学生的源程序,代码的相似度是抄袭检测的关键技术.文章介绍了一种串匹配算法——GST算法,包括GST算法的核心思想以及伪代码实现.
【 关键词 】 程序代码抄袭检测；GST算法；相似度
1 引言
程序设计课程是高等学校计算机专业中的核心课程,这些课程的实践教学环节都需要学生在程序环境内编写程源代码,而这些在计算机上的代码很容易被复制抄袭,为了保证实践教学的质量和学生评价的公平客观,防止学生抄袭,需要对程序代码进行抄袭检测.若教师人工进行比较检查,工作量非常大,且不能做到完全准确.现在通过比较代码优化后的目标代码检测已经非常有效,能在很大程度上提高教师的检测抄袭的效率,节省大量的工作时间.源代码抄袭检测可以使用代码相似度度量技术,若想判断两个源程序代码是不是存在复制,实质上就是对其相似程度进行度量,按照度量结果给出一个相似度的数值表示,然后由这个值判断程序之间是否存在抄袭.
文中的代码抄袭检测程序就是采用串匹配算法—GST算法（贪婪式字符串匹配算法）来寻找两段程序代码的最大公共子串,然后计算两个程序的相似度.
2 程序代码抄袭检测技术概述
2.1 程序代码抄袭
比较普遍的抄袭是直接拷贝,也有将程序简单修改,比如增加注释或更改标识符等.其实,对于大多数的抄袭都属于“词汇级”的.
2.2 基于串匹配方法的程序代码抄袭检测技术
基于串匹配方法的程序代码抄袭检测过程可分为两个步骤：第一步：对待检测的程序源代码进行分析,然后将其标记,转化形成特定的标记（Token）串；第二步：比较两个程序的标记（Token）串,以便确定程序代码间存在的相似性,计算相似度的数值,根据数值确定代码之间是否存在抄袭,以及抄袭的程度.
2.2.1程序源代码转化为标记（Token）串
在程序检测比较之前,将程序分解出词法元素,与程序结构不相关的注释等表面元素需去除,代表结构的信息元素需保留,这样会使相似性比较得到的结果更准确.格式化就代表着需要用标记串去替换某些词法元素.某些元素的改变将直接影响到语义或程序结构的改变,则不需对其进行规格化,反之,则要进行规格化处理.
2.2.2 通过比较两个标记串来确定程序代码之间的相似度值
从两个标记串的第一个字符开始比较两个标记串的每个字符,尽可能的扩展匹配,直到两个标记串对应元素不匹配或者任意一个标记串已经读完时,表示当次匹配完成.接着将这一次匹配的长度与上一次的相比较,假如比上一次的匹配长度长,就丢掉以前的所有公共字串的记录,只将此次的匹配串纪录下来.如果等于上次匹配的长度,则将本次的匹配串纪录下来.
当两个标记串的所有字符匹配结束时,计算出所有公共子串的总长度.然后对两个标记串中对应公共子串位置的字符设置标记.设置标记后,这些字符在之后查找中不会被重新匹配.便于进行下一轮的最大公共匹配子集的查找.
然后继续进行查找,重复上面的工作.直到再也找不出最大公共子串,整个过程结束.
最后根据求出最大公共子串的总长度和两个标记串的长度计算两个程序代码的相似度值.
2.3 相似度
程序段间的相似度可用它们对应的标记串中全部公共子串在整个串中所占的百分比表示.
Similarity （M,N）等于2 × MatchLen/（| M | + | N |）
MatchLen 等于∑match （j, k, length） ∈matches
式中： | M |和| N |为标记串 M串与N 串的长度.match（j,k,length）表示某公共子串在M和N中起始位置分别为j与k, length表示其长度.matches为公共子串集合.
本文的程序代码抄袭检测程序中,我们人为规定相似度等于1时,两个程序完全是抄袭.相似度在1到0.9之间时,两个程序之间有抄袭的可能；相似度小于0.8时,两个程序抄袭的可能性就非常小了.
3 程序代码抄袭检测技术中串匹配算法
3.1 最长公共子串
最长公共子串问题指的是求出给定的一组字符串的长度最大的共有的子串.如果将字符串看成由多个子串组成,则其相似度可用全部公共子字符串在整个字符串中所占的百分比表示.
3.2 GST算法描述
先定义一个集合matches{},在这集合中每个元素match都是一个最大匹配串,且每个元素match相互之间都不重叠.例如：s1等于”main（）{int a等于3；int b等于4；int s；s等于a+b；cout< 该算法的伪代码如下： 1 double part2 （string A,string B）{ 2 La 等于Length （A）； 3 Lb 等于Length （B）； 4 matchlen 等于 0； 5 do{ 6 maxmatch 等于MinLen； 程序代码论文参考资料： 结论：程序代码抄袭检测中串匹配算法为关于本文可作为相关专业程序代码论文写作研究的大学硕士与本科毕业论文程序代码论文开题报告范文和职称论文参考文献资料。
