[發明專利]一種基于關鍵詞字典樹構造的中文AC自動機工作方法

有效

• 申請號: 201510515497.5
• 申請日: 2015-08-20
• 公開（公告）號: CN105260354B
• 公開（公告）日: 2018-08-21
• 發明（設計）人: 司冰
• 申請（專利權）人: 及時標訊網絡信息技術（北京）有限公司
• 主分類號: G06F17/27
• 分類號: G06F17/27
• 代理公司: 北京風雅頌專利代理有限公司 11403
• 代理人: 李陽

本發明公開了一種基于關鍵詞字典樹構造的中文AC自動機工作方法，包括：獲取所有關鍵詞，將所有關鍵詞編碼，并將所有關鍵詞按其關鍵詞編碼的字符順序排列；建立字典樹，并將所有關鍵詞按字符排列順序加入字典樹中；為字典樹中的每個非虛根節點加入前綴指針；為字典樹中的每個非虛根節點加入失敗指針；獲取待檢測文章，根據包括前綴指針與錯誤指針的字典樹在待檢測文章中查詢并記錄下所有的關鍵詞。本發明通過將關鍵詞按順序排列加入字典樹中的技術方案，有效地將具有相同前綴的關鍵詞排布在字典樹中相鄰的位置，使得節點對查詢其子節點所在位置的信息量被大幅度壓縮，降低了中文AC自動機的工作占用空間。

技術領域

本發明涉及信息技術領域，特別地，涉及一種基于關鍵詞字典樹構造的中文AC自動機工作方法。

背景技術

AC自動機(Aho-Corasick automaton)是一種著名的多模匹配方法，用于在文章當中檢索多個關鍵詞出現的次數。傳統的AC自動機只能識別26個英文字母，現有技術則將傳統的AC自動機工作原理套用到了中文文章中，但這種方案下中文AC自動機工作的空間復雜度過高，缺乏實際應用價值。

針對現有技術中中文AC自動機工作的空間復雜度過高的問題，目前尚未有有效的解決方案。

發明內容

針對現有技術中系統結構識別與優化方法抑或主觀片面、計算能力差，抑或耗時費力、仿真精度低的問題，本發明的目的在于提出一種基于關鍵詞字典樹構造的中文AC自動機工作方法，能夠用降低中文AC自動機工作時需要的空間復雜度，壓縮了中文AC自動機的工作占用空間。

基于上述目的，本發明提供的技術方案如下：

根據本發明的一個方面，提供了一種基于關鍵詞字典樹構造的中文AC自動機工作方法，包括：

獲取所有關鍵詞，將所有關鍵詞編碼，并將所有關鍵詞按其關鍵詞編碼的字符順序排列；

建立字典樹，并將所有關鍵詞按字符排列順序加入字典樹中；

為字典樹中的每個非虛根節點加入前綴指針；

為字典樹中的每個非虛根節點加入失敗指針；

獲取待檢測文章，根據包括前綴指針與錯誤指針的字典樹在待檢測文章中查詢并記錄下所有的關鍵詞。

其中，將所有關鍵詞編碼，為將所有關鍵詞按照指定的漢字編碼方式以數字組合的形式表示；將所有關鍵詞按其關鍵詞編碼的字符順序排列，為將所有關鍵詞按其編碼后每個字符所對應數字的大小順序對所有關鍵詞進行排列。

并且，數字組合為十六進制數字的數字組合；指定的漢字編碼方式為GB2312、GBK、BIG5、UTF-8中的一種。

同時，建立字典樹為指定一虛根，并根據虛根建立字典樹。

并且，將所有關鍵詞按字符排列順序加入字典樹中包括：

根據字符排列順序依次指定每個關鍵詞；

為被指定的關鍵詞建立一個樹枝，并為被指定的關鍵詞編碼的每一位在樹枝上建立一個節點，每一位都是其前一位的子節點，每一位都是其后一位的父節點，父子節點在樹枝上相鄰；

從虛根開始，將指定的關鍵詞的樹枝與現有字典樹上字符相同的節點合并，直到出現不同的節點為止；

依次指定每個關鍵詞直到所有關鍵詞均加入字典樹中。

并且，包括：

為被指定的關鍵詞編碼的每一位在樹枝上建立一個節點，為最后一位建立一個終止節點，為最后一位之外的每一個其他位建立一個內部節點；