多模字符串匹配算法在這里指的是在一個字符串中尋找多個模式字符字串的問題。一般來說，給出一個長字符串和很多短模式字符串，如何最快最省的求出哪些模式字符串出現在長字符串中是我們所要思考的。該算法廣泛應用于關鍵字過濾、入侵檢測、病毒檢測、分詞等等問題中。多模問題一般有trie樹，ac算法，wm算法等等。
背景
在做實際工作中，最簡單也最常用的一種自然語言處理方法就是關鍵詞匹配，例如我們要對n條文本進行過濾，那本身是一個過濾詞表的，通常進行過濾的代碼如下
|
1
2
3
4
5
6
7
|
for (string document : documents) { for (string filterword : filterwords) { if (document.contains(filterword)) { //process ... } }} |
如果文本的數量是n，過濾詞的數量是k，那么復雜度為o(nk)；如果關鍵詞的數量較多，那么支行效率是非常低的。
計算機科學中，aho–corasick算法是由alfredv.aho和margaretj.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表。
代碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
|
import java.util.*;/** */public class actrie { private boolean failurestatesconstructed = false; //是否建立了failure表 private node root; //根結點 public actrie() { this.root = new node(true); } /** * 添加一個模式串 * @param keyword */ public void addkeyword(string keyword) { if (keyword == null || keyword.length() == 0) { return; } node currentstate = this.root; for (character character : keyword.tochararray()) { currentstate = currentstate.insert(character); } currentstate.addemit(keyword); } /** * 模式匹配 * * @param text 待匹配的文本 * @return 匹配到的模式串 */ public collection<emit> parsetext(string text) { checkforconstructedfailurestates(); node currentstate = this.root; list<emit> collectedemits = new arraylist<>(); for (int position = 0; position < text.length(); position++) { character character = text.charat(position); currentstate = currentstate.nextstate(character); collection<string> emits = currentstate.emit(); if (emits == null || emits.isempty()) { continue; } for (string emit : emits) { collectedemits.add(new emit(position - emit.length() + 1, position, emit)); } } return collectedemits; } /** * 檢查是否建立了failure表 */ private void checkforconstructedfailurestates() { if (!this.failurestatesconstructed) { constructfailurestates(); } } /** * 建立failure表 */ private void constructfailurestates() { queue<node> queue = new linkedlist<>(); // 第一步，將深度為1的節點的failure設為根節點 //特殊處理：第二層要特殊處理，將這層中的節點的失敗路徑直接指向父節點(也就是根節點)。 for (node depthonestate : this.root.children()) { depthonestate.setfailure(this.root); queue.add(depthonestate); } this.failurestatesconstructed = true; // 第二步，為深度 > 1 的節點建立failure表，這是一個bfs 廣度優先遍歷 /** * 構造失敗指針的過程概括起來就一句話：設這個節點上的字母為c，沿著他父親的失敗指針走，直到走到一個節點，他的兒子中也有字母為c的節點。 * 然后把當前節點的失敗指針指向那個字母也為c的兒子。如果一直走到了root都沒找到，那就把失敗指針指向root。 * 使用廣度優先搜索bfs，層次遍歷節點來處理，每一個節點的失敗路徑。 */ while (!queue.isempty()) { node parentnode = queue.poll(); for (character transition : parentnode.gettransitions()) { node childnode = parentnode.find(transition); queue.add(childnode); node failnode = parentnode.getfailure().nextstate(transition); childnode.setfailure(failnode); childnode.addemit(failnode.emit()); } } } private static class node{ private map<character, node> map; private list<string> emits; //輸出 private node failure; //失敗中轉 private boolean isroot = false; //是否為根結點 public node(){ map = new hashmap<>(); emits = new arraylist<>(); } public node(boolean isroot) { this(); this.isroot = isroot; } public node insert(character character) { node node = this.map.get(character); if (node == null) { node = new node(); map.put(character, node); } return node; } public void addemit(string keyword) { emits.add(keyword); } public void addemit(collection<string> keywords) { emits.addall(keywords); } /** * success跳轉 * @param character * @return */ public node find(character character) { return map.get(character); } /** * 跳轉到下一個狀態 * @param transition 接受字符 * @return 跳轉結果 */ private node nextstate(character transition) { node state = this.find(transition); // 先按success跳轉 if (state != null) { return state; } //如果跳轉到根結點還是失敗，則返回根結點 if (this.isroot) { return this; } // 跳轉失敗的話，按failure跳轉 return this.failure.nextstate(transition); } public collection<node> children() { return this.map.values(); } public void setfailure(node node) { failure = node; } public node getfailure() { return failure; } public set<character> gettransitions() { return map.keyset(); } public collection<string> emit() { return this.emits == null ? collections.<string>emptylist() : this.emits; } } private static class emit{ private final string keyword; //匹配到的模式串 private final int start; private final int end; /** * 構造一個模式串匹配結果 * @param start 起點 * @param end 重點 * @param keyword 模式串 */ public emit(final int start, final int end, final string keyword) { this.start = start; this.end = end; this.keyword = keyword; } /** * 獲取對應的模式串 * @return 模式串 */ public string getkeyword() { return this.keyword; } @override public string tostring() { return super.tostring() + "=" + this.keyword; } } public static void main(string[] args) { actrie trie = new actrie(); trie.addkeyword("hers"); trie.addkeyword("his"); trie.addkeyword("she"); trie.addkeyword("he"); collection<emit> emits = trie.parsetext("ushers"); for (emit emit : emits) { system.out.println(emit.start + " " + emit.end + "\t" + emit.getkeyword()); } }} |
總結
以上就是本文關于多模字符串匹配算法原理及java實現代碼的全部內容，希望對大家有所幫助。如有不足之處，歡迎留言指出。感謝朋友們對本站的支持。
原文鏈接：https://www.cnblogs.com/hwyang/p/6836438.html
