萌新筆記——用KMP演算法與詞典實現屏蔽敏感詞（UTF-8編碼）

前幾天寫好了字典，又剛好重溫了KMP演算法，恰逢遇到朋友吐槽最近被和諧的詞越來越多了，於是突發奇想，想要自己實現一下敏感詞屏蔽。基本敏感詞的屏蔽說起來很簡單，只要把字元串中的敏感詞替換成“***”就可以了。對於子串的查找，就KMP演算法就可以了。但是敏感詞這麼多，總不能一個一個地遍歷看看裡面有沒有相應 ...

　　前幾天寫好了字典，又剛好重溫了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 =