面向大數據庫正則表達式查詢的有效算法

張曉煜，林 曉，王志杰

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

?

面向大數據庫正則表達式查詢的有效算法

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

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

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

正則表達式；查詢處理；大數據庫；索引

0 引言

模式匹配在計算機科學領域有著廣泛應用，如文本編輯、符號操縱、數據檢索、網絡入侵檢測等[1-2]。‘正則表達式’在模式匹配中有著舉足輕重的作用，用來描述一系列符合某個句法規則的字符串。過去數十年，正則表達式相關研究吸引了許多學者關注[3-5]。正則表達式匹配的一種經典方法是創建一個確定性的有限自動機(DFA)，通過它來驗證輸入信息是否匹配目標信息[3]。由于DFA中狀態數目可能呈指數級，該方法可擴展性較差。另一種是基于Patricia樹的方法[6]，該方法通過創建有效的索引結構來克服傳統方法的缺陷，適合于整個索引條目能夠載入到主存儲器的情形，不太適用于處理大數據。

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

1 符號及問題定義

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

2 基于索引的方法

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

2.1 修改的前綴樹

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

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

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

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

除以上基本信息外，每個節點將附帶一個二維數組。介紹這兩個二維數組的具體構成前，先進行如下定義。

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

注意：給定一個節點和一個字符，其關鍵節點可能有多個，因為給定節點可能對應多個子樹。例如，字符‘x’關于根節點的關鍵節點為：Node(2,3)，Node(3,6)，Node(1,2)，Node(2,6)。

定義3(首次/末次關鍵節點) 給定一個節點Nd以及一個字符c，假定節點n2，n3，…，nk為字符c關于節點n1在樹的第l層出現的所有關鍵節點，則首次/末次出現的那個關鍵節點為字符c關于節點n1在第l層的首次/末次關鍵節點。特別當第l層只有一個關鍵節點時，該節點既是字符c關于節點n1在第l層的首次關鍵節點，也是末次關鍵節點。

例如，字符‘x’關于根節點在第2層的首次關鍵節點為Node(2,3)，末次關鍵節點為Node(2,6)。注意：字符‘x’關于根節點在第3層的首次和末次關鍵節點均為節點Node(3,6)，因為在該層中，字符‘x’關于根節點只有一個關鍵節點。

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

因為某些字符在某些層上可能存在多個關鍵節點，為了便于訪問所有關鍵節點，對每個節點附加一個關鍵節點指針，該指針用于指向同一層的下一個關鍵節點，用pnext表示該指針。對于末次關鍵節點，讓其pnext指針指向null。自此，就可基于節點所附加的二維數組和關鍵節點指針pnext對有相同符號的所有(關鍵)節點有效地遍歷。例如，如果初始位置在根節點，并想訪問字符‘y’在第3層的所有節點，可先通過根節點的首次關鍵節點數組得知‘y’在第3層的首次關鍵節點為Node(3,1)。然后，通過Node(3,1)的指針pnext得知其下一個關鍵節點為Node(3,2)；類似地，通過Node(3.2)的指針pnext得知下一個關鍵節點為Node(3,4)。最后，因為Node(3,4)的pnext指針為null，遍歷到此步終止。到目前為止，已經討論了MP-tree的主要構件。在下一小節，介紹如何利用MP-tree支持正則表達式查詢。值得注意的是，當對數據庫進行記錄的增加或刪除時，需要相應地更新MP-tree，其更新操作與前綴樹類似，但需要額外開銷更新MP-tree中新增的組件。

表2 根節點首次關鍵節點

表3 Node(1,4)首次關鍵節點

2.2 正則表達式查詢處理

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

表4 正則表達式查詢處理

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

表5 查詢子樹中相符記錄

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

2.3 復雜度分析

3 實驗結果

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

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

實驗運行環境如下：2.6GHzCPU，2G內存，4K頁面大小，Windows7操作系統。所有代碼均采用C++編程語言，開發工具為MicrosoftVisualStudio2010。接下來報告主要的實驗結果。

表6為數據集大小從1e+3增加到1e+8時的平均查詢時間。由表6可知：當數據集增大時，CM的查詢時間急劇增加，然而MPM的查詢時間增長速度相對較緩慢，說明其可擴展性較好。特別當數據集大小達到一定規模時，查詢時間比基線方法的查詢小幾個數量級，說明了提出方法的有效性。

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

表6 查詢時間與數據集大小

表7 I/O時間與數據集大小

表8為查詢字串長度從3增大到9的查詢時間。從表8中可知：查詢字串的長度幾乎對CM的查詢時間沒有影響，然而當查詢字串增長時，提出方法的查詢時間呈遞減趨勢，這主要因為查詢字串越長，查詢范圍將會越受限，從而大多數節點可以提前被修剪。同時，MPM的查詢時間比CM的查詢時間小幾個數量級，進一步說明了提出方法的有效性。

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

表8 查詢時間與查詢字串長度

表9 I/O時間與查詢字串長度

4 結束語

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

[1] 樊愛京,楊照峰.用于網絡入侵檢測的模式匹配新方法[J].計算機應用,2011,31(11):2961-2964.

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

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

[4] 張樹壯,羅浩,方濱興,等.一種面向網絡安全檢測的高性能正則表達式匹配算法[J].計算機學報,2010,33(10):1976-1986.

[5] 王培鳳,李莉.一種改進的多模式匹配算法在Snort中的應用[J].計算機科學,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.

國家自然科學基金項目(U1304616);河南省科技攻關基金項目(122102210480)

張曉煜(1973-),女,河南洛陽人,副教授,碩士,主要研究方向為數據處理、模式識別.

2014-11-24

1672-6871(2015)04-0056-06

TP3

A