[發(fā)明專利]一種正則表達式DFA空間壓縮方法和系統(tǒng)

在審

• 申請?zhí)枺?/td>: 201910134200.9
• 申請日: 2019-02-22
• 公開（公告）號: CN109977275A
• 公開（公告）日: 2019-07-05
• 發(fā)明（設(shè)計）人: 高曌;孫毅;張志強
• 申請（專利權(quán)）人: 中國科學(xué)院計算技術(shù)研究所
• 主分類號: G06F16/903
• 分類號: G06F16/903;H04L29/06
• 代理公司: 北京律誠同業(yè)知識產(chǎn)權(quán)代理有限公司 11006
• 代理人: 祁建國;梁揮

1.一種正則表達式DFA空間壓縮方法，其特征在于，包括：

步驟1、通過對正則表達式的狀態(tài)轉(zhuǎn)移邊進行掃描，讀入轉(zhuǎn)移矩陣，將該轉(zhuǎn)移矩陣中每一列的值以字符串形式存儲；

步驟2、將該該二維數(shù)組中相等的字符串對應(yīng)的字符表元素合并，得到多個等價類的哈希表；

步驟3、通過偽代碼狀態(tài)轉(zhuǎn)移邊壓縮算法，計算該正則表達式的狀態(tài)機中兩兩狀態(tài)間的相似度和該相似度對應(yīng)的權(quán)值，通過該相似度構(gòu)建相似度矩陣；

步驟4、根據(jù)該狀態(tài)機中各狀態(tài)點的狀態(tài)深度，更新該相似度矩陣；

步驟5、計算得到兩兩狀態(tài)間的相似度對應(yīng)的字符集合；

步驟6、從該相似度矩陣對應(yīng)的有向圖中的每個狀態(tài)節(jié)點開始遍歷，選取該狀態(tài)節(jié)點對應(yīng)的最大相似度轉(zhuǎn)移邊，從而完成默認(rèn)路徑的構(gòu)造，保存該默認(rèn)路徑作為最大生成樹；

步驟7、利用該最大生成樹，找到該默認(rèn)路徑的相似度對應(yīng)的權(quán)值以及對應(yīng)的該哈希表，刪除在邊壓縮前DFA中的狀態(tài)轉(zhuǎn)移邊，并在刪除前的狀態(tài)轉(zhuǎn)移路徑中增添一條權(quán)值為默認(rèn)路徑權(quán)值的默認(rèn)路徑，以完成對原來的DFA存儲進行簡化壓縮。

2.如權(quán)利要求1所述的正則表達式DFA空間壓縮方法，其特征在于，該步驟4包括：步驟41、將該狀態(tài)機中的深度低的狀態(tài)點到深度高的狀態(tài)點之間的相似度值更新為-1。

3.如權(quán)利要求1所述的正則表達式DFA空間壓縮方法，其特征在于，該步驟1包括：步驟11、根據(jù)正則表達式的狀態(tài)機中字母表和該狀態(tài)機的狀態(tài)數(shù)，創(chuàng)建用于存儲狀態(tài)轉(zhuǎn)移邊信息的二維數(shù)組。

4.如權(quán)利要求1所述的正則表達式DFA空間壓縮方法，其特征在于，該步驟7包括：步驟71、根據(jù)默認(rèn)路徑的相似度對應(yīng)的權(quán)值以及對應(yīng)的字母表，找到狀態(tài)節(jié)點A指向狀態(tài)節(jié)點B的默認(rèn)路徑，狀態(tài)節(jié)點A指向狀態(tài)節(jié)點B的鄰接邊的權(quán)值為resembleDegree[i][j]，刪除從狀態(tài)節(jié)點A開始的對應(yīng)默認(rèn)路徑的相似度權(quán)值resembleDegree[i][j]和與其相對應(yīng)的字符集合linkedAlphabet[i][j]中字符的轉(zhuǎn)移邊，之后在原來的狀態(tài)轉(zhuǎn)移路徑中增添一條權(quán)值為默認(rèn)路徑相似度resembleDegree[i][j]下的與之對應(yīng)的權(quán)值defaultWeight[i][j]的默認(rèn)路徑。

5.如權(quán)利要求4所述的正則表達式DFA空間壓縮方法，其特征在于，該狀態(tài)轉(zhuǎn)移路徑包括多個狀態(tài)轉(zhuǎn)移邊。

6.一種正則表達式DFA空間壓縮系統(tǒng)，其特征在于，包括：

模塊1、通過對正則表達式的狀態(tài)轉(zhuǎn)移邊進行掃描，讀入轉(zhuǎn)移矩陣，將該轉(zhuǎn)移矩陣中每一列的值以字符串形式存儲；

模塊2、將該該二維數(shù)組中相等的字符串對應(yīng)的字符表元素合并，得到多個等價類的哈希表；

模塊3、通過偽代碼狀態(tài)轉(zhuǎn)移邊壓縮算法，計算該正則表達式的狀態(tài)機中兩兩狀態(tài)間的相似度和該相似度對應(yīng)的權(quán)值，通過該相似度構(gòu)建相似度矩陣；

模塊4、根據(jù)該狀態(tài)機中各狀態(tài)點的狀態(tài)深度，更新該相似度矩陣；

模塊5、計算得到兩兩狀態(tài)間的相似度對應(yīng)的字符集合；

模塊6、從該相似度矩陣對應(yīng)的有向圖中的每個狀態(tài)節(jié)點開始遍歷，選取該狀態(tài)節(jié)點對應(yīng)的最大相似度轉(zhuǎn)移邊，從而完成默認(rèn)路徑的構(gòu)造，保存該默認(rèn)路徑作為最大生成樹；

模塊7、利用該最大生成樹，找到該默認(rèn)路徑的相似度對應(yīng)的權(quán)值以及對應(yīng)的該哈希表，刪除在邊壓縮前DFA中的狀態(tài)轉(zhuǎn)移邊，并在刪除前的狀態(tài)轉(zhuǎn)移路徑中增添一條權(quán)值為默認(rèn)路徑權(quán)值的默認(rèn)路徑，以完成對原來的DFA存儲進行簡化壓縮。

7.如權(quán)利要求6所述的正則表達式DFA空間壓縮系統(tǒng)，其特征在于，該模塊4包括：模塊41、將該狀態(tài)機中的深度低的狀態(tài)點到深度高的狀態(tài)點之間的相似度值更新為-1。

8.如權(quán)利要求6所述的正則表達式DFA空間壓縮系統(tǒng)，其特征在于，該模塊1包括：模塊11、根據(jù)正則表達式的狀態(tài)機中字母表和該狀態(tài)機的狀態(tài)數(shù)，創(chuàng)建用于存儲狀態(tài)轉(zhuǎn)移邊信息的二維數(shù)組。