點擊上方"java全棧技術"關注,每天學習一個java知識點
背景
在做實際工作中,最簡單也最常用的一種自然語言處理方法就是關鍵詞匹配,例如我們要對n條文本進行過濾,那本身是一個過濾詞表的,通常進行過濾的代碼如下
![「算法」關鍵詞匹配算法(多模字符串匹配算法-Aho–Corasick)](http://p2.ttnews.xyz/loading.gif)
如果文本的數量是n,過濾詞的數量是k,那麼複雜度為O(nk);如果關鍵詞的數量較多,那麼支行效率是非常低的。
計算機科學中,Aho–Corasick算法是由Alfred V. Aho和Margaret J.Corasick 發明的字符串搜索算法,用於在輸入的一串字符串中匹配有限組“字典”中的子串。它與普通字符串匹配的不同點在於同時與所有字典串進行匹配。算法均攤情況下具有近似於線性的時間複雜度,約為字符串的長度加所有匹配的數量。然而由於需要找到所有匹配數,如果每個子串互相匹配(如字典為a,aa,aaa,aaaa,輸入的字符串為aaaa),算法的時間複雜度會近似於匹配的二次函數。
原理
在一般的情況下,針對一個文本進行關鍵詞匹配,在匹配的過程中要與每個關鍵詞一一進行計算。也就是說,每與一個關鍵詞進行匹配,都要重新從文檔的開始到結束進行掃描。AC自動機的思想是,在開始時先通過詞表,對以下三種情況進行緩存:
- 按照字符轉移成功進行跳轉(success表)
- 按照字符轉移失敗進行跳轉(fail表)
- 匹配成功輸出表(output表)
因此在匹配的過程中,無需從新從文檔的開始進行匹配,而是通過緩存直接進行跳轉,從而實現近似於線性的時間複雜度。
構建
構建的過程分三個步驟,分別對success表,fail表,output表進行構建。其中output表在構建sucess和fail表進行都進行了補充。fail表是一對一的,output表是一對多的。
按照字符轉移成功進行跳轉(success表)
sucess表實際就是一棵trie樹,構建的方式和trie樹是一樣的,這裡就不贅述。
按照字符轉移失敗進行跳轉(fail表)
設這個節點上的字母為C,沿著他父親的失敗指針走,直到走到一個節點,他的兒子中也有字母為C的節點。然後把當前節點的失敗指針指向那個字母也為C的兒子。如果一直走到了root都沒找到,那就把失敗指針指向root。 使用廣度優先搜索BFS,層次遍歷節點來處理,每一個節點的失敗路徑。
匹配成功輸出表(output表)
匹配
舉例說明,按順序先後添加關鍵詞he,she,,his,hers。在匹配ushers過程中。先構建三個表,如下圖,實線是sucess表,虛線是fail表,結點後的單詞是ourput表。
![「算法」關鍵詞匹配算法(多模字符串匹配算法-Aho–Corasick)](http://p2.ttnews.xyz/loading.gif)
代碼
閱讀更多 java全棧技術 的文章