如何快速计算两个字符串之间的相似度

我的想法: 对所有要比较的代码段进行词法分析，并将它们转换为特定的标记字符串，然后自己制定转换规则. 然后，比较令牌串以确定代码之间的相似性，从而确定代码之间的抄袭程度. 在将这两个代码转换为令牌字符串后，基于算法RKR-GST（running-karp-rabin贪婪字符串-平铺）算法，循环将找到两个令牌字符串不匹配部分的最大公共子字符串，将其替换与空格，并根据公式找到两个令牌字符串A和B的相似性. 源代码#include #include #include #include #include #include #include #define N 10000#define M 10000#define MAXSTRLEN 10000 //定义最大字符串长度typedef int状态; typedef unsigned char SString [MAXSTRLEN +1]; //字符串SString a [3] = {“ int”，“ long”，“ short”}的固定长度顺序存储表示； SString b [2] = {“ float”，“ double”}; SString c [15] = {“ &&”，“ ||”，“ ++”，“-”，“ +”，“-”，“ *”，“ /”，“ =”，“> =” = “，” <=“，” ==“，”！ =“，”>“，” <“}; SString d [12] = {” [“，”]“，” {“，”}“，”（“，”）“，”，“，”;“ ，“'”，“#”，“;”，“. ”}; SString e [29] = {“ auto”，“ break”，“ case”，“ char”，“ const”字符串相似度匹配，“ continue”，“默认为“，”执行“，” else“，”枚举“，” extern“，”为“，goto”，“ if”，“ main”，“ printf”，“ register”，“ return”，“ signed” ，“ sizeof”，“ static”，“ struct”，“ switch”，“ ty pedef”，“ union”，“ unsigned”，“ void”，“而”，“ volatile”}； HANDLE hOut；编写的DWORD； void ShadowWindowLine（char * str）; char类型（char * str）; void令牌（char name []，char list []，char token []，FILE *表）; void simple（int MinMatchLen，FILE * fp1，FILE * fp2）;状态替换（SString s，int pos，int len，int Ls）; int复制（float n）; void ShadowWindowLine（char * str）{SMALL_RECT rc; CONSOLE_SCREEN_BUFFER_INFO bInfo; //窗口缓冲区信息WORD att0，att1， attBack; int i，chNum = strlen（str）; GetConsoleScreenBufferInfo（hOut，＆bInfo）; //获取窗口缓冲区信息//计算显示窗口的大小和位置rc.Left =（bInfo.dwSize.X-chNum）/ 2-2; rc.Top = 8; // bInfo在原始代码段.dwSize.Y / 2-2中，但是如果您的DOS屏幕具有垂直滚动条，则需要下拉滚动条才能看到它，为方便起见，将其更改为10rc. = rc.Left + chNum + 4; rc.Bottom = rc.Top + 4; att0 = Background_RED | Background_BLUE; //阴影属性att1 = FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY | BACKGROU ND_RED |背景|蓝色| Background_INTENSITY; //文本属性attBack = Background_RED | Background_GREEN |背景|蓝色| Background_INTENSITY; //背景属性//设置阴影并填充COORD posShadow = {rc.Left + 1，rc.Top + 1}，posText = {rc.Left，rc.Top}，posBack = {0,0};对于（i = 0; i <25; i ++）{FillConsoleOutputAttribute（hOut，attBack，80，posBack，＆写）; posBack.Y ++;}用于（i = 0; i <5; i ++）{FillConsoleOutputAttribute（hOut字符串相似度匹配，att0，chNum + 4，posShadow，＆写）; posShadow.Y ++;}表示（i = 0; i <5; i ++）{FillConsoleOutputAttribute（hOut，att1，chNum + 4，posText，＆写）; posText.Y ++;）//编写文本和边框posText.X = rc.Left + 2; posText.Y = rc.Top + 2; WriteConsoleOutputCharacter（hOut，str，strlen（str），posText，和书面）; SetConsoleTextAttribute（hOut，bInfo.wAttributes）; //恢复原始属性} char type（char * str）//此函数判断单词类型{int i; for（i = 0; i <3; i ++）// {if（strcmp（str，a [i]）== 0）中的关键字返回'K';} for（i = 0; i <2 ; i ++）/ b中的关键字{if（strcmp（str，b [i]）== 0）返回'E';} for（i = 0; i <15; i ++）// c中的符号（if（strcmp（str，c [i]）== 0）返回'A';}（i = 0; i <12; i ++）// {if（strcmp（str，d [ i]）== 0）返回'R';} for（i = 0; i <29; i ++）// e关键字{if（strcmp（str，e [i]）== 0）返回'Y ';} if（isdigit（str [0]））// 0-9是一个数字{return'N';} //常规变量和字符if（！Isalnum（str [0]））返回'H';否则返回'C'; //变量} void令牌（字符名称[]，字符列表[]，字符令牌[]，FILE *表）//分别剪切两个文件中的字符串令牌字符串{FILE * in， * out; char ch，c，缓冲区[N]，*链接[M]; int i = 0，j = 0，k = 0，LenLink = 0; if（（in = fopen（name，“ r +”） ）== NULL）{printf（“无法打开源文件！\ n”）;退出（0）;} if（（out = fopen（list，“ w +”））== NULL）{printf（ “文件写入失败！\ n”）;退出（0 ）;} if（（table = fopen（token，“ w +”））== NULL）{printf（“文件写入失败！ \ n“）; exit（0）;} while（！feof（in））//读取逐字读取文件{ch = fgetc（in）; if（ch =='\ t'|| ch ==''| | ch =='\ n'）//删除空格，制表符，回车继续； if（isalpha（ch））//如果第一个字符是字母（while（isalnum（ch）&&（i '|| ch =='<'|| ch = ='！'） //以下代码实现了高级搜索{if（（（c = fgetc（in））=='='）//> =，<= ,! =必须将它们视为符号{buffer [i ++] = ch;缓冲区[i ++] = c;缓冲区[i] ='\ 0';链接[j ++] =（char *）malloc（sizeof（char）* 3）; strcpy（链接[j-1]，缓冲区）； i = 0;} else {buffer [i ++] = ch;缓冲区[i] ='\ 0';链接[j ++] =（char *）malloc（sizeof（char）* 2）; strcpy（链接[j-1]，缓冲区）； i = 0； fseek（in -1L，1）;}}否则if（ch =='+'|| ch =='-'|| ch =='＆'|| ch =='|'|| ch == '='）{if（（c = fgetc（in））== ch）// ++，-，&&，||，==这些必须视为符号{buffer [i ++] = ch;缓冲区[i ++] = c;缓冲区[i] ='\ 0';链接[j ++] =（char *）malloc（sizeof（char）* 3）; strcpy（链接[j-1]，缓冲区）； i = 0;} else {buffer [i ++] = ch;缓冲区[i] ='\ 0';链接[j ++] =（char *）malloc（sizeof（char）* 2）; strcpy（链接[j-1]，缓冲区）； i = 0； fseek（in，-1L，1）;}} else //其他符号{buffer [i ++] = ch;缓冲区[i] ='\ 0';链接[j ++] =（char *）malloc（sizeof（char）* 2）; strcpy（链接[j-1]，缓冲区）； i = 0;}}}} LenLink = j-1; //存储在链接中的总长度（i = 0; i maxmatch）{maxmatch = k; x =我; y = j;}}} if（maxmatch> MinMatchLen）{replace（A，x，maxmatch，La）;替换（B，y，maxmatch，Lb）; La = La-maxmatch + 1; Lb = Lb-最大匹配+ 1; MatchLen + = maxmatch;} if（ch =='Y'|| ch =='y'）{printf（“检查两个字符串中的匹配字符串％d次\ n”，a）; ++; for（s = 1; s <= La; s ++）printf（“％c”，A [s]）; printf（“ \ n”）; for（s = 1; s <= Lb; s ++）printf（“％c”，B [s]）; printf（“ \ n”）;}} while（maxmatch> MinMatchLen）; printf（“ \ n没有可以匹配的公共子字符串\ n”）; n =（2.0 * MatchLen）/（lena + lenb）; printf（“公共子字符串的总长度为％d，”，MatchLen）； printf（“根据公式\ n”）； printf（“ \ t \ t —————————————————————————— printf（“ \ t \ t |相似度=（2×公用子字符串长度）÷（字符串A长度+字符串B长度）| \ n”）； printf（“ \ t \ t —————————————————————————— printf（“这两个代码字符串的相似度为％f \ n”，n）;复制（n）;} status replace（SString s，int pos，int len，int Ls）//使用空格替换两个令牌字符串中最大的匹配子字符串{int i;如果（pos <1 || pos> Ls-len + 1 || len <0）返回0; s [p os] =”； for（i = pos + len; i <= Ls; i ++）{s [i-len + 1] = s [i];} return 1;} int copy（float n）//此函数判断是否{窃{printf（“ \ n相似度超过0.8，被认为是窃”）；如果（n> = 0.8）printf（“ \ n这两个代码涉嫌抄袭，请做进一步检查”）； （“ \ n这两个代码均不涉嫌pla窃”）； return 0;} void main（void）{hout = GetStdHandle（STD_OUTPUT_HANDLE）; //获取标准输出设备句柄SetConsoleOutputCP（936）; //设置代码页，此为简体中文ShadowWindowLine（“欢迎使用C语言代码复制/相似性检测软件”）； getchar（）;系统（“ cls”）； //清除屏幕上的char name1 [50];字符名称2 [50]; //存储输入文件路径字符串FILE * f1，* f2;系统（“颜色F3”）； printf（“ \ nCode1: ”）; scanf（“％s”，name1）;令牌（名称1，“ f: \\ list1.txt”，“ f: \\ token1.txt”，f1）； printf（“代码2: ”）； scanf（“％s”，name2）;令牌（name2，“ f: \\ list2.txt”，“ f: \\ token2.txt”，f2）; printf（“ \ ntoken字符串已成功生成，”）; getchar（）;简单（3，f1，f2）;}

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-206447-1.html