[發明專利]一種前綴匹配算法

無效

• 申請號: 200810088002.5
• 申請日: 2008-03-24
• 公開（公告）號: CN101272386A
• 公開（公告）日: 2008-09-24
• 發明（設計）人: 邢獻武;符永貴
• 申請（專利權）人: 凹凸電子（武漢）有限公司
• 主分類號: H04L29/06
• 分類號: H04L29/06;G06F17/30
• 代理公司: 北京信慧永光知識產權代理有限責任公司
• 代理人: 王月玲;武玉琴

1.一種用于將輸入流與預定義特征字符串進行匹配的設備，包括：

一個查詢表，用于把預定義特征字符串的前綴信息存儲在一組表項中；

一個邏輯電路，連接至所述查詢表，以根據所述輸入流的一部分讀取查詢表中的表項；

一個表項緩存器，連接至所述邏輯電路，以存儲所述預定數量表項的臨時表項值，其中所述邏輯電路判斷是否找到一個基于臨時表項值的可能匹配。

2.根據權利要求1所述的設備，其特征在于，還包括：

一個輸出模塊，連接至所述邏輯電路，用于當找到所述可能的匹配時收集由臨時表項值表示的前綴信息，其中所述由臨時表項值表示的前綴信息被進一步傳送到一個精確匹配引擎進行精確特征匹配。

3.根據權利要求1所述的設備，其特征在于，所述查詢表中的所述表項是以索引的形式組織的，并且所述表項的索引對應所述預定義特征字符串的前綴。

4.根據權利要求1所述的設備，其特征在于，所述查詢表對應一個預編譯的快速存儲器。

5.根據權利要求1所述的設備，其特征在于，所述查詢表是被哈希處理的。

6.根據權利要求1所述的設備，其特征在于，輸入流的所述部分被分割成預定數量的相鄰重疊字符串，并且所述預定數量的相鄰重疊字符串分別對應所述預定數量的表項的索引。

7.根據權利要求1所述的設備，其特征在于，所述預定數量的表項在連續時鐘周期內被讀取。

8.根據權利要求1所述的設備，其特征在于，所述每個所述查詢表中的表項包括一個位置段，一個長度段和一個地址段，其中位置段的位N表示表項的索引是否對應某一預定義特征字符串中的位置N，所述長度段存儲最短預定義特征字符串的長度，其中所述最短預定義特征字符串的前綴對應所述表項的索引，并且所述地址段存儲一列預定義特征字符串的地址，其中所述預定義特征字符串的前綴對應所述表項的索引。

9.根據權利要求1所述的設備，其特征在于，所述每個臨時表項值包含位置比特組和長度比特組，所述長度比特組能夠確定與所述可能的匹配判斷相關的表項值，并且每個與臨時表項值相關的預設位置比特被檢查，以便作出可能匹配的判斷。

10.根據權利要求1所述的設備，其特征在于，當臨時表項值組滿足一個預設的條件時，則找到一個可能的匹配。

11.根據權利要求1所述的設備，其特征在于，所述匹配設備以現場可編程門陣列或者特定用途集成電路的方式實施。

12.一種將一個輸入流與預定義特征字符串進行匹配的方法，其特征在于，包括：

將預定義特征字符串的前綴信息存儲在表項組中；

根據所述輸入流的一部分讀取一預定數量的表項；

存儲所述預定數量的表項組的臨時表項值；

基于所述臨時表項值判斷是否有一個可能匹配。

13.根據權利要求12所述的方法，其特征在于，還包括：

對所述預定義特征字符串的前綴信息執行一個哈希處理。

14.根據權利要求12所述的方法，其特征在于，對所述預定數量表項的在連續時鐘周期內讀取的。

15.根據權利要求12所述的方法，其特征在于，還包括：

將由臨時表項值表示的前綴信息傳送到一精確匹配引擎；并且

基于接收到的前綴信息，在精確匹配引擎中進行精確匹配判斷。

16.根據權利要求12所述的方法，其特征在于，還包括：

使用所述預定義特征字符串的前綴對所述表項組進行索引。

17.根據權利要求12所述的方法，其特征在于，還包括：

將輸入流的一部分分割成預定數量的相鄰重疊字符串，其中預定數量的相鄰重疊字符串對應預定數量的表項索引。

18.根據權利要求12所述的方法，其特征在于，當臨時表項值組符合一預設條件時，確定一可能的匹配。

19.根據權利要求12所述的方法，其特征在于，所述每個臨時表項值包含位置比特組，長度比特組和地址比特組。