[發明專利]關鍵詞快速過濾方法

有效

• 申請號: 201310092433.X
• 申請日: 2013-03-21
• 公開（公告）號: CN103186669B
• 公開（公告）日: 2018-07-06
• 發明（設計）人: 余小峰;程行榮;林賀輝;時宜
• 申請（專利權）人: 廈門雅迅網絡股份有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 廈門市新華專利商標代理有限公司 35203
• 代理人: 朱凌

本發明提供了一種關鍵詞快速過濾方法，包括關鍵詞索引步驟和關鍵詞匹配步驟；本發明對關鍵詞集合中的各個關鍵詞進行哈希編碼，然后通過哈希編碼進行關鍵詞匹配，其效率高于普通的多模式關鍵詞匹配算法；本發明采用的是結束符觸發關鍵詞匹配，以實現文本掃描過程中當前文本不與任何關鍵詞匹配的快速判定，并且只有當首、尾字符一致時才通過哈希值匹配關鍵詞，從而大大加快了文本掃描和匹配速度。

技術領域

本發明具體涉及一種關鍵詞快速過濾方法。

背景技術

在計算機的研究領域中，關鍵詞匹配是最早出現的計算機應用之一，其解決的問題是快速判斷某一數據塊中是否包含關鍵詞集合中的某一或某些關鍵詞。關鍵詞匹配技術廣泛應用于文本處理、網絡內容分析、入侵檢測、信息檢索和病毒檢測等領域。近年來隨著網絡技術的飛速發展和用戶的劇烈增長，網絡傳輸數據量越來越大，網絡用語越來越趨于多樣化。如何快速的屏蔽用戶的不當言論、過濾用戶發表內容中的非法詞匯已成為關鍵詞匹配領域的一項重大難題。

在網絡應用的早期，誕生了自動機、WM（Wu-Manber算法）等關鍵詞匹配算法。自動機算法是一種最直接的方法，其將每一個關鍵詞都與待匹配文本進行一次匹配，復雜度在最壞情況下需要對待匹配文本進行N(關鍵詞個數)次掃描和匹配。WM算法是在1994年由SunWu和Udi Manber提出的另一種快速而有效的多模式匹配算法。WM（Wu-Manber算法）算法利用了多級匹配和散列的思想，利用SHIFT（移動表），HASH（哈希）和PREFIX（前綴表）三個在輸入模式集合上預先建立的哈希表，以及BM算法中跳躍的思想來避免大量不必要的匹配測試。通過這兩個技術，WM算法在實際的應用中表現出了很高的效率。

WM算法是精確匹配算法，主要適用于待匹配文本是阿拉伯語系、拉丁語系的環境。在中文領域，文本的最小單元是單個漢字，且漢字與漢字之間可任意組詞，詞匯量相對于任何語言都是最龐大的。這就需要對關鍵詞匹配算法有更精確的要求，從而使得現有的關鍵詞匹配算法在實際應用中不能達到令人滿意的效率，特別是進行多關鍵詞的精確匹配，性能尤其差。

發明內容

本發明所要解決的技術問題在于提供一種關鍵詞快速過濾方法，不僅克服了傳統模式下關鍵詞匹配效率低的弊端，同時解決了現有的多模式關鍵字匹配針對漢字領域無法發揮高效特點的問題。

本發明是通過以下技術方案解決上述技術問題的：一種關鍵詞快速過濾方法，包括關鍵詞索引方法和關鍵詞匹配方法，

所述關鍵詞索引方法包含以下內容：

步驟10：構建一哈希表H1，將預設的關鍵詞集合中的各關鍵詞的哈希值存儲于哈希表H1；

步驟20：構建哈希表H2和哈希表H3，將所述關鍵詞集合中的各關鍵詞的首字符哈希值存儲于哈希表H2，將所述關鍵詞集合中的各關鍵詞的尾字符哈希值存儲于哈希表H3中；

步驟30：查詢所述關鍵詞集合中字符數最多的關鍵詞，并記錄該關鍵詞的字符長度L；

所述關鍵詞匹配方法包含以下內容：

步驟40：構造一與所述字符長度L相等長度的線性表，得到首字符列表P_L；

步驟50：將待匹配文本從前往后掃描一字符C；

步驟60：判斷字符C是否屬于所述哈希表H2中的各關鍵詞的首字符之一，若是，則將字符C及其在待匹配文本的位置地址存儲于所述首字符列表P_L，并執行步驟70；若否，執行步驟70；

步驟70：判斷字符C是否屬于哈希表H3中的各關鍵詞的尾字符之一，若是，則執行步驟90；若否，則執行步驟80；

步驟80：將待匹配文本繼續往后掃描一個字符C，判斷字符C是否為空，若是，結束流程；若否，則執行步驟60；