林 婧 何震瀛

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

0 引 言

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

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

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

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

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

1 正則表達式匹配定義

1.1 正則表達式

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

表1 正則表達式主要元字符

1.2 正則表達式匹配

本文中的字符串匹配，即給定一個正則表達式Q,一個文本T，得到T中能夠滿足Q所描述的所有字符串集合。如Q=t(a|c),T=ttatcdta,則Q在T上的匹配集合SQT={ta1,tc3,ta6}(下標(biāo)為子串在T中的起始位置)。特別地，當(dāng)正則表達式包含克林閉包時(尤其是包含“.*”時)，匹配文本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 過濾因子

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

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

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

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

2.2 廣義后綴樹

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

圖1 GST示例

2.3 基于GST的正則表達式匹配算法

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

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

2)將Q轉(zhuǎn)換為自動機，在后綴樹上以DFS的順序運行。

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

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

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

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

(5)匹配到t的子樹分支a時，自動機達到最終狀態(tài)，匹配完成。獲取該節(jié)點下方所有葉子節(jié)點的信息，得到匹配Q的所有文本。本例中為文本0和文本1。從文本0的第一個位置開始匹配(索引為0)，從文本1的第一個位置開始匹配(索引為0)。

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

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

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

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

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

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

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

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

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

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

3.對文本集合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代表第一個必要因子,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

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

3 實驗與結(jié)果分析

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

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

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

對于每個數(shù)據(jù)集，隨機抽取5個正則表達式展示實驗效果。抽取的正則表達式如表2所示。

表2 抽取的部分正則表達式

實驗結(jié)果如圖3-圖4所示。

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

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

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

4 結(jié) 語

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