[發(fā)明專利]一種加速壓縮流量正則表達(dá)式匹配的Pairs方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201810420111.6
• 申請(qǐng)日: 2018-05-04
• 公開（公告）號(hào): CN108563795B
• 公開（公告）日: 2021-01-19
• 發(fā)明（設(shè)計(jì)）人: 胡成臣;孫秀文;李昊
• 申請(qǐng)（專利權(quán)）人: 西安交通大學(xué)
• 主分類號(hào): G06F16/903
• 分類號(hào): G06F16/903;H03M7/30
• 代理公司: 西安通大專利代理有限責(zé)任公司 61200
• 代理人: 徐文權(quán)

1.一種加速壓縮流量正則表達(dá)式匹配的Pairs方法，其特征在于，核心部件是壓縮流量Pairs匹配引擎(101)，其包括解碼模塊(1011)、Pairs匹配算法(1012)和有限狀態(tài)自動(dòng)機(jī)(1013)三個(gè)處理模塊，以及處理過程所需的狀態(tài)記錄數(shù)據(jù)(1014)；

壓縮流量Pairs匹配引擎(101)使用待匹配正則表達(dá)式(103)構(gòu)建有限狀態(tài)自動(dòng)機(jī)(1013)，之后對(duì)壓縮流量(102)字節(jié)內(nèi)容進(jìn)行解碼，最后使用Pairs匹配算法(1012)進(jìn)行匹配，輸出匹配結(jié)果(104)；Pairs匹配算法(1012)使用有限狀態(tài)自動(dòng)機(jī)(1013)掃描解碼后的文本字符串，使用Pairs算法對(duì)編碼字符串進(jìn)行處理；

對(duì)構(gòu)造的有限狀態(tài)自動(dòng)機(jī)(1013)的各個(gè)狀態(tài)進(jìn)行標(biāo)記，區(qū)分出Initial狀態(tài)、Begin狀態(tài)、End狀態(tài)和Normal狀態(tài)；同時(shí)以待匹配正則表達(dá)式(103)的序號(hào)，分別對(duì)Begin和End狀態(tài)進(jìn)行編號(hào)，使同一條正則表達(dá)式的具有相同的Begin和End狀態(tài)編號(hào)；

其中，在構(gòu)造非確定性有限狀態(tài)自動(dòng)機(jī)過程中，非確定性有限狀態(tài)自動(dòng)機(jī)的起始狀態(tài)的ε閉包中的所有狀態(tài)均為Initial狀態(tài)；通過Initial狀態(tài)讀入待匹配正則表達(dá)式(103)的第一個(gè)字符所到達(dá)的狀態(tài)為Begin狀態(tài)；非確定性有限狀態(tài)自動(dòng)機(jī)的接受狀態(tài)為End狀態(tài)，除被標(biāo)記為Initial、Begin和End狀態(tài)之外的其他所有非確定性有限狀態(tài)自動(dòng)機(jī)的狀態(tài)標(biāo)記為Normal狀態(tài)；

非確定性有限狀態(tài)自動(dòng)機(jī)轉(zhuǎn)換為確定性有限狀態(tài)自動(dòng)機(jī)過程中，子集中所有非確定性有限狀態(tài)自動(dòng)機(jī)狀態(tài)均為Initial狀態(tài)，則轉(zhuǎn)換后的確定性有限狀態(tài)自動(dòng)機(jī)狀態(tài)標(biāo)記為Initial狀態(tài)；子集中只要有一個(gè)狀態(tài)為Begin狀態(tài)或者End狀態(tài)，則轉(zhuǎn)換后的確定性有限狀態(tài)自動(dòng)機(jī)狀態(tài)分別對(duì)應(yīng)標(biāo)記為Begin狀態(tài)或者End狀態(tài)；除被標(biāo)記為Initial、Begin和End狀態(tài)之外的其余所有的確定性有限狀態(tài)自動(dòng)機(jī)的狀態(tài)標(biāo)記為Normal狀態(tài)；

在標(biāo)記Begin或End編號(hào)時(shí)，如果同一非確定性有限狀態(tài)自動(dòng)機(jī)或者確定性有限狀態(tài)自動(dòng)機(jī)狀態(tài)對(duì)應(yīng)多條正則表達(dá)式，則以可區(qū)分的方式標(biāo)記Begin或End的編號(hào)。

2.根據(jù)權(quán)利要求1所述的一種加速壓縮流量正則表達(dá)式匹配的Pairs方法，其特征在于，可區(qū)分的方式包括使用可區(qū)分的非確定性有限狀態(tài)自動(dòng)機(jī)或確定性有限狀態(tài)自動(dòng)機(jī)，使得每個(gè)狀態(tài)只對(duì)應(yīng)一條正則表達(dá)式規(guī)則；或者使用bitmap標(biāo)記多條規(guī)則。

3.根據(jù)權(quán)利要求1所述的一種加速壓縮流量正則表達(dá)式匹配的Pairs方法，其特征在于，使用Pairs算法處理編碼字符串時(shí)，根據(jù)出現(xiàn)的模式起始位置與編碼字符串的位置關(guān)系，分為前綴和非前綴兩種情況進(jìn)行處理；出現(xiàn)的模式起始于編碼字符串之前按前綴處理，出現(xiàn)的模式起始于編碼字符串中按非前綴處理。

4.根據(jù)權(quán)利要求3所述的一種加速壓縮流量正則表達(dá)式匹配的Pairs方法，其特征在于，壓縮流量正則表達(dá)式匹配引擎中Pairs匹配算法(1012)對(duì)編碼字符串兩種情況進(jìn)行順序處理，步驟如下：

按前綴處理時(shí)，判斷編碼字符串前一字節(jié)處返回的狀態(tài)是否為Initial狀態(tài)，若不是，從編碼字符串的開始位置繼續(xù)進(jìn)行之前的掃描，直至掃描字符后返回標(biāo)記為Initial狀態(tài)的狀態(tài)，記錄結(jié)束時(shí)候的位置偏移offPos；否則，結(jié)束按前綴處理，offPos＝0；

按非前綴處理時(shí)，找到第一個(gè)標(biāo)記為Begin狀態(tài)的位置，記為scanPos，之后查找對(duì)應(yīng)的參考字符串偏移scanPos位置之后的狀態(tài)記錄數(shù)據(jù)(1014)，若在scanPos位置之后發(fā)現(xiàn)Initial狀態(tài)或者具有相同自動(dòng)機(jī)狀態(tài)的Begin狀態(tài)，則移動(dòng)scanPos到發(fā)現(xiàn)Initial狀態(tài)或者具有相同自動(dòng)機(jī)狀態(tài)的Begin狀態(tài)的位置；若發(fā)現(xiàn)End狀態(tài)，則將此處的匹配信息記錄到匹配結(jié)果(104)，并移動(dòng)scanPos到發(fā)現(xiàn)End狀態(tài)的位置的下一字節(jié)處；檢查完成后，拷貝offPos和scanPos之間的狀態(tài)記錄值到編碼字符串對(duì)應(yīng)的位置處，并以自動(dòng)機(jī)的初始狀態(tài)，從scanPos處開始新的自動(dòng)機(jī)匹配掃描。