摘要
为了降低贪婪模式匹配(GST)算法的运行时间,提高字符串相似度检测效率,提出一种将改进KR算法与GST相结合的字符串相似度检测算法.以学生作业源代码作为实验数据,对改进算法和GST算法进行了性能测试,结果表明,改进算法能够在较少的比较次数情况下达到与GST算法类似的查重结果.
To reduce the running time and improve the efficiency of string similarity detection,an improved string similarity detection algorithm is proposed utilizing the improved KR algorithm and GST algorithm.Using students'homework source code as the experimental data,the performance of the improved algorithm is tested,and the results show that the improved algorithm can achieve the duplicate check result similar to GST in less fewer comparison times.
作者
孙宇扬
欧云
奉松绿
周恺卿
SUN Yuyang;OU Yun;FENG Songlyu;ZHOU Kaiqing(College of Information Science & Engineering, Jishou University, Jishou 416000, Hunan China)
出处
《吉首大学学报（自然科学版）》
CAS
2021年第5期34-37,共4页
Journal of Jishou University(Natural Sciences Edition)
基金
湖南省教育厅科学研究重点项目(19A414)
吉首大学校级科学研究项目(14JD027)
吉首大学校级科研项目(JDX21021)
2021年吉首大学大学生创新创业训练计划项目(教通[2021]21号130)。
关键词
字符串
相似度
近似匹配
贪婪模式匹配算法
随机串匹配算法
string
similarity
approximate matching
greedy pattern matching algorithm
Karp-Rabin algorithm
