一種改進的字符串匹配模型研究

焦文歡，馮興杰

(中國民航大學信息網絡中心，天津 300300)

1 引言

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

2 概述

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

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

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

3 相關算法

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

Boyer-Moore算法

Boyer-Moore(BM)算法是字符串模式匹配最流行的算法之一。BM算法基于三種思想，即從右到左字符比較法、壞字符啟發式和好后綴啟發式。從右到左字符比較思想主要用來收集有關字符的詳細信息，并且在搜索階段使用這些信息；壞字符啟發式思想則通過文本串中導致文本串與模式串不匹配的字符調整模式串移動距離；好后綴啟發式思想根據模式串和文本串相似的后綴，使用好的后綴啟發式將模式串移動到文本的右側。由于BM算法在許多應用中的有效性，從原始BM算法中衍生出許多算法，以適應多種用途。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算法的改進，但它執行更容易、更快、實現簡單。算法在模式串與文本串的匹配操作中使用壞字符移位功能，并且字符比較過程按任意順序進行。在文本串T中匹配P[m-1](即模式串P的最后一個字符)，若匹配失敗，則模式串根據bmBc數組繼續向前移動，直到匹配相同字符；在此情況下，比較模式串和目標文本串其它字符是否匹配，若匹配失敗，則將模式串向前移動固定距離constShift=bmBc[P[m-1]]；然后比較字符P[m-1]和T[constShift+m-1]是否相等，如果相等，比較模式串和目標文本串是否相同，否則，繼續移動模式串到文本串中下一個與P[m-1]字符相同的位置[15]。

Tuned BM算法移動距離計算如下

(1)

Zhu-Takaoka算法

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

Zhu-Takaoka算法移動距離計算如下

skip2Zhu-Takaoka(y)=

(2)

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

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

4 改進模型

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

改進模型最大安全移動距離計算如下

(3)

預處理階段描述如下：

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

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

搜索階段描述如下：

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

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

步驟3：如果T[m-1+shiftNum]和P[m-1]不相等或者字符串匹配失敗，根據bmBc[ASIZE]數組查找下一個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；轉到步驟2。

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

改進模型的實現代碼如下：

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 實驗分析

實驗目的：通過對改進模型進行數據分析和實驗，驗證改進模型在字符集環境下可以有效減少字符比較次數和增大模式串移動距離，在不增加算法時間復雜度的情況下，盡量保證模式串每次移動都能獲取最大安全移動距離，提高字符串模式匹配的穩定性和準確性。

實驗環境：改進模型采用Visual C#實現，運行于3.4GHz雙核Intel CPU和操作系統為Windows Server 2019 64位的工作站上。

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

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

圖1 E.coli數據集模式串移動次數

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

圖2 E.coli數據集字符比較次數

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

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

表1 改進模型最大安全移動距離占比

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

圖3 random數據集模式串移動次數

圖4 random數據集字符比較次數

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

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

表2 a字符集實驗結果

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

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

對比模型在三個數據集上的運行時間如圖6所示。

圖5 E.coli數據集算法運行時間

圖6 random數據集算法運行時間

表3 a字符集算法運行時間

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

6 總結

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

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