前几天写好了字典，又刚好重温了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
#ifndef __DICTIONARYDATA_H__
#define __DICTIONARYDATA_H__ #include <string>
#include <unordered_map>
#include <memory> namespace ccx{ using std::string;
using std::unordered_map;
using std::shared_ptr; struct DictElem
{
string _word;
bool _isend;//是否到词尾
int _next;//KMP next值 此处有修改，存的是弹栈数量
unordered_map<string, shared_ptr<DictElem> > _words;
}; typedef shared_ptr<DictElem> pDictElem; } #endif
相应地，字典树的成员函数也要进行修改。
Dictionary.h
#ifndef __DICTIONARY_H__
#define __DICTIONARY_H__ #include "DictionaryData.h"
#include "DictionaryConf.h" #include <memory>
#include <vector>
#include <list> namespace ccx{ using std::shared_ptr;
using std::vector;
using std::list;
using std::pair; class Dictionary
{
typedef pair<int, int> Loc;
typedef unordered_map<string, pDictElem>::iterator WordIt;
public:
Dictionary();
void push(const string & word);//插入
void push(vector<string> & words);//插入
bool search(const string & word);//查找
bool associate(const string & word, vector<string> & data);//联想
string Kmp(const string & word); private:
bool Kmp(vector<string> & word, vector<Loc> & loc);
void getKmpNext(const vector<string> & characters, vector<int> & next);
void AddWord(const string & word);
void splitWord(const string & word, vector<string> & characters);//把词拆成字
int search(vector<string> & data, pDictElem & pcur);
pDictElem _dictionary;
DictionaryConf _conf; //遍历
public:
string getCurChar();
string getCurWord();
bool isEnd();
void resetIt();
void next();
private:
void resetPoint(pDictElem pcur);
void next(pDictElem & pcur, list<WordIt> & stackWord, list<pDictElem> & stackDict);
void nextWord(pDictElem & pcur, list<WordIt> & stackWord, list<pDictElem> & stackDict);
string getCurWord(list<WordIt> & stackWord); pDictElem _pcur;
WordIt _itcur; //用list实现栈，遍历时方便
list<WordIt> _stackWord;
list<pDictElem> _stackDict; //导入导出
public:
void leading_in();
void leading_out();
}; } #endif
首先是对插入新词进行修改：
void Dictionary::AddWord(const string & word)
{
vector<string> characters;
splitWord(word, characters);
vector<int> kmpnext;
getKmpNext(characters, kmpnext); vector<int>::iterator it_int;
it_int = kmpnext.begin();
vector<string>::iterator it_char;
it_char = characters.begin();
pDictElem root;
root = _dictionary;
for(; it_char != characters.end(); ++it_char, ++it_int)
{
WordIt it_word;
it_word = root->_words.find(*it_char); if(it_word == root->_words.end())
{
pair<string, pDictElem> temp;
temp.first = *it_char;
pDictElem dictemp(new DictElem);
dictemp->_word = *it_char;
dictemp->_next = *it_int;
dictemp->_isend = false;
temp.second = dictemp;
root->_words.insert(temp);
root = dictemp;
}else{
root = it_word->second;
}
}
if(!root->_isend)
{
root->_isend = true;
}
}
这里的getKmpNext方法是新加入的，用来求next值：
void Dictionary::getKmpNext(const vector<string> & characters, vector<int> & kmpnext)
{
int size = characters.size();
for(int i = ; i < size; ++i)
{
kmpnext.push_back();
} int i = -;
int j = ;
kmpnext[] = -;
while(j < size)
{
if(i == - || kmpnext[i] == kmpnext[j])
{
++i;
++j;
kmpnext[j] = i;
}else{
i = kmpnext[i];
}
}
for(i = ; i < size; ++i)
{
kmpnext[i] = i - kmpnext[i];
}
}
第4~7行可以用vector 的resize方法，直接修改它的容量。
22行之前就是用来求KMP算法的next数组的，后几行是求弹栈数量的。
举个例子：
对于模式串“编程软件”，next数组为：-1 0 0 0，弹栈数量为1 1 2 3。如：
字典树 栈
此时若匹配不成功，则要把“件”、“软”、“程”全弹出来。当“编”也不匹配时，弹出，重新在root中的unordered_map中查找。
进行匹配的代码如下：
bool Dictionary::Kmp(vector<string> & word, vector<Loc> & loc)
{
pDictElem root = _dictionary;
list<pDictElem> stackDict; int start = ;
int size = word.size();
int i = ;
while(i < size)
{
WordIt it_word;
it_word = root->_words.find(word[i]);
if(it_word == root->_words.end())
{
if(stackDict.size())
{
int num = root->_next;
for(int j = ; j < num - ; ++j)
{
stackDict.pop_back();
}
root = stackDict.back();
stackDict.pop_back();
start += num;
}else{
++i;
start = i;
}
continue;
}else{
stackDict.push_back(root);
root = it_word->second;
if(root->_isend)
{
Loc loctemp;
loctemp.first = start;
loctemp.second = i;
loc.push_back(loctemp);
start = i + ;
}
}
++i;
}
return loc.size();
}
形参中，word是把主串拆成字后的集合，loc是要传出的参数，参数内容为所有的敏感词的起始位置与结束位置。外层还有一层封装：
string Dictionary::Kmp(const string & word)
{
vector<string> temp;
splitWord(word, temp);
vector<Loc> loc; if(!Kmp(temp, loc))
{
return word;
}
int size = loc.size();
for(int i = ; i < size; ++i)
{
for(int j = loc[i].first; j <= loc[i].second; ++j)
{
temp[j] = "*";
}
}
string ret;
for(auto & elem : temp)
{
ret += elem;
}
return ret;
}
在这里，调用之前写的splitWord方法对主串进行分字操作，并且把敏感词替换成“*”，然后把结果传出。
这些写完差不多就可以用了。以下是测试内容：
敏感词设定为“好好玩耍”、“编程软件”、“编程学习”、“编程学习网站”、“编程训练”、“编程入门”六个词。
主串设定为“我不要好好玩耍好好进行编程学习然后建一个编程编程编程学习网站给编程纩编程软件者使用进行编程训练与编程学习”。
测试结果如下：
我不要好好玩耍好好进行编程学习然后建一个编程编程编程学习网站给编程纩编程软件者使用进行编程训练与编程学习
我不要****好好进行****然后建一个编程编程******给编程纩****者使用进行****与****
那么，如果机智的小伙伴在敏感词中间加了空格要怎么办呢？
我又想到两种方案：
方案一，在分字之后删除空格。
空格只占一个字节，但是在splitWord中也会被当成字存进vector，此时用erase+remore_if删除即可：
bool deleterule(string & word)
{
return word == " ";
} string Dictionary::Kmp(const string & word)
{
vector<string> temp;
splitWord(word, temp); temp.erase(std::remove_if(temp.begin(), temp.end(), deleterule)); vector<Loc> loc; if(!Kmp(temp, loc))
{
return word;
}
int size = loc.size();
for(int i = ; i < size; ++i)
{
for(int j = loc[i].first; j <= loc[i].second; ++j)
{
temp[j] = "*";
}
}
string ret;
for(auto & elem : temp)
{
ret += elem;
}
return ret;
}
测试如下：
我不要好好 玩耍好好进行编程学习然后建一个编程编程编程学 习网站给编程纩编程软件者使用进行编程训练与编程学习
我不要****好好进行****然后建一个编程编程******给编程纩****者使用进行****与****
方案二，在匹配的时候读到空格就跳过：
bool Dictionary::Kmp(vector<string> & word, vector<Loc> & loc)
{
pDictElem root = _dictionary;
list<pDictElem> stackDict; int start = ;
int size = word.size();
int i = ;
while(i < size)
{
if(word[i] == " ")
{
++i;
if(!stackDict.size())
{
++start;
}
continue;
}
WordIt it_word;
it_word = root->_words.find(word[i]);
if(it_word == root->_words.end())
{
if(stackDict.size())
{
int num = root->_next;
for(int j = ; j < num - ; ++j)
{
stackDict.pop_back();
}
root = stackDict.back();
stackDict.pop_back();
start += num;
}else{
++i;
start = i;
}
continue;
}else{
stackDict.push_back(root);
root = it_word->second;
if(root->_isend)
{
Loc loctemp;
loctemp.first = start;
loctemp.second = i;
loc.push_back(loctemp);
start = i + ;
}
}
++i;
}
return loc.size();
}
测试：
我不要好好 玩耍好好进行编程学习然后建一个编程编程编程学 习网站给编程纩编程软件者使用进行编程训练与编程学习
我不要*****好好进行****然后建一个编程编程**********给编程纩****者使用进行****与****
一开始的时候的BUG：
1、“编程编程编程学习”无法提取出“编程学习”
2、敏感词起始位置乱七八糟
3、弹栈时机乱七八糟
4、敏感词中同时存在“编程学习”与“编程学习网站”时会发生段错误
5、4解决了之后，会出现只匹配“编程学习”，而“网站”二字没有替换
1~4 BUG调整一下就可以了，至于5嘛，莫明其妙就可以了，我也不知道怎么回事。
Dictionary.cc
#include "Dictionary.h"
#include <json/json.h>
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm> #define PLAN1 namespace ccx{ using std::endl;
using std::cout;
using std::pair;
using std::ofstream;
using std::ifstream; Dictionary::Dictionary()
: _dictionary(new DictElem)
, _conf()
{
_dictionary->_isend = false;
_dictionary->_next = ;
_pcur = _dictionary;
} void Dictionary::splitWord(const string & word, vector<string> & characters)
{
int num = word.size();
int i = ;
while(i < num)
{
int size = ;
if(word[i] & 0x80)
{
char temp = word[i];
temp <<= ;
do{
temp <<= ;
++size;
}while(temp & 0x80);
}
string subWord;
subWord = word.substr(i, size);
characters.push_back(subWord);
i += size;
}
} void Dictionary::getKmpNext(const vector<string> & characters, vector<int> & kmpnext)
{
int size = characters.size();
for(int i = ; i < size; ++i)
{
kmpnext.push_back();
} int i = -;
int j = ;
kmpnext[] = -;
while(j < size)
{
if(i == - || kmpnext[i] == kmpnext[j])
{
++i;
++j;
kmpnext[j] = i;
}else{
i = kmpnext[i];
}
}
for(i = ; i < size; ++i)
{
kmpnext[i] = i - kmpnext[i];
}
} void Dictionary::AddWord(const string & word)
{
vector<string> characters;
splitWord(word, characters);
vector<int> kmpnext;
getKmpNext(characters, kmpnext); vector<int>::iterator it_int;
it_int = kmpnext.begin();
vector<string>::iterator it_char;
it_char = characters.begin();
pDictElem root;
root = _dictionary;
for(; it_char != characters.end(); ++it_char, ++it_int)
{
WordIt it_word;
it_word = root->_words.find(*it_char); if(it_word == root->_words.end())
{
pair<string, pDictElem> temp;
temp.first = *it_char;
pDictElem dictemp(new DictElem);
dictemp->_word = *it_char;
dictemp->_next = *it_int;
dictemp->_isend = false;
temp.second = dictemp;
root->_words.insert(temp);
root = dictemp;
}else{
root = it_word->second;
}
}
if(!root->_isend)
{
root->_isend = true;
}
} void Dictionary::push(const string & word)
{
AddWord(word);
} void Dictionary::push(vector<string> & words)
{
int size = words.size();
for(int i = ; i < size; ++i)
{
push(words[i]);
}
} bool Dictionary::search(const string & word)
{
pDictElem root = _dictionary;
vector<string> temp;
splitWord(word, temp); int ret = search(temp, root);
int size = temp.size();
if(ret != size)
{
return false;
}
return true;
} int Dictionary::search(vector<string> & characters, pDictElem & root)
{
vector<string>::iterator it_char;
it_char = characters.begin();
root = _dictionary;
int i = ;
for(; it_char != characters.end(); ++it_char, ++i)
{
WordIt it_word;
it_word = root->_words.find(*it_char); if(it_word == root->_words.end())
{
break;
}else{
root = it_word->second;
}
}
return i;
} bool Dictionary::associate(const string & word, vector<string> & data)
{
pDictElem root = _dictionary;
vector<string> temp;
splitWord(word, temp); int ret = search(temp, root);
int size = temp.size();
if(ret != size)
{
return false;
} list<WordIt> stackWord;
list<pDictElem> stackDict;
next(root, stackWord, stackDict);
while(root)
{
string temp = getCurWord(stackWord);
data.push_back(temp);
next(root, stackWord, stackDict);
} if(!data.size())
{
return false;
}
return true;
} #ifdef PLAN1
//敏感词中带空格的第一种方案
bool deleterule(string & word)
{
return word == " ";
}
#endif string Dictionary::Kmp(const string & word)
{
vector<string> temp;
splitWord(word, temp); #ifdef PLAN1
temp.erase(std::remove_if(temp.begin(), temp.end(), deleterule));
#endif vector<Loc> loc; if(!Kmp(temp, loc))
{
return word;
}
int size = loc.size();
for(int i = ; i < size; ++i)
{
for(int j = loc[i].first; j <= loc[i].second; ++j)
{
temp[j] = "*";
}
}
string ret;
for(auto & elem : temp)
{
ret += elem;
}
return ret;
} bool Dictionary::Kmp(vector<string> & word, vector<Loc> & loc)
{
pDictElem root = _dictionary;
list<pDictElem> stackDict; int start = ;
int size = word.size();
int i = ;
while(i < size)
{
#ifdef PLAN2
//敏感词中带空格的第二种方案
if(word[i] == " ")
{
++i;
if(!stackDict.size())
{
++start;
}
continue;
}
#endif
WordIt it_word;
it_word = root->_words.find(word[i]);
if(it_word == root->_words.end())
{
if(stackDict.size())
{
int num = root->_next;
for(int j = ; j < num - ; ++j)
{
stackDict.pop_back();
}
root = stackDict.back();
stackDict.pop_back();
start += num;
}else{
++i;
start = i;
}
continue;
}else{
stackDict.push_back(root);
root = it_word->second;
if(root->_isend)
{
Loc loctemp;
loctemp.first = start;
loctemp.second = i;
loc.push_back(loctemp);
start = i + ;
}
}
++i;
}
return loc.size();
} //遍历用 void Dictionary::resetPoint(pDictElem pcur)
{
_pcur = pcur;
if(_stackDict.size())
{
_stackDict.clear();
}
if(_stackWord.size())
{
_stackWord.clear();
}
next();
} void Dictionary::resetIt()
{
resetPoint(_dictionary);
} void Dictionary::next()
{
next(_pcur, _stackWord, _stackDict);
} void Dictionary::next(pDictElem & pcur, list<WordIt> & stackWord, list<pDictElem> & stackDict)
{
while(pcur)
{
nextWord(pcur, stackWord, stackDict);
if(!pcur || pcur->_isend)
{
break;
}
}
} void Dictionary::nextWord(pDictElem & pcur, list<WordIt> & stackWord, list<pDictElem> & stackDict)
{
if(pcur)
{
if(pcur->_words.size())
{
stackDict.push_back(pcur);
stackWord.push_back(pcur->_words.begin());
pcur = stackWord.back()->second;
}else{
++(stackWord.back());
}
while(stackWord.back() == stackDict.back()->_words.end())
{
stackDict.pop_back();
stackWord.pop_back();
if(!stackDict.size())
{
pcur = NULL;
}
++(stackWord.back());
}
if(pcur)
{
pcur = stackWord.back()->second;
}
}
} string Dictionary::getCurChar()
{
return _pcur->_word;
} string Dictionary::getCurWord()
{
return getCurWord(_stackWord);
} string Dictionary::getCurWord(list<WordIt> & stackWord)
{
string temp;
list<WordIt>::iterator it_word;
it_word = stackWord.begin(); for(; it_word != stackWord.end(); ++it_word)
{
temp += (*it_word)->first;
}
return temp;
} bool Dictionary::isEnd()
{
return _pcur == NULL;
} void Dictionary::leading_in()//导入，失败没必要退出程序
{
ifstream ifs;
const char * path = _conf.getDictionaryPath().c_str();
ifs.open(path);
if(!ifs.good())
{
cout << "open Dictionary.json error(leading_in)" << endl;
}else{
Json::Value root;
Json::Reader reader; if(!reader.parse(ifs, root, false))
{
cout << "json read Dictionary.json error" << endl;
}else{
int size = root.size();
for(int i = ; i < size; ++i)
{
string word = root[i]["Word"].asString();
AddWord(word);
}
}
}
} void Dictionary::leading_out()
{
Json::Value root;
Json::FastWriter writer; resetIt(); while(!isEnd())
{
Json::Value elem;
elem["Word"] = getCurWord();
root.append(elem);
next();
} string words;
words = writer.write(root); ofstream ofs;
const char * path = _conf.getDictionaryPath().c_str();
ofs.open(path);
if(!ofs.good())
{
cout << "open Dictionary.json error(leading_out)" << endl;
ofs.open("Dictionary.tmp");
if(!ofs.good())
{
exit(EXIT_FAILURE);
}
} ofs << words;
ofs.close();
} }
结论：我的词典真的成了胖接口了！！！
萌新笔记——用KMP算法与Trie字典树实现屏蔽敏感词（UTF-8编码）的更多相关文章
-
用KMP算法与Trie字典树实现屏蔽敏感词（UTF-8编码）
前几天写好了字典,又刚好重温了KMP算法,恰逢遇到朋友吐槽最近被和谐的词越来越多了,于是突发奇想,想要自己实现一下敏感词屏蔽. 基本敏感词的屏蔽说起来很简单,只要把字符串中的敏感词替换成“***”就可 ...
-
萌新笔记——Cardinality Estimation算法学习（二）（Linear Counting算法、最大似然估计(MLE)）
在上篇,我了解了基数的基本概念,现在进入Linear Counting算法的学习. 理解颇浅,还请大神指点! http://blog.codinglabs.org/articles/algorithm ...
-
萌新笔记——Cardinality Estimation算法学习（一）（了解基数计算的基本概念及回顾求字符串中不重复元素的个数的问题）
最近在菜鸟教程上自学redis.看到Redis HyperLogLog的时候,对"基数"以及其它一些没接触过(或者是忘了)的东西产生了好奇. 于是就去搜了"HyperLo ...
-
萌新笔记——C++里创建 Trie字典树（中文词典）（一）（插入、遍历）
萌新做词典第一篇,做得不好,还请指正,谢谢大佬! 写了一个词典,用到了Trie字典树. 写这个词典的目的,一个是为了压缩一些数据,另一个是为了尝试搜索提示,就像在谷歌搜索的时候,打出某个关键字,会提示 ...
-
算法笔记之KMP算法
本文是<算法笔记>KMP算法章节的阅读笔记,文中主要内容来源于<算法笔记>.本文主要介绍了next数组.KMP算法及其应用以及对KMP算法的优化. KMP算法主要用于解决字符串 ...
-
萌新笔记——C++里将string类字符串（utf-8编码）分解成单个字（可中英混输）
最近在建词典,使用Trie字典树,需要把字符串分解成单个字.由于传入的字符串中可能包含中文或者英文,它们的字节数并不相同.一开始天真地认为中文就是两个字节,于是很happy地直接判断当前位置的字符的A ...
-
算法导论：Trie字典树
1. 概述 Trie树,又称字典树,单词查找树或者前缀树,是一种用于快速检索的多叉树结构,如英文字母的字典树是一个26叉树,数字的字典树是一个10叉树. Trie一词来自retrieve,发音为/tr ...
-
[原创] Trie树 php 实现敏感词过滤
目录 背景 简介 存储结构 PHP 其他语言 字符串分割 示例代码 php 优化 缓存字典树 常驻服务 参考文章 背景 项目中需要过滤用户发送的聊天文本, 由于敏感词有将近2W条, 如果用 str_r ...
-
C++里创建 Trie字典树（中文词典）（一）（插入、遍历）
萌新做词典第一篇,做得不好,还请指正,谢谢大佬! 写了一个词典,用到了Trie字典树. 写这个词典的目的,一个是为了压缩一些数据,另一个是为了尝试搜索提示,就像在谷歌搜索的时候,打出某个关键字,会提示 ...
随机推荐
-
day8-------socket网络编程
简单的socket 一个server同时只能处理一个链接 代码如下: server端代码 #author = ruixin li import socket server = socket.so ...
-
Bootstrap <;基础五>;表格
Bootstrap 提供了一个清晰的创建表格的布局.下表列出了 Bootstrap 支持的一些表格元素: 标签 描述 <table> 为表格添加基础样式. <thead> 表格 ...
-
加强型无穷集合：InfiniteList<;T>;，可指定遍历方向和偏移量，只要集合有元素并且偏移量不为 0，将永远遍历下去。
主类: public class InfiniteList<T> : IEnumerable<T> { public List<T> SourceList { ge ...
-
JBOSS集群技术升级版解决方案分享(图示篇)
JBOSS集群技术升级版解决方案分享(实现篇) 前段时间,由于阿堂一直较忙,没有写点什么了,有空时一直在关注"web架构和性能,高并发,Cache层"技术领域的 ...
-
AutoCAD.NET二次开发：创建自定义菜单的两种方法比较
目前我已经掌握的创建CAD菜单方法有两种: COM方式: http://www.cnblogs.com/bomb12138/p/3607929.html CUI方式: http://www.cnblo ...
-
lambda -- Java 8 find first element by predicate
Java 8 find first element by predicate up vote6down votefavorite I've just started playing with ...
-
python中使用递归实现反转链表
反转链表一般有两种实现方式,一种是循环,另外一种是递归,前几天做了一个作业,用到这东西了. 这里就做个记录,方便以后温习. 递归的方法: class Node: def __init__(self,i ...
-
Nginx反向代理2--配置文件配置
2.1Nginx的反向代理 什么是正向代理? 1.2 使用nginx实现反向代理 Nginx只做请求的转发,后台有多个http服务器提供服务,nginx的功能就是把请求转发给后面的服务器,决定把请 ...
-
8.1 服务器开发 API 函数封装，select 优化服务器和客户端
#include <unistd.h> #include <sys/types.h> #include <sys/socket.h> #include <ne ...
-
java与数据库交互常用到的一些方法
下面我整理了一下java中常用的几个与数据库交互的常用方法,仅供参考: 1.执行SQL(dao层的实现类中) (1)SQL查询: //import org.hibernate.Query;//impo ...