[發明專利]一種適用于關鍵字快速檢索的方法

有效

• 申請號: 201910648907.1
• 申請日: 2019-07-18
• 公開（公告）號: CN110362669B
• 公開（公告）日: 2022-07-01
• 發明（設計）人: 徐根偉;胡建勛;王彥杰;喻民;劉超;楊瑞軍
• 申請（專利權）人: 中科信息安全共性技術國家工程研究中心有限公司
• 主分類號: G06F16/332
• 分類號: G06F16/332;G06F16/36
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明公開了信息檢索技術領域的一種適用于關鍵字快速檢索的方法，包括如下步驟：建立轉向函數；建立失效函數；建立輸出函數，通過使用哈希方法對壓縮節點組織查找表，可以在恒定時間內確定下一個狀態，若在壓縮節點處失配，不再直接進行狀態轉移，而是將模式串回退兩個字符，從root節點處重新開始匹配，僅比AC拓展算法多了一次狀態轉移，消除了80％以上的過渡邊緣，減少了大量的空間開銷，處理速度存在一定程度的提高。

技術領域

本發明涉及信息檢索技術領域，具體為一種適用于關鍵字快速檢索的方法。

背景技術

模式匹配一般是指在文本數據中搜索預定義的關鍵字。模式匹配問題是計算機科學中的一個基本問題，其研究內容在信息檢索、模式識別等眾多領域均有重要價值，在拼寫檢查、語言翻譯、數據壓縮、搜索引擎、入侵檢測、內容過濾、計算機病毒特征碼匹配以及基因序列比較等應用中起著重要的作用。比如，在一些信息獲取、文本編輯應用中，用戶會指定些關鍵字，需要在文本中快速定位關鍵字的位置。

Aho-Corasick算法(阿霍一克若思克算法，簡稱AC算法)描述了一種簡單有效的算法，能夠在任意的文本中定位有限數目的關鍵字的所有位置。其原理是:首先根據這一系列關鍵字定義一個有限狀態模式匹配機，然后把文本作為模式匹配機的輸入。只要匹配到關鍵字，就會通報本關鍵字匹配成功。

AC算法在本文中有2個版本稱為AC-basic和AC-expanded。AC-basic由3個函數實現相關功能組成，具體包括GOTO函數，和輸出功能。GOTO函數用于根據給定模式集的基礎字符Trie跟蹤正向轉換。如果沒有為輸入字符找到GOTO函數中的有效轉換，則自動機轉換到由失敗函數指定的狀態而不消耗輸入字符。故障功能和輸出功能使用線性陣列實現，而GOTO功能使用鏈接列表實現。通過將GOTO和失敗函數擴展為由當前狀態ID和輸入字符索引的全尺寸2D轉換規則表，可以提高匹配算法的處理速度。AC-basic和AC-expanded算法代表了時空頻譜中的兩個極端。AC擴展具有最快的處理速度，但需要大量的存儲空間。AC-basic的數據結構允許使用最小內存量來表示底層DFA，但其處理速度要慢得多。

基于現有AC-basic和AC-expanded存在的技術缺陷，本發明提出了一種新的AC壓縮方法。

發明內容

本發明的目的在于提供一種適用于關鍵字快速檢索的方法，以解決上述背景技術中提出的亟需設計一種關鍵字快速檢索的方法的問題。

為實現上述目的，本發明提供如下技術方案：一種適用于關鍵字快速檢索的方法，包括如下步驟：

步驟一：構建有限狀態自動機M，所述有限狀態自動機M包含轉向函數g，失敗函數f和輸出函數output，以及compress_states數組；

步驟二：建立轉向函數；

步驟三：建立失效函數；

步驟四：建立輸出函數。

進一步的，所述轉向函數的建立包括以下步驟：

A)定義有關鍵字集P＝{p₁,p₂,p₃,···,p_n}和函數enter(y)，創建第一狀態0、狀態s和字符a，根據i個模式串，建立字典樹，對在字典樹第一層不存在的字符，狀態0在這些字符上的跳轉依然指向狀態0，進行狀態s與字符a的匹配，并輸出函數enter(a1,a2,a3,···,a_m)；

B)設定初始狀態為0，模式串的索引為1，判斷循環在字典樹中是否找到已存在的模式串的相同前綴，是，得到這個前綴的最后一個狀態state，否，state＝0，前綴后面的第一個字符索引j；

C)將前綴后面的字符加入到字典樹中，并進行匹配；