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

有效

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

本發明涉及一種數字查找樹的壓縮表示方法、系統、存儲介質及規則匹配裝置。該方法包括：采用完全矩陣表示法建立數字查找樹的結點，并建立狀態轉換表；建立基值表，并利用數組記錄葉子結點狀態中對應的規則編號；利用基值表對狀態行進行歸一化，生成歸一化矩陣；利用數組來記錄歸一化矩陣的狀態，對歸一化矩陣的狀態進行去重，得到約簡的狀態轉移矩陣；利用位圖對約簡的狀態轉移矩陣進行修正，使其中的元素能夠用一個字節來表示；利用基值表、記錄歸一化矩陣狀態的數組、位圖和修正后的矩陣進行狀態的匹配，并輸出匹配結果。本發明以完全矩陣表示法為原型，能夠保證結點間狀態轉移的時間復雜度為O(1)，同時可大幅度減少數據結構的存儲空間。

技術領域

本發明屬于信息技術、軟件技術領域，具體涉及一種數字查找樹的壓縮表示方法、系統、存儲介質及規則匹配裝置。

背景技術

Trie，又稱為字典樹或者數字查找樹，是一種常用的表示字符串集合并提供前綴查找功能的數據結構。Trie的每一個結點，對應于字符串的一個前綴。每個結點最多有σ＝|Σ|個后繼狀態，其中Σ表示字符集。對Trie進行高效、緊湊地表示與壓縮，以支持快速的查詢操作，是一個基礎而重要的問題。

通常，對于Trie的表示方法有如下兩種，可以看作是在時間和空間性能上的兩個極端：

1.完全矩陣表示法：將Trie表示為N×σ大小的完全矩陣，也稱為狀態轉換表。Trie的每個結點對應于矩陣中的一行，用σ大小的數組來存儲種可能的后繼狀態。對于這種表示方法，結點間狀態轉換非常快，時間復雜度為O(1)。

2.順序數組表示法：對于Trie的每一個結點用順序數組存儲該結點的所有出度，在該數組上采用二分查找確定后繼狀態。其優點是存儲空間非常小，與狀態數量N線性相關，與字符集大小σ無關。

現有的技術方案主要是上面所述的完全矩陣表示法和順序數組表示法，這兩種方案在空間或匹配時間上都一些不足，具體如下：

1.完全矩陣表示法：這種表示方法的存儲空間往往是巨大的。假設Trie的每個結點編號用32位整數表示，則總的空間大小是4Nσ字節。

2.順序數組表示法：對于這種表示方法，結點間狀態轉換比較慢，時間復雜度為O(log₂σ)，不能實現快速定位的需求。

發明內容

本發明首先提供一種針對數字查找樹的的壓縮表示方法及系統，該方法及系統以完全矩陣表示法為原型，能夠保證結點間狀態轉移的時間復雜度為O(1)，同時可大幅度減少數據結構的存儲空間。

本發明提供的一種數字查找樹的的壓縮表示方法，包括以下步驟：

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

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

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

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

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

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

下面具體說明本發明的方法，該方法包括初始化階段和匹配階段。

1.初始化階段：

1)對數字查找樹中的結點按照完全矩陣表示法的方式建立結點，首先進行層次遍歷和順序編號，根結點的編號為0，每一層的結點編號從左到右順序遞增，所有結點的序號為0,1,···,N-1，建立狀態轉換表A[N,σ]。