基于改进GST算法的字符串相似度检测

doi:10.13438/j.cnki.jdzk.2021.05.006

吉首大学学报（自然科学版） ›› 2021, Vol. 42 ›› Issue (5): 34-37.DOI: 10.13438/j.cnki.jdzk.2021.05.006

基于改进GST算法的字符串相似度检测

孙宇扬，欧云，奉松绿，周恺卿

（吉首大学信息科学与工程学院，湖南吉首 416000）

出版日期:2021-09-25 发布日期:2022-01-18
通讯作者: 欧云(1979—)，男，湖南衡阳人，吉首大学信息科学与工程学院讲师，硕士，主要从事群智能算法及其应用研究.
基金资助:
湖南省教育厅科学研究重点项目(19A414)；吉首大学校级科学研究项目(14JD027)；吉首大学校级科研项目(JDX21021)；2021年吉首大学大学生创新创业训练计划项目（教通[2021]21号130）

String Similarity Detection Based on Improved GST Algorithm

SUN Yuyang， OU Yun， FENG Songlyu， ZHOU Kaiqing

(College of Information Science & Engineering， Jishou University， Jishou 416000， Hunan China)

Online:2021-09-25 Published:2022-01-18

摘要/Abstract

摘要：为了降低贪婪模式匹配(GST)算法的运行时间，提高字符串相似度检测效率，提出一种将改进KR算法与GST相结合的字符串相似度检测算法.以学生作业源代码作为实验数据，对改进算法和GST算法进行了性能测试，结果表明，改进算法能够在较少的比较次数情况下达到与GST算法类似的查重结果.

关键词： 字符串, 相似度, 近似匹配, 贪婪模式匹配算法, 随机串匹配算法

Abstract: 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.

Key words: string, similarity, approximate matching, greedy pattern matching algorithm, Karp-Rabin algorithm

孙宇扬, 欧云, 奉松绿, 周恺卿. 基于改进GST算法的字符串相似度检测[J]. 吉首大学学报（自然科学版）, 2021, 42(5): 34-37.

SUN Yuyang, OU Yun, FENG Songlyu, ZHOU Kaiqing. String Similarity Detection Based on Improved GST Algorithm[J]. Journal of Jishou University(Natural Sciences Edition), 2021, 42(5): 34-37.

基于改进GST算法的字符串相似度检测

String Similarity Detection Based on Improved GST Algorithm

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价