一種改進(jìn)的字符串匹配模型研究

焦文歡，馮興杰

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

1 引言

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

2 概述

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

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

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

3 相關(guān)算法

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

Boyer-Moore算法

Boyer-Moore(BM)算法是字符串模式匹配最流行的算法之一。BM算法基于三種思想，即從右到左字符比較法、壞字符啟發(fā)式和好后綴啟發(fā)式。從右到左字符比較思想主要用來(lái)收集有關(guān)字符的詳細(xì)信息，并且在搜索階段使用這些信息；壞字符啟發(fā)式思想則通過(guò)文本串中導(dǎo)致文本串與模式串不匹配的字符調(diào)整模式串移動(dòng)距離；好后綴啟發(fā)式思想根據(jù)模式串和文本串相似的后綴，使用好的后綴啟發(fā)式將模式串移動(dòng)到文本的右側(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)簡(jiǎn)單。算法在模式串與文本串的匹配操作中使用壞字符移位功能，并且字符比較過(guò)程按任意順序進(jìn)行。在文本串T中匹配P[m-1](即模式串P的最后一個(gè)字符)，若匹配失敗，則模式串根據(jù)bmBc數(shù)組繼續(xù)向前移動(dòng)，直到匹配相同字符；在此情況下，比較模式串和目標(biāo)文本串其它字符是否匹配，若匹配失敗，則將模式串向前移動(dòng)固定距離constShift=bmBc[P[m-1]]；然后比較字符P[m-1]和T[constShift+m-1]是否相等，如果相等，比較模式串和目標(biāo)文本串是否相同，否則，繼續(xù)移動(dòng)模式串到文本串中下一個(gè)與P[m-1]字符相同的位置[15]。

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

(1)

Zhu-Takaoka算法

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

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

skip2Zhu-Takaoka(y)=

(2)

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

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

4 改進(jìn)模型

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

改進(jìn)模型最大安全移動(dòng)距離計(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的起始位置對(duì)齊，模式串移動(dòng)當(dāng)前總長(zhǎ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ù)組查找下一個(gè)P[m-1]的位置，并記錄移動(dòng)總距離shiftTemp。

步驟4：比較shiftTemp和ztBc[T[m-2+shiftNum]][T[m-1+shiftNum]]，選取最大值作為模式串移動(dòng)的最大安全距離，即shift=MAX(shiftTemp， ztBc[T[m-2+shiftNum]][T[m-1+shiftNum]])，同時(shí)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)康模和ㄟ^(guò)對(duì)改進(jìn)模型進(jìn)行數(shù)據(jù)分析和實(shí)驗(yàn)，驗(yàn)證改進(jìn)模型在字符集環(huán)境下可以有效減少字符比較次數(shù)和增大模式串移動(dòng)距離，在不增加算法時(shí)間復(fù)雜度的情況下，盡量保證模式串每次移動(dòng)都能獲取最大安全移動(dòng)距離，提高字符串模式匹配的穩(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ù)類(lèi)型文件分別進(jìn)行實(shí)驗(yàn)分析：實(shí)驗(yàn)A采用基因組數(shù)據(jù)對(duì)模型進(jìn)行實(shí)驗(yàn)分析；實(shí)驗(yàn)B采用隨機(jī)字符集和a字符集數(shù)據(jù)文件對(duì)比測(cè)試改進(jìn)模型在無(wú)規(guī)則數(shù)據(jù)集和單個(gè)字符集中的匹配效率。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 總結(jié)

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

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