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

有效

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

1.一種適用于關鍵字快速檢索的方法，其特征在于，包括如下步驟：

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

步驟二：建立轉向函數；

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

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

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

④若匹配過程跳轉到模式串的最后一個狀態，說明該模式串匹配成功，輸出轉向函數g和輸出函數output；

步驟三：建立失效函數；

①輸入來自步驟二的轉向函數g和輸出函數output，初始化隊列為空，使字典樹的第一層跳轉的字符入隊，第一層狀態的失敗函數跳轉到狀態0；

②從第一層開始，廣度優先搜索樹；

③設置狀態r的失敗跳轉和初始化狀態s的失敗跳轉，使狀態s的輸出一定包含s的失敗跳轉狀態的輸出；

④得到層L1和L2所有狀態L12_states和壓縮狀態compress_states，刪除壓縮狀態的失效函數f(compress_states)；

⑤遍歷第一層狀態，入隊并加入到L12_states，遍歷第二層狀態，加入到L12_states；

⑥如果某個狀態的失敗跳轉指向層L1或L2狀態，將它加入到compress_states，并刪除它的失敗跳轉存儲；

步驟四：建立輸出函數并輸出。