[發明專利]一種大規模關鍵詞匹配方法

無效

• 申請號: 200710122231.X
• 申請日: 2007-09-24
• 公開（公告）號: CN101398820A
• 公開（公告）日: 2009-04-01
• 發明（設計）人: 葉潤國;周濤;華東明;孫海波;駱擁政;焦玉峰
• 申請（專利權）人: 北京啟明星辰信息技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京市商泰律師事務所
• 代理人: 毛燕生

1.一種大規模關鍵詞匹配方法，包括預處理階段和模式匹配階段，其特征在于包括以下步驟：

A)所述預處理階段包括以下步驟：

A1、根據設定的關鍵詞特征串長度，對關鍵詞集合中各關鍵詞進行特征串抽取，構成關鍵詞特征串集合；

A2、構造多個僅包含一個散列函數且該散列函數支持遞歸運算的簡單布隆過濾器，將步驟A1所得到的關鍵詞特征串集合同時映射到多個簡單布隆過濾器中；

A3、構造一個哈希表，將關鍵詞特征串集合映射到哈希表各單元中，對于具有哈希值沖突的元素，用鏈表方式串接起來；

A4、構建一個包含所有原始關鍵詞的線性表，步驟A3中建立的關鍵詞特征串哈希表項中包含對應原始關鍵詞的索引號；

B)所述模式匹配階段包括以下步驟：

B1、設置一個與關鍵詞特征串等長度的文本匹配窗口，首先將文本匹配窗口與待匹配文本左對齊；

B2、以當前文本匹配窗口中文本串為輸入，依次使用各簡單布隆過濾器及其散列函數，實現當前文本串不與任何關鍵詞特征串匹配的快速判定：如果基于某一簡單布隆過濾器成功實現對當前文本串的快速排除判定，則直接跳躍到步驟B5執行；如果基于當前簡單布隆過濾器的排除判定失敗，則繼續使用下一個簡單布隆過濾器；如果所有簡單布隆過濾器都執行排除判定失敗，則進入步驟B3；

B3、依據文本匹配窗口中文本串檢索關鍵詞特征串哈希表，如果找到匹配的關鍵詞特征串表項，則執行步驟B4；如果未找到任何匹配表項，則直接跳躍到步驟B5執行；

B4、根據關鍵詞特征串表項中的索引號從原始關鍵詞線性表讀取對應的原始關鍵詞，并與當前匹配窗口處文本串進行全長度字符串比較，如果匹配成功則報告一個成功的關鍵詞匹配事件；最后，不管匹配成功與失敗，都繼續執行步驟B5；

B5、將當前文本匹配窗口向右移動1字節，并跳躍到步驟B2繼續執行，直至整個文本掃描結束。

2.根據權利要求1所述的大規模關鍵詞匹配方法，其特征在于，所述預處理階段A的步驟A1為：對于原始關鍵詞集合中各關鍵詞，抽取的關鍵詞特征串為整個關鍵詞集合中出現次數最少的關鍵詞子串。

3.根據權利要求1所述的大規模關鍵詞匹配方法，其特征在于，在步驟A2中構造的簡單布隆過濾器只包含一個散列函數，該散列函數基于可遞歸運算的羅賓指紋多項式模算法構建。

4.根據權利要求1所述的大規模關鍵詞匹配方法，其特征在于，在步驟A3構造關鍵詞特征串哈希表時，選擇的哈希表散列函數是步驟A2中構造的多個簡單布隆過濾器中最后一個布隆過濾器的散列函數。