2023年7月20日发(作者：)

基于GST字符串近似匹配算法的研究

徐黎明

【摘 要】GST算法作为字符串近似匹配的经典算法,被广泛应用于防剽窃系统中,而针对匹配信息量大,GST算法效率严重下降的问题,提出了一种基于KMP算法的改进算法,该算法主要是在scan-pattern阶段对GST算法进行改进,同时融合了传统GST算法局部最大存储技术,从理论分析KMP-GST算法所需要的时间可以从最初的O(n^3)提高到O(m+n)的线性时间,并通过实验验证改进后的KMP-GST算法的执行效率明显高于GST算法和RKR-GST算法.

【期刊名称】《内蒙古科技与经济》

【年(卷),期】2016(000)007

【总页数】3页(P87-89)

【关键词】近似匹配;GST算法;KMP算法

【作 者】徐黎明

【作者单位】北京物资学院,北京 101149

【正文语种】中 文

【中图分类】TP391

字符串匹配问题一直作为计算机领域的基础性研究课题，其中字符串精确匹配研究已经发展到比较成熟的阶段。但在实际应用中，字符串近似匹配的应用范围更加广泛，如信息查询和提取、防剽窃系统、自动评分系统、DNA序列匹配、语音识别、OCR纠错等领域。字符串近似匹配算法有编辑距离(Levenshtein Distance，LD)算法、最长公共子串(Longest Common Subsequences，LCS)算法、贪心字符串匹配(Greedy String Tiling，GST))算法、RKR-GST(Running Karp-Rabin Greedy String Tiling)算法。

GST算法作为字符串近似匹配经典算法，一直被广泛应用于防剽窃系统、文本分类领域，但GST算法在处理字符串匹配的过程中存在效率低、扫描时间长的缺点，而Wise采用KR算法对GST算法的scanpattern阶段进行了改进，形成了著名的RKR-GST算法，与GST算法相比，RKR-GST算法的效率有了明显的提高。但RKR-GST算法依赖于hash散列函数的选择，hash散列函数选择不恰当，反而会影响GST算法的效率。笔者针对GST算法进行改进，提出了一种基于KMP算法的改算法—KMP-GST算法，从而明显改善了GST算法的效率。

贪心字符串匹配(Greedy String Tiling，GST)算法,是由澳大利亚悉尼大学Michael Wise设计。介绍GST算法前先明确几个基本概念：①最大匹配(maximal-match)：是指在匹配过程中，模式串中从m处开始的子串Pm与文本串中从n处开始的子串Tn的最长可能匹配。②不匹配(non-match)：是指在逐个元素的比较过程中，遇到了一个不相同的元素或以作上了记号的元素。③tile：一个tile是一个P与T中匹配(一对一的)的子串，它永久且唯一。而对于生成的每一个最大匹配tile，对两个子串中的相应元素作上了记号，之后的匹配不再可用。④最小匹配长度(minimum-match-length，MML)：用来定义匹配所允许的最小长度，所有小于该长度的匹配将被忽略，其值可以为1，但一般取大于1的整数。

最大匹配三元组表示为max_ matches(m，n，j)，j是匹配的长度。如T=THEKRLDARITH,P=ARITHLDKR，当m=0，n=7时两字符串最大匹配字符串为“ARITH”，所以j=5,最大匹配三元组为max_matches(0，7，5)；在GST算法中，通过为最大匹配的标记作记号来组成一个“tile”(Wise称其为“tile”)，由多个“tile”组成“tiles”集合。对后续的最大匹配和“tiles”集合来说，已经作了记号的标记就不再可用了。这样，模式串P和文本串T中子串的元素就永久、唯一的对应起来了。一个“tile”用三元组表示为tile(m，n，j)。在上面的例子中，执行GST算法后，“tiles”集合包括tile(0，7，5)， tile(5，5，2)，tile(7，3，2)。

步骤一 循环移动T字符串与P进行比较，如果T[n+j]==P[m+j],则j++; 当j>maxmatch，把j的值赋给maxmatch，寻找局部的最大匹配值(贪心算法的核心思想)，当j的值局部最大时，把匹配子串的信息加入到matches?集合中，如公式(1)(2):

matches=matches∪match(a,b,j); (j==maxmatch)

matches=match(a,b,j); (j>maxmatch)

步骤二、两层循环执行结束后，将matches存入tiles中，并对已经匹配上的字符串进行标注。

tiles=tiles∪match(a,b,maxmatch)

步骤三、如果j>MML，则重复执行上边步骤一、二。

在算法处理过程中，我们通常把步骤一称为模式扫描(scanpattern)阶段，而步骤二称为作标记(markstrings)阶段。以T= THEKRLDARITH，P= ARITHLDKR，为例，第一次循环结束后，最大匹配的公共字符串为“ARITH”，长度为5，则最大匹配三元组为max_ matches(0，7，5)；在整个循环中只有一个长度为5的匹配字符串，所以matches集合中只有一个三元组(0，7，5)，对T与P匹配上的字符串进行标记。

j=5>MML,进行第二次循环匹配，其中“ARITH”字符串已经被标记，则不再进行循环匹配，移动T和P进行匹配，首先字符串“LD”匹配成功，产生局部最大三元组为max_ matches(5，5，2)，此时j=2,继续循环字符串“KR”匹配，max_ matches(7，3，2),长度也为2,根据公式(1);max_ matches(5，5，2)和max_ matches(7，3，2)都存入matches中，最后标记T与P相匹配的字符串。字符串P全被标记，循环结束。

Running Karp-Rabin Greedy String Tiling(简称RKR-GST)算法，该算法是基于Karp-Rabin算法对GST算法的扫描过程进行改进，从而优化GST算法的时间复杂度。串匹配随机 (Karp-Rabin，KR) 算法，该算法的基本思想是把长度为w的模式串看作是一个键(key)，而把文本串中每w个字符也看作是一个键。定义一个散列函数把这些键都映射为它们对应的散列值，那么显然只有那些与模式串具有相同散列值的文本字串才有可能与模式串匹配,所以,首先要确定w的长度,求步长w的过程是RKR-GST算法与GST算法的不同点。算法的主要循环从扫描(scanpattem)过程开始，这个过程返回w的一个新值，如果得到了一个较长的最大匹配数Lmax，算法则将Lmax的值赋给w,并重新开始搜索。否则，执行markstrings过程，即为最大匹配中所有未作记号的标记作记号。作记号过程结束后，如果w的值被更新为比最小匹配长度更小的新值，算法就结束了。否则，给w赋以新值并重新执行循环扫描过程。

与GST算法相比，RKR-GST算法主要对字符串扫描过程(scanpattern)进行了改进。scanpattem过程扫描文本文档中从Tn到Tn+w-1的文本串中未作记号的字符串并为其产生散列值。当这个过程执行完成后，会生成所有未作记号的标记的映射表，随后，为每一个从Pm到Pm+w-1的模式串生成散列值，并将其与文本串的散列值作比较，如果找到了相等的散列值，则对具有相同散列值的两个字符串进行比较。而markstrings过程RKR-GST算法与GST算法采用相同的结构。

计算模式串和文本串的第一个子串的散列值需要的时间为O(m)，而得到文本串其他子串的散列值所需的时间为O(n-m)；将模式串和文本串的所有散列值逐一比较，如果相等，再比较对应字符是否相等，所需时间为O(n-m+1)。但最坏情况下，RKR-GST算法的时间复杂度和GST算法一样，仍然是O(n^3)。然而，算法的平均时间复杂度在O(n)和O(n^2)之间。因此，实际上RKR-GST算法的效率要优于GST算法。

通过前面的分析可知，GST算法的时间主要应用在扫描比较中，每次扫描要进行(|P|- MML)*(|T|-MML)次比较，GST算法在扫描过程中是使用的蛮力字符串匹配 (Brute Force，BF) 算法实现的，为了提高扫描比较的效率，改进其时间复杂度，所以考虑在扫描过程中使用KMP算法，下面简单介绍一下KMP算法。

KMP(Knuth-Morris-Pratt)的基本思想，假设在模式匹配的进程中，执行T[i]和P[j]的匹配检查。若T[i]=P[j]，则继续检查T[i+1]和P[j+1]是否匹配。若T[i]≠P[j]，则分成两种情况：若j=1，则模式串右移一位，检查T[i+1]和P[1]是否匹配；若1

基于KMP算法改进的GST算法称为KMP-GST算法，KMP-GST算法的伪代码为：

titles<-{}

repeat

maxmatch<-MinimumMatchLength ; matches<-{} ;j<-0;

//利用模式串P的next函数求P在主串T中的位置的KMP算法

WHILE (nlength&&m<=P->length)

IF Pm+j=Tn=j&&unmarked(Pm+j) && unmarked(Tn+j) ;j<-j+1;//继续比较后续字符

ELSE{n=n+j; m=m+j; m=next[m]; } //模式串向右移动 END

IF (j = maxmatch) THEN {matches<-matches U match(m，n，j)}

ELSE IF (j>maxmatch THEN) {matches<-{match(m，n，j);maxmatch<-j}END

END FOR all match(m，n，maxmatch)∈matches do

FOR (j<-0 maxmatch-1 do) mark(Pm+j); mark(Tn+j);END

tiles<-tiles Umatch(m,n，maxmatch)

END

Untilmaxmatch = MinimumMatchLength

RETURN tiles

而求next[k]的伪代码为：

i=1;next[1]=0;j=0; //求模式串T的next函数值并存入数组next

WHILE (ilength)

IF (j==0||P->str[i-1]==P->str[j-1]){++i;++j;next[i]=j;}

ELSE j=next[j];

KMP-GST算法与传统的GST算法相比，在扫描过程中失配时不回溯，而是将模式串右移j-next(j)位，从而减少了比较的次数。

本文提出的KMP-GST算法对原有的GST算法的扫描阶段进行改进，这样扫描阶段的时间复杂度为O(m+n), KMP-GST算法所需要的时间为O(m+n)的线性时间，从而提高了GST算法的效率。KMP-GST算法与RKR-GST算法相比，效率更稳定，因为RKR-GST算法对hash散列函数的依赖性比较大，hash函数的好坏直接影响算法的效率。

为了评测改进算法的性能，本文实验数据为中国知网中随机下载100篇期刊，其摘要字数在200字～250字，作为模式串P，而正文内容在5 000字～6 000字之间，作为文本串T，在同一台计算机上分别利用GST算法、RKR-GST算法、KMP-GST算法进行字符串近似匹配计算，并统计每种算法匹配时的字符比较次数。

实验前提条件,3种算法的最小匹配长度MML初始值为1。RKR-GST算法的hash函数是通过汉字的ASCII建立的对应关系散列值，计算公式为：id=(c1-176)*94+(c2-161),其中，id是汉字对应的散列值，c1和c2是汉字的两个字节的ASCII码。按照这个公式“啊”的ASCII码为c1=176，c2=161，散列值计算得0；“阿”的176,162，散列值计算得1，…，最后“齄”的ASCII码为247 254，散列值计算的6767。如表1，为3种不同算法在100次匹配实验中字符比较次数的平均值，可见，改进KMP-GST算法的比较次数小于GST算法和RKR-GST算法的比较次数，见表1。

而且在100组数据的测试过程中，只有2次KMP-GST算法的运行时间略大于RKR-GST算法，可见KMP-GST算法具有很大的优越性。而在Wise的曲线拟合实验中得出RKR-GST算法的平均复杂度为O(n^1.12)，KMP-GST算法所需要的时间为O(m+n)的线性时间，所以，随着匹配的数据量的增加，KMP-GST算法的优势越突出。

随着当今信息量的日益增多，对处理信息效率的要求也越来越高，这也给信息查重和检索领域带来了新的挑战，笔者针对广泛应用于信息查重领域的GST算法进行改进，通过分析GST算法的scanpattern过程，提出了一种高效的近似字符串匹配算法KMP-GST算法，并通过实验验证了该算法在效率上有很大的改进。该算法已经应用于自主研发的防剽窃系统，系统效率高且稳定。