基于完全后缀数的滑动窗口字符串匹配搜索算法

1、基于完全后缀数的滑动窗口字符串匹配搜索算法摘要：字符串匹配是数据压缩、搜索引擎和信息检索等领域的一项关键技术，滑动窗口中的字符串匹配搜索是基于字典(LZ系列？)压缩算法的核心。后缀数组因其结构简单且空间占用低而被用在字符串匹配中以提高匹配效率，为克服现有基于后缀数组的滑动窗口字符串匹配算法在字典窗口滑动时需要重复构建后缀数组的缺点，本文提出完全后缀数组的概念，并根据滑动窗口的特点，利用后缀数组重构的有序性，进而提出一种新的滑动窗口字符串匹配搜索算法AAA，使得在窗口滑动时无需重复构建后缀数组，进而提高了字符串匹配的效率，理论分析和实验结果验证了AAA算法的有效性。关键字：字符串匹配 后缀数组

2、滑动窗口 完全后缀数组1 Introduction字符串匹配介绍，应用领域，主要作用(扩展成一段)。滑动窗口中的字符串匹配搜索是基于字典的压缩算法的核心，最初的来源是LZ77算法，基本思想是采用两个窗口加滑动的模式。一个窗口包含的是已输入数据流，并以此作为压缩字典DCT (Dictionary)，即搜索缓冲存储器，另一个窗口包含的是待压缩编码的字符串，称为前向缓冲存储器LAB(Look Ahead Buffer)。（此处增加简单描述这两个窗口的工作原理，一两句话既可）为了更好的压缩字符串，编码匹配时选择最长匹配字符串，在查找过程若发现存在多个最长匹配的字符串时，为简化编码一般选择最后一个匹配的

3、字符串。虽然理论上经典的字典压缩算法通过滑动窗口模式可以在线性时间内进行处理，但在实践中这些算法需要大量内存并且执行速率较慢。经典的字典压缩算法的时间主要消耗在查找最长的匹配串上，每次前向缓冲存储器在字典中查找到最长匹配字符串时，首先进行编码，然后窗口滑动，接着在新的字典上进行新一轮查找。也就是说，一次查找的效率决定了算法的效率。为解决经典字典压缩算法中查找匹配机制效率低下并需要大量内存的缺点，学者们开始寻找新的查找匹配机制。后缀树ST（Suffix Tree）和后缀数组（Suffix Arry）（这里简要介绍优点，并说明后缀数组比后缀树更优），所以，后缀数组开始作为字典压缩算法的基础数据结构

4、来进行查询优化。Artur J. Ferreira等在经典字典压缩算法与后缀数组结合方面做出突出贡献。文献101112对ST和SA两种结构进行了比较分析，研究结果表明，在处理字符串查找问题时，ST所需的内存消耗比SA大；且随字典大小线性增长，而SA却与文本输入无关；对于小字典来说，两者间几乎没有差异，而对于大字典来说，SA的压缩速度较ST快，而SA的压缩率却稍逊于ST。文献13 提出一种紧凑的方式来描述在一个“词袋”标签中的文本，以及一种在静态字典中，允许快速找到所有起始字为给定字符的快速索引机制，利用该机制可以提高字符串查找效率。文献14采用滑动窗口不断更新的特点，并结合SA和一个包含256

5、个ASCII码的辅助数组，来进行查找匹配。通过对DCT和LAB两个窗口字符的后缀进行排序，在窗口滑动时，LAB中的窗口字符将会滑入字典窗口中，而LAB的新内容将会从输入中继续读取, 通过不断更新两者的内容，来提高压缩效果。尽管采用后缀数组后，经典字典压缩算法在滑动窗口中进行字符串匹配查找的效率有了很大提高，但现有的算法还存在以下不足之处：(1)在滑动窗口中每次查找到最长匹配子串时，移动窗口后将得到新的窗口字符串，此时需要重构后缀数组，造成查找效率不理想。(2) 在对重复查找结果筛选时，结合算法还是根据经典字典压缩算法的查找机制，即当出现相同的匹配字符串时，算法选择最后一个匹配字符串，虽然这种机

6、制在压缩效率上提高了，但是没有考虑到时间复杂度。 (3)查找时采用二分查找，但由于待查的字符串一般集中在后缀数组的某个特定子区间内，因而没有使查找效率达到最优。针对上述前两个不足，本文通过分析滑动窗口和后缀数组结合后的特点，提出完全后缀数组的概念，进而提出一种新的滑动窗口字符串匹配算法AAA。论文的后续部分组织如下：第二章给出了相关术语定义，并给出了完全后缀数组的概念。第三章描述了基于完全后缀数组的滑动窗口下字符串匹配算法AAA的基本思想和算法的伪码，分析了提出的算法的时间复杂度和空间复杂度，并与现有算法进行了对比。为了更进一步论证提出的算法的优越性，第四章通过实验对算法的查找效率进行了比较和

7、分析。第五章对全文进行了总结。2 Preliminaries2.1 Definition of the Problem约定对任意一个字符串s，其第i个字符用si来表示,而第i个到第j个字符所组成的字符串用si.j表示。给定一个长度为n的字符串T和一个长度为m的模式P，如果存在一个长度为d的字符串s，使得sT, sP,且s=P1.d,其中m <= n，则称s为字符串P在T中的一个d匹配，用ss表示所有s所组成的集合，而smax为ss中长度最大的元素，称其为P在T中的最长匹配，用dmax表示其长度。给定一个来自有限字符集的长度N的字符串S,在其上定义一个长度为n的字典窗口DCT和长度为m的前

8、向缓冲存储器窗口LAB，用SDCT和SLAB来分别表示DCT和LAB中所包含的字符串，其中SDCTS, SLABS, m <= n, n<<N。假定DCT在S中的位置为i而LAB在S中的位置为j，即Si=SDCT1,Sj= SLAB1，我们有j>=i+n。窗口滑动的含义是DCT和LAB可以同时在S上向右滑动，直到SLABm=SN,假定最大的滑动次数为M,我们用SDCTp和SLABp来表示经过第p次滑动后DCT和LAB中所包含的字符串，假定第p次滑动的字符个数为dp，其中0<=p<=M。滑动窗口字符串匹配搜索问题描述如下：给定长度为N的字符串S之上的长度为n的

9、DCT窗口和长度为m的LAB窗口，当窗口从初始位置向最终位置滑动时，在每次窗口滑动后，寻找SLABp在SDCTp中的最长匹配。2.2 后缀数组后缀数组是字符串匹配中常用的数据结构之一。给定一个长度为n的字符串T,称Suffx(i)为T的一个后缀(Suffix)，其中Suffix(i)=Ti.n，即Suffix(i)为起始位置为i至n的T的一个子串。T的后缀数组SA(Suffix Array)定义为按照某种顺序(一般为递增)排列的T的所有后缀，并把排序后的位置i放入到数组SA中，因此每个后缀可以用Suffix(SAi)表示。定义T的名次数组R(Rank)为SA的逆，表示每个后缀在后缀数组中的排序

10、位置，即Rank=SA-1。如果Ranki=j，则有SAj=i，另外RankSAj=j。2.3 LCP及其计算给定两个字符串u和v,则它们的最长公共前缀lcp(u,v)定义为maxk|u=kv，其中=k表示u和v的前k个字符相等。根据此定义，定义长度为n的字符串T的最长公共前缀数组Height的第i个元素为:而作为后缀数组的辅助工具，LCP的计算也至关重要的，其现行计算时间是根据下面的LCP定理1620。其中u=Suffix(SAi),v=Suffix(SAj)根据LCP定理及推论，计算一个后缀与其相邻后缀的LCP时，没有必要比较两者的全部字符，更有效的LCP计算方法是一次扫描遍历即可。因此，

11、基于已排序的后缀数组，根据LCP定理和RMQ(Range Minimum Query)问题的解决方法，可以在线性时间内计算出LCP数组Height。2.4 完全后缀数组给定一个长度为n的字符串T,T的后缀数组SA和SA上的一个后缀Suffix(i)，如果在SA上存在另一个后缀Suffix(j),使得lcp(Suffix(i), Suffix(j) = n-i+1，则称Suffix(i)为T在SA上的一个完全后缀。如果不存在另一个后缀Suffix(j),使得lcp(Suffix(i), Suffix(j) = n-i+1，则称Suffix(i)为T在SA上的一个非完全后缀(Uncompleted

12、-Suffix)。T在SA上的所有完全后缀组成的数组叫完全后缀数组CSA,用SuffixCSA表示CSA之上的字符串数组，而所有非完全后缀组成的数组叫非完全后缀数组UCSA，用SuffixUCSA表示UCSA之上的字符串数组。一个已排序好的后缀数组由完全后缀数组和非完全后缀数组构成，即SA=CSA+UCSA。以T=”abbacbba”为例，按字母顺序排序后Suffix = a, abbacbba, acbba, ba, baccbba, bba, bbacbba, cbba,SA=8,1,4,7,3,6,2,5,从而可以知道T有三个完全后缀,即 “a”、 “ba”、和“bba”,其他都为非完全

13、后缀。则CSA = 8,7,6,UCSA=1,4,3,2,5,SuffixCSA=a,ba,bba，而SuffixUCSA = abbacbba, acbba, baccbba, bbacbba, cbba。3 滑动窗口字符串匹配算法AAA3.1 改进算法的思路现有的利用后缀数组进行滑动窗口字符串匹配搜索的基本思路是：首先读入DCT和LAB字符串，对DCT所包含的字符串SDCT构建后缀数组，然后二分查找在SDCT中找出SLAB对应的最长公共前缀，然后滑动窗口，再对新的SDCT构建后缀数组，直到滑动结束。在每一次匹配搜索过程中，搜索的时间复杂度为O(m+logn)10，这优于一般的查找算法，但其

14、缺点是每次窗口滑动后都需要重建后缀数组。此外，如果存在多个匹配结果时，需要选择最后一个匹配的结果，这也造成了查找效率变低。事实上利用完全后缀我们可以不需要重新完全构建后缀数组，或者说可以简化后缀数组的构建，从而达到减低查找时间的目的。通过分析完全后缀，我们可以得到以下性质：（1）若Height(i)=Len(Suffix(SAi-1)，则Suffix(SAi-1)为完全后缀。这也是判断一个后缀是否为完全后缀的条件。证明：给定一个长度为n的字符串T和T的后缀数组SA,当i>=2时，Height(i)=lcp(Suffix(SAi-1), Suffix(SAi),如果Suffix(SAi)使

15、得Suffix(SAi-1)为T在SA上的一个完全后缀，则Height(i)= n SAi-1 + 1 = Len(Suffix(SAi-1).（2）当匹配到最长字符串时，窗口进行第p次滑动。此时如果存在一个滑动前的后缀SAi的起始字符Ti没有滑出窗口，则此时该后缀的原来的排序索引位置i在滑动后新形成的后缀数组后可能会发生改变，即重建后缀数组时该后缀的排序位置可能不是以前的位置。(3)全部非完全后缀的相对顺序还是不变的，因为非完全后缀在此前未结束的字符之处已经比较完了。窗口滑动并不会影响非完全后缀的偏序关系。假定窗口在第p次滑动前，存在两个非完全后缀，其排序位置分别为i和j,如果i <

16、j,由于SAiUCSA, SAjUCSA,窗口滑动后，如果两个后缀继续留在新窗口中，这两个后缀和新进入窗口的字符串结合后会形成两个新的后缀，假定形成新的后缀数组后，这两个新后缀的名次内容分别变为i'和j'，则i'<j'，即它们的名次顺序不会发生改变。从以上性质我们可以发现，在窗口滑动后产生新的后缀数组可以由以下步骤构成，把原来继续留在窗口中的非完全后缀与新进入的字符串结合后生成的新后缀按原来饿顺序保留下来，然后再把完全后缀与新进入的字符串结合后生成的新后缀以及新进入的字符串自身生成的后缀按顺序插入到后缀数组中即可生成新的后缀数组，而不必重新构造整个后缀数组

17、，这样做的动机是根据实验分析发现完全后缀和新进入窗口中的后缀数量要远远小于保留在窗口中的非完全后缀的数量，从而使得构建后缀数组的时间可以缩短。且判断一个后缀是否为完全后缀只需要与其相邻的后缀比较即可，时间复杂度也很低。此外，在进行字符串匹配时，只要找到最大的匹配字符串即返回，不寻找最后一个匹配的字符串。3.2 算法过程给定一个长度为n的字典窗口DCT,算法AAA的在第p次窗口滑动时构造后缀数组的过程如下: 假定上次得到的最长匹配字符串长度为k，即第p次滑动后窗口内要新增k个后缀，假定滑入窗口的字符串为t。（1）滑动时，首先遍历SA,对每一个1=<i<n,当SAi>k时判断He

18、ight(i+1)是否与Len(Suffix(SAi)相等，相等时把Suffix(SA i)+t移动到CSA，否则把Suffix(SAi)变成Suffix(SAi)+t，最后从SA中删除SAi<=k的元素。(2) 假定CSA的势为d,遍历CSA的每一个元素，并采用二分插入法插入到SA中。（3）把t1,t1.2,t1.k采用二分插入法插入到SA中。进而算法AAA的伪代码可以表示如下：图 1 算法AAA伪代码其中，这里解释CreateSA, Search, TellTypem Insert,并做简要描述。对没说明的变量也要在这里说明一下。3.3 算法复杂度分析为了展示提出的算法AAA的优势，

19、我们在算法复杂度方面和的算法进行比较，窗口匹配算法每次窗口滑动后的计算过程可分为两部分：(1)构造后缀数组，（2）查找最长匹配字符串。由于算法AAA并没有第2步上进行特别突出的改进，为此我们仅分析第1步的时间复杂度。算法AAA构造后缀数组的过程分为：(1)划分完全后缀数组和非完全后缀数组，并剔除滑出窗口的后缀。(2)在没有滑出窗口的非完全后缀中插入完全后缀。(3) 把新滑进窗口的后缀插入到后缀数组中。对于长度为n的字典窗口，假定在第p次滑动时，滑出窗口的后缀数量为k，剩下没有滑出的后缀中，原来的完全后缀数量为d,而非完全后缀为c。对第一步来讲，由于只需要判断相邻的后缀即可确定是否为完全后缀，因

20、此算法执行次数为T(n)。然后采用二分插入法把d个完全后缀插入到c个非完全后缀中，该操作时间复杂度为<=dlogn；接着是把滑入字典窗口字符的新后缀插入到新的非完全后缀，此操作的时间复杂度为<=klogn。实验结果表明C一般接近n(我们的实验结果表明n>C>=0.99n)。因此整个算法的执行时间小于T(n+(k+d)logn)，其中k+d << n，相对n来讲k+d可以认为是常量,因此算法AAA的时间复杂度为O(n)。而需要完全重构后缀数组，构建后缀数组的算法通常有3种，即倍增算法，KA算法1716，KS算法1816。相对而言，倍增算法的时间复杂度较高，O(

21、nlogn)，而KS和KA都为线性构造算法19，但由于倍增算法实现简单，所以很多时候都采用它来构造后缀数组。而三种算法的详细执行时间分别如下：倍增算法的执行时间为T(n+nlogn)，KA算法的执行时间为T(n/2)+O(n)，KS算法的执行时间为T(c-1)n/c)+O(n)，其中c3为分解因子,因此算法AAA可以认为是一种快速算法，在执行时间上具有优势。至于空间复杂度，原始算法的空间复杂度为后缀数组构建和查找匹配的空间复杂度，倍增算法的空间复杂度是O(n)，主要存放每次排序的索引位置，查找匹配则只需O(1)，存放查找区间值的起始位置low和终始位置high，故原算法的空间复杂度为O(n)。

22、而算法AAA的空间分配较复杂，首先AAA在分类后缀时需要两个后缀数组，两个数组的大小加起来不大于O(n)，在原始数组中，需要淘汰一部分溢出；然后是滑入字典窗口字符串后缀的空间复杂度，由于任何一个后缀字符串的都可以表示为Suffix(i)=t+i, t为滑入字典窗口的字符串。每次查找时只需以t+i为参数，这是一个指针，空间复杂度为O(1)。所以算法AAA的空间复杂度为为O(n)，与原算法一致。4 experiments为了验证提出的算法AAA的有效性，实验通过对任意选取的11个TXT文件paper1-paper8,Bigpaper1-Bigpaper3,文件大小为4k、8k、12k，16k,32

23、k,64k,128k,256k，1M,2M,4M。分别执行算法AAA和的算法中的字符串匹配部分，实验比较两个算法的执行时间，其中在每次实验中对两个算法都设置相同的DCT窗口和LAB窗口。实验分五次，每次窗口参数设置如下： A: DCT=1024, LAB=1024; B: DCT=1024, LAB=512；C: DCT=1024, LAB=256; D: DCT=512, LAB=512；E: DCT=512, LAB=256。实验室平台为PC机：Pentium(R) Dual-Core CPU E5200 2.5GHZ 2G内存。实验结果如表1所示（每组数据都是多次采样结果的平均值），其中

24、每一行的上面为算法的执行时间，下面的为算法AAA的执行时间。表1 算法实验时间对比原始算法(/s)ABCDEpaper14.815.465.793.043.19Paper211.2611.8712.196.626.69Paper319.1318.5818.4710.0110.14Paper422.9622.3622.1512.1612.09Paper524.4724.5624.3313.5713.42Paper627.3827.3627.2615.2215.08Paper733.2832.2632.2217.9817.72Paper837.7137.2537.0220.9220.48BigPa

25、per1200196195109107BigPaper2406394393217215BigPaper3805804793439437表 多个文件的原始结合算法实验结果改进算法(/s)ABCDEpaper10.8500.6820.5890.3580.332Paper21.441.231.190.7700.678Paper32.491.981.871.191.06Paper42.151.421.261.451.22Paper53.182.622.451.581.38Paper63.602.932.751.761.58Paper74.223.483.251.961.83Paper84.933.99

26、3.732.472.15BigPaper126.1520.9519.5812.7712.69BigPaper252.8241.1937.2625.7622.19BigPaper3102.585.479.546.844.9表 多个文件的改进结合算法实验结果注：一般来说，LABDCT把两张表合成一张从表1可以看出，在任何一组(DCT,LAB)的情况下，算法AAA的效率都比原始算法的要高。首先我们研究两种算法的实验结果共性。上述的各个文件大小是递增的。随着文件大小的递增，查找匹配时间也随之增大。而在A，B，C的三种情况下，执行时间差不多，且D，E执行的时间也差不多。前三者情况的执行时间一般都比后二者

27、的执行时间要多，因为前三者情况的DCT比后二者大，造成二分查找的时间增大。而且，从表1可以看出LAB的大小对整个执行时间影响不大，因为最长公共匹配前缀的字符大部分已经在二分查找时已经找到，而进一步匹配LAB的工作量较小。此外，从表1还发现一个线性规律，在DCT不变的情况下，算法执行时间与文件大小成正比，通过进一步实验，发现大文件仍存在这种规律。接着我们来分析两种算法之间的差异。通过对比实验的文件输出结果可知，算法执行的结果是一致的。通过理论和算法执行分析，可知改进算法对后缀数组的重建工作要比原始算法的工作量要小的多。窗口滑动时，原始算法的重建工作量几乎不变，因为这一过程的时间复杂度主要由窗口大

28、小决定，而改进算法则不同，其重建后缀数组的时间复杂度不仅受窗口大小影响，而且当窗口滑动小(匹配结果较短，这种情况会发生在输入文件的重复性不高时)，时间复杂度可更低，因为大部分的后缀结果已经在上一次排好序了，这也是改进算法的改进效果如此明显的主要原因。重复利用上一次后缀数组的排序结果，可以大量减少重建后缀数组的工作量。而且从算法时间复杂度中，可以看出改进算法的时间复杂度大约为O(n)，而原始算法的时间复杂度大约为O(nlogn)，所以后者是前者的logn倍，反应在实验中就是相同条件下，后者的执行时间是前者的logn倍，也就是在9，10左右，由于一些其他IO因素及被忽略的因素影响，这一值有稍许偏差

29、，大概在8-10倍。5 Conclusion本文对基于后缀数组的滑动窗口下字符串匹配搜索算法进行了改进，提出一种后缀数组的新颖重建方法，缩短构建时间，提高字符串匹配搜索算法的执行时间，在不降低压缩率的前提下，减少了压缩时间。本文的创新点在于：提出一种与滑动窗口相适应的后缀数组结合的字符串匹配算法。基于原始后缀，新建后缀的大部分与原始后缀相似，划分后缀类型，提出一种新的概念完全后缀，采用一种二分插入算法，重建后缀数组，然后再进行查找。经过理论证明和实验结果，说明改进算法比原始结合算法更高效。算法AAA还有待改进提高，在查找算法中，可以考虑建索引，没必要对整个数组检索，而只在指定索引区间位置来检索

30、，缩短查找范围，提高查找效率。可以考虑对后缀数组的首字母建索引，这样会针对相应的索引位置进行检索。参考文献1. J. Ziv and A. Lempel, “A universal algorithm for sequential data compression,” IEEE Trans. Inf. Theory, vol.IT-23, no.3, pp.337343, May 1977.2. N. J. Larsson, “Extended application of suffix trees to data compression,” Proc. IEEE Data Compressi

31、on Conference, pp.190199, April 1996.3. Kunihiko SADAKANE, Nonmember and Hiroshi IMAI, Regular Member, Improving the Speed of LZ77 Compression by Hashing and Suffix Sorting, IEICE TRANS. FUNDAMENTALS, VOL.E83A, NO.12 DECEMBER 20004. Storer, J. A. and T. G. Szymanski (1982)”Data Compression via Textu

32、al Substitution,” Journal of the ACM, 29:928-9515. Ziv, J. and A. Lempel (1978)”Compression of Individual Sequences via variable-Rate coding,”IEEE Transaction on Information Theory It-24(5):530-536.6. Philips, Dwayne (1992) “LZW Data Compression,” The Computer Application Journal Circuit Cellar Inc.

33、, 27:36-48, June/July7. Welch, T.A. (1984) “A Technique for High-Performance Data Compression,” IEEE Computer 17(6):8-19, July.8. Valerio Freschi, Alessandro Bogliolo, A faster algorithm for the computation of string convolutions using LZ78 parsing, Department of Mathematics, Physics and Informatics

34、, University of Urbino “Carlo Bo”, Urbino, Italy9. Macarie Breazu, Antoniou Pitic, Daniel Volovici Remus Brad, Near-Lossless LZW Image Compression, University “Lucian Blaga” of Sibiu, Computer Science Department Emil Cioran 4, Sibiu, Romania10. Artur J. Ferreira Arlindo L. Oliveira Mario A. T. Figue

35、iredo, “On the Suitability of Suffix Arrays for Lempel-Ziv Data Compression”. Communications in Computer and Information Science, 2009, Volume 48, Part 4, 267-28011. Artur J. Ferreira Arlindo L. Oliveira Mario A. T. Figueiredo, “On the Use of Suffix Arrays for Memory-Efficient Lempel-Ziv Data Compre

36、ssion”, DCC '09 Proceedings of the 2009 Data Compression Conference12. Artur J. Ferreira Arlindo L. Oliveira Mario A. T. Figueiredo, “Suffix Arrays: A Competitive Choice for Fast Lempel-Ziv Compression”, SIGMAP 2008 page 5-1213. Artur J. Ferreira Arlindo L. Oliveira Mario A. T. Figueiredo, “Time and Memory Efficient Lempel-Ziv Compression Using Suffix Arrays”, CoRR 2009 0912.544914. Artur J. Ferreira Arlindo L. Oliveira Mario A. T. Figueiredo, “Sliding Window Up