[發明專利]一種多字符串匹配方法和芯片

無效

• 申請號: 200710099389.X
• 申請日: 2007-05-18
• 公開（公告）號: CN101051321A
• 公開（公告）日: 2007-10-10
• 發明（設計）人: 嵩天
• 申請（專利權）人: 北京哲安科技有限公司;嵩天
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京三高永信知識產權代理有限責任公司
• 代理人: 何文彬

1.一種多字符串匹配方法，其特征在于，所述方法包括：

步驟A：接收到當前字符后，根據當前狀態、緩存狀態和所述當前字符在轉換規則庫中查找下一個狀態；所述緩存狀態為根據預設的緩存規則存儲的狀態；

步驟B：查找成功后，跳到下一個狀態，將所述下一個狀態作為當前狀態，返回步驟A，直至沒有字符輸入。

2.如權利要求1所述的多字符串匹配方法，其特征在于，所述步驟A具體包括：

步驟A1：接收到當前字符后，檢查基本轉換規則中是否有下一個狀態，如果有，根據緩存規則將所述下一個狀態緩存或清空緩存，并執行所述步驟B；否則，執行步驟A2；

步驟A2：在基本轉換規則中檢查當前狀態為緩存狀態、接收的字符為所述當前字符時是否有下一個狀態，如果有，根據緩存規則將所述下一個狀態緩存或清空緩存，并執行所述步驟B；否則，執行步驟A3；

步驟A3：在基本轉換規則中檢查當前狀態為初始狀態、接收的字符為所述當前字符時是否有下一個狀態，如果有，根據緩存規則將所述下一個狀態緩存或清空緩存，并執行所述步驟B；否則，跳到初始狀態。

3.如權利要求1或2所述的多字符串匹配方法，其特征在于，所述預設的緩存規則具體為：

在基本轉換規則中查看初始狀態接收當前字符時，如果存在下一個狀態，則將所述下一個狀態緩存，如果不存在下一個狀態，則清空緩存。

4.如權利要求1所述的多字符串匹配方法，其特征在于，所述步驟A前還包括：

合并基本轉換規則中的同構路徑。

5.如權利要求4所述的多字符串匹配方法，其特征在于，所述預設的緩存規則具體為：

如果當前狀態為匯聚狀態，則將所述當前狀態緩存；如果當前狀態為脫離狀態，則取出緩存中的緩存狀態，并清空緩存，如果當前狀態為一般狀態，則不對緩存進行操作。

6.如權利要求5所述的多字符串匹配方法，其特征在于，所述步驟A具體包括：

接收到當前字符后，判斷當前狀態的類型；

如果所述當前狀態為匯聚狀態，根據所述預設的緩存規則將所述當前狀態存儲在緩存中，并按照基本轉換規則查找下一個狀態；

如果所述當前狀態為一般狀態，則按照基本轉換規則查找下一個狀態；

如果所述當前狀態為脫離狀態，將緩存中的緩存狀態取出，根據所述當前狀態、緩存狀態和當前字符在轉換規則庫中查找下一個狀態。

7.一種多字符串匹配芯片，其特征在于，所述芯片包括：接口模塊、狀態寄存器、緩存狀態寄存器、轉換規則模塊和控制模塊；

所述接口模塊用于接收輸入的字符；

所述狀態寄存器用于存儲當前狀態；

所述緩存狀態寄存器用于存儲緩存狀態；

所述轉換規則模塊用于存儲狀態轉換規則庫，并根據所述接口模塊接收的字符、所述狀態寄存器中存儲的當前狀態和所述緩存狀態寄存器中存儲的緩存狀態查找下一個狀態；

所述控制模塊用于控制所述接口模塊正常接收輸入的字符、控制所述狀態寄存器更新當前狀態、控制所述緩存狀態寄存器更新緩存的狀態、以及控制所述轉換規則模塊查找下一個狀態。

8.如權利要求7所述的多字符串匹配芯片，其特征在于，所述轉換規則庫中的基本轉換規則為合并同構路徑后的基本轉換規則。