張曉煜，林 曉，王志杰

(1.鄭州航空工業(yè)管理學(xué)院 計(jì)算機(jī)科學(xué)與應(yīng)用系，河南 鄭州 450015；2.上海交通大學(xué) 計(jì)算機(jī)科學(xué)與工程系，上海 200240)

?

面向大數(shù)據(jù)庫正則表達(dá)式查詢的有效算法

張曉煜1，林 曉2，王志杰2

(1.鄭州航空工業(yè)管理學(xué)院 計(jì)算機(jī)科學(xué)與應(yīng)用系，河南 鄭州 450015；2.上海交通大學(xué) 計(jì)算機(jī)科學(xué)與工程系，上海 200240)

針對(duì)大數(shù)據(jù)庫中正則表達(dá)式查詢，提出了一種基于索引的有效算法。首先，構(gòu)造索引。該索引結(jié)構(gòu)在前綴樹基礎(chǔ)上加以改進(jìn)，為每個(gè)節(jié)點(diǎn)創(chuàng)建二維數(shù)組存放該節(jié)點(diǎn)所轄子樹各層的首次關(guān)鍵節(jié)點(diǎn)，并對(duì)每個(gè)節(jié)點(diǎn)附加關(guān)鍵節(jié)點(diǎn)指針以指向同層的下一關(guān)鍵節(jié)點(diǎn)。然后，通過所提出的索引結(jié)構(gòu)進(jìn)行查詢。最后，分析了所提出算法的時(shí)間和空間復(fù)雜度，并進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果證明：隨著數(shù)據(jù)集的增加，其查詢時(shí)間和輸入/輸出(I/O)時(shí)間增長(zhǎng)速度較緩慢，說明其可擴(kuò)展性較好，適合于大數(shù)據(jù)庫中正則表達(dá)式查詢。并且，隨著查詢字串的增加，查詢時(shí)間與I/O時(shí)間均呈遞減趨勢(shì)，證明了該算法的效率和有效性。

正則表達(dá)式；查詢處理；大數(shù)據(jù)庫；索引

0 引言

模式匹配在計(jì)算機(jī)科學(xué)領(lǐng)域有著廣泛應(yīng)用，如文本編輯、符號(hào)操縱、數(shù)據(jù)檢索、網(wǎng)絡(luò)入侵檢測(cè)等[1-2]?！齽t表達(dá)式’在模式匹配中有著舉足輕重的作用，用來描述一系列符合某個(gè)句法規(guī)則的字符串。過去數(shù)十年，正則表達(dá)式相關(guān)研究吸引了許多學(xué)者關(guān)注[3-5]。正則表達(dá)式匹配的一種經(jīng)典方法是創(chuàng)建一個(gè)確定性的有限自動(dòng)機(jī)(DFA)，通過它來驗(yàn)證輸入信息是否匹配目標(biāo)信息[3]。由于DFA中狀態(tài)數(shù)目可能呈指數(shù)級(jí)，該方法可擴(kuò)展性較差。另一種是基于Patricia樹的方法[6]，該方法通過創(chuàng)建有效的索引結(jié)構(gòu)來克服傳統(tǒng)方法的缺陷，適合于整個(gè)索引條目能夠載入到主存儲(chǔ)器的情形，不太適用于處理大數(shù)據(jù)。

面向大數(shù)據(jù)庫的正則表達(dá)式相關(guān)課題在國(guó)內(nèi)外受到廣泛關(guān)注。文獻(xiàn)[7]討論了如何高效地索引正則表達(dá)式。文獻(xiàn)[8]討論了參數(shù)化模式查詢。文獻(xiàn)[9]討論了時(shí)間序列數(shù)據(jù)庫中的子串匹配。文獻(xiàn)[10]講解了面向數(shù)據(jù)流的正則表達(dá)式查詢等。這些工作與本文關(guān)注的問題有相似之處，但在語義上與本文不同。本文提出一種有效的索引結(jié)構(gòu)MP-tree，基于該索引結(jié)構(gòu)進(jìn)一步提出了查詢處理算法，并對(duì)算法的復(fù)雜度進(jìn)行了詳細(xì)分析。隨后，通過大量實(shí)驗(yàn)證實(shí)了提出方法的效率和有效性。

1 符號(hào)及問題定義

定義1(正則表達(dá)式查詢) 給定數(shù)據(jù)庫D和查詢字串Q，正則表達(dá)式查詢是指找出記錄的字段S與查詢字串Q的正則表達(dá)式匹配的所有記錄。即對(duì)任意記錄r∈D，如果r.S為匹配字串Q的正則表達(dá)式，則r將作為結(jié)果返回；否則，r不是查詢結(jié)果。

2 基于索引的方法

為了有效支持面向大數(shù)據(jù)庫的正則表達(dá)式查詢，提出一種基于索引的方法。其主要思想是通過構(gòu)造索引來有效管理記錄。為了適應(yīng)所解決問題，提出的索引結(jié)構(gòu)在傳統(tǒng)前綴樹基礎(chǔ)上進(jìn)行適當(dāng)修改(注：傳統(tǒng)的前綴樹不能用于正則表達(dá)式查詢，因?yàn)檎齽t表達(dá)式查詢不是傳統(tǒng)意義上簡(jiǎn)單的字符串匹配)。為了區(qū)分起見，將其稱之為修改的前綴樹(MP-tree)。本節(jié)將詳細(xì)介紹這種索引結(jié)構(gòu)，并介紹具體算法來描述如何采用該索引完成所討論的查詢。

2.1 修改的前綴樹

為便于討論，本節(jié)采用一個(gè)具體例子來解釋改進(jìn)前綴樹的原理及細(xì)節(jié)。如某數(shù)據(jù)庫存放了一系列記錄(見表1)，每條記錄由兩個(gè)字段構(gòu)成：標(biāo)示字段ID及一個(gè)字符串屬性字段S。改進(jìn)索引結(jié)構(gòu)的概貌如圖1所示。

圖1 改進(jìn)的前綴樹(MP-tree)

MP-tree中每條從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑對(duì)應(yīng)于數(shù)據(jù)庫中記錄S字段的值(即一個(gè)字符串)。節(jié)點(diǎn)所處層數(shù)對(duì)應(yīng)于樹的深度，其中，根節(jié)點(diǎn)為第0層，其他節(jié)點(diǎn)層數(shù)依次類推。為每節(jié)點(diǎn)賦予一個(gè)位置信息，該信息有助于訪問和存儲(chǔ)節(jié)點(diǎn)。其位置信息由兩個(gè)元素構(gòu)成：節(jié)點(diǎn)所處的層數(shù)和節(jié)點(diǎn)在該層數(shù)所插入的次序。例如在第2層，節(jié)點(diǎn)被插入的次序?yàn)椋旱?條記錄的‘y’，第2條記錄的‘z’，第3條記錄的‘x’，依次類推。為簡(jiǎn)短起見，令Node(x，y)表示節(jié)點(diǎn)的位置信息，其中，x表示層數(shù)，y表示節(jié)點(diǎn)在該層數(shù)的位置順序。例如，Node(3,6)表示節(jié)點(diǎn)位于第3層，次序?yàn)?。

為快速知曉節(jié)點(diǎn)本身及所轄子節(jié)點(diǎn)對(duì)應(yīng)記錄的ID，為每個(gè)非葉子節(jié)點(diǎn)創(chuàng)建一個(gè)鏈表，用于保存其本身及孩子節(jié)點(diǎn)的ID信息，用Ilist表示。例如對(duì)于Node(1,1)，其Ilist將保存4個(gè)ID信息，分別為：null，3,8,1，其中，null表示從根節(jié)點(diǎn)到該節(jié)點(diǎn)所組成的字符串本身在數(shù)據(jù)庫中不存在。假如正則表達(dá)式在Node(1,1)已經(jīng)滿足匹配，那么就可簡(jiǎn)單地返回第3條、第8條和第1條記錄，因?yàn)镹ode(1,1)的子節(jié)點(diǎn)有共同的前綴。

除以上基本信息外，每個(gè)節(jié)點(diǎn)將附帶一個(gè)二維數(shù)組。介紹這兩個(gè)二維數(shù)組的具體構(gòu)成前，先進(jìn)行如下定義。

定義2(關(guān)鍵節(jié)點(diǎn)) 給定一個(gè)節(jié)點(diǎn)Nd及一個(gè)字符c，若該字符c在給定節(jié)點(diǎn)Nd的某個(gè)子樹中首次出現(xiàn)，且出現(xiàn)字符c的節(jié)點(diǎn)沒有祖先節(jié)點(diǎn)(除去節(jié)點(diǎn)Nd)也出現(xiàn)字符c，則稱出現(xiàn)字符c的那個(gè)節(jié)點(diǎn)為字符c關(guān)于節(jié)點(diǎn)Nd在該子樹的關(guān)鍵節(jié)點(diǎn)。

注意：給定一個(gè)節(jié)點(diǎn)和一個(gè)字符，其關(guān)鍵節(jié)點(diǎn)可能有多個(gè)，因?yàn)榻o定節(jié)點(diǎn)可能對(duì)應(yīng)多個(gè)子樹。例如，字符‘x’關(guān)于根節(jié)點(diǎn)的關(guān)鍵節(jié)點(diǎn)為：Node(2,3)，Node(3,6)，Node(1,2)，Node(2,6)。

定義3(首次/末次關(guān)鍵節(jié)點(diǎn)) 給定一個(gè)節(jié)點(diǎn)Nd以及一個(gè)字符c，假定節(jié)點(diǎn)n2，n3，…，nk為字符c關(guān)于節(jié)點(diǎn)n1在樹的第l層出現(xiàn)的所有關(guān)鍵節(jié)點(diǎn)，則首次/末次出現(xiàn)的那個(gè)關(guān)鍵節(jié)點(diǎn)為字符c關(guān)于節(jié)點(diǎn)n1在第l層的首次/末次關(guān)鍵節(jié)點(diǎn)。特別當(dāng)?shù)趌層只有一個(gè)關(guān)鍵節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)既是字符c關(guān)于節(jié)點(diǎn)n1在第l層的首次關(guān)鍵節(jié)點(diǎn)，也是末次關(guān)鍵節(jié)點(diǎn)。

例如，字符‘x’關(guān)于根節(jié)點(diǎn)在第2層的首次關(guān)鍵節(jié)點(diǎn)為Node(2,3)，末次關(guān)鍵節(jié)點(diǎn)為Node(2,6)。注意：字符‘x’關(guān)于根節(jié)點(diǎn)在第3層的首次和末次關(guān)鍵節(jié)點(diǎn)均為節(jié)點(diǎn)Node(3,6)，因?yàn)樵谠搶又校址畑’關(guān)于根節(jié)點(diǎn)只有一個(gè)關(guān)鍵節(jié)點(diǎn)。

現(xiàn)在介紹附加在每個(gè)節(jié)點(diǎn)上的二維數(shù)組的具體構(gòu)成。明確二維數(shù)組用于存放每個(gè)字符在該節(jié)點(diǎn)所轄子樹各層的首次關(guān)鍵節(jié)點(diǎn)。例如，表2和表3分別為根節(jié)點(diǎn)和Node(1,4)各自所附加的二維數(shù)組。以表3的第1行為例，它表示字符‘w’關(guān)于根節(jié)點(diǎn)在第l、2、3、4層的首次關(guān)鍵節(jié)點(diǎn)分別為Node(1,1)，Node(2,4)，Node(3,5)和null，其中null即為空，返回結(jié)果為Φ。

因?yàn)槟承┳址谀承由峡赡艽嬖诙鄠€(gè)關(guān)鍵節(jié)點(diǎn)，為了便于訪問所有關(guān)鍵節(jié)點(diǎn)，對(duì)每個(gè)節(jié)點(diǎn)附加一個(gè)關(guān)鍵節(jié)點(diǎn)指針，該指針用于指向同一層的下一個(gè)關(guān)鍵節(jié)點(diǎn)，用pnext表示該指針。對(duì)于末次關(guān)鍵節(jié)點(diǎn)，讓其pnext指針指向null。自此，就可基于節(jié)點(diǎn)所附加的二維數(shù)組和關(guān)鍵節(jié)點(diǎn)指針pnext對(duì)有相同符號(hào)的所有(關(guān)鍵)節(jié)點(diǎn)有效地遍歷。例如，如果初始位置在根節(jié)點(diǎn)，并想訪問字符‘y’在第3層的所有節(jié)點(diǎn)，可先通過根節(jié)點(diǎn)的首次關(guān)鍵節(jié)點(diǎn)數(shù)組得知‘y’在第3層的首次關(guān)鍵節(jié)點(diǎn)為Node(3,1)。然后，通過Node(3,1)的指針pnext得知其下一個(gè)關(guān)鍵節(jié)點(diǎn)為Node(3,2)；類似地，通過Node(3.2)的指針pnext得知下一個(gè)關(guān)鍵節(jié)點(diǎn)為Node(3,4)。最后，因?yàn)镹ode(3,4)的pnext指針為null，遍歷到此步終止。到目前為止，已經(jīng)討論了MP-tree的主要構(gòu)件。在下一小節(jié)，介紹如何利用MP-tree支持正則表達(dá)式查詢。值得注意的是，當(dāng)對(duì)數(shù)據(jù)庫進(jìn)行記錄的增加或刪除時(shí)，需要相應(yīng)地更新MP-tree，其更新操作與前綴樹類似，但需要額外開銷更新MP-tree中新增的組件。

表2 根節(jié)點(diǎn)首次關(guān)鍵節(jié)點(diǎn)

表3 Node(1,4)首次關(guān)鍵節(jié)點(diǎn)

2.2 正則表達(dá)式查詢處理

令recordList表示存放結(jié)果集的鏈表。ch表示存放字符的變量，Q[i]表示查詢字串中第i個(gè)字符，root表示MP-tree的根節(jié)點(diǎn)。表4描述了正則表達(dá)式查詢處理的偽代碼。其大致步驟是先判斷查詢字串是否為空，或者查詢字串的第1個(gè)字符是否在根節(jié)點(diǎn)的首次關(guān)鍵節(jié)點(diǎn)數(shù)組中的第i層到第(m-i+1)層存在(m是指數(shù)據(jù)庫中記錄字段S的最大長(zhǎng)度)。如果查詢字串為空或者查詢字串的第1個(gè)字符不能在根節(jié)點(diǎn)的首次關(guān)鍵節(jié)點(diǎn)數(shù)組中第i層到第(m-i+1)層找到，那么直接返回結(jié)果為Φ。否則，根據(jù)根節(jié)點(diǎn)的首次關(guān)鍵節(jié)點(diǎn)數(shù)組以及節(jié)點(diǎn)的pnext指針，找到第1個(gè)字符關(guān)于根節(jié)點(diǎn)的所有第i層到第(m-i+1)層關(guān)鍵節(jié)點(diǎn)。對(duì)于上述找到的每個(gè)關(guān)鍵節(jié)點(diǎn)，調(diào)用子函數(shù)FindRecordInSubtree( )，然后將子函數(shù)找到的結(jié)果逐一合并，最后返回結(jié)果集合recordList。

表4 正則表達(dá)式查詢處理

算法1中子函數(shù)FindRecordInSubtree( ) 是一個(gè)遞歸函數(shù)，該函數(shù)在當(dāng)前節(jié)點(diǎn)所轄子樹中進(jìn)一步查找將滿足匹配的具體記錄。算法2描述了該函數(shù)的偽代碼，如表5所示。其大致步驟為先判斷到當(dāng)前節(jié)點(diǎn)為止，是否已經(jīng)匹配；如果是，則將該節(jié)點(diǎn)Ilist中的所有記錄ID返回；注意，Ilist是用于存放節(jié)點(diǎn)本身及孩子節(jié)點(diǎn)ID的鏈表。如不能確定已經(jīng)匹配，繼續(xù)查找該節(jié)點(diǎn)的首次關(guān)鍵節(jié)點(diǎn)數(shù)組，如在該數(shù)組中找不到相應(yīng)字符的首次關(guān)鍵節(jié)點(diǎn)，則表明該節(jié)點(diǎn)后不需繼續(xù)查找，直接返回Φ。否則，根據(jù)當(dāng)前節(jié)點(diǎn)的首次關(guān)鍵節(jié)點(diǎn)數(shù)組以及節(jié)點(diǎn)的pnext指針，找到相應(yīng)字符關(guān)于當(dāng)前節(jié)點(diǎn)的所有關(guān)鍵節(jié)點(diǎn)。然后，對(duì)于上述找到的關(guān)鍵節(jié)點(diǎn)，繼續(xù)調(diào)用該遞歸函數(shù)，合并結(jié)果并返回。

表5 查詢子樹中相符記錄

例如，假定查詢字串為‘zx’，首先根據(jù)根節(jié)點(diǎn)的關(guān)鍵節(jié)點(diǎn)數(shù)組找到關(guān)于字符‘z’的在第1層到第4層的首次關(guān)鍵節(jié)點(diǎn)，這里，Node(1,4)、Node(2,2)和Node(3,3)分別為第1、2、3層的首次關(guān)鍵節(jié)點(diǎn)。然后，根據(jù)節(jié)點(diǎn)的指針pnext找到在該層的所有關(guān)于字符‘z’的關(guān)鍵節(jié)點(diǎn)。這里，Node(1,4)的pnext為空，所以第1層只有一個(gè)關(guān)于字符‘z’的關(guān)鍵節(jié)點(diǎn)；第3層也只有一個(gè)關(guān)于字符‘z’的關(guān)鍵節(jié)點(diǎn)。然而，Node(2,2)的指針pnext為Node(2,8)，Node(2,8)的指針pnext為空，所以在第2層有兩個(gè)關(guān)鍵節(jié)點(diǎn)。接下來，針對(duì)每個(gè)關(guān)于字符‘z’的關(guān)鍵節(jié)點(diǎn)，在該節(jié)點(diǎn)的關(guān)鍵節(jié)點(diǎn)數(shù)組中的第2層到第3層找關(guān)于字符‘x’的首次關(guān)鍵節(jié)點(diǎn)，根據(jù)關(guān)于字符‘x’的首次關(guān)鍵節(jié)點(diǎn)的pnext指針找到所有關(guān)于字符‘x’的關(guān)鍵節(jié)點(diǎn)。這里，Node(1,4)的關(guān)于字符‘x’的首次關(guān)鍵節(jié)點(diǎn)為Node(2,6)，且Node(2,6)的pnext為空，所以Node(1,4)的關(guān)于字符‘x’的關(guān)鍵節(jié)點(diǎn)只有一個(gè)，即Node(2,6)。類似地，對(duì)于Node(2,2)、Node(2,8)和Node(3,3)也可以找到其關(guān)于字符‘x’的關(guān)鍵節(jié)點(diǎn)，其中，關(guān)于字符‘x’的關(guān)鍵節(jié)點(diǎn)Node(2,2)的為空，Node(2,8)的為Node(3,6)，Node(3,3)的為空。所以，到目前為止，只剩下Node(2,6)和Node(3,6)這兩個(gè)關(guān)鍵節(jié)點(diǎn)所處路徑為候選結(jié)果。此時(shí)，查詢字串‘zx’的兩個(gè)字符都已檢查，因此，直接返回這兩個(gè)節(jié)點(diǎn)Ilist中的元組ID，最終返回結(jié)果為{6,8}。

2.3 復(fù)雜度分析

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

為驗(yàn)證提出方法的有效性和效率，與文獻(xiàn)[4]中方法進(jìn)行了比較。為適應(yīng)所討論問題，文獻(xiàn)[4]的算法需進(jìn)行簡(jiǎn)單的修改。具體地，首先，需要將查詢字串轉(zhuǎn)換為‘.*’形式的正則表達(dá)式；然后，調(diào)用其正則表達(dá)式匹配算法對(duì)每條記錄進(jìn)行匹配驗(yàn)證；最后，返回所有匹配記錄的ID信息。簡(jiǎn)短起見，稱這種方法為參照方法，用CM表示。稱本文提出方法為基于MP-tree方法，用MPM表示。

隨機(jī)生成一些列的字符串作為測(cè)試數(shù)據(jù)集。字符串的每個(gè)字母都從字符集合C中選取。設(shè)C={a,b,c,…,y,z}，設(shè)每條生成字符串的長(zhǎng)度為10。為測(cè)試數(shù)據(jù)集大小的影響，生成了幾組數(shù)據(jù)集大小不同的集合，其數(shù)量分別為：1e+3，1e+4，1e+5，1e+6，1e+7，5e+7，1e+8(其中,1e+7為缺省設(shè)置)。此外，為測(cè)試查詢字串長(zhǎng)度影響，使用長(zhǎng)度分別為3、4、5、6、7、8、9的字串作為查詢字串(其中，5為缺省設(shè)置)。這些字串均隨機(jī)生成，且每組生成10個(gè)。每次測(cè)試運(yùn)行10遍，然后計(jì)算平均輸入/輸出(I/O)時(shí)間和平均查詢時(shí)間(CUP時(shí)間和I/O時(shí)間之和)。

實(shí)驗(yàn)運(yùn)行環(huán)境如下：2.6GHzCPU，2G內(nèi)存，4K頁面大小，Windows7操作系統(tǒng)。所有代碼均采用C++編程語言，開發(fā)工具為MicrosoftVisualStudio2010。接下來報(bào)告主要的實(shí)驗(yàn)結(jié)果。

表6為數(shù)據(jù)集大小從1e+3增加到1e+8時(shí)的平均查詢時(shí)間。由表6可知：當(dāng)數(shù)據(jù)集增大時(shí)，CM的查詢時(shí)間急劇增加，然而MPM的查詢時(shí)間增長(zhǎng)速度相對(duì)較緩慢，說明其可擴(kuò)展性較好。特別當(dāng)數(shù)據(jù)集大小達(dá)到一定規(guī)模時(shí)，查詢時(shí)間比基線方法的查詢小幾個(gè)數(shù)量級(jí)，說明了提出方法的有效性。

表7為數(shù)據(jù)集大小對(duì)I/O時(shí)間的影響。正如所預(yù)料的，CM的I/O時(shí)間隨數(shù)據(jù)集大小增加迅速增加，然而對(duì)MPM的I/O時(shí)間影響較小(只是輕微增加)。這組結(jié)果表明：MPM更適合于大數(shù)據(jù)庫中正則表達(dá)式查詢。

表6 查詢時(shí)間與數(shù)據(jù)集大小

表7 I/O時(shí)間與數(shù)據(jù)集大小

表8為查詢字串長(zhǎng)度從3增大到9的查詢時(shí)間。從表8中可知：查詢字串的長(zhǎng)度幾乎對(duì)CM的查詢時(shí)間沒有影響，然而當(dāng)查詢字串增長(zhǎng)時(shí)，提出方法的查詢時(shí)間呈遞減趨勢(shì)，這主要因?yàn)椴樵冏执介L(zhǎng)，查詢范圍將會(huì)越受限，從而大多數(shù)節(jié)點(diǎn)可以提前被修剪。同時(shí)，MPM的查詢時(shí)間比CM的查詢時(shí)間小幾個(gè)數(shù)量級(jí)，進(jìn)一步說明了提出方法的有效性。

表9為查詢字串長(zhǎng)度對(duì)I/O的影響。從表9中容易看到：CM的I/O時(shí)間幾乎與查詢字串長(zhǎng)度無關(guān)，然而對(duì)于MPM，其I/O時(shí)間與查詢字串長(zhǎng)度成反比。即查詢字串長(zhǎng)度越大，I/O時(shí)間越小，其主要原因如先前所述，即較長(zhǎng)的查詢字串有助于限定(或減小)MP-tree搜索范圍。

表8 查詢時(shí)間與查詢字串長(zhǎng)度

表9 I/O時(shí)間與查詢字串長(zhǎng)度

4 結(jié)束語

本文提出了一種處理大數(shù)據(jù)庫中正則表達(dá)式查詢的算法，并通過理論分析和大量實(shí)驗(yàn)證明了其有效性。該算法構(gòu)造了一種新的索引結(jié)構(gòu)，并在此基礎(chǔ)上對(duì)正則表達(dá)式進(jìn)行查詢處理。查詢時(shí)，隨著數(shù)據(jù)集的增加，I/O時(shí)間和查詢時(shí)間的增加均較為緩慢，證明其適用于大數(shù)據(jù)庫中正則表達(dá)式查詢。并且隨著查詢字串的增加，其I/O時(shí)間和查詢時(shí)間反而呈遞減趨勢(shì)，其查詢效率較高。在未來工作中，將嘗試擴(kuò)展該方法使其適用于大數(shù)據(jù)庫中其他類型的查詢處理。

[1] 樊愛京,楊照峰.用于網(wǎng)絡(luò)入侵檢測(cè)的模式匹配新方法[J].計(jì)算機(jī)應(yīng)用,2011,31(11):2961-2964.

[2] 孫欽東,黃新波,王倩.面向中英文混合環(huán)境的多模式匹配算法[J].軟件學(xué)報(bào),2008,19(3):674-686.

[3] 黃昆,張大方,謝高崗,等.一種面向深度數(shù)據(jù)包檢測(cè)的緊湊型正則表達(dá)式匹配算法[J].中國(guó)科學(xué):信息科學(xué),2010,40(2):356-370.

[4] 張樹壯,羅浩,方濱興,等.一種面向網(wǎng)絡(luò)安全檢測(cè)的高性能正則表達(dá)式匹配算法[J].計(jì)算機(jī)學(xué)報(bào),2010,33(10):1976-1986.

[5] 王培鳳,李莉.一種改進(jìn)的多模式匹配算法在Snort中的應(yīng)用[J].計(jì)算機(jī)科學(xué),2012,39(2):72-75.

[6] Ricardo A B Y,Gaston H G.Fast Text Searching for Regular Expressions or Automaton Searching on Tries[J].Journal of ACM,1996,43(6):915-936.

[7] Junghoo C,Rajagopalan S.A Fast Regular Expression Indexing Engine[C]//ICDE.2002:419-430.

[8] Cédric du M,Philippe R,Michel S.Efficient Evaluation of Parameterized Pattern Queries[C]//CIKM.2005:728-735.

[9]Wook-Shin H,Jinsoo L,Yang-Sae M,et al.A New Approach for Processing Ranked Subsequence Matching Based on Ranked Union[C]//SIGMOD.2011:457-468.

[10] Anirban M,Rajeev R,Sriram V.Scalable Regular Expression Matching on Data Streams[C]//SIGMOD.2008:161-172.

國(guó)家自然科學(xué)基金項(xiàng)目(U1304616);河南省科技攻關(guān)基金項(xiàng)目(122102210480)

張曉煜(1973-),女,河南洛陽人,副教授,碩士,主要研究方向?yàn)閿?shù)據(jù)處理、模式識(shí)別.

2014-11-24

1672-6871(2015)04-0056-06

TP3

A