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

有效

• 申請號: 201810420111.6
• 申請日: 2018-05-04
• 公開（公告）號: CN108563795B
• 公開（公告）日: 2021-01-19
• 發明（設計）人: 胡成臣;孫秀文;李昊
• 申請（專利權）人: 西安交通大學
• 主分類號: G06F16/903
• 分類號: G06F16/903;H03M7/30
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 徐文權

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

壓縮流量Pairs匹配引擎(101)使用待匹配正則表達式(103)構建有限狀態自動機(1013)，之后對壓縮流量(102)字節內容進行解碼，最后使用Pairs匹配算法(1012)進行匹配，輸出匹配結果(104)；Pairs匹配算法(1012)使用有限狀態自動機(1013)掃描解碼后的文本字符串，使用Pairs算法對編碼字符串進行處理；

對構造的有限狀態自動機(1013)的各個狀態進行標記，區分出Initial狀態、Begin狀態、End狀態和Normal狀態；同時以待匹配正則表達式(103)的序號，分別對Begin和End狀態進行編號，使同一條正則表達式的具有相同的Begin和End狀態編號；

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

非確定性有限狀態自動機轉換為確定性有限狀態自動機過程中，子集中所有非確定性有限狀態自動機狀態均為Initial狀態，則轉換后的確定性有限狀態自動機狀態標記為Initial狀態；子集中只要有一個狀態為Begin狀態或者End狀態，則轉換后的確定性有限狀態自動機狀態分別對應標記為Begin狀態或者End狀態；除被標記為Initial、Begin和End狀態之外的其余所有的確定性有限狀態自動機的狀態標記為Normal狀態；

在標記Begin或End編號時，如果同一非確定性有限狀態自動機或者確定性有限狀態自動機狀態對應多條正則表達式，則以可區分的方式標記Begin或End的編號。

2.根據權利要求1所述的一種加速壓縮流量正則表達式匹配的Pairs方法，其特征在于，可區分的方式包括使用可區分的非確定性有限狀態自動機或確定性有限狀態自動機，使得每個狀態只對應一條正則表達式規則；或者使用bitmap標記多條規則。

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

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

按前綴處理時，判斷編碼字符串前一字節處返回的狀態是否為Initial狀態，若不是，從編碼字符串的開始位置繼續進行之前的掃描，直至掃描字符后返回標記為Initial狀態的狀態，記錄結束時候的位置偏移offPos；否則，結束按前綴處理，offPos＝0；

按非前綴處理時，找到第一個標記為Begin狀態的位置，記為scanPos，之后查找對應的參考字符串偏移scanPos位置之后的狀態記錄數據(1014)，若在scanPos位置之后發現Initial狀態或者具有相同自動機狀態的Begin狀態，則移動scanPos到發現Initial狀態或者具有相同自動機狀態的Begin狀態的位置；若發現End狀態，則將此處的匹配信息記錄到匹配結果(104)，并移動scanPos到發現End狀態的位置的下一字節處；檢查完成后，拷貝offPos和scanPos之間的狀態記錄值到編碼字符串對應的位置處，并以自動機的初始狀態，從scanPos處開始新的自動機匹配掃描。