基于廣義后綴樹(shù)結(jié)合過(guò)濾因子的正則表達(dá)式匹配算法

林 婧 何震瀛

1(復(fù)旦大學(xué)軟件學(xué)院 上海 201203) 2(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 201203) 3(復(fù)旦大學(xué)上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室 上海 200433)

0 引 言

隨著科學(xué)技術(shù)的飛速發(fā)展，數(shù)字化信息呈爆炸式增長(zhǎng)，文本數(shù)據(jù)作為信息的載體，包含了大量寶貴的資源，而如何從這些數(shù)據(jù)中查詢(xún)出有價(jià)值的信息，是人們?nèi)找骊P(guān)注的一個(gè)重要問(wèn)題。

正則表達(dá)式具有強(qiáng)大而靈活的文本處理能力，是解決查詢(xún)問(wèn)題的一個(gè)重要手段，應(yīng)用領(lǐng)域十分廣泛[1-5]。

由于正則表達(dá)式與有限自動(dòng)機(jī)完全等價(jià)[6],因此一般采用有限自動(dòng)機(jī)來(lái)分析和匹配正則表達(dá)式。傳統(tǒng)算法的匹配過(guò)程描述如下：對(duì)于給定的正則表達(dá)式Q，將其轉(zhuǎn)換為自動(dòng)機(jī)；一個(gè)待匹配的文本序列T，從T的起始位置開(kāi)始運(yùn)行自動(dòng)機(jī)。每當(dāng)自動(dòng)機(jī)達(dá)到最終狀態(tài)時(shí)，得到一個(gè)匹配結(jié)果[7-8]；然后繼續(xù)從T的下一位置開(kāi)始重新運(yùn)行自動(dòng)機(jī)，最終得到Q在T上匹配的所有字符串集合。這種算法需要從文本的每個(gè)位置開(kāi)始逐一檢驗(yàn)，當(dāng)文本序列較長(zhǎng)時(shí)，匹配效率低下。為此，研究者們提出了很多方法來(lái)加速正則表達(dá)式的匹配過(guò)程。MultiStringRE算法[9]首先計(jì)算出所有能夠匹配正則表達(dá)式Q的文本的前綴集合。對(duì)文本序列T,得到包含這些前綴的起始位置集合，進(jìn)而得到候選區(qū)間。利用類(lèi)似Commentz-Water的算法來(lái)對(duì)候選區(qū)間中的子串進(jìn)行驗(yàn)證，這樣可以過(guò)濾掉某些位置，減少重復(fù)驗(yàn)證的次數(shù)。NRGrep算法[10]也是利用前綴因子來(lái)減少匹配次數(shù)。不同的是，它使用正則表達(dá)式的反向前綴(即正則表達(dá)式的后綴)，并使用反向自動(dòng)機(jī)來(lái)對(duì)候選集合進(jìn)行驗(yàn)證。GNU grep算法[11]提出了必要因子的概念。必要因子是匹配正則表達(dá)式的字符串中必須出現(xiàn)的子串。例如，正則表達(dá)式Q為(a|g)td*,則Q的必要因子集合為{t}。必要因子能夠?qū)⒄齽t表達(dá)式拆分為左右兩部分，如Q中的必要因子t將Q拆分為(a|g)和d*。對(duì)這兩部分分別構(gòu)造兩個(gè)自動(dòng)機(jī)，在字符串中每個(gè)必要因子出現(xiàn)的位置，前后雙向驗(yàn)證。

這些算法的主要問(wèn)題如下：當(dāng)一個(gè)文本序列含有多個(gè)前綴因子或必要因子時(shí)，會(huì)削弱減少匹配次數(shù)的能力；在匹配文本集合時(shí)，需要逐條記錄進(jìn)行匹配，運(yùn)行時(shí)間與集合大小成線性關(guān)系，當(dāng)文本集合較大時(shí)，匹配代價(jià)依舊非常昂貴。

因此，本文提出一種基于廣義后綴樹(shù)與過(guò)濾因子相結(jié)合的正則表達(dá)式匹配算法。將待匹配的文本序列集合構(gòu)建成一顆廣義后綴樹(shù)，每條邊包含一個(gè)字符，從根節(jié)點(diǎn)到某一葉子節(jié)點(diǎn)的路徑即為一個(gè)后綴，葉子節(jié)點(diǎn)為包含該后綴的文本序列索引以及該后綴在文本序列中的起始位置。廣義后綴樹(shù)具有強(qiáng)大的剪枝能力，在其上運(yùn)行自動(dòng)機(jī)時(shí)，如果到達(dá)某一內(nèi)部節(jié)點(diǎn)時(shí)就已經(jīng)滿足自動(dòng)機(jī)的最終狀態(tài)，將不會(huì)再遍歷余下的分支，直接提取該內(nèi)部節(jié)點(diǎn)下所有葉子節(jié)點(diǎn)所包含的信息。并且該過(guò)程相當(dāng)于同時(shí)匹配含有該共享后綴的多個(gè)文本序列，這將節(jié)約大量的計(jì)算代價(jià)。然而當(dāng)正則表達(dá)式中含有克林閉包時(shí)，自動(dòng)機(jī)會(huì)在后綴樹(shù)上進(jìn)行很多不必要的匹配嘗試，并不能起到很好的剪枝作用。通過(guò)在廣義后綴樹(shù)中定位前綴因子和必要因子，確定所有滿足條件的文本序列候選區(qū)間，并根據(jù)前綴因子和必要因子的序列要求，產(chǎn)生更高效的過(guò)濾，從而提高整體匹配性能。通過(guò)實(shí)驗(yàn)可以證明該方法能夠顯著提高正則表達(dá)式在文本序列集合上的匹配性能。當(dāng)正則表達(dá)式包含克林閉包時(shí)，將有更顯著的性能提升。

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

1.1 正則表達(dá)式

正則表達(dá)式是一種能夠匹配一個(gè)或多個(gè)字符的模式字符串，由一系列普通字符和元字符組成。普通字符由美國(guó)信息交換標(biāo)準(zhǔn)碼ASCII構(gòu)成，元字符則包含了一些特殊的含義。正則表達(dá)式中的主要元字符如表1所示。

表1 正則表達(dá)式主要元字符

1.2 正則表達(dá)式匹配

本文中的字符串匹配，即給定一個(gè)正則表達(dá)式Q,一個(gè)文本T，得到T中能夠滿足Q所描述的所有字符串集合。如Q=t(a|c),T=ttatcdta,則Q在T上的匹配集合SQT={ta1,tc3,ta6}(下標(biāo)為子串在T中的起始位置)。特別地，當(dāng)正則表達(dá)式包含克林閉包時(shí)(尤其是包含“.*”時(shí))，匹配文本T的字符串集合將包含很多子串，如Q=t.*，T=ttatcdta，則SQT={t0,tt0,tta0,ttat0,ttatc0,ttatcd0,ttatcdt0,ttatcdta0,t1,ta1,tat1,tatc1,tatcd1,tatcdt1,tatcdta1,t3,tc3,tcd3,tcdt3,tcdta3,t6,ta6}。

2 算 法

2.1 過(guò)濾因子

經(jīng)典的正則表達(dá)式匹配算法將正則表達(dá)式編譯為一個(gè)等價(jià)的自動(dòng)機(jī)，對(duì)于文本中的每一個(gè)位置，都要重新運(yùn)行一遍自動(dòng)機(jī)來(lái)進(jìn)行驗(yàn)證，最終得到所有的匹配結(jié)果。一些算法利用過(guò)濾驗(yàn)證技術(shù)，從正則表達(dá)式中提取出一個(gè)子串，在文本中快速定位子串，得到候選匹配區(qū)間。只有這些候選區(qū)間需要被自動(dòng)機(jī)驗(yàn)證，加速了匹配過(guò)程。這些被提取的子串包括前綴因子和必要因子。

前綴因子是正則表達(dá)式中的前綴字符串，通常需要指定長(zhǎng)度。如正則表達(dá)式Q=(a|g)td*,設(shè)定前綴因子的長(zhǎng)度為2，則Q的前綴因子集合為Sp={at,gt}。匹配Q的任意一個(gè)字符串都必須以Q的前綴因子開(kāi)始。對(duì)于文本T，前綴因子所在的位置就是候選匹配結(jié)果的開(kāi)始位置，只需要從這些位置開(kāi)始驗(yàn)證自動(dòng)機(jī)。

必要因子是正則表達(dá)式的所有匹配結(jié)果中必須出現(xiàn)的最長(zhǎng)子串。例如，正則表達(dá)式Q=(a|g)td*，則必要因子集合為Sf={t}。若正則表達(dá)式Q=(a|g)taad*，則必要因子集合為Sf={taa}。必要因子將正則表達(dá)式劃分為左右兩部分。例如，Q=(a|g)taad*，必要因子taa將其劃分為兩個(gè)子表達(dá)式(a|g)和d*。在文本中定位必要因子，然后以其為中心，左右分別運(yùn)行拆分后的兩個(gè)自動(dòng)機(jī)，得到匹配結(jié)果。有些子串可能既是前綴因子，又是必要因子。本文為了高效利用前綴因子和必要因子，將包含在前綴因子中的必要因子剔除。

前綴因子和必要因子都是利用過(guò)濾技術(shù)，減少待匹配的候選區(qū)間，加速匹配過(guò)程。本文同時(shí)使用前綴因子和必要因子，增加過(guò)濾強(qiáng)度，進(jìn)一步提高匹配效率。

2.2 廣義后綴樹(shù)

廣義后綴樹(shù)是對(duì)后綴樹(shù)的擴(kuò)展。后綴樹(shù)是包含一個(gè)字符串s的所有后綴的Trie[12]結(jié)構(gòu)，可以在O(|s′|)內(nèi)確定另一個(gè)字符串s′是否為s的子串。而廣義后綴樹(shù)(Generalized Suffix Tree，GST)包含一組字符串的所有后綴，依舊可以將子串查找問(wèn)題限制在O(|s′|)的時(shí)間復(fù)雜度內(nèi)。如圖1所示，廣義后綴樹(shù)的邊包含一個(gè)字符，＄0是終端符號(hào)，葉節(jié)點(diǎn)為包含從自身到根節(jié)點(diǎn)的這條路徑(后綴)的原始字符串s0的id以及該后綴在s0中的起始位置。為了更好地理解如何在GST上進(jìn)行正則表達(dá)式匹配，本文首先介紹在GST上進(jìn)行純字符串匹配的算法。為了找到GST中包含子串s′的所有字符串，按深度優(yōu)先搜索(DFS)順序從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每個(gè)字符逐一與s′中的字符比較。如果s′的所有字符都出現(xiàn)在GST的某條路徑p中，就可以從p的葉節(jié)點(diǎn)中得到相應(yīng)的匹配結(jié)果。

圖1 GST示例

2.3 基于GST的正則表達(dá)式匹配算法

GST具有很強(qiáng)的剪枝能力，若自動(dòng)機(jī)在GST上運(yùn)行到某一內(nèi)部節(jié)點(diǎn)時(shí)就達(dá)到最終狀態(tài)，將不必再遍歷余下的分支，直接獲取該節(jié)點(diǎn)下所有葉子節(jié)點(diǎn)的文本信息。并且該過(guò)程相當(dāng)于同時(shí)匹配所有文本，有效提升了匹配速率。例如，給定文本集合T={tactgds,tadgt},正則表達(dá)式Q=ta?；贕ST的正則表達(dá)式匹配算法步驟為：

1)根據(jù)文本集合構(gòu)建GST。

2)將Q轉(zhuǎn)換為自動(dòng)機(jī)，在后綴樹(shù)上以DFS的順序運(yùn)行。

(1)從根節(jié)點(diǎn)出發(fā)，匹配第一條邊s，s≠t，匹配失敗。

(2)繼續(xù)嘗試匹配下一條邊c，c≠t，匹配失敗。

(3)繼續(xù)嘗試匹配下一條邊a，a≠t，匹配失敗。

(4)繼續(xù)嘗試匹配下一條邊t，t=t，匹配成功，遍歷余下分支。

(5)匹配到t的子樹(shù)分支a時(shí)，自動(dòng)機(jī)達(dá)到最終狀態(tài)，匹配完成。獲取該節(jié)點(diǎn)下方所有葉子節(jié)點(diǎn)的信息，得到匹配Q的所有文本。本例中為文本0和文本1。從文本0的第一個(gè)位置開(kāi)始匹配(索引為0)，從文本1的第一個(gè)位置開(kāi)始匹配(索引為0)。

但當(dāng)正則表達(dá)式中含有克林閉包時(shí)，自動(dòng)機(jī)會(huì)在GST上進(jìn)行很多無(wú)效的嘗試，尤其是包含.*時(shí)，算法性能會(huì)受到嚴(yán)重影響。如Q=t.*m，自動(dòng)機(jī)會(huì)在分支t的所有子孫進(jìn)行匹配嘗試，最終才發(fā)現(xiàn)沒(méi)有匹配結(jié)果。又如Q=t.*，t下的分支節(jié)點(diǎn)全部可以匹配，但自動(dòng)機(jī)依舊需要在所有分支上進(jìn)行匹配嘗試。當(dāng)文本集合較為龐大時(shí)，GST的內(nèi)部節(jié)點(diǎn)下可能會(huì)包含大量分支，逐一遍歷時(shí)，算法的時(shí)間復(fù)雜度較高。

2.4 基于GST與過(guò)濾因子相結(jié)合的正則表達(dá)式匹配算法

為了解決GST面對(duì)克林閉包時(shí)效率低下的問(wèn)題，同時(shí)進(jìn)一步加速正則表達(dá)式在文本集合上的匹配過(guò)程，本文將GST與過(guò)濾因子相結(jié)合，提出一種高效的正則表達(dá)式匹配算法。

首先為正則表達(dá)式構(gòu)建一棵解析樹(shù)[13]，以提取過(guò)濾因子。解析樹(shù)是一種存儲(chǔ)正則表達(dá)式語(yǔ)法信息的二叉樹(shù)。每個(gè)非葉子節(jié)點(diǎn)表示一個(gè)操作符，符號(hào)&表示連接左子樹(shù)和右子樹(shù)。解析樹(shù)左子樹(shù)的葉子節(jié)點(diǎn)集合就是前綴因子集合。從根節(jié)點(diǎn)到表示必要因子的葉子節(jié)點(diǎn)的路徑上不能含有不確定性的元字符，如|和*。為了更好地劃分前綴因子和必要因子，本文所運(yùn)用的必要因子只從根節(jié)點(diǎn)的右子樹(shù)開(kāi)始選取。圖2為正則表達(dá)式(a|c).*gt*d的解析樹(shù)，它的前綴因子集合為{a,c}，必要因子集合為{g,d}?；贕ST與過(guò)濾因子相結(jié)合的正則表達(dá)式匹配算法如算法1所示。

圖2 Q=(a|c).*gt*d的解析樹(shù)

算法1基于GST與過(guò)濾因子相結(jié)合的正則表達(dá)式匹配算法

輸入：正則表達(dá)式Q,文本集合T。

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

1.構(gòu)造解析樹(shù)，得到前綴因子集合P和必要因子集合F

2.根據(jù)P和F對(duì)Q拆分，得到子表達(dá)式集合regexCollect

3.對(duì)文本集合T構(gòu)造GST

4.For eachpinPdo

//regex_match_on_GST(p,GST)的返回結(jié)果為

//((id1,index1),(id2,index2),…)

5.matchsp←regex_match_on_GST(p,GST)

6.For eachfinFdo

7.matchsf←regex_match_on_GST(f,GST)

8.For eachmp(idp,indexp)inmatchsp

//f0代表第一個(gè)必要因子,indexf0是f0在Tidp上的索引

9.R0=Verify(Tidp,indexp,indexf0,regexCollect(0))

10.Fori<-1 1 untilregexCollect.size

11.Ri=Verify(Tidfi,indexfi-1,indexfi,regexCollect(i))

12.ReturnR

得到正則表達(dá)式的過(guò)濾因子后，將其與GST相結(jié)合，加速正則表達(dá)式在文本集合上的匹配過(guò)程。如給定文本集合T={tactgds,tadgt},Q=(a|c).*gt*d。則前綴因子集合為{a,c},必要因子集合為{g,d}。利用過(guò)濾因子將Q拆分為子表達(dá)式集合regexCollect={(a|c).*,gt*,d}。對(duì)文本集合T構(gòu)造GST，如圖1所示。在GST上匹配前綴因子，前綴因子a的匹配結(jié)果為{(0,1),(1,1)},((0,1)表示文本T0的第一個(gè)位置)，前綴因子c的匹配結(jié)果為((0,2))。在GST上匹配后綴因子,匹配g的結(jié)果為{(0,4)，(1,3)},匹配d的結(jié)果為{(0,5),(1,2)}。將前綴因子的匹配結(jié)果與第一個(gè)必要因子的匹配結(jié)果相結(jié)合，得到第一個(gè)子表達(dá)式的驗(yàn)證區(qū)間。之后對(duì)于剩余的每個(gè)必要因子，根據(jù)它與前一個(gè)必要因子的文本位置信息，依次得到后續(xù)的子表達(dá)式的驗(yàn)證區(qū)間。對(duì)于最后一個(gè)子表達(dá)式，驗(yàn)證區(qū)間為最后一個(gè)必要因子在文本中的匹配位置到文本末尾。將各個(gè)子表達(dá)式的匹配結(jié)果合并，得到最終匹配結(jié)果。算法1描述了基于GST與過(guò)濾因子相結(jié)合的整體算法流程。

3 實(shí)驗(yàn)與結(jié)果分析

為了測(cè)試基于GST與過(guò)濾因子相結(jié)合的正則表達(dá)式匹配算法的有效性，本文在兩個(gè)真實(shí)的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，分別是來(lái)自NCBI的BLAST蛋白質(zhì)序列數(shù)據(jù)集(https://blast.ncbi.nlm.nih.gov/Blast.cgi)以及DBLP-Citation的論文記錄數(shù)據(jù)集(http://arnetminer.org/DBLP Citation)，每個(gè)數(shù)據(jù)集分別抽取10 000條記錄。本文采用兩種類(lèi)型的正則表達(dá)式來(lái)評(píng)估算法在數(shù)據(jù)集上的性能，分別是人工合成的正則表達(dá)式和谷歌RE2工具(https://github.com/google/re2)自動(dòng)生成的正則表達(dá)式。每個(gè)數(shù)據(jù)集分別包含10個(gè)正則表達(dá)式，5個(gè)由人工合成，5個(gè)由RE2自動(dòng)生成。每個(gè)正則表達(dá)式查詢(xún)?cè)谙鄳?yīng)的數(shù)據(jù)集上運(yùn)行10次，取平均性能。

經(jīng)典的正則表達(dá)式匹配算法，將正則表達(dá)式轉(zhuǎn)換為自動(dòng)機(jī)，在文本的每個(gè)位置運(yùn)行一遍自動(dòng)機(jī)，得到全部匹配結(jié)果。其他算法如GNU Grep等，當(dāng)一個(gè)序列中存在多個(gè)匹配結(jié)果時(shí)，只獲取匹配的第一個(gè)結(jié)果。而本文算法是能夠匹配序列中的所有結(jié)果，因此無(wú)法公平地進(jìn)行比較。本文比較的三個(gè)算法為經(jīng)典的正則表達(dá)式匹配算法、基于廣義后綴樹(shù)的正則表達(dá)式匹配算法、基于廣義后綴樹(shù)與過(guò)濾因子相結(jié)合的正則表達(dá)式匹配算法。

實(shí)驗(yàn)所有的算法都是用Scala實(shí)現(xiàn)的，并使用C++來(lái)提取前綴因子和必要因子。實(shí)驗(yàn)是在Intel Core i5-7400 3.00 GHz CPU上進(jìn)行的，操作系統(tǒng)是Windows 10。該程序在JVM中執(zhí)行，其參數(shù)為java-Xmx4096m。

對(duì)于每個(gè)數(shù)據(jù)集，隨機(jī)抽取5個(gè)正則表達(dá)式展示實(shí)驗(yàn)效果。抽取的正則表達(dá)式如表2所示。

表2 抽取的部分正則表達(dá)式

實(shí)驗(yàn)結(jié)果如圖3-圖4所示。

圖3 蛋白質(zhì)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖4 論文數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

由實(shí)驗(yàn)結(jié)果分析可見(jiàn)，在兩個(gè)數(shù)據(jù)集中，GST+Filter的匹配效率均優(yōu)于其余兩種算法。在蛋白質(zhì)數(shù)據(jù)集中，其最大時(shí)間開(kāi)銷(xiāo)為3 s，平均時(shí)間開(kāi)銷(xiāo)為0.613 s；在論文數(shù)據(jù)集中，最大時(shí)間開(kāi)銷(xiāo)和平均時(shí)間開(kāi)銷(xiāo)分別為8.9 s和2.8 s。而GST算法在兩個(gè)數(shù)據(jù)集上的平均時(shí)間開(kāi)銷(xiāo)為84.4 s和60.2 s，經(jīng)典算法在兩個(gè)數(shù)據(jù)集中的平均時(shí)間開(kāi)銷(xiāo)為93.8 s和76.8 s。GST算法的匹配性能取決于具體的數(shù)據(jù)集和給定的正則表達(dá)式，在不包含克林閉包的情況下，GST算法具有優(yōu)異的匹配性能。但當(dāng)包含克林閉包時(shí)，GST算法的性能可能會(huì)受到影響。如對(duì)于蛋白質(zhì)數(shù)據(jù)集上的Q3e查詢(xún)及論文數(shù)據(jù)集上的Q5p查詢(xún)，GST算法的時(shí)間開(kāi)銷(xiāo)已經(jīng)近似于經(jīng)典算法，時(shí)間復(fù)雜度較大，因此影響到GST的平均匹配性能。這主要取決于廣義后綴樹(shù)的結(jié)構(gòu)以及給定的正則表達(dá)式。平均而言，GST+Filter算法的時(shí)間開(kāi)銷(xiāo)與經(jīng)典匹配算法相差兩個(gè)數(shù)量級(jí)。并且無(wú)論是否包含克林閉包，GST+Filter算法始終具有優(yōu)異的匹配性能。

4 結(jié) 語(yǔ)

正則表達(dá)式具有強(qiáng)大的表達(dá)能力，能夠提供復(fù)雜的查詢(xún)邏輯，在很多領(lǐng)域內(nèi)都發(fā)揮著重要作用。本文研究了正則表達(dá)式的匹配問(wèn)題，提出一種基于廣義后綴樹(shù)與過(guò)濾因子相結(jié)合的正則表達(dá)式匹配算法。本文首先介紹了過(guò)濾因子與廣義后綴樹(shù)的概念，將文本集合構(gòu)建成廣義后綴樹(shù)，利用過(guò)濾因子將正則表達(dá)式進(jìn)行拆分，在廣義后綴樹(shù)上匹配過(guò)濾因子，根據(jù)過(guò)濾因子的序列位置信息來(lái)確定驗(yàn)證空間。本文算法具有強(qiáng)大的過(guò)濾能力，并且能夠同時(shí)匹配多條文本，進(jìn)一步提高了正則表達(dá)式在文本集合中的匹配效率。實(shí)驗(yàn)結(jié)果表明基于廣義后綴樹(shù)與過(guò)濾因子相結(jié)合的匹配算法能夠有效提升正則表達(dá)式的匹配性能，特別當(dāng)正則表達(dá)式中包含克林閉包時(shí)，性能提升尤為顯著。