利用關鍵因子過濾的正則表達式匹配算法*

邱　濤，王　斌，楊曉春

東北大學信息科學與工程學院，沈陽110819

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2016/10(03)-0326-12

?

利用關鍵因子過濾的正則表達式匹配算法*

邱濤+，王斌，楊曉春

東北大學信息科學與工程學院，沈陽110819

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2016/10(03)-0326-12

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

* The National Natural Science Foundation of China under Grant Nos. 61272178, 61322208 (國家自然科學基金); the National Natural Science Foundation of China on International Cooperation under Grant No. 61129002 (國家自然科學基金海外及港澳學者合作基金).

Received 2015-06,Accepted 2015-08.

CNKI網絡優(yōu)先出版: 2015-08-12, http://www.cnki.net/kcms/detail/11.5602.TP.20150812.0917.001.html

摘要：正則表達式（regular expression，RE）是一種能夠提供復雜查詢能力的技術，其通過特定的語法結構來

1　引言

隨著信息社會的到來，數據量急速增長，人們也對信息查詢有了更高的要求，簡單的信息匹配已經不能滿足用戶的需求。正則表達式（regular expression, RE）不僅能處理傳統(tǒng)的精確文本匹配，更加重要的是其具有強大的描述能力，能夠描述文本深層次的特征，從而提供復雜的查詢邏輯。正則表達式在各個領域都被廣泛地應用，當前的一些文本編輯軟件，如vim、eclipse，還有shell命令中的grep命令[1]被廣泛地應用于文本查詢中，其也是通過正則表達式查詢來實現(xiàn)的。例如，可以通過shell命令“grep ^[0-9]+@[a-z]+.com emails.txt”在文件emails.txt中查詢包含匹配結果的行，匹配結果是以數字開始，中間包含@，并且以.com結尾的郵箱號。此外，正則表達式的功能已經被集成到了一些語言的語法當中（如Perl、Ruby和AWK），或者通過標準庫的形式被其他高級語言所支持，如JAVA、.NET等。

傳統(tǒng)的實現(xiàn)正則表達式查詢的方法是，對于查詢Q構造其對應的自動機，然后對于字符串中的每一個位置，通過自動機來判斷從該位置開始的子串是否可以被該自動機所接受。這種方法的主要限制在于需要重復這種驗證過程很多次，并且驗證代價往往是比較大的。有許多方法提出了改進措施來加速匹配過程[1-5]，基本思路都是先確定字符串上的一些候選區(qū)間，然后一個接一個地驗證這些區(qū)間（如圖1所示）。這些方法從正則表達式中提取出一些子串（過濾因子）來確定候選區(qū)間出現(xiàn)的位置。每一個候選區(qū)間都將用一個或者多個自動機來驗證。即使這些方法可以減少許多驗證過程，但是當過濾后產生的候選區(qū)間較多時，這些方法的效率將變得非常低，尤其當文本非常長的時候更加明顯。

Fig.1　 RE matching based on filtering strategy圖1　基于過濾策略的匹配方法

現(xiàn)有方法采用的過濾因子包括前綴因子和必要因子。前綴因子和必要因子都是通過分析查詢Q而得到子串集合，并沒有考慮文本中字符不均勻分布對過濾能力的影響。實際情況中文本的字符不是均勻分布的，這將導致文本中子串出現(xiàn)的頻率差別較大。例如，英文文檔中子串like、they作為常用的單詞，其出現(xiàn)的頻率遠大于klmn出現(xiàn)的頻率。又如蛋白序列中，QLD和ELV等子串是很多蛋白結構的基本單元，因此其出現(xiàn)頻率要高于其他子串的頻率。

基于這個觀察，在所有查詢Q的匹配結果所包含的子串中，挑選一組在文本中出現(xiàn)頻率低的作為過濾因子，將產生更好的過濾效果，因為這部分子串才是能否出現(xiàn)一個匹配結果的關鍵所在。本文將這樣的頻率少且用于過濾的子串稱為關鍵因子。利用關鍵因子進行過濾將獲得更好的過濾能力，從而提高整體的匹配性能。

本文的貢獻主要有以下3個方面：描述一類文本的共同特征。正則表達式強大的表達能力和簡潔的語法，使得其在各個領域都被廣泛地應用。為了提高正則表達式的匹配效率，提出了一種利用關鍵因子進行過濾的匹配技術，關鍵因子指的是在文本中具有最小出現(xiàn)頻率的有效過濾因子。由于實際文本中字符并不是均勻分布的，子串在文本中出現(xiàn)頻率的差異將影響過濾因子的過濾能力。通過考慮有效過濾因子在文本中出現(xiàn)的頻率，關鍵因子能獲得更好的過濾能力。提出了利用正則表達式的劃分來求取關鍵因子的算法，進而通過關鍵因子來過濾候選位置。通過在真實的蛋白序列和英文文本上進行實驗，說明了基于關鍵因子過濾的匹配方法可以有效地提升正則表達式的匹配性能。關鍵詞：正則表達式；過濾策略；算法性能；關鍵因子

（1）分析了基于過濾因子的正則表達式匹配方法，總結了可進行驗證的有效過濾因子特點，提出了基于關鍵因子的過濾技術。

（2）為了構造給定正則表達式的關鍵因子，提出了一種高效的關鍵因子構造算法，即先求得正則表達式的所有劃分，再通過劃分發(fā)現(xiàn)所有有效過濾因子，從而得到關鍵因子。

（3）在真實數據上進行了全面的測試，結果表明了基于關鍵因子過濾的匹配方法可以有效地提升正則表達式的匹配性能。

2　相關工作

本文將從兩個方面對正則表達式匹配的相關工作進行介紹，即經典的正則表達式匹配方法和基于過濾策略的匹配方法。

經典的正則表達式匹配方法的基本思路是先將正則表達式轉換成自動機，然后直接利用自動機進行搜索。目前已經提出了很多基于該思路的方法[6-9]。文獻[8]中Thompson在給出了NFA（non-deterministic finite automata）定義的同時，還在對該NFA直接模擬的基礎上提出了一個復雜度為O(mn)的算法，稱之為NFAThompson。它將當前活動狀態(tài)的集合存儲起來，對于每次讀入的新字符，依次查看當前的每一個活動狀態(tài)，以獲得被激活的新狀態(tài)。然后，將這些新狀態(tài)加入一個新的活動狀態(tài)集合。對這些新的活動狀態(tài)，再跟隨其所有的ε-轉移獲得其他所有可到達狀態(tài)，并將其加入新活動狀態(tài)集合中。通過這種方式，可以通過判斷終止狀態(tài)是否激活來判斷是否找到RE的一個匹配[7]。DFAClassical算法[10]利用的是DFA （deterministic finite automata）來進行匹配，其可以保證具有O(n)的線性搜索時間。此外，基于Thompson NFA模擬，文獻[5]提到了一種很有競爭力的算法BPThompson，它巧妙地運用了位并行的方法來模擬NFA的匹配。

上述經典的正則表達式匹配技術雖然提升了自動機匹配的效率，但由于經典的正則表達式匹配算法需要對文本逐個字符進行檢驗，這在很大程度上影響了匹配的效率。一種比較新穎的做法是利用過濾-驗證模式來回答正則表達式查詢。如圖1所示，基于過濾策略的匹配方法的基本思路是，先通過多串匹配算法匹配出正則表達式在文本中的候選區(qū)域，然后再通過經典的正則表達式匹配算法對候選區(qū)域進行驗證。由于過濾策略的應用，使得算法可以避免讀入文本中的所有字符。下面介紹幾種主要的基于過濾策略的匹配算法。

文獻[3]介紹了一種MultiStringRE算法。該算法首先計算出可以匹配正則表達式中所有長度為lmin （lmin表示正則表達式的最短成功匹配長度）的前綴集合Pref(RE)，然后利用一種類似Commentz-Water的算法，實現(xiàn)對Pref(RE)的多字符串匹配。因為正則表達式的每次成功匹配必須要以Pref(RE)中的字符串開始，所以只要從Pref(RE)在文本中的初始位置開始驗證就可以。

RegularBNDM[11]是一種擴展的BNDM算法，其基本思想是通過對DFA自動機進行反轉，使得自動機能夠識別所有的反轉正則表達式的前綴。算法在文本中滑動大小為lmin的窗口，并且自后向前讀取窗口中的字符。窗口中的反向搜索會在兩種情況下停止：一是DFA中沒有活動狀態(tài)，這時可以滑動窗口重新開始匹配過程；二是匹配位置到達了窗口的起始位置，這種情況說明算法識別出了RE的一個前綴，這時就可以使用正常的無自循環(huán)DFA自動機進行向前驗證。

GNU Grep[1]使用的是基于必要因子的過濾方法，其基本思想也是先求得一個必要因子的集合，然后使用多串匹配計算搜索。對于文本中每一個必要因子出現(xiàn)的位置，它都需要分別向前和向后進行驗證。例如，對于正則表達式(C|A)*GA(T|C)，其中GA就是必要因子。必要因子的選取不僅僅是精確的子串，同時也可以是正則表達式的一個子表達式。必要因子必須是一個完整的子表達式（為了方便對候選區(qū)間進行前后驗證），并且對于有些正則表達式并不存在必要因子。

前綴因子和必要因子實際是從找到匹配結果包含的子串的角度進行過濾，這種結果中包含的子串可以統(tǒng)稱為正向因子。文獻[12]介紹了一種基于反向因子的過濾技術，反向因子指的是匹配結果中一定不包含的子串。其通過同時利用正向因子和反向因子進行過濾，獲得了更好的過濾能力。本文提出的關鍵因子屬于一種正向因子，基于關鍵因子也可以利用反向因子實現(xiàn)過濾能力的進一步提升。

正如引言部分所描述的，前綴因子和關鍵因子主要問題在于忽略了文本中子串頻率分布不均勻對于過濾能力的影響。本文對正則表達式的過濾因子進行了分析，提出了利用關鍵因子進行過濾的技術，通過考慮過濾因子在文本中出現(xiàn)的頻率，構造出具有最少出現(xiàn)頻率的有效過濾因子集合，即關鍵因子。因此關鍵因子總是能獲得比前綴因子和必要因子更好的過濾能力，從而提升正則表達式匹配的效率。

3　正則表達式匹配定義

本文給出了正則表達式匹配的形式化定義，并在后面的章節(jié)中采用統(tǒng)一的標識符形式化表示這些概念。

定義1（正則表達式）一個正則表達式RE是有限字母表Σ與運算符集合{ε, | ,·,?, ( ,)}中的元素組成的一個字符序列。它的遞歸定義如下：

（1）空字符ε是一個正則表達式，它表示一個空串。

（2）任意字符w∈Σ也是一個正則表達式，它表示的是字符串集合{w}。

（3）如果e1和e2都是正則表達式，那么(e1)，(e1·e2)，(e1| e2)，(e1+)也都是正則表達式。

①(e1)表示的字符串集合與e1所表示集合相等。

②(e1·e2)表示一個字符串的集合x，并且x可以表示成x=yz，其中y可以被e1匹配，z可以被e2匹配。

③(e1| e2)表示的字符串集合x可以被e1匹配或者被e2匹配。

④(e1+)所表示的字符串集合x，可以被表示成x=x1, x2,…,xk,并且e1匹配每個字符串xi(1≤i≤k )。表達式(ε|e1+)表示的是柯林閉包e1*。本文接下來考慮的都是更為通用的e1*。

定義2（展開式集合）對于任意一個正則表達式查詢Q，都存在一個字符串集合SQ來表示Q所描述的所有查詢，本文稱SQ為正則表達式Q的展開式集合。

正則表達式的展開式集合可能是一個無限大的集合，因為當其存在柯林閉包項時，柯林閉包項可以進行無限的擴展。如圖5所示，對于正則表達式Q=(QL|EL ) V*D，它的展開式集合為SQ={QLD, ELD, QLVD, ELVD, QLVVD, ELVVD…}，由于V*表示空或者任意多個V，因此對于該查詢Q，其SQ是一個無限大的集合。SQ[i]表示集合中第i項( i≥0 )，SQ[0]為集合的第一項，它表示閉包項都為空時，Q所能匹配的字符串。正則表達式Q的展開式集合SQ中的字符串在文本T中的精確匹配即為Q在T上的匹配結果。

定義3（最小匹配長度）對于正則表達式Q，其在文本T上最短的匹配結果長度稱為Q的最小匹配長度，本文用lmin進行表示。

由展開式集合的定義可以知道，對于一個正則表達式Q，其最小匹配長度lmin等于SQ中字符串長度最短的項的長度。例如，對于上述正則表達式Q，其lmin=3，因為SQ中最短串長度為3。

給定一個正則表達式，如果它的最短成功匹配長度為lmin，則任何跳躍方法都必須對每lmin個字符中的至少一個進行檢驗，以免錯過匹配位置。因此，基于過濾因子的方法選取的過濾因子長度都不會超過lmin[13]。本文后面介紹關鍵因子長度也必須小于等于lmin。

對于文本T，T[i]表示文本中第i個字符（從0開始），T[i,j]表示T中從第i個字符到第j個字符的子串。闡述了正則表達式的定義以及相關概念后，下面給出本文研究內容的問題定義。

問題1（正則表達式匹配）給定文本T和正則表達式Q，T∈Σ*，正則表達式匹配即在文本T上匹配出所有滿足Q的匹配結果。

例1給定正則表達式Q=(QL|EL)V*D，文本T如圖2所示。

Fig.2　 An example of protein sequences圖2　蛋白序列文本例子

T[8,10]和T[25,27]即為Q在文本T中的匹配，正則表達式匹配需要返回所有滿足Q的結果。

本文接下來介紹的基于關鍵因子的匹配技術是基于索引結構實現(xiàn)的，即可以通過索引快速得到子串在文本中的出現(xiàn)頻率和位置。該技術也可以擴展到非索引的情況。在非索引的情況下，有多種技術可以用于估算子串在文本中的出現(xiàn)頻率，例如采樣技術和分階段查詢技術。

4　關鍵因子

本章將對關鍵因子的定義進行詳細介紹。首先對基于過濾因子的正則表達式匹配技術進行分析，然后通過分析總結出可用于驗證的有效過濾因子的特點，最后基于有效過濾因子進而定義關鍵因子。

定義4（等價查詢）對于正則表達式Q1、Q2和Q，如果Q1·Q2與Q的匹配結果一致（即通過轉換后具有相同的最小化確定自動機），那么稱Q1·Q2與Q是等價的。

例如，對于Q=(QL|EL)V*D，存在Q1=(QL|EL), Q2=V*D，Q1·Q2與Q即為等價的正則表達式。

定義5（有效劃分）對于正則表達式Q1，Q2和Q，如果Q1·Q2與Q是等價的，那么稱Q1和Q2為Q的一組有效劃分（簡稱劃分），記為。

對于一組過濾因子F，當SQ中的所有字符串的左子式通過或操作(|)所得到的正則表達式QL與右子式通過或操作(|)得到的正則表達式QR分別匹配與Q存在等價關系( QL?QR=Q )，那么對于任意一個過濾因子f(f∈F)在文本中的出現(xiàn)位置π，都可以直接利用QL與QR直接進行前后驗證。顯然這種方式不需要單獨處理每一個f，且對于任意f匹配得到的候選位置使用的都是同樣的表達式進行驗證。例如，對于Q= (QL|EL)V*D，存在一組過濾因子F3={LD, LVD, LVV}，SQ中字符串關于F3中過濾因子的左子式可以表示為QL= (Q|E)，右子式表示為QR= LV*D。

定義6（有效過濾因子）給定正則表達式Q，F(xiàn)為Q的一組過濾因子，Q通過F得到的用于前后驗證的正則表達式分別為QL和QR，如果QL?QR=Q ( 為Q的一組劃分)，那稱F為Q的一組有效過濾因子。

可以發(fā)現(xiàn)，前綴因子和必要因子都屬于有效過濾因子，因為它們用于驗證的表達式與查詢Q是等價的。對于前綴因子，其后向驗證表達式為空。

定義7（發(fā)生頻率）給定正則表達式Q和文本T, F為Q的一組有效過濾因子，F(xiàn)中元素個數為k。過濾因子fi(fi∈F)在文本中出現(xiàn)的次數為ci，那么對于F中所有過濾因子在文本中出現(xiàn)次數的總和稱為F的發(fā)生頻率，表示為

例如，對于過濾因子集合F1={QLD,ELD,QLV, ELV}，其在圖3所示文本T中的發(fā)生頻率為Fre(F1)=3。

定義8（關鍵因子）給定正則表達式Q和文本T，F(xiàn)all為Q的所有有效過濾因子的集合，對于一組有效過濾因子P(P∈Fall)，如果Fall中不存在另外一組有效過濾因子P′，使得Fre(P′)

對于前面所述的有效過濾因子集合中，F(xiàn)3即為Q的關鍵因子集合，其在圖3所示文本T中的發(fā)生頻率為1，其余的有效過濾因子集合的發(fā)生頻率都大于1。

由關鍵因子的定義可以知道，由于考慮了有效過濾因子在文本中出現(xiàn)的頻率，相較于前綴因子和必要因子而言，關鍵因子總可以獲得最好的過濾能力。

5　關鍵因子的構造方法

本章開始介紹關鍵因子的構造算法。關鍵因子實質是具有最小發(fā)生頻率的有效過濾因子，只有滿足有效過濾因子這個前提才能有效地對候選區(qū)間進行驗證。一種最基本求取正則表達式Q的有效過濾因子的方法是先求取出所有的過濾因子，再對過濾因子進行有效性驗證。通過對Q進行展開得到Q的展開集合SQ，然后通過SQ來枚舉出Q的所有過濾因子集合。但是這種方法具有很高的代價，因為需要枚舉出所有的過濾因子，再通過判斷自動機是否等價來確定有效過濾因子。接下來，本文介紹一種高效的求取有效過濾因子的方法，它的基本思想是先找到查詢Q的所有劃分，通過Q的劃分來找到滿足條件的有效過濾因子集合，進而結合有效過濾因子的發(fā)生頻率構造出關鍵因子。

5.1利用劃分發(fā)現(xiàn)有效過濾因子

本節(jié)將介紹有效劃分與有效過濾因子間的關系。通過前面的介紹可以發(fā)現(xiàn)，如果存在Q的一組有效過濾因子F，那么必然存在用于前后驗證的劃分。直觀上來說，QR在文本中驗證的起始位置就是過濾因子在文本中出現(xiàn)的起始位置π。然而，實際上QR在文本中驗證的起始位置π′與過濾因子在文本中出現(xiàn)的起始位置π并不需要一樣。例如，對于F1={QLD,ELD,QLV,ELV}，其過濾因子在圖3所示文本T中的出現(xiàn)位置為8、12和25，那么也可以利用劃分<(QL|EL)，V*D>分別從10、14和27位置開始進行前后驗證?；谶@個觀察，下面介紹一種基于偏移量offset的驗證方式。

定理1給定正則表達式Q，為Q的一組劃分，如果對于SQ中的任意字符串s，s都存在子串f(f∈F)，QR在s中起始匹配位置為πs′，f在s中起始匹配位置為πs，當且僅當πs′-πs都相同時，那么F 為Q的一組有效過濾因子，并且可利用進行驗證。

定理1所描述的驗證方式稱為基于偏移量offset的驗證，offset=πs′-πs。圖3可以用于說明基于偏移量的驗證方式的原理。對于一個正則表達式Q，如果它在文本中存在一個匹配，那么這個匹配即是它展開式中的一個項，如圖3所示，s∈SQ,過濾因子f得到了文本T中的一個起始位置為π的匹配。為了驗證是否存在關于π的一個正則表達式匹配，可以選擇基于位置π的前后驗證，也可以選擇基于位置π′的驗證，很顯然這兩種方法得到的驗證結果是一致的，只不過用于前后驗證的劃分不一樣。但是因為有效過濾因子對于SQ中的任意一項都使用相同的驗證方式，所以對于任意s( s∈SQ)，s作為待驗證字符串，其上的驗證起始位置πs′與過濾因子出現(xiàn)的起始位置πs的差值應該等于offset。

Fig.3　 Verification based on offset starting position圖3　基于偏移量的驗證方法

通過定理1可以知道，對于正則表達式Q，如果存在一組有效劃分，那么可以求出基于該劃分的具有不同偏移量offset的所有有效過濾因子集合。

5.2利用解析樹計算有效劃分

5.1節(jié)理論分析了通過有效劃分可以找到基于該劃分的所有有效過濾因子集合。為了求得所有有效過濾因子，接下來需要解決的一個問題就是如何求得正則表達式Q的所有有效劃分。定義9（頂層操作符）對于正則表達式Q，Q中未被嵌套的操作符稱為頂層操作符。正則表達式可以嵌套地包含子表達式，例如Q=(QL|EL )，其中QL|EL即嵌套于()操作符中的子表達式，Q中包含3個頂層項(QL|EL)、V*和D，其中V*的閉包操作為頂層閉包操作符。同時Q可以顯式地表示為Q=ε?(QL|EL)?V*?D?ε，其中的4個連接操作即為Q的頂層連接操作符。定義10（最簡化正則表達式）對于正則表達式Q，如果Q的所有等價的用于前后驗證的劃分在Q中都是通過頂層連接操作符來連接，那么稱Q為最簡化正則表達式。當且僅當Q為最簡化正則表達式時，通過求得Q的所有頂層連接操作符即可得到所有有效的前后驗證劃分。文獻[14]提出了一種等價轉換的方法，使得Q可以轉換為最簡化的正則表達式。例如，對于前面所述的Q，其最簡化的表達式為(Q|E)LV*D。本文接下來的討論都是基于最簡化的正則表達式展開的。

本節(jié)提出了一種基于解析樹的劃分計算方法。構造解析樹是常用的正則表達式分析方式[13]，該解析樹亦可用于構造驗證需要的自動機。為了快速得到所有頂層連接操作符，本文介紹了一種巧妙的方式來實現(xiàn)這一過程。通過在正則表達式的首尾添加一個非字符表Σ中的字符（本文以$符號為例），對于正則表達式Q=(Q|E)LV*D，將轉換為表達式Q′=$(Q|E) LV*D$，通過Q′可以得到如圖4所示的解析樹。在之后通過解析樹計算展開式集合和構造自動機的時候，將$解析成空即可，這樣不會影響正則表達式的匹配。

通過圖4可以發(fā)現(xiàn)當添加$符號后，頂層連接操作符（包括原正則表達式Q首尾的連接操作符）將連續(xù)出現(xiàn)在以根節(jié)點開始的所有右孩子節(jié)點上，直到遇到最后一個$符號結束，例如節(jié)點1、節(jié)點3、節(jié)點5、節(jié)點9、節(jié)點11都為頂層連接操作符。這是由解析樹的構造過程決定的，解析樹中所有的一元操作符僅存在一個子節(jié)點，例如節(jié)點10表示的是閉包操作。所有的二元操作符將存在左右孩子節(jié)點，如或操作(|)和連接操作(·)。

Fig.4　 Parse tree of RE $(QL|EL)V*D$圖4　正則表達式$(QL|EL)V*D$的解析樹

5.3基于滑動窗口的關鍵因子構造算法

本節(jié)將介紹一種基于滑動窗口的關鍵因子構造算法。為了得到關鍵因子，需要先計算出有效過濾因子的集合。計算有效過濾因子集合的基本思路是利用定理1，找到所有與劃分相關的有效過濾因子。由于在SQ的每項分割位置不一定是相同的，為了便于理解，本文先假設SQ中的元素可以按著分割位置進行“對齊”。如圖5（a）所示為SQ中元素按著QL=(Q|E)L, QR=V*D這種劃分進行對齊后的效果，圖5（b）為按劃分QL=(Q|E)LV*,QR=D對齊的效果。

Fig.5　 Computing valid filtering factors based on sliding window圖5　基于滑動窗口的有效過濾因子計算過程

當SQ中元素對齊之后，就可以利用長度為lmin的“滑動窗口”來取SQ的子串集合，這樣可以保證滑動窗口所取的子串起始位置與分割位置都是等距的，因此滑動窗口中的子串集合即有效過濾因子集合（見定理1）?；瑒哟翱谛枰獫M足如下兩方面的條件：

條件1滑動窗口中必須含有SQ中每一項的子串。如果有些項的子串沒有包含在滑動窗口中那么就有可能導致匹配過程漏解。

條件2滑動窗口中子串必須是左對齊的。當且僅當滑動窗口中所有元素都左對齊時，其所有子串的文本中匹配的起始位置與驗證起始位置才是等距的。

基于上述兩個條件，可以選擇從右向左移動滑動窗口，起始位置應為最右端的滿足兩個條件的位置，向左滑動直到任意一個條件不滿足則停止。通過觀察可以發(fā)現(xiàn)，起始窗口ws一定為僅包含SQ[0]中最右端字符的窗口，因為SQ[0]為展開式集合中最短的項，對于SQ[0]，如果ws滿足條件1，那么其余的項也會滿足條件1，并且其余所有項在ws中的子串也都是左對齊的（滿足條件2）。至于終止窗口we，其位置分為兩種情況：

（1）劃分中用于后向驗證的表達式QL的展開項的長度都是相等的，這種情況下we可以移動到窗口僅包含最左側字符的位置。如圖5（a）所示，后向驗證表達式(Q|E)L所展開的字符串都是等長的，因此即使we僅包含最左側字符時也會滿足上述兩個條件。

（2）后向驗證的表達式QL的展開項的長度不等。此時we的起始位置應為SQ[0]的起始位置，因為SQ[0]為展開式集合中最短的項，再向左移動將不滿足條件2，如圖5（b）所示。

算法1描述了計算關鍵因子的過程。為了實現(xiàn)上述展開式的對齊操作，需要在通過解析樹計算展開式集合SQ的過程中記錄下每個劃分在SQ中的分割位置集合StartPos。通過StartPos和當前的偏移量offest，就可以通過對SQ進行一次遍歷來求得當前窗口中的所有子串（第9行所示）。對于每一個劃分的每一個窗口位置，當求得其有效過濾因子集合F后，都會比較F與當前所求得的具有最小發(fā)生頻率的有效過濾因子集合P的發(fā)生頻率，如果F具有更小的發(fā)生頻率，那么利用F來替換P，并且更新當前的最小頻率值minFre。

為了快速得到過濾因子在文本T上的發(fā)生頻率，一種最基本的方法是將T存儲為后綴樹的形式，在樹的每個節(jié)點上存儲從根節(jié)點到該節(jié)點所示子串在文本中的發(fā)生頻率，但是當T很長時后綴樹需要很大的存儲空間。為了進一步減少空間開銷，也可以利用BWT格式來存儲文本T[15]。基于BWT索引，可以在常數時間O(|f|)內得到過濾因子f的發(fā)生頻率。

算法1關鍵因子構造算法

輸入：有效劃分集合S( ) QL,QR，正則表達式解析樹TQ。

輸出：關鍵因子集合P，用于驗證的劃分，驗證偏移量offset。

1.通過TQ計算基于擴展邊界的集合SQ，并且返回S( ) QL,QR對應的QR在SQ中的起始位置集合Pos;

2. minFre←MAXVALUE;

3. For each in S( ) QL,QRdo

4.計算下的始末窗口ws與we;

5.獲取當前QR在擴展集合SQ的起始位置集合StartPos←Pos[QR];

6. w←ws;

7. For ws與we間的每一個窗口w do

8. offset←w的起始位置-QR起始位置;

9. F←FindFactorsWin(SQ,offset,StartPos);

10.計算F的發(fā)生頻率Fre(F);

11. If Fre(F)< minFre then

12. minFre←Fre(P); P←F;

13. ← ;

14. Return P, 與offset;

6　基于關鍵因子的正則表達式匹配

本章開始介紹基于關鍵因子的正則表達式匹配算法。5.1節(jié)介紹了基于偏移量的驗證方式，本節(jié)將對其進行進一步的闡述?；谶^濾-驗證模式的正則表達式匹配技術分為兩個階段，過濾階段和驗證階段。算法2描述了本文所介紹的基于關鍵因子的正則表達式匹配技術的執(zhí)行過程。

算法2基于關鍵因子的正則表達式匹配算法

輸入：正則表達式查詢Q，文本T。

輸出：匹配結果集合R。

1.利用算法1求得Q的關鍵因子P，相應的劃分和驗證偏移量offset;

2.通過QL′和QR′分別構造后向和前向驗證自動機AL和AR；

3.獲得P′中元素在T中出現(xiàn)的起始位置集合Sπ;

4. For each π in Sπdo

5.π′=π+offset；

6. resultB=VerifyB(T,π′-1, AL, startPos) ;

7. resultF=VerifyF(T,π′, AR, endPos);

8. If resultB and resultF are true then

9. R←< startPos, endPos>;

10. Return R;

在過濾階段，不僅求出了查詢表達式Q的關鍵因子集合P，而且需要返回對應的前后驗證表達式和驗證偏移量offset。通過QL′和QR′，可以構造得到用于后向和前向驗證的自動機AL和AR（見算法2的第1~3行）。

在驗證階段（見第4~9行），對于關鍵因子出現(xiàn)的每一個位置π，首先需要通過驗證偏移量offset，確定出驗證的起始位置π′，然后從π′-1位置開始利用后向驗證自動機AL進行驗證，驗證成功將返回結束位置startPos（后向驗證的匹配結果位置實際為Q匹配結果的起始位置）。前向驗證將從π′開始，驗證成功將返回匹配位置endPos。當前向與后向驗證都匹配成功時將記錄一個成功匹配結果。

例如，對于正則表達式Q=(QL|EL)V*D，其關鍵因子集合為{LD,LVD,LVV}，其在圖2所示文本T上的候選驗證位置為9和26，該關鍵因子集合的劃分為<ε,(Q|E)LV*D>，那么可以得到驗證偏移量offset=-1。由于后向驗證表達式為空，只需要進行前向驗證。前向驗證自動機AR將從8和25位置開始繼續(xù)向前驗證。

7　實驗測試與分析

為了測試本文提出的基于關鍵因子的正則表達式匹配技術的有效性，本文在兩個真實的數據集上進行了實驗。

第一個數據集是蛋白序列（ftp://ftp.sanger.ac.uk/ pub/databases/Pfam/releases），實驗所采用的蛋白數據庫是Pfam 26.0，它包含了大量的蛋白質族，蛋白質都是由Pfam-A和Pfam-B組成的。蛋白質中字符全是由大寫英文字母組成，除了字母“O”和字母“J”。數據集是從Pfam-B中隨機抽取的長度范圍在101和9 143之間的序列。

第二個數據集是英文文檔（http://arnetminer.org/ DBLP_Citation），實驗采用的是DBLP-Citation-network中的數據，其包括1 632 442個塊，每個塊都對應一篇論文的引用信息，例如標題、作者、摘要等。本文從每個塊中抽取出摘要信息，字符集由52個英文字母和10個數字組成。

實驗從蛋白序列和英文文本中連續(xù)抽取了大小為100 MB的數據集。因為不存在隨機的正則表達式[16]，所以實驗在兩個數據集上分別合成了5組正則表達式，每組包含10個正則表達式查詢，這些正則表達式的長度為6到21，lmin大小為2到5。本文實驗圖中的查詢（如Q1p）均表示一組查詢，對應的值為該組查詢的平均值。

所有算法均用C++實現(xiàn)，實驗在Intel 3.10 GHz Quad Core CPU i5和8 GB內存的64位ubuntu系統(tǒng)上進行。

7.1匹配性能對比測試

首先實驗比較的是本文提出的基于關鍵因子的正則表達式匹配方法PivotalRE與當今主流方法Agrep、GNU Grep還有NR-grep在不同數據集上的匹配性能和過濾能力。由于3個對比方法的設計初衷是用于匹配一組序列集合，當一個序列中存在多個匹配結果時，它們僅匹配第一個結果，并報告該序列存在一個結果匹配。為了公平地進行比較，本文修改了對比方法的源代碼，使其可以找到序列中所有的匹配結果。此外PivotalRE利用了索引來快速獲得關鍵因子的匹配位置，而對比方法都是利用多串匹配方法來獲取過濾因子位置，因此本文也修改了其過濾因子匹配部分的代碼，使其也可以利用索引快速匹配到過濾因子在文本中出現(xiàn)的位置。

圖6所示為在100 MB的數據集上匹配性能的對比結果。無論在蛋白序列還是英文文本上，Pivotal-RE的匹配效率都要優(yōu)于其余3種方法。例如，對于蛋白序列上的Q4p查詢來說，PivotalRE花費時間為142 ms，而Agrep、GNU Grep、NR-grep花費時間分別為338 ms、343 ms和246 ms。PivotalRE在英文文檔上的優(yōu)勢則更為明顯，例如對于查詢Q5e，PivotalRE需要128 ms完成查詢，而Agrep、GNU Grep、NR-grep花費時間分別為349 ms、408 ms和262 ms。

從圖6還可以發(fā)現(xiàn)，NR-grep算法的效率要優(yōu)于GNU Grep，即使在NR-grep過濾能力要低于GNU Grep的情況下（圖7所示），原因是NR-grep的驗證效率要優(yōu)于GNU Grep，其采用的是基于位并行的Regular-BNDM算法。

Fig.6　 Comparison on query performance of different algorithms圖6　不同算法的查詢性能對比

7.2過濾能力對比測試

PivotalRE的匹配效率優(yōu)于對比方法的主要原因在于PivotalRE可以獲得最少的候選驗證位置。本節(jié)通過實驗比較了PivotalRE與對比方法的過濾能力。本文使用過濾因子匹配位置個數（候選驗證位置個數）來衡量算法的過濾能力，算法過濾能力越好，其得到的過濾因子匹配位置個數就越少。Agrep直接使用了位并行的BPThompson算法進行匹配，相當于對每一個字符位置都需要進行驗證，因此實驗僅比較PivotalRE與GNU Grep、NR-grep的過濾能力。

過濾能力對比的實驗結果如圖7所示，PivotalRE過濾能力的優(yōu)勢在英文文本上更為明顯。例如對于Q1e，GNU Grep與NR-grep需要驗證的位置個數分別為733 729與1 507 066，而PivotalRE僅需要驗證400 003，原因是英文文檔比蛋白序列的子串頻率分布更為不均勻，使得關鍵因子與前綴、必要因子在文本中的發(fā)生頻率差別更大。

從圖7還可以發(fā)現(xiàn)，對于Q1p與Q3e，GNU Grep與NR-grep的驗證個數相差并不多，原因是對于這兩組查詢，GNU Grep對其中的多數查詢進行過濾使用的是前綴因子作為其必要因子，因此對于這些查詢GNU Grep得到的驗證數目與NR-grep是一樣的，從而導致了這兩種方法在Q1p與Q3e這兩組查詢上的過濾能力差異不大。此外通過實驗還發(fā)現(xiàn)，有些情況下由于選取的必要因子長度小于前綴因子長度，導致必要因子在文本中出現(xiàn)的頻率反而更多。例如對于Q2p與Q4p，GNU Grep得到的候選驗證位置個數分別為371 597和55 437，而NR-grep的驗證位置個數僅為301 587和47 030。

Fig.7　 Comparison on pruning power of different algorithms圖7　不同算法的過濾能力對比

7.3關鍵因子的構造代價

當系統(tǒng)收到用戶的正則表達式查詢Q后，需要在線地對Q進行關鍵因子計算，關鍵因子構造的時間代價是正則表達式匹配代價的一部分。因此，關鍵因子的構造過程非常關鍵，如果關鍵因子的構造代價過大，那么過濾過程將起不到加速正則表達式匹配的效果。本節(jié)將對PivotalRE的關鍵因子構造代價進行測試。

實驗結果如表1所示，Basic與Improved兩種構造關鍵因子算法的區(qū)別在于，Improved方法采用了5.4節(jié)介紹的優(yōu)化技術來避免對等價劃分的計算。蛋白序列和英文文本上的測試結果都表明了Improved方法的構造代價要優(yōu)于Basic方法的構造代價。在蛋白序列上的Q5p查詢，Improved方法節(jié)省的構造時間最多，Basic方法需要花費9.380 ms，而Improved方法僅花費1.016 ms。英文文本上也得到了相似的測試結果，對于Improved方法來說，構造代價最大的查詢Q1e也僅需要0.417 ms來構造關鍵因子。實驗結果表明，PivotalRE可以有效地進行關鍵因子的構造。

8　結束語

本文研究了基于過濾策略的正則表達式匹配問題。通過考慮過濾因子在文本中出現(xiàn)的頻率差異，提出了一種利用關鍵因子進行過濾的匹配技術。為了構造給定正則表達式的關鍵因子，本文提出了一種高效的關鍵因子構造算法，先求得正則表達式的所有劃分，再通過劃分發(fā)現(xiàn)所有有效過濾因子，從而得到關鍵因子。最后，提出了基于關鍵因子過濾的具有偏移量的驗證方式。實驗結果表明了基于關鍵因子過濾的匹配方法可以有效地提升正則表達式的匹配性能。

References:

[1] GNU grep[EB/OL]. [2015-04-30]. ftp://reality.sgiweb.org/ freeware/relnotes/fw-5.3/fw_gnugrep/gnugrep.html.

[2] Crochemore M, Czumaj A, Gasieniec L, et al. Speeding up two strings matching algorithms[J]. Algorithmica, 1994, 12 (4/5): 247-267.

[3] Watson B W. A new regular grammar pattern matching algorithm[C]//LNCS 1136: Proceedings of the 4th Annual European Symposium, Barcelona, Spain, Sep 25-27, 1996. Berlin, Heidelberg: Springer, 1996: 364-377.

[4] Mohri M. String matching with automata[J]. Nordic Journal of Computing, 1997: 217-231.

[5] Navarro C, Raffinot M. Compact DFA representation for fast regular expression search[C]//LNCS 2141: Proceedings of the 5th International Workshop on Algorithm Engineering, ?rhus, Denmark, Aug 28-31, 2001. Berlin, Heidelberg: Springer, 2001: 1-13.

[6] Myers E W. A four Russians algorithm for regular expression pattern matching[J]. Journal of the ACM, 1992, 39(2): 430-448.

[7] Wu Sun, Manber U. Fast text searching allowing errors[J]. Communications of the ACM, 1992, 35(10): 83-91.

[8] Thompson K. Programming techniques: regular expression search algorithm[J]. Communications of the ACM, 1968, 11 (6): 419-422.

[9] Baeza-Yates R A, Gonnet G H. Fast text searching for regular expressions or automaton searching on tries[J]. Journal of the ACM, 1996, 43(6): 915-936.

[10] Sethi R, Aho A V, Ullman J D. Compilers-principles, techniques and tools[M]. Singapore: Pearson Education, 1986.

[11] Navarro G. NR-grep: a fast and flexible pattern matching tool[J]. Software Practice and Experience, 2001, 31(13): 1265-1312.

[12] Yang Xiaochun, Wang Bin, Qiu Tao, et al. Improving regularexpression matching on strings using negative factors[C]// Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, New York, USA, Jun 22-27, 2013. New York, USA:ACM, 2013: 361-372.

[13] Navarro G, Raffinot M. Flexible pattern matching in strings: practical on-line search algorithms for texts and biological sequences[M]. Cambridge, UK: Cambridge UniversityPress, 2002.

Table 1　 Construction cost of pivotal factors表1　關鍵因子構造代價　ms

[14] Hopcroft J E, Motwani R, Ullman J D. Automata theory, languages, and computation[M]. [S.l.]: Pearson, 2006.

[15] Lam T W, Sung W K, Tam S L, et al. Compressed indexing and local alignment of DNA[J]. Bioinformatic, 2008, 24(6): 791-797.

[16] Navarro C, Raffinot M. New techniques for regular expression searching[J].Algorithmica, 2004, 41(2): 89-116.

QIU Tao was born in 1989. He is a Ph.D. candidate at Northeastern University. His research interests include approximate string query and bioinformatics, etc.邱濤（1989—），男，江西萍鄉(xiāng)人，東北大學博士研究生，主要研究領域為字符串近似查詢，生物信息學等。

WANG Bin was born in 1972. He is a lecturer at Northeastern University. His research interests include distributed database management and system structure, etc.王斌（1972—），男，遼寧沈陽人，東北大學講師，主要研究領域為分布式數據管理，體系結構等。

YANG Xiaochun was born in 1973. She received the Ph.D. degree in computer software and theory from Northeastern University in 2001. Now she is a professor and Ph.D. supervisor at Northeastern University, and the senior member of CCF. Her research interests include theory and technology of database, data quality analysis and data privacy protection, etc.楊曉春（1973—），女，遼寧沈陽人，2001年于東北大學計算機軟件與理論專業(yè)獲得博士學位，現(xiàn)為東北大學教授、博士生導師，CCF高級會員，主要研究領域為數據庫理論與技術，數據質量分析，數據隱私保護等。

Regular Expression Matching Algorithm Using Pivotal Factors?

QIU Tao+, WANG Bin, YANG Xiaochun
College of Information Science and Engineering, Northeastern University, Shenyang 110819, China
+ Corresponding author: E-mail: qiutao@stumail.neu.edu.cn

QIU Tao, WANG Bin, YANG Xiaochun. Regular expression matching algorithm using pivotal factors. Journal of Frontiers of Computer Science and Technology, 2016, 10(3): 326-337.

Abstract:Regular expression (RE) can describe complicated query, it depicts the common features of a set of text by the specific syntax. Since regular expression has the strong ability of expression and succinct syntax, it has been applied in many applications. In order to improve the matching performance of RE, this paper proposes a novel technique that pruning false negatives by utilizing pivotal factors, which are the valid filters with the least occurrences in text. Since the characters in text are not well-distributed, the difference of occurrences count of substrings will affect the pruning power of filters. Pivotal factors can achieve better pruning power by considering the occurrences count in text, which can also improve the matching performance of RE. This paper proposes the algorithm that computing pivotal factors by the partitions of RE, then further prunes the candidate positions by pivotal factors. Comprehensive experiments are conducted on real protein sequences and English text, the results show the significant performance improvement when utilizing the technique of pivotal factors.

Key words:regular expression; filtering strategy; performance; pivotal factors

doi:10.3778/j.issn.1673-9418.1507070

文獻標志碼：A

中圖分類號：TP311.131