[發明專利]數字查找樹的壓縮表示方法、系統、存儲介質及規則匹配裝置

有效

• 申請號: 201810119184.1
• 申請日: 2018-02-06
• 公開（公告）號: CN108399152B
• 公開（公告）日: 2021-05-07
• 發明（設計）人: 張春燕;劉燕兵;曹聰;盧毓海;袁方方;譚建龍;郭莉
• 申請（專利權）人: 中國科學院信息工程研究所
• 主分類號: G06F40/14
• 分類號: G06F40/14;G06F16/31
• 代理公司: 北京君尚知識產權代理有限公司 11200
• 代理人: 邱曉鋒

1.一種數字查找樹的壓縮表示方法，其特征在于，包括以下步驟：

1)采用完全矩陣表示法建立數字查找樹的結點，并建立狀態轉換表；

2)將查詢狀態轉換表得到的當前狀態的最小后繼狀態作為基值，建立基值表，并利用數組記錄葉子結點狀態中對應的規則編號；

3)利用基值表對狀態行進行歸一化，生成歸一化矩陣；

4)利用數組來記錄歸一化矩陣的狀態，對歸一化矩陣的狀態進行去重，得到約簡的狀態轉移矩陣；

5)利用位圖對約簡的狀態轉移矩陣進行修正，使其中的元素能夠用一個字節來表示，得到修正后的矩陣；

6)利用基值表、記錄歸一化矩陣狀態的數組、位圖和修正后的矩陣進行狀態的匹配，并輸出匹配結果；

步驟2)中，設數字查找樹對應的狀態轉換表為A[N,σ]，t＝A[s,c]表示有一條以c為轉移從狀態s到狀態t的邊，用A[s,c]＝-1表示狀態s沒有以c為轉移的后繼狀態，對于狀態s對應的行A[s,·]，選擇最小的后繼狀態作為基值base[s]，即

步驟2)利用數組match_id來記錄葉子結點狀態中對應的規則編號，即match_id[s]＝r，s表示數字查找樹中的某一個狀態，r為匹配上的規則標號；

步驟3)生成歸一化矩陣D的操作過程為：對于每個狀態行A[s,·]，若A[s,·]＝-1，則歸一化矩陣D中相應的值也存儲為-1；若A[s,c]≥1，則矩陣D中相應的值為將A[s,·]減去步驟2)中得到的基值base[s]；

步驟4)包括：

4-1)用一個大小為N的數組eq來記錄歸一化矩陣D狀態，使得eq[s]＝k，k代表D中與s狀態相同的某一狀態，由此得到完整的數組eq；

4-2)建立約簡的狀態轉移矩陣M，矩陣D和矩陣M的行對應關系是：矩陣D中的第s行對應于矩陣M中的第eq[s]行，即D[s,·]＝M[eq[s],·]；

步驟5)包括：

5-1)定義位圖bitmap為：

5-2)對約簡的狀態轉移矩陣M進行修正，得到修正后的矩陣m：

步驟6)根據四個數據結構：base、eq、bitmap和m，得出狀態轉移的公式，表示為：

匹配過程如下：

a)如果當前基值為0，即base[s]＝0，則A[s,c]＝-1，返回匹配結果失??；

b)如果當前狀態能夠和c匹配時，即bitmap[eq[s],c]＝1，轉換到下一個狀態，轉換公式為：A[s,c]＝base[s]+m[eq[s],c]，轉到步驟a)，直至轉換狀態的次數達到文本的長度，輸出其匹配成功的規則標號match_id[s]；

c)如果當前狀態不匹配，即bitmap[eq[s],c]＝0，則返回匹配結果失敗。

2.一種采用權利要求1所述方法的數字查找樹的壓縮表示系統，其特征在于，包括：

建立狀態轉換表部件，負責建立完全矩陣，并進行層次遍歷和順序標號，從而建立狀態轉換表；

存儲各項輔助表部件，負責存儲各項輔助表，包括基值表、記錄葉子結點規則編號的數組、記錄歸一化矩陣狀態的數組、歸一化矩陣、約簡的狀態轉移矩陣、位圖、修正后的矩陣；

匹配數據部件，負責輸入待匹配的數據，并根據輔助表項進行匹配；

返回結果部件，負責返回匹配結果，匹配上的規則輸出規則號，否則輸出未匹配任何規則。

3.一種非易失性計算機可讀存儲介質，其特征在于，存儲有計算機程序，當計算機執行所述計算機程序時，所述計算機執行權利要求1所述方法的步驟。

4.一種采用權利要求1所述方法的規則匹配裝置，其特征在于，包括：

存儲單元，負責利用壓縮表示的數字查找樹存儲規則集合；

匹配單元，負責將待匹配的數據與數字查找樹中存儲的規則進行匹配，并輸出匹配結果。