邱　濤，王　斌，楊曉春

東北大學(xué)信息科學(xué)與工程學(xué)院，沈陽(yáng)110819

ISSN 1673-9418 CODEN JKYTA8

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

?

利用關(guān)鍵因子過(guò)濾的正則表達(dá)式匹配算法*

邱濤+，王斌，楊曉春

東北大學(xué)信息科學(xué)與工程學(xué)院，沈陽(yáng)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 (國(guó)家自然科學(xué)基金); the National Natural Science Foundation of China on International Cooperation under Grant No. 61129002 (國(guó)家自然科學(xué)基金海外及港澳學(xué)者合作基金).

Received 2015-06,Accepted 2015-08.

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

摘要：正則表達(dá)式（regular expression，RE）是一種能夠提供復(fù)雜查詢能力的技術(shù)，其通過(guò)特定的語(yǔ)法結(jié)構(gòu)來(lái)

1　引言

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

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

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

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

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

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

（1）分析了基于過(guò)濾因子的正則表達(dá)式匹配方法，總結(jié)了可進(jìn)行驗(yàn)證的有效過(guò)濾因子特點(diǎn)，提出了基于關(guān)鍵因子的過(guò)濾技術(shù)。

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

（3）在真實(shí)數(shù)據(jù)上進(jìn)行了全面的測(cè)試，結(jié)果表明了基于關(guān)鍵因子過(guò)濾的匹配方法可以有效地提升正則表達(dá)式的匹配性能。

2　相關(guān)工作

本文將從兩個(gè)方面對(duì)正則表達(dá)式匹配的相關(guān)工作進(jìn)行介紹，即經(jīng)典的正則表達(dá)式匹配方法和基于過(guò)濾策略的匹配方法。

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

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

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

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

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

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

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

3　正則表達(dá)式匹配定義

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

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

（1）空字符ε是一個(gè)正則表達(dá)式，它表示一個(gè)空串。

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

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

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

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

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

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

定義2（展開(kāi)式集合）對(duì)于任意一個(gè)正則表達(dá)式查詢Q，都存在一個(gè)字符串集合SQ來(lái)表示Q所描述的所有查詢，本文稱SQ為正則表達(dá)式Q的展開(kāi)式集合。

正則表達(dá)式的展開(kāi)式集合可能是一個(gè)無(wú)限大的集合，因?yàn)楫?dāng)其存在柯林閉包項(xiàng)時(shí)，柯林閉包項(xiàng)可以進(jìn)行無(wú)限的擴(kuò)展。如圖5所示，對(duì)于正則表達(dá)式Q=(QL|EL ) V*D，它的展開(kāi)式集合為SQ={QLD, ELD, QLVD, ELVD, QLVVD, ELVVD…}，由于V*表示空或者任意多個(gè)V，因此對(duì)于該查詢Q，其SQ是一個(gè)無(wú)限大的集合。SQ[i]表示集合中第i項(xiàng)( i≥0 )，SQ[0]為集合的第一項(xiàng)，它表示閉包項(xiàng)都為空時(shí)，Q所能匹配的字符串。正則表達(dá)式Q的展開(kāi)式集合SQ中的字符串在文本T中的精確匹配即為Q在T上的匹配結(jié)果。

定義3（最小匹配長(zhǎng)度）對(duì)于正則表達(dá)式Q，其在文本T上最短的匹配結(jié)果長(zhǎng)度稱為Q的最小匹配長(zhǎng)度，本文用lmin進(jìn)行表示。

由展開(kāi)式集合的定義可以知道，對(duì)于一個(gè)正則表達(dá)式Q，其最小匹配長(zhǎng)度lmin等于SQ中字符串長(zhǎng)度最短的項(xiàng)的長(zhǎng)度。例如，對(duì)于上述正則表達(dá)式Q，其lmin=3，因?yàn)镾Q中最短串長(zhǎng)度為3。

給定一個(gè)正則表達(dá)式，如果它的最短成功匹配長(zhǎng)度為lmin，則任何跳躍方法都必須對(duì)每lmin個(gè)字符中的至少一個(gè)進(jìn)行檢驗(yàn)，以免錯(cuò)過(guò)匹配位置。因此，基于過(guò)濾因子的方法選取的過(guò)濾因子長(zhǎng)度都不會(huì)超過(guò)lmin[13]。本文后面介紹關(guān)鍵因子長(zhǎng)度也必須小于等于lmin。

對(duì)于文本T，T[i]表示文本中第i個(gè)字符（從0開(kāi)始），T[i,j]表示T中從第i個(gè)字符到第j個(gè)字符的子串。闡述了正則表達(dá)式的定義以及相關(guān)概念后，下面給出本文研究?jī)?nèi)容的問(wèn)題定義。

問(wèn)題1（正則表達(dá)式匹配）給定文本T和正則表達(dá)式Q，T∈Σ*，正則表達(dá)式匹配即在文本T上匹配出所有滿足Q的匹配結(jié)果。

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

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

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

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

4　關(guān)鍵因子

本章將對(duì)關(guān)鍵因子的定義進(jìn)行詳細(xì)介紹。首先對(duì)基于過(guò)濾因子的正則表達(dá)式匹配技術(shù)進(jìn)行分析，然后通過(guò)分析總結(jié)出可用于驗(yàn)證的有效過(guò)濾因子的特點(diǎn)，最后基于有效過(guò)濾因子進(jìn)而定義關(guān)鍵因子。

定義4（等價(jià)查詢）對(duì)于正則表達(dá)式Q1、Q2和Q，如果Q1·Q2與Q的匹配結(jié)果一致（即通過(guò)轉(zhuǎn)換后具有相同的最小化確定自動(dòng)機(jī)），那么稱Q1·Q2與Q是等價(jià)的。

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

定義5（有效劃分）對(duì)于正則表達(dá)式Q1，Q2和Q，如果Q1·Q2與Q是等價(jià)的，那么稱Q1和Q2為Q的一組有效劃分（簡(jiǎn)稱劃分），記為。

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

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

可以發(fā)現(xiàn)，前綴因子和必要因子都屬于有效過(guò)濾因子，因?yàn)樗鼈冇糜隍?yàn)證的表達(dá)式與查詢Q是等價(jià)的。對(duì)于前綴因子，其后向驗(yàn)證表達(dá)式為空。

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

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

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

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

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

5　關(guān)鍵因子的構(gòu)造方法

本章開(kāi)始介紹關(guān)鍵因子的構(gòu)造算法。關(guān)鍵因子實(shí)質(zhì)是具有最小發(fā)生頻率的有效過(guò)濾因子，只有滿足有效過(guò)濾因子這個(gè)前提才能有效地對(duì)候選區(qū)間進(jìn)行驗(yàn)證。一種最基本求取正則表達(dá)式Q的有效過(guò)濾因子的方法是先求取出所有的過(guò)濾因子，再對(duì)過(guò)濾因子進(jìn)行有效性驗(yàn)證。通過(guò)對(duì)Q進(jìn)行展開(kāi)得到Q的展開(kāi)集合SQ，然后通過(guò)SQ來(lái)枚舉出Q的所有過(guò)濾因子集合。但是這種方法具有很高的代價(jià)，因?yàn)樾枰杜e出所有的過(guò)濾因子，再通過(guò)判斷自動(dòng)機(jī)是否等價(jià)來(lái)確定有效過(guò)濾因子。接下來(lái)，本文介紹一種高效的求取有效過(guò)濾因子的方法，它的基本思想是先找到查詢Q的所有劃分，通過(guò)Q的劃分來(lái)找到滿足條件的有效過(guò)濾因子集合，進(jìn)而結(jié)合有效過(guò)濾因子的發(fā)生頻率構(gòu)造出關(guān)鍵因子。

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

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

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

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

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

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

5.2利用解析樹(shù)計(jì)算有效劃分

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

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

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

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

5.3基于滑動(dòng)窗口的關(guān)鍵因子構(gòu)造算法

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

Fig.5　 Computing valid filtering factors based on sliding window圖5　基于滑動(dòng)窗口的有效過(guò)濾因子計(jì)算過(guò)程

當(dāng)SQ中元素對(duì)齊之后，就可以利用長(zhǎng)度為lmin的“滑動(dòng)窗口”來(lái)取SQ的子串集合，這樣可以保證滑動(dòng)窗口所取的子串起始位置與分割位置都是等距的，因此滑動(dòng)窗口中的子串集合即有效過(guò)濾因子集合（見(jiàn)定理1）。滑動(dòng)窗口需要滿足如下兩方面的條件：

條件1滑動(dòng)窗口中必須含有SQ中每一項(xiàng)的子串。如果有些項(xiàng)的子串沒(méi)有包含在滑動(dòng)窗口中那么就有可能導(dǎo)致匹配過(guò)程漏解。

條件2滑動(dòng)窗口中子串必須是左對(duì)齊的。當(dāng)且僅當(dāng)滑動(dòng)窗口中所有元素都左對(duì)齊時(shí)，其所有子串的文本中匹配的起始位置與驗(yàn)證起始位置才是等距的。

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

（1）劃分中用于后向驗(yàn)證的表達(dá)式QL的展開(kāi)項(xiàng)的長(zhǎng)度都是相等的，這種情況下we可以移動(dòng)到窗口僅包含最左側(cè)字符的位置。如圖5（a）所示，后向驗(yàn)證表達(dá)式(Q|E)L所展開(kāi)的字符串都是等長(zhǎng)的，因此即使we僅包含最左側(cè)字符時(shí)也會(huì)滿足上述兩個(gè)條件。

（2）后向驗(yàn)證的表達(dá)式QL的展開(kāi)項(xiàng)的長(zhǎng)度不等。此時(shí)we的起始位置應(yīng)為SQ[0]的起始位置，因?yàn)镾Q[0]為展開(kāi)式集合中最短的項(xiàng)，再向左移動(dòng)將不滿足條件2，如圖5（b）所示。

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

為了快速得到過(guò)濾因子在文本T上的發(fā)生頻率，一種最基本的方法是將T存儲(chǔ)為后綴樹(shù)的形式，在樹(shù)的每個(gè)節(jié)點(diǎn)上存儲(chǔ)從根節(jié)點(diǎn)到該節(jié)點(diǎn)所示子串在文本中的發(fā)生頻率，但是當(dāng)T很長(zhǎng)時(shí)后綴樹(shù)需要很大的存儲(chǔ)空間。為了進(jìn)一步減少空間開(kāi)銷，也可以利用BWT格式來(lái)存儲(chǔ)文本T[15]?；贐WT索引，可以在常數(shù)時(shí)間O(|f|)內(nèi)得到過(guò)濾因子f的發(fā)生頻率。

算法1關(guān)鍵因子構(gòu)造算法

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

輸出：關(guān)鍵因子集合P，用于驗(yàn)證的劃分，驗(yàn)證偏移量offset。

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

2. minFre←MAXVALUE;

3. For each in S( ) QL,QRdo

4.計(jì)算下的始末窗口ws與we;

5.獲取當(dāng)前QR在擴(kuò)展集合SQ的起始位置集合StartPos←Pos[QR];

6. w←ws;

7. For ws與we間的每一個(gè)窗口w do

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

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

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

11. If Fre(F)< minFre then

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

13. ← ;

14. Return P, 與offset;

6　基于關(guān)鍵因子的正則表達(dá)式匹配

本章開(kāi)始介紹基于關(guān)鍵因子的正則表達(dá)式匹配算法。5.1節(jié)介紹了基于偏移量的驗(yàn)證方式，本節(jié)將對(duì)其進(jìn)行進(jìn)一步的闡述。基于過(guò)濾-驗(yàn)證模式的正則表達(dá)式匹配技術(shù)分為兩個(gè)階段，過(guò)濾階段和驗(yàn)證階段。算法2描述了本文所介紹的基于關(guān)鍵因子的正則表達(dá)式匹配技術(shù)的執(zhí)行過(guò)程。

算法2基于關(guān)鍵因子的正則表達(dá)式匹配算法

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

輸出：匹配結(jié)果集合R。

1.利用算法1求得Q的關(guān)鍵因子P，相應(yīng)的劃分和驗(yàn)證偏移量offset;

2.通過(guò)QL′和QR′分別構(gòu)造后向和前向驗(yàn)證自動(dòng)機(jī)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;

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

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

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

7　實(shí)驗(yàn)測(cè)試與分析

為了測(cè)試本文提出的基于關(guān)鍵因子的正則表達(dá)式匹配技術(shù)的有效性，本文在兩個(gè)真實(shí)的數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。

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

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

實(shí)驗(yàn)從蛋白序列和英文文本中連續(xù)抽取了大小為100 MB的數(shù)據(jù)集。因?yàn)椴淮嬖陔S機(jī)的正則表達(dá)式[16]，所以實(shí)驗(yàn)在兩個(gè)數(shù)據(jù)集上分別合成了5組正則表達(dá)式，每組包含10個(gè)正則表達(dá)式查詢，這些正則表達(dá)式的長(zhǎng)度為6到21，lmin大小為2到5。本文實(shí)驗(yàn)圖中的查詢（如Q1p）均表示一組查詢，對(duì)應(yīng)的值為該組查詢的平均值。

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

7.1匹配性能對(duì)比測(cè)試

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

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

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

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

7.2過(guò)濾能力對(duì)比測(cè)試

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

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

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

Fig.7　 Comparison on pruning power of different algorithms圖7　不同算法的過(guò)濾能力對(duì)比

7.3關(guān)鍵因子的構(gòu)造代價(jià)

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

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

8　結(jié)束語(yǔ)

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

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　關(guān)鍵因子構(gòu)造代價(jià)　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)人，東北大學(xué)博士研究生，主要研究領(lǐng)域?yàn)樽址撇樵?，生物信息學(xué)等。

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—），男，遼寧沈陽(yáng)人，東北大學(xué)講師，主要研究領(lǐng)域?yàn)榉植际綌?shù)據(jù)管理，體系結(jié)構(gòu)等。

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—），女，遼寧沈陽(yáng)人，2001年于東北大學(xué)計(jì)算機(jī)軟件與理論專業(yè)獲得博士學(xué)位，現(xiàn)為東北大學(xué)教授、博士生導(dǎo)師，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫(kù)理論與技術(shù)，數(shù)據(jù)質(zhì)量分析，數(shù)據(jù)隱私保護(hù)等。

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

文獻(xiàn)標(biāo)志碼：A

中圖分類號(hào)：TP311.131