焦文歡，馮興杰

(中國民航大學(xué)信息網(wǎng)絡(luò)中心，天津 300300)

1 引言

隨著云計(jì)算、物聯(lián)網(wǎng)、社交網(wǎng)絡(luò)等信息技術(shù)的迅猛發(fā)展以及智能終端、可穿戴設(shè)備等電子產(chǎn)品的大量涌現(xiàn)，人類社會的數(shù)據(jù)種類和規(guī)模正以前所未有的速度增長，全球已經(jīng)進(jìn)入大數(shù)據(jù)時代。越來越多的行業(yè)需要從海量數(shù)據(jù)中挖掘蘊(yùn)藏的內(nèi)在聯(lián)系，并通過大數(shù)據(jù)分析加以利用。如何髙效地實(shí)現(xiàn)針對大數(shù)據(jù)信息的檢測分析，成為網(wǎng)絡(luò)安全、網(wǎng)絡(luò)搜索引擎、計(jì)算生物學(xué)、人工智能等領(lǐng)域的關(guān)鍵問題[1-3]。字符串模式匹配技術(shù)作為大數(shù)據(jù)分析的基礎(chǔ)和核心，在計(jì)算機(jī)病毒特征碼匹配、文本檢索、語音識別和DNA檢測等領(lǐng)域被廣泛應(yīng)用，而高效的字符串匹配算法將大大提高大數(shù)據(jù)分析的效率[4，5]。

2 概述

字符串模式匹配定義為：假設(shè)一組特定的字符集合P，對于任意的目標(biāo)文本串T，找出模式串P在文本串T中所有出現(xiàn)的位置。所有字符來自一個有限的字母表(或字符集)[6]。如果模式串匹配次數(shù)為0，則匹配失?。蝗裟Ｊ酱ヅ浯螖?shù)大于或等于1，則匹配成功。模式匹配按功能分類有精確模式匹配、近似模式匹配和正則表達(dá)式匹配三種；按照匹配數(shù)目分為單模式匹配和多模式匹配[7]。本文主要研究基于單模式匹配和精確模式匹配的字符串匹配技術(shù)。

常用的模式匹配算法主要包括：KMP、Boyer-Moore、BMF、Quick Search、TurnedBM等[8-11]。其中，文獻(xiàn)[12]對BM算法進(jìn)行了改進(jìn)，選取模式串末尾位置對應(yīng)文本串中的下一個和再下一個字符作為組合字符組，并計(jì)算該字符組在模式串中出現(xiàn)的位置，增大失配時模式串向右移動的最大距離；文獻(xiàn)[13]提出一種對模式串進(jìn)行分組預(yù)處理并使用字符組計(jì)算跳躍集的分組QS算法，給出壞字符組啟發(fā)規(guī)則與最佳分組長度的計(jì)算方法。

字符串匹配算法的改進(jìn)思想主要?dú)w納為兩點(diǎn)：①減少模式串與文本串字符比較的次數(shù)；②增大模式串移動的最大距離。為滿足上述條件，只有保證模式串每次移動的距離為最大安全距離，才能有效實(shí)現(xiàn)降低字符比較次數(shù)、增大移動距離的目的，進(jìn)而提高算法執(zhí)行效率。為此，在分析掌握字符串匹配算法思想及改進(jìn)思路的前提下，本文提出一種改進(jìn)的字符串匹配模型，確保模式串每次移動的距離為最大安全距離，并進(jìn)行分組對比實(shí)驗(yàn)和字符串匹配性能分析。

3 相關(guān)算法

大多數(shù)字符串匹配算法都有兩個階段，即預(yù)處理和搜索階段。預(yù)處理階段通過預(yù)處理模式串字符以確定模式串移動距離，搜索階段使用信息對比查找文本串中出現(xiàn)的匹配模式。

Boyer-Moore算法

Boyer-Moore(BM)算法是字符串模式匹配最流行的算法之一。BM算法基于三種思想，即從右到左字符比較法、壞字符啟發(fā)式和好后綴啟發(fā)式。從右到左字符比較思想主要用來收集有關(guān)字符的詳細(xì)信息，并且在搜索階段使用這些信息；壞字符啟發(fā)式思想則通過文本串中導(dǎo)致文本串與模式串不匹配的字符調(diào)整模式串移動距離；好后綴啟發(fā)式思想根據(jù)模式串和文本串相似的后綴，使用好的后綴啟發(fā)式將模式串移動到文本的右側(cè)。由于BM算法在許多應(yīng)用中的有效性，從原始BM算法中衍生出許多算法，以適應(yīng)多種用途。Boyer-Moore子組算法主要有：Turbo BM、Apostolico Giancarlo、Reverse Colussi、Horspool、Quick Search(QS)、Raita、Tuned BM、Zhu-Takaoka、Fast Search和Ssabs等算法[14]。

Tuned BM算法

Tuned BM(TBM)算法是Boyer-Moore算法的改進(jìn)，但它執(zhí)行更容易、更快、實(shí)現(xiàn)簡單。算法在模式串與文本串的匹配操作中使用壞字符移位功能，并且字符比較過程按任意順序進(jìn)行。在文本串T中匹配P[m-1](即模式串P的最后一個字符)，若匹配失敗，則模式串根據(jù)bmBc數(shù)組繼續(xù)向前移動，直到匹配相同字符；在此情況下，比較模式串和目標(biāo)文本串其它字符是否匹配，若匹配失敗，則將模式串向前移動固定距離constShift=bmBc[P[m-1]]；然后比較字符P[m-1]和T[constShift+m-1]是否相等，如果相等，比較模式串和目標(biāo)文本串是否相同，否則，繼續(xù)移動模式串到文本串中下一個與P[m-1]字符相同的位置[15]。

Tuned BM算法移動距離計(jì)算如下

(1)

Zhu-Takaoka算法

BM算法的另一個改進(jìn)是Zhu-Takaoka(ZT)算法，其中差異表現(xiàn)在壞字符規(guī)則的確定階段[16]。在BM算法中，壞字符僅由一維數(shù)組組成，而在ZT算法中，壞字符被修改為二維數(shù)組，模式串根據(jù)文本串窗口最右邊的兩個連續(xù)字符進(jìn)行移位。ZT算法的字符比較從右到左進(jìn)行，當(dāng)匹配或不匹配發(fā)生時，它要么使用好后綴移位，要么使用壞字符移位，選取好后綴移位數(shù)組bmGs和壞字符移位數(shù)組ztBc中最大值作為模式串移動距離[14]。

Zhu-Takaoka算法移動距離計(jì)算如下

skip2Zhu-Takaoka(y)=

(2)

在Boyer-Moore子組算法中，根據(jù)最小嘗試移動次數(shù)和字符比較次數(shù)原則，最有效的算法是ZT算法和TBM算法。然而，TBM算法在模式串不匹配的情況下，移位距離取決于預(yù)處理階段獲得的固定移位值，此固定移位值在文本窗口到達(dá)結(jié)尾之前不會更改，而且TBM算法在DNA數(shù)據(jù)的長模式串匹配中消耗更多的時間。ZT算法在模式串不匹配的情況下，移位距離值取決于好壞字符表，采用好壞字符數(shù)組中較大值作為移位距離，但是ZT算法在短模式串匹配中消耗更多運(yùn)行時間[14]。

為了克服ZT和TBM算法的局限性和矛盾性，本文提出一種改進(jìn)的字符串匹配模型。即充分利用ZT和TBM算法正特征的顯著優(yōu)勢，排除它們的負(fù)屬性，克服它們的性能弱點(diǎn)，保證在模式串滿足最大安全移動距離的前提下，實(shí)現(xiàn)減少字符比較次數(shù)和增大模式串移動距離的目的，從而為面向大數(shù)據(jù)分析提供更加高效的字符串匹配模型。

4 改進(jìn)模型

改進(jìn)的字符串模型分為預(yù)處理和搜索兩個階段。在預(yù)處理階段，選擇preBmBc函數(shù)和preZtBc函數(shù)對模式串字符進(jìn)行預(yù)處理；在搜索階段，根據(jù)bmBc數(shù)組和ztBc數(shù)組分別計(jì)算模式串總移動步長，采用較大值作為模式串進(jìn)行下次比較的移動距離。

改進(jìn)模型最大安全移動距離計(jì)算如下

(3)

預(yù)處理階段描述如下：

步驟1：使用preBmBc函數(shù)預(yù)處理模式串P計(jì)算bmBc[ASIZE]，其中constShift=bmBc[x[m-1]]，然后將bmBc[x[m-1]]賦值為0。

步驟2：使用preZtBc函數(shù)預(yù)處理模式串P計(jì)算ztBc[ASIZE][ASIZE]，ztBc為二維數(shù)組，ASIZE為字符集合總數(shù)。

搜索階段描述如下：

步驟1：從文本串T和模式串P的起始位置對齊，模式串移動當(dāng)前總長度為shiftNum；

步驟2：判斷P[T[m-1+shiftNum]]值是否為0，如果為0，模式串按照從左到右的順序比較其它字符，轉(zhuǎn)到步驟5；

步驟3：如果T[m-1+shiftNum]和P[m-1]不相等或者字符串匹配失敗，根據(jù)bmBc[ASIZE]數(shù)組查找下一個P[m-1]的位置，并記錄移動總距離shiftTemp。

步驟4：比較shiftTemp和ztBc[T[m-2+shiftNum]][T[m-1+shiftNum]]，選取最大值作為模式串移動的最大安全距離，即shift=MAX(shiftTemp， ztBc[T[m-2+shiftNum]][T[m-1+shiftNum]])，同時shiftNum+=shift；轉(zhuǎn)到步驟2。

步驟5：比較模式串除P[m-1]字符以外的其它字符是否和文本串中字符匹配，如果全部匹配，則字符串匹配成功；否則，轉(zhuǎn)到步驟3．

改進(jìn)模型的實(shí)現(xiàn)代碼如下：

Void Improved(char *x， int m， char *y， int n)

{

/* Preprocessing */

preBmBc(x， m， bmBc)；

preZtBc(x， m， ztBc)；

/* Searching */

j=0； ∥ shiftNum

while (j < (n-m)) {

k=bmBc[y[j+m-1]]；

i=0； ∥ shiftTemp

if(k==0){

if (memcmp(x， y+j， m-1)==0)

OUTPUT(j)；

i+=constShift；

k=bmBc[y[j+m-1+i]]；

}

while ((k ！=0)&&(j+i

i+=k； k=bmBc[y[j+i+m-1]]；

i+=k； k=bmBc[y[j+i+m-1]]；

i+=k； k=bmBc[y[j+i+m-1]]；

}

j+=MAX(i， ztBc[T[m-2+j]][T[m-1+j]])；∥shift

}

}

5 實(shí)驗(yàn)分析

實(shí)驗(yàn)?zāi)康模和ㄟ^對改進(jìn)模型進(jìn)行數(shù)據(jù)分析和實(shí)驗(yàn)，驗(yàn)證改進(jìn)模型在字符集環(huán)境下可以有效減少字符比較次數(shù)和增大模式串移動距離，在不增加算法時間復(fù)雜度的情況下，盡量保證模式串每次移動都能獲取最大安全移動距離，提高字符串模式匹配的穩(wěn)定性和準(zhǔn)確性。

實(shí)驗(yàn)環(huán)境：改進(jìn)模型采用Visual C#實(shí)現(xiàn)，運(yùn)行于3.4GHz雙核Intel CPU和操作系統(tǒng)為Windows Server 2019 64位的工作站上。

實(shí)驗(yàn)數(shù)據(jù)：采用Corpus 數(shù)據(jù)集[17]中不同數(shù)據(jù)類型文件分別進(jìn)行實(shí)驗(yàn)分析：實(shí)驗(yàn)A采用基因組數(shù)據(jù)對模型進(jìn)行實(shí)驗(yàn)分析；實(shí)驗(yàn)B采用隨機(jī)字符集和a字符集數(shù)據(jù)文件對比測試改進(jìn)模型在無規(guī)則數(shù)據(jù)集和單個字符集中的匹配效率。

實(shí)驗(yàn)A：本組實(shí)驗(yàn)選取基因序列文件E.coli中前700000個字符作為文本串序列進(jìn)行實(shí)驗(yàn)分析，模式串長度在8-140之間。采用改進(jìn)模型和QS、TBM、ZT算法進(jìn)行分組對比實(shí)驗(yàn)，從模式串移動次數(shù)和字符比較次數(shù)兩方面進(jìn)行對比分析。

圖1 E.coli數(shù)據(jù)集模式串移動次數(shù)

如上圖所示，在相同文本串和模式串長度情況下，改進(jìn)模型中模式串移動次數(shù)最少，模式串移動次數(shù)的變化趨勢符合改進(jìn)算法的預(yù)期效果。由于改進(jìn)模型對TBM算法模式串移動距離的計(jì)算進(jìn)行了優(yōu)化，摒棄了TBM算法的模式串移動固定步長值，采用不斷查找bmBc[T[x]]=0的條件累加步長，因此改進(jìn)模型在執(zhí)行初期保持了較少的模式串移動次數(shù)。

圖2 E.coli數(shù)據(jù)集字符比較次數(shù)

從上圖可以看出，改進(jìn)模型前期表現(xiàn)出TBM算法在短模式串下字符匹配的算法優(yōu)勢，后期表現(xiàn)出ZT算法在長模式串下字符匹配的算法優(yōu)勢。由于改進(jìn)模型大幅度減少模式串移動次數(shù)，間接促使匹配過程中字符比較次數(shù)的減少。改進(jìn)模型采用從左到右的順序依次比較除模式串最后一個字符以外的字符是否相等，同時，只有在模式串最后一個字符匹配時才進(jìn)行其它字符的比較。在充分利用較少模式串移動次數(shù)的同時，進(jìn)一步從字符嘗試比較的條件上進(jìn)行判斷，盡量減少無效的字符比較次數(shù)。

下表展示的是改進(jìn)模型在字符串匹配過程中計(jì)算最大安全移動距離的兩個階段值占比。從表中可以看出，改進(jìn)的bmBc數(shù)組摒棄了固定步長的移動方式，通過累加步長的方法提高了命中最大安全移動距離的概率，在不同長度模式串的應(yīng)用場景下其命中概率都在60%及以上；而bmBc數(shù)組的不足被ztBc數(shù)組以20%的概率加以彌補(bǔ)，表現(xiàn)為在長短模式串場景下，改進(jìn)模型都保持了良好的匹配效果。

表1 改進(jìn)模型最大安全移動距離占比

實(shí)驗(yàn)B：本節(jié)實(shí)驗(yàn)選取隨機(jī)字符文本文件random.txt中前90000個字符作為文本串序列進(jìn)行實(shí)驗(yàn)分析，對比算法選取ZT算法和改進(jìn)模型兩種。模式串移動次數(shù)、字符比較次數(shù)結(jié)果如圖3和圖4所示。

圖3 random數(shù)據(jù)集模式串移動次數(shù)

圖4 random數(shù)據(jù)集字符比較次數(shù)

從上圖可以看出，ZT算法在短模式串場景中效果較差，但是隨著模式串長度的增大，其模式串移動次數(shù)和字符比較次數(shù)驟減，算法的優(yōu)越性迅速體現(xiàn)；而改進(jìn)模型采用計(jì)算最大安全移動距離的方法，不僅在長模式串匹配中保持較好運(yùn)行效果，而且在短模式串匹配中也保持了穩(wěn)定的匹配效率。

本節(jié)實(shí)驗(yàn)選取a字符文本文件aaa.txt作為文本串序列，以aabbaa作為特殊模式串進(jìn)行實(shí)驗(yàn)分析。aaa.txt文件內(nèi)容為單個a字符集合，對比算法選取TBM算法和改進(jìn)模型兩種。模式串移動次數(shù)、字符比較次數(shù)結(jié)果如表2所示。

表2 a字符集實(shí)驗(yàn)結(jié)果

從上表可以看出，在aaa.txt文件中TBM算法陷入字符串匹配最壞情況。由于文本串是單個a字符集合，模式串是aabbaa，TBM算法的移動距離一直是1，而且模式串每次移動時，字符從左到右比較次數(shù)都為3，算法執(zhí)行效果較差；改進(jìn)模型引入preZtBc函數(shù)，通過二維數(shù)據(jù)計(jì)算出ztBc[a][a]=4為最大安全移動距離，從而避免算法在單字符集文本串中陷入匹配最壞情況。

TBM算法字符串預(yù)處理時間復(fù)雜度為O(m+σ)，搜索階段最壞情況下時間復(fù)雜度為O(σ2)[15]；在ZT算法中，預(yù)處理階段的時間復(fù)雜度為O(m+σ2)，搜索階段的時間復(fù)雜度為O(mn)[18]；改進(jìn)模型預(yù)處理階段時間復(fù)雜度為O(m+σ2)，搜索階段時間復(fù)雜度O(mn)。

對比模型在三個數(shù)據(jù)集上的運(yùn)行時間如圖6所示。

圖5 E.coli數(shù)據(jù)集算法運(yùn)行時間

圖6 random數(shù)據(jù)集算法運(yùn)行時間

表3 a字符集算法運(yùn)行時間

對以上圖表進(jìn)行分析，可以得出在E.coli數(shù)據(jù)集中改進(jìn)模型的執(zhí)行時間一直在TBM算法和ZT算法的時間范圍內(nèi)波動，在保持較少模式串移動次數(shù)和字符比較次數(shù)的同時，基本保證了算法執(zhí)行時間的合理性；而在random.txt和aaa.txt文件中，改進(jìn)模型的時間優(yōu)勢較為明顯，且避免在搜索階段陷入最壞時間復(fù)雜度的情況，在數(shù)據(jù)集合的文本串中一直保持較快的匹配速度，為改進(jìn)模型在大數(shù)據(jù)匹配分析中的應(yīng)用提供了穩(wěn)定、高效的匹配模型。

6 總結(jié)

改進(jìn)模型對現(xiàn)有兩種算法TBM和ZT進(jìn)行分析和改進(jìn)，從兩種原始模型中提取出良好特性。模型通過使用preBmBc函數(shù)和preZtBc函數(shù)預(yù)處理模式串從而計(jì)算最大安全移動距離，摒棄了TBM算法的固定移動距離機(jī)制，盡量保證模型搜索匹配過程中模式串每次都能移動最大安全距離，減少字符比較次數(shù)和模式串移動次數(shù)，實(shí)驗(yàn)表明其在短模式串和長模式串匹配過程中表現(xiàn)良好。

在更高階段的研究中，將通過對模型進(jìn)行算法優(yōu)化和部署高性能計(jì)算環(huán)境等措施減少其運(yùn)行時間，從而應(yīng)用于更快速的流式大數(shù)據(jù)匹配分析。