[發明專利]用于模式匹配的方法、設備和電路

有效

• 申請號: 201310260868.0
• 申請日: 2013-06-27
• 公開（公告）號: CN104252469B
• 公開（公告）日: 2017-10-20
• 發明（設計）人: 劉丹;潘永峰;劉洋;陸泳;英彥
• 申請（專利權）人: 國際商業機器公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 中國國際貿易促進委員會專利商標事務所11038
• 代理人: 李玲

1.一種用于模式匹配的方法，所述模式匹配在模式流中尋找目標模式，所述模式流和目標模式均由元素組成，該方法包括：

獲取目標模式中的目標元素的出現次數；

初始化暫存區，其中所述暫存區指示模式流中的一個區間；

判斷暫存區中所述目標元素的出現次數是否達到所述目標模式中的目標元素的出現次數；

響應于暫存區中所述目標元素的出現次數未達到所述目標模式中的目標元素的出現次數，更新所述暫存區后返回所述判斷步驟；

響應于暫存區中所述目標元素的出現次數達到所述目標模式中的目標元素的出現次數，將最后進入所述暫存區的β個元素輸出供后續處理，其中β為所述目標模式的長度。

2.如權利要求1所述的方法，其中所述暫存區的初始長度為所述目標模式的長度。

3.如權利要求1所述的方法，在輸出所述暫存區中的元素供后續處理后進一步包括：

響應于所述后續處理發現暫存區中不包含所述目標模式，重設所述暫存區后返回所述判斷步驟。

4.如權利要求3所述的方法，其中重設所述暫存區使得新暫存區的前β-1個元素與舊暫存區的最后β-1個元素重合。

5.如權利要求1所述的方法，其中所述目標元素是可能的目標模式所包含的全部元素。

6.一種用于模式匹配的設備，所述模式匹配在模式流中尋找目標模式，所述模式流和目標模式均由元素組成，該設備包括：

獲取裝置，配置為獲取目標模式中的目標元素的出現次數；

暫存區初始化裝置，配置為初始化暫存區，其中所述暫存區指示模式流中的一個區間；

比較裝置，配置為判斷暫存區中所述目標元素的出現次數是否達到所述目標模式中的目標元素的出現次數；

更新裝置，配置為響應于暫存區中所述目標元素的出現次數未達到所述目標模式中的目標元素的出現次數，更新所述暫存區后返回進行所述判斷；

輸出裝置，配置為響應于暫存區中所述目標元素的出現次數達到所述目標模式中的目標元素的出現次數，將最后進入所述暫存區的β個元素輸出供后續處理，其中β為所述目標模式的長度。

7.如權利要求6所述的設備，其中所述暫存區的初始長度為所述目標模式的長度。

8.如權利要求6所述的設備，進一步包括：

暫存區重設裝置，響應于所述后續處理發現暫存區中不包含所述目標模式，重設所述暫存區后返回進行所述判斷。

9.如權利要求8所述的設備，其中重設所述暫存區使得新暫存區的前β-1個元素與舊暫存區的最后β-1個元素重合。

10.如權利要求6所述的設備，其中所述目標元素是可能的目標模式所包含的全部元素。

11.一種用于模式匹配的電路，包括：

暫存模塊，用于存儲當前被處理的元素；

元素解析模塊，用于確定新加入暫存區的元素；

暫存區特征表更新模塊，用于根據所述元素解析模塊的確定結果，更新暫存區中目標元素的出現次數；

暫存區特征表存儲模塊，用于記錄暫存區中各目標元素的出現次數；

參考特征表存儲模塊，用于存儲參考特征表；

比較模塊，用于比較所述暫存區特征表存儲模塊和所述參考特征表存儲模塊，以判斷暫存區中各元素的出現次數是否達到目標模式中各元素的出現次數，并且在兩者相同時輸出信號指示暫存模塊將將最后進入所述暫存區的β個元素輸出供后續處理，其中β為所述目標模式的長度。

12.如權利要求11所述的電路，其中所述元素解析模塊為譯碼器。

13.如權利要求11或12所述的電路，其中所述暫存區特征表存儲模塊在初始化暫存區時所記錄的每個元素的出現次數為0；

暫存區特征表更新模塊隨著元素逐個加入到暫存區中，對暫存區特征表存儲模塊中記錄的出現次數進行遞增；

所述參考特征表存儲模塊中存儲目標模式中各元素的出現次數。

14.如權利要求11或12所述的電路，其中所述暫存區特征表存儲模塊在初始化暫存區時所記錄的每個元素的出現次數為目標模式中各元素的出現次數；

暫存區特征表更新模塊隨著元素逐個加入到暫存區中，對暫存區特征表存儲模塊中記錄的出現次數進行遞減；

所述參考特征表存儲模塊中存儲0值。