前幾天寫好了字典，又剛好重溫了KMP算法，恰逢遇到朋友吐槽最近被和諧的詞越來越多了，於是突發奇想，想要自己實現一下敏感詞屏蔽。
基本敏感詞的屏蔽說起來很簡單，只要把字符串中的敏感詞替換成“***”就可以了。對於子串的查找，就KMP算法就可以了。但是敏感詞這麼多，總不能一個一個地遍歷看看裡面有沒有相應的詞吧！
於是我想到了前幾天寫的字典樹。如果把它改造一下，並KMP算法結合，似乎可以節約不少時間。
首先說明一下思路：
對於KMP算法，這裡不過多闡述。對於敏感詞庫，如果把它存進字典樹，並在每個節點存上它的next值。在進行匹配的時候，遍歷主串，提取出單個字（對於UTF-8編碼，可以是任何國家的字），然後去字典樹的根結點的unordered_map中進行查找是否存在。如果不存在，則對下一個字進行相同處理；如果存在，則進入該子節點，然後繼續查找。字典樹結構如下圖：
1~6是編號，後面說明一些東西的時候用到。
Root節點裡不存任何數據，只是提供一個詞典的起始位置。那個表格用的是unordered_map。
對於一個樹型結構，如果直接用KMP算法中的next值來確定下一個應該在哪個節點進行查找似乎會有點問題。比如，對於5號節點，next值為1，但是要怎麼用這個"1"進入要查找的節點呢？
由於每個節點只需要知道自己如果匹配失敗應該跳到哪個節點，我想了以下兩種方案：
1、把next改成存著節點的地址，類似線索二叉樹，這樣可以很方便地進行節點轉換。
2、用棧，每次進入子節點，就對原節點的地址進行壓棧，next中存的值是要從棧中彈出幾個元素。
由於之前的字典樹在遍歷的時候采用list實現的棧來確定下一個詞是哪個，於是我選擇用第二種方案。
方案有了，就是如何實現的事了。
我先對字典樹的數據結構進行修改：
DictionaryData.h
1 #ifndef __DICTIONARYDATA_H__
2 #define __DICTIONARYDATA_H__
3
4 #include <string>
5 #include <unordered_map>
6 #include <memory>
7
8 namespace ccx{
9
10 using std::string;
11 using std::unordered_map;
12 using std::shared_ptr;
13
14 struct DictElem
15 {
16 string _word;
17 bool _isend;//是否到詞尾
18 int _next;//KMP next值 此處有修改，存的是彈棧數量
19 unordered_map<string, shared_ptr<DictElem> > _words;
20 };
21
22 typedef shared_ptr<DictElem> pDictElem;
23
24 }
25
26 #endif
相應地，字典樹的成員函數也要進行修改。
Dictionary.h
1 #ifndef __DICTIONARY_H__
2 #define __DICTIONARY_H__
3
4 #include "DictionaryData.h"
5 #include "DictionaryConf.h"
6
7 #include <memory>
8 #include <vector>
9 #include <list>
10
11 namespace ccx{
12
13 using std::shared_ptr;
14 using std::vector;
15 using std::list;
16 using std::pair;
17
18 class Dictionary
19 {
20 typedef pair<int, int> Loc;
21 typedef unordered_map<string, pDictElem>::iterator WordIt;
22 public:
23 Dictionary();
24 void push(const string & word);//插入
25 void push(vector<string> & words);//插入
26 bool search(const string & word);//查找
27 bool associate(const string & word, vector<string> & data);//聯想
28 string Kmp(const string & word);
29
30 private:
31 bool Kmp(vector<string> & word, vector<Loc> & loc);
32 void getKmpNext(const vector<string> & characters, vector<int> & next);
33 void AddWord(const string & word);
34 void splitWord(const string & word, vector<string> & characters);//把詞拆成字
35 int search(vector<string> & data, pDictElem & pcur);
36 pDictElem _dictionary;
37 DictionaryConf _conf;
38
39 //遍歷
40 public:
41 string getCurChar();
42 string getCurWord();
43 bool isEnd();
44 void resetIt();
45 void next();
46 private:
47 void resetPoint(pDictElem pcur);
48 void next(pDictElem & pcur, list<WordIt> & stackWord, list<pDictElem> & stackDict);
49 void nextWord(pDictElem & pcur, list<WordIt> & stackWord, list<pDictElem> & stackDict);
50 string getCurWord(list<WordIt> & stackWord);
51
52 pDictElem _pcur;
53 WordIt _itcur;
54
55 //用list實現棧，遍歷時方便
56 list<WordIt> _stackWord;
57 list<pDictElem> _stackDict;
58
59 //導入導出
60 public:
61 void leading_in();
62 void leading_out();
63 };
64
65 }
66
67 #endif
View Code
首先是對插入新詞進行修改：
1 void Dictionary::AddWord(const string & word)
2 {
3 vector<string> characters;
4 splitWord(word, characters);
5 vector<int> kmpnext;
6 getKmpNext(characters, kmpnext);
7
8 vector<int>::iterator it_int;
9 it_int = kmpnext.begin();
10 vector<string>::iterator it_char;
11 it_char = characters.begin();
12 pDictElem root;
13 root = _dictionary;
14 for(; it_char != characters.end(); ++it_char, ++it_int)
15 {
16 WordIt it_word;
17 it_word = root->_words.find(*it_char);
18
19 if(it_word == root->_words.end())
20 {
21 pair<string, pDictElem> temp;
22 temp.first = *it_char;
23 pDictElem dictemp(new DictElem);
24 dictemp->_word = *it_char;
25 dictemp->_next = *it_int;
26 dictemp->_isend = false;
27 temp.second = dictemp;
28 root->_words.insert(temp);
29 root = dictemp;
30 }else{
31 root = it_word->second;
32 }
33 }
34 if(!root->_isend)
35 {
36 root->_isend = true;
37 }
38 }
這裡的getKmpNext方法是新加入的，用來求next值：
1 void Dictionary::getKmpNext(const vector<string> & characters, vector<int> & kmpnext)
2 {
3 int size = characters.size();
4 for(int i = 0; i < size; ++i)
5 {
6 kmpnext.push_back(0);
7 }
8
9 int i = -1;
10 int j = 0;
11 kmpnext[0] = -1;
12 while(j < size)
13 {
14 if(i == -1 || kmpnext[i] == kmpnext[j])
15 {
16 ++i;
17 ++j;
18 kmpnext[j] = i;
19 }else{
20 i = kmpnext[i];
21 }
22 }
23 for(i = 0; i < size; ++i)
24 {
25 kmpnext[i] = i - kmpnext[i];
26 }
27 }
第4~7行可以用vector 的resize方法，直接修改它的容量。
22行之前就是用來求KMP算法的next數組的，後幾行是求彈棧數量的。
舉個例子：
對於模式串“編程軟件”，next數組為：-1 0 0 0，彈棧數量為1 1 2 3。如：
字典樹 棧
此時若匹配不成功，則要把“件”、“軟”、“程”全彈出來。當“編”也不匹配時，彈出，重新在root中的unordered_map中查找。
進行匹配的代碼如下：
1 bool Dictionary::Kmp(vector<string> & word, vector<Loc> & loc)
2 {
3 pDictElem root = _dictionary;
4 list<pDictElem> stackDict;
5
6 int start = 0;
7 int size = word.size();
8 int i = 0;
9 while(i < size)
10 {
11 WordIt it_word;
12 it_word = root->_words.find(word[i]);
13 if(it_word == root->_words.end())
14 {
15 if(stackDict.size())
16 {
17 int num = root->_next;
18 for(int j = 0; j < num - 1; ++j)
19 {
20 stackDict.pop_back();
21 }
22 root = stackDict.back();
23 stackDict.pop_back();
24 start += num;
25 }else{
26 ++i;
27 start = i;
28 }
29 continue;
30 }else{
31 stackDict.push_back(root);
32 root = it_word->second;
33 if(root->_isend)
34 {
35 Loc loctemp;
36 loctemp.first = start;
37 loctemp.second = i;
38 loc.push_back(loctemp);
39 start = i + 1;
40 }
41 }
42 ++i;
43 }
44 return loc.size();
45 }
形參中，word是把主串拆成字後的集合，loc是要傳出的參數，參數內容為所有的敏感詞的起始位置與結束位置。外層還有一層封裝：
1 string Dictionary::Kmp(const string & word)
2 {
3 vector<string> temp;
4 splitWord(word, temp);
5 vector<Loc> loc;
6
7 if(!Kmp(temp, loc))
8 {
9 return word;
10 }
11 int size = loc.size();
12 for(int i = 0; i < size; ++i)
13 {
14 for(int j = loc[i].first; j <= loc[i].second; ++j)
15 {
16 temp[j] = "*";
17 }
18 }
19 string ret;
20 for(auto & elem : temp)
21 {
22 ret += elem;
23 }
24 return ret;
25 }
在這裡，調用之前寫的splitWord方法對主串進行分字操作，並且把敏感詞替換成“*”，然後把結果傳出。
這些寫完差不多就可以用了。以下是測試內容：
敏感詞設定為“好好玩耍”、“編程軟件”、“編程學習”、“編程學習網站”、“編程訓練”、“編程入門”六個詞。
主串設定為“我不要好好玩耍好好進行編程學習然後建一個編程編程編程學習網站給編程纩編程軟件者使用進行編程訓練與編程學習”。
測試結果如下：
我不要好好玩耍好好進行編程學習然後建一個編程編程編程學習網站給編程纩編程軟件者使用進行編程訓練與編程學習 我不要****好好進行****然後建一個編程編程******給編程纩****者使用進行****與****
那麼，如果機智的小伙伴在敏感詞中間加了空格要怎麼辦呢？
我又想到兩種方案：
方案一，在分字之後刪除空格。
空格只占一個字節，但是在splitWord中也會被當成字存進vector，此時用erase+remore_if刪除即可：
1 bool deleterule(string & word)
2 {
3 return word == " ";
4 }
5
6 string Dictionary::Kmp(const string & word)
7 {
8 vector<string> temp;
9 splitWord(word, temp);
10
11 temp.erase(std::remove_if(temp.begin(), temp.end(), deleterule));
12
13 vector<Loc> loc;
14
15 if(!Kmp(temp, loc))
16 {
17 return word;
18 }
19 int size = loc.size();
20 for(int i = 0; i < size; ++i)
21 {
22 for(int j = loc[i].first; j <= loc[i].second; ++j)
23 {
24 temp[j] = "*";
25 }
26 }
27 string ret;
28 for(auto & elem : temp)
29 {
30 ret += elem;
31 }
32 return ret;
33 }
測試如下：
我不要好好 玩耍好好進行編程學習然後建一個編程編程編程學 習網站給編程纩編程軟件者使用進行編程訓練與編程學習 我不要****好好進行****然後建一個編程編程******給編程纩****者使用進行****與****
方案二，在匹配的時候讀到空格就跳過：
1 bool Dictionary::Kmp(vector<string> & word, vector<Loc> & loc)
2 {
3 pDictElem root = _dictionary;
4 list<pDictElem> stackDict;
5
6 int start = 0;
7 int size = word.size();
8 int i = 0;
9 while(i < size)
10 {
11 if(word[i] == " ")
12 {
13 ++i;
14 if(!stackDict.size())
15 {
16 ++start;
17 }
18 continue;
19 }
20 WordIt it_word;
21 it_word = root->_words.find(word[i]);
22 if(it_word == root->_words.end())
23 {
24 if(stackDict.size())
25 {
26 int num = root->_next;
27 for(int j = 0; j < num - 1; ++j)
28 {
29 stackDict.pop_back();
30 }
31 root = stackDict.back();
32 stackDict.pop_back();
33 start += num;
34 }else{
35 ++i;
36 start = i;
37 }
38 continue;
39 }else{
40 stackDict.push_back(root);
41 root = it_word->second;
42 if(root->_isend)
43 {
44 Loc loctemp;
45 loctemp.first = start;
46 loctemp.second = i;
47 loc.push_back(loctemp);
48 start = i + 1;
49 }
50 }
51 ++i;
52 }
53 return loc.size();
54 }
測試：
我不要好好 玩耍好好進行編程學習然後建一個編程編程編程學 習網站給編程纩編程軟件者使用進行編程訓練與編程學習 我不要*****好好進行****然後建一個編程編程**********給編程纩****者使用進行****與****
一開始的時候的BUG：
1、“編程編程編程學習”無法提取出“編程學習”
2、敏感詞起始位置亂七八糟
3、彈棧時機亂七八糟
4、敏感詞中同時存在“編程學習”與“編程學習網站”時會發生段錯誤
5、4解決了之後，會出現只匹配“編程學習”，而“網站”二字沒有替換
1~4 BUG調整一下就可以了，至於5嘛，莫明其妙就可以了，我也不知道怎麼回事。
Dictionary.cc
1 #include "Dictionary.h"
2 #include <json/json.h>
3 #include <iostream>
4 #include <fstream>
5 #include <string>
6 #include <algorithm>
7
8 #define PLAN1
9
10 namespace ccx{
11
12 using std::endl;
13 using std::cout;
14 using std::pair;
15 using std::ofstream;
16 using std::ifstream;
17
18 Dictionary::Dictionary()
19 : _dictionary(new DictElem)
20 , _conf()
21 {
22 _dictionary->_isend = false;
23 _dictionary->_next = 0;
24 _pcur = _dictionary;
25 }
26
27 void Dictionary::splitWord(const string & word, vector<string> & characters)
28 {
29 int num = word.size();
30 int i = 0;
31 while(i < num)
32 {
33 int size = 1;
34 if(word[i] & 0x80)
35 {
36 char temp = word[i];
37 temp <<= 1;
38 do{
39 temp <<= 1;
40 ++size;
41 }while(temp & 0x80);
42 }
43 string subWord;
44 subWord = word.substr(i, size);
45 characters.push_back(subWord);
46 i += size;
47 }
48 }
49
50 void Dictionary::getKmpNext(const vector<string> & characters, vector<int> & kmpnext)
51 {
52 int size = characters.size();
53 for(int i = 0; i < size; ++i)
54 {
55 kmpnext.push_back(0);
56 }
57
58 int i = -1;
59 int j = 0;
60 kmpnext[0] = -1;
61 while(j < size)
62 {
63 if(i == -1 || kmpnext[i] == kmpnext[j])
64 {
65 ++i;
66 ++j;
67 kmpnext[j] = i;
68 }else{
69 i = kmpnext[i];
70 }
71 }
72 for(i = 0; i < size; ++i)
73 {
74 kmpnext[i] = i - kmpnext[i];
75 }
76 }
77
78 void Dictionary::AddWord(const string & word)
79 {
80 vector<string> characters;
81 splitWord(word, characters);
82 vector<int> kmpnext;
83 getKmpNext(characters, kmpnext);
84
85 vector<int>::iterator it_int;
86 it_int = kmpnext.begin();
87 vector<string>::iterator it_char;
88 it_char = characters.begin();
89 pDictElem root;
90 root = _dictionary;
91 for(; it_char != characters.end(); ++it_char, ++it_int)
92 {
93 WordIt it_word;
94 it_word = root->_words.find(*it_char);
95
96 if(it_word == root->_words.end())
97 {
98 pair<string, pDictElem> temp;
99 temp.first = *it_char;
100 pDictElem dictemp(new DictElem);
101 dictemp->_word = *it_char;
102 dictemp->_next = *it_int;
103 dictemp->_isend = false;
104 temp.second = dictemp;
105 root->_words.insert(temp);
106 root = dictemp;
107 }else{
108 root = it_word->second;
109 }
110 }
111 if(!root->_isend)
112 {
113 root->_isend = true;
114 }
115 }
116
117 void Dictionary::push(const string & word)
118 {
119 AddWord(word);
120 }
121
122 void Dictionary::push(vector<string> & words)
123 {
124 int size = words.size();
125 for(int i = 0; i < size; ++i)
126 {
127 push(words[i]);
128 }
129 }
130
131 bool Dictionary::search(const string & word)
132 {
133 pDictElem root = _dictionary;
134 vector<string> temp;
135 splitWord(word, temp);
136
137 int ret = search(temp, root);
138 int size = temp.size();
139 if(ret != size)
140 {
141 return false;
142 }
143 return true;
144 }
145
146 int Dictionary::search(vector<string> & characters, pDictElem & root)
147 {
148 vector<string>::iterator it_char;
149 it_char = characters.begin();
150 root = _dictionary;
151 int i = 0;
152 for(; it_char != characters.end(); ++it_char, ++i)
153 {
154 WordIt it_word;
155 it_word = root->_words.find(*it_char);
156
157 if(it_word == root->_words.end())
158 {
159 break;
160 }else{
161 root = it_word->second;
162 }
163 }
164 return i;
165 }
166
167 bool Dictionary::associate(const string & word, vector<string> & data)
168 {
169 pDictElem root = _dictionary;
170 vector<string> temp;
171 splitWord(word, temp);
172
173 int ret = search(temp, root);
174 int size = temp.size();
175 if(ret != size)
176 {
177 return false;
178 }
179
180 list<WordIt> stackWord;
181 list<pDictElem> stackDict;
182 next(root, stackWord, stackDict);
183 while(root)
184 {
185 string temp = getCurWord(stackWord);
186 data.push_back(temp);
187 next(root, stackWord, stackDict);
188 }
189
190 if(!data.size())
191 {
192 return false;
193 }
194 return true;
195 }
196
197 #ifdef PLAN1
198 //敏感詞中帶空格的第一種方案
199 bool deleterule(string & word)
200 {
201 return word == " ";
202 }
203 #endif
204
205 string Dictionary::Kmp(const string & word)
206 {
207 vector<string> temp;
208 splitWord(word, temp);
209
210 #ifdef PLAN1
211 temp.erase(std::remove_if(temp.begin(), temp.end(), deleterule));
212 #endif
213
214 vector<Loc> loc;
215
216 if(!Kmp(temp, loc))
217 {
218 return word;
219 }
220 int size = loc.size();
221 for(int i = 0; i < size; ++i)
222 {
223 for(int j = loc[i].first; j <= loc[i].second; ++j)
224 {
225 temp[j] = "*";
226 }
227 }
228 string ret;
229 for(auto & elem : temp)
230 {
231 ret += elem;
232 }
233 return ret;
234 }
235
236 bool Dictionary::Kmp(vector<string> & word, vector<Loc> & loc)
237 {
238 pDictElem root = _dictionary;
239 list<pDictElem> stackDict;
240
241 int start = 0;
242 int size = word.size();
243 int i = 0;
244 while(i < size)
245 {
246 #ifdef PLAN2
247 //敏感詞中帶空格的第二種方案
248 if(word[i] == " ")
249 {
250 ++i;
251 if(!stackDict.size())
252 {
253 ++start;
254 }
255 continue;
256 }
257 #endif
258 WordIt it_word;
259 it_word = root->_words.find(word[i]);
260 if(it_word == root->_words.end())
261 {
262 if(stackDict.size())
263 {
264 int num = root->_next;
265 for(int j = 0; j < num - 1; ++j)
266 {
267 stackDict.pop_back();
268 }
269 root = stackDict.back();
270 stackDict.pop_back();
271 start += num;
272 }else{
273 ++i;
274 start = i;
275 }
276 continue;
277 }else{
278 stackDict.push_back(root);
279 root = it_word->second;
280 if(root->_isend)
281 {
282 Loc loctemp;
283 loctemp.first = start;
284 loctemp.second = i;
285 loc.push_back(loctemp);
286 start = i + 1;
287 }
288 }
289 ++i;
290 }
291 return loc.size();
292 }
293
294 //遍歷用
295
296 void Dictionary::resetPoint(pDictElem pcur)
297 {
298 _pcur = pcur;
299 if(_stackDict.size())
300 {
301 _stackDict.clear();
302 }
303 if(_stackWord.size())
304 {
305 _stackWord.clear();
306 }
307 next();
308 }
309
310 void Dictionary::resetIt()
311 {
312 resetPoint(_dictionary);
313 }
314
315 void Dictionary::next()
316 {
317 next(_pcur, _stackWord, _stackDict);
318 }
319
320 void Dictionary::next(pDictElem & pcur, list<WordIt> & stackWord, list<pDictElem> & stackDict)
321 {
322 while(pcur)
323 {
324 nextWord(pcur, stackWord, stackDict);
325 if(!pcur || pcur->_isend)
326 {
327 break;
328 }
329 }
330 }
331
332 void Dictionary::nextWord(pDictElem & pcur, list<WordIt> & stackWord, list<pDictElem> & stackDict)
333 {
334 if(pcur)
335 {
336 if(pcur->_words.size())
337 {
338 stackDict.push_back(pcur);
339 stackWord.push_back(pcur->_words.begin());
340 pcur = stackWord.back()->second;
341 }else{
342 ++(stackWord.back());
343 }
344 while(stackWord.back() == stackDict.back()->_words.end())
345 {
346 stackDict.pop_back();
347 stackWord.pop_back();
348 if(!stackDict.size())
349 {
350 pcur = NULL;
351 }
352 ++(stackWord.back());
353 }
354 if(pcur)
355 {
356 pcur = stackWord.back()->second;
357 }
358 }
359 }
360
361 string Dictionary::getCurChar()
362 {
363 return _pcur->_word;
364 }
365
366 string Dictionary::getCurWord()
367 {
368 return getCurWord(_stackWord);
369 }
370
371 string Dictionary::getCurWord(list<WordIt> & stackWord)
372 {
373 string temp;
374 list<WordIt>::iterator it_word;
375 it_word = stackWord.begin();
376
377 for(; it_word != stackWord.end(); ++it_word)
378 {
379 temp += (*it_word)->first;
380 }
381 return temp;
382 }
383
384 bool Dictionary::isEnd()
385 {
386 return _pcur == NULL;
387 }
388
389 void Dictionary::leading_in()//導入，失敗沒必要退出程序
390 {
391 ifstream ifs;
392 const char * path = _conf.getDictionaryPath().c_str();
393 ifs.open(path);
394 if(!ifs.good())
395 {
396 cout << "open Dictionary.json error(leading_in)" << endl;
397 }else{
398 Json::Value root;
399 Json::Reader reader;
400
401 if(!reader.parse(ifs, root, false))
402 {
403 cout << "json read Dictionary.json error" << endl;
404 }else{
405 int size = root.size();
406 for(int i = 0; i < size; ++i)
407 {
408 string word = root[i]["Word"].asString();
409 AddWord(word);
410 }
411 }
412 }
413 }
414
415 void Dictionary::leading_out()
416 {
417 Json::Value root;
418 Json::FastWriter writer;
419
420 resetIt();
421
422 while(!isEnd())
423 {
424 Json::Value elem;
425 elem["Word"] = getCurWord();
426 root.append(elem);
427 next();
428 }
429
430 string words;
431 words = writer.write(root);
432
433 ofstream ofs;
434 const char * path = _conf.getDictionaryPath().c_str();
435 ofs.open(path);
436 if(!ofs.good())
437 {
438 cout << "open Dictionary.json error(leading_out)" << endl;
439 ofs.open("Dictionary.tmp");
440 if(!ofs.good())
441 {
442 exit(EXIT_FAILURE);
443 }
444 }
445
446 ofs << words;
447 ofs.close();
448 }
449
450 }
View Code
github:https://github.com/ccx19930930/KMP_with_Dictionary
結論：我的詞典真的成了胖接口了！！！
