程序相似性检测系统

福州大学 软件学院 软件工程 2007级（3）班 蔡丹莉程序相似性检测系统1. 问题提出第1个程序，功能：程序相似性检测入口参数(3个)：2个待比较的程序名和1个存放比较结果的文件名出口参数：程序相似度(0100之间的值)数据结构，算法描述，异常条件及处理方法描述，编程者/版本/版权，编程开始/结束时间，测试说明，其他需要说明的问题(参考文献、使用和移植限制)等。第2个程序，功能：成批程序相似性检测入口参数(3个)：1个存放待比较的所有程序名的文件名，1个存放相似度限制(1100之间的值，只有超过该值的程序才记录)，1个存放比较结果的文件名数据结构，算法描述，异常条件及处理方法描述，编程者/版本/版权，编程开始/结束时间，测试说明，其他需要说明的问题(参考文献、使用和移植限制)等。2. 目的和意义在各程序设计教程中，由于计算机数据的易复制性，导致许多学生抄袭他人程序作业，影响了成绩的公平性，然而使用传统人工方法检查作业抄袭不仅费时，且不准确，开发出一种智能检测系统，能够快速、高效、准确的检查出相类似的程序代码，减少学生的程序抄袭现象。3. 软件功能描述检测两个程序或多个程序代码之间的相似度D（0-100），D越大，相似程度越高，反之，D越小，相似度越小，并根据相似度大小，将相似度(D70)的定为低度相似，将相似度(80D90)的定为中度相似, 将相似度(90D100)的定为高度相似函数(模块)和主要算法的描述根据两个程序代码之间存在的相似性问题,采用属性计数与目标代码对比相结合的思想实施相似性代码的检测,实现对输入程序代码相似度和评价结果的获取.同时运用最长公共子序列(Longest Common Subsequence,LCS)算法来对比两个源程序文件在结构上的相似性。采用面向对象的功能模快设计思想，在构建属性数据库的基础上，设计预处理模快，属性检测模快，相似目标代码检测模快和相似度评价模快等五大功能模快预处理模快:1.冗余处理模块(包括去掉预处理命令,去除标准输入输出毫不语句,去除注释,去除程序中的空白字符和空行)2.分词模块属性检测模快: 物理属性 程序代码的总行数,物理容量,总的词数,总的字符数 Halstead属性:总的字符数,唯一的标志符数,用户定义的标识符数,程序的Halstead容量相似目标代码检测模快:用最长公共子序列(Longest Common Subsequence,LCS)算法相似度评价模快.通过对五个模快的处理,实现了对程序相似性的检测主要算法是：最长公共子序列(Longest Common Subsequence,LCS)算法, 字符串哈希函数（著名的ELFhash算法）,权重系数的计算.4. 数据结构定义了一个文件流类 class Cppout();5. 其出说明(环境, 总结与体会等)系统软件设计开发基于Visual C+ 6.0的开发平台6. 总结与体会 通过课程设计培养了我的动手能力以及综合运用所学的C+语言基础理论，基础知识，基本技能,进行程序分析和程序开发，提高在实际开发中解决问题的能力，达到了能够利用C+语言进行应用程序的规划，分析，设计和实施，更能进一步使我对这门语言有深刻的理解和更好的得到巩固，更能对我所学的知识得到检验。在本题中,因为没有提前去查找相关材料和时间的关系只写了程序的预处理模快(编译还没通过),而且本题对我来说确实有一定的难度,从中我认识到了自己与其他好的同学的差距,今后我一定要经常编程,经常实践,只有更加努力才能让自己不断进步.虽然只写了一小部分且还存在着错误,敬请老师指正！7. 致谢在这里，我要感谢老师一直以来对我们的耐心指导和讲解和那些在这次课程设计中给予我热心助人的同学们。同学间的相互帮助，相互讨论更让我们有了一个良好的学习氛围，促进了大家彼此之间的相互进步。 8. 参考文献 C+程序课件 王灿辉C+程序设计 钱能 清华大学出版社 C+程序设计试验指导 钱能 清华大学出版社 C程序相似代码识别方法的研究与实现 张鹏 硕士学士学位论文C+Primer中文版 Stanley B.Lippman Josee Lajoie Barbara E.Mo 人民邮电出版社9. 附录程序清单/自己写的预除理模块#include #include #include #include#include#includeusing namespace std; class Cppout public: vector &l; string line; void Erase(ifstream &in) int total(vector &l); int xunhuan(vector &l); int totalfor_while(vector &l); int :totalif_switch(vector &l); int lines(vector l); ; /删除空格,预处理命令,输入输出语句,注释 void Cppout:Erase(ifstream &in) string line; do int pos=0; int size=line.size(); line=getline(in,Line); /删除空格 if(line.empty() continue; /删除预处理命令 if(line.begin()=#) line.erase(line.begin(),line.end(); continue; /删除输入输出语句 while(posline.size() if(string s1=line.substr(pos,4)&s1=cout) line=line.erase(line.begin(),line.end();break; else if(string s2=line.substr(pos,3)&s2=cin) line=line.erase(line.begin(),line.end();break; else if(string s3=line.substr(pos,5)&s3=scanf) line=line.erase(line.begin(),line.end();break; else if(string s4=line.substr(pos,6)&s4=printf) line=line.erase(line.begin(),line.end();break; pos+; /删除注释 for(;posLine.size();pos+) getline(in,Line); if(Linepos=/&Linepos+1=-) if(int i=pos & Linepos=) else l.push_back(line); while(getline(in,Line); /统计行数 int Cppout:totalhang(vector &l) return l.size(); /统计for和while循环次数 int Cppout:totalfor_while(vector &l) int i1,i2,i3,i,j,k; for(i=0;il.size();i+) for(j=0;jline.size();j+) if(string s1=line.substr(i,3)&s1=for) i1+; else if(string s2=line.substr(i,5)&s2=while) i2+; j=i1+i2; return k; /统计if和switch次数 int Cppout:totalif_switch(vector &l) int i1,i2,i3,i,j,k; for(i=0;il.size();i+) for(j=0;jline.size();j+) if(string s1=line.substr(i,2)&s1=if) i1+; else if(string s2=line.substr(i,6)&s1=switch) i2+; k=i1+i2; return k; /统计重复字的次数 int Cppout:totalsames(vector&l) int i,j; for(i=0;il.size();i+) for(j=0;jline.size();j+) string m; mi=linek; j+; return j; /主函数 int mainstring example1;string example2;cout欢迎进入程序相似性检测系统!endl;coutexample1;ifstream in(example1.c_str();if(!in)cout读取打开文件时出错!不能打开此文件或文件不存在! endl; cout 按任意键退出系统!endl;getch（）；exit(1); coutexample2;ifstream in(example2.c_str();if(!in)cout读取打开文件时出错!不能打开此文件或文件不存在! endl; cout 按任意键退出系统!endl;getch（）；exit(1); return 1;/以下的LCS算法是参考的别的同学的，我还没写，做为自己的参考/最长公共子序列(Longest Common Subsequence,LCS)算法(#include #include using namespace std;string:size_type LCS_Length(string x,string y,int *b,int m,int n)/cij表示xi-1,yj-1之前公共子序列的长度,i表示x数组前进，j表示y数组前进/不用cij表示xi,yj之前公共子序列的长度是因为需要使用c00来表示没有公共子序列，/即c00恒等于0，因此c数组最大下标为cm+1n+1int *c;int count = 0;int i = 0;int j = 0;/ 动态申请二维数组cc=new int*m+1;for(i=0;im+1;i+)ci=new intn+1;for(i=0;im+1;i+)ci0=0;for(j=0;jn+1;j+)c0i=0;for(i=1;i=m;i+)for(j=1;j=n;j+)if(xi-1=yj-1)/找到一个公共“字符”cij=ci-1j-1+1;/公共子序列的长度在原来的基础上加1bij=0;/做一个辅助标志，表示要达到目前的长度，x，y数组均需“前进”一步/即xi-1，yj-1都要作出贡献cout xi-1;/cout 相同的字符: xi-1;/+count;/cout 总的相同的个数为: count =cij-1)cij=ci-1j;/当前最长公共子序列可以不需要xi-1bij=-1;/和上面分析类似elsecij=cij-1;/当前最长公共子序列可以不需要yj-1bij=1;/ 释放动态申请的二维数组cfor(i=0;im+1;i+) delete ci;ci=NULL; / 为避免下次被使用,将指针赋值为NULL(空) delete c; c=NULL; return x