[發明專利]一種多關鍵詞匹配方法和裝置

無效

• 申請號: 200810212218.8
• 申請日: 2008-09-05
• 公開（公告）號: CN101364237A
• 公開（公告）日: 2009-02-11
• 發明（設計）人: 薛一波;李雪;卞建光
• 申請（專利權）人: 成都市華為賽門鐵克科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;H04L9/36;H04L29/06
• 代理公司: 北京挺立專利事務所
• 代理人: 葉樹明

1、一種多關鍵詞匹配方法，其特征在于，包括：

對關鍵詞集合進行預處理并建立相應的數據結構，所述數據結構中包括跳躍表、前綴表、子跳躍表和相同前綴長度表；

根據待匹配內容檢索所述跳躍表；

當所述跳躍表的跳躍值為零時，根據前綴表表項，調用子跳躍表和/或相同前綴長度表對所述待匹配內容進行匹配。

2、如權利要求1所述的方法，其特征在于，建立所述跳躍表包括：

對每個可能的大小為B1字節的字符串生成移動表的索引值，并將所述跳躍表中所有表項的跳躍值初始化為m-B1+1；所述m為所有關鍵詞中最短關鍵詞的長度，所述B1為2或2.5；

考察每一個關鍵詞的前m個字節，從m個字節的末尾開始依次向前，分別取B1長度的數據塊，所述數據塊的起始位置為q，對所述數據塊產生的索引查跳躍表，得到的跳躍值與m-q中較小的一個作為該項跳躍表值。

3、如權利要求1所述的方法，其特征在于，建立所述前綴表包括：

使用預定長度為B2的數據塊產生前綴表表項的索引，將具有相同前綴關鍵詞組成的鏈表作為相應表項的值，所述B2為2或3。

4、如權利要求3所述的方法，其特征在于，還包括：對所述前綴表中的每個入口加入頭節點并進行處理，所述處理具體為：

入口下只有一個關鍵詞時，所述入口的頭節點計數為1，并為所述關鍵詞建立所述子跳躍表；

入口下有多個關鍵詞時，關鍵詞個數為s，此入口頭節點的計數為s，并對該組關鍵詞按字典序排序，然后建立相同前綴長度表，最后為每個所述關鍵詞建立相對應的所述子跳躍表。

5、如權利要求4所述的方法，其特征在于，所述為關鍵詞建立所述子跳躍表包括：

初始化所有關鍵詞對應的子跳躍表項為0；

保持前m項的表值為0不變，所述m為所有關鍵詞中最短關鍵詞的長度；

將一個大小為m的窗口置于關鍵詞的第二字節處，對窗口中預定的后B1個字節產生索引查找跳躍表，得到跳躍值x；

跳躍值x不為零時，設置所述子跳躍表的m+1項跳躍值為x，并將窗口移動x個字節；

根據當前窗口后B1個字節查找跳躍表，若跳躍值不為零，則窗口中最后一個字符所對應所述子跳躍表的跳躍值為上述查找到的跳躍表的跳躍值，并重復本步驟直至查找到跳躍表中的跳躍值為零或窗口到達關鍵詞最末端；

若查找到的跳躍表中的跳躍值為零或窗口到達關鍵詞最末端，則從第m+2項開始，子跳躍表的每一項跳躍值等于當前項跳躍值與前一項跳躍值之和。

6、如權利要求4所述的方法，其特征在于，所述建立所述相同前綴長度表包括：

獲取相鄰關鍵詞的最長相同前綴子串，并將其值記錄在相應的相同前綴長度表項中。

7、如權利要求4所述的方法，其特征在于，所述頭節點具體為具有相同前綴的關鍵詞的數目，為0、1或大于1。

8、如權利要求1所述的方法，其特征在于，所述根據待匹配內容檢索所述跳躍表包括：

將一個大小為m的窗口置于待匹配內容的開始處，所述m為所有關鍵詞中最短關鍵詞的長度；

對窗口內預定的后B1個字節進行運算，用得到的運算結果檢索跳躍表。