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

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

(吉首大学信息科学与工程学院，湖南 吉首 416000)

字符串相似度检测是计算机领域的基础研究问题之一，在抄袭检测系统[1]、防代码剽窃系统[2]、自动评分系统和生物DNA序列匹配[3]等领域都有非常广泛的应用.字符串近似匹配算法有编辑距离算法(Levenshtein Distance，LD)、最长公共子串算法(Longest Common Subsequence，LCS)、贪婪串匹配算法( Greedy String Tiling，GST)[4]等.

GST是字符串近似匹配的经典算法的代表[5].该算法设计的目的是为了检测2个字符串的相似度.由于算法执行过程中采取字符串逐个比较的机制，因而GST存在效率低、时间复杂度较大、扫描时间长等缺陷[6].徐黎明等[4]提出了一种将克努特-莫里斯-普拉特算法(Knuth-Morria-Pratt，KMP)和GST算法相结合的改进算法来提升GST算法的扫描速度.巫喜红等[7]采用2次Hash函数和双向并行匹配方法改进随机串匹配(Karp-Rabin，KR)算法，提高了模式匹配速度.金恩海等[8]将LCS算法应用到GST算法中的数据预处理阶段，提升了算法的准确性.受以上研究启发，笔者拟设计一种改进的双向的KR算法，并将其应用到GST算法中的扫描阶段，以期减少字符的比较次数，提高字符串相似度检测算法的运行效率.

1 相关概念和技术

1.1 GST算法

GST算法通过反复对模式串和文本串遍历搜索来实现字符串匹配功能，其中较短的字符串被称为模式串，较长的字符串则被称为文本串[5].GST算法的基本原理为：若比较的2个字符串相同，则返回一个与较短字符串的长度相同的值，反之，则返回最小值0.

1.2 KR算法

KR算法是使用散列函数从文本中搜寻单个模式串的字符串搜索算法[6].其算法思想为：定义一个Hash函数，利用Hash函数先对模式串进行数值化，得到一个散列码；……