当前位置： 文江博客话题详情

C++-如何设计高效的聊天过滤词算法？

发布于 2017-01-19 08:04:02 字数 63 浏览 1320 评论 11

众所周知，基本上每个游戏或者每个应用系统里面都有过滤词算法，怎么样的过滤词算法最高效，请提供C++/PHP版本。

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（11）

清晨说ぺ晚安 2017-10-25 23:35:24

以前见过一个方案：把所有要过滤的字保存起来（set<string>）,然后对要过滤的字，循环正则匹配。这个方案的核心就在正则匹配上面。

回复
浮生未歇 2017-10-04 08:30:59

用bloomfilter wikipedia.org
bloomfilter 中文介绍文章

Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。

Bloom-Filter有可能会误判，也就是说会将一个并不存在于集合中的元素误认为已存在于集合中。但是另一方面，它绝对不可能会将一个已经存在于集合中的元素误认为是不存在于集合中。正所谓“宁可错杀一千，也不放过一个”，正好用于敏感词过滤。

C++ Lib
Perl Lib

回复
瑾兮 2017-09-27 22:49:00

聊天过滤词算法的解决思路
提高过滤的算法个人认为主要从两个方面考虑：（1）尽量减少内存、IO的次数。（2）增加串内查找的速度。
基于这两点我想采用连续的内存片，可以减少内存地址跳跃的次数，采用静态的内存这就解决了（1）的问题，第二点是增加串内查找的速度，这个比较公认的事KMP算法。

class WordFilter
{
public:
WordFilter();
~WordFilter();

void Init();
void FilterWord(string& word);
int Index_KMP(const char* S, const char* T, int pos);

private:
std::set<string> m_storage;
const char** m_words;
uint32 m_count;
};

WordFilter::WordFilter()
{
m_words = NULL;
m_count = 0;
}

WordFilter::~WordFilter()
{
if(m_words) {
free(m_words);
}
}

void WordFilter::Init()
{
// 把所有屏蔽词都放到m_storage里
m_count = m_storage.size();
if(m_count) {
m_words = (const char**)malloc(sizeof(char*)*m_count);
std::set<string>::iterator ptr;
int i = 0;
for(ptr = m_storage.begin(); ptr != m_storage.end(); ++ptr,i++) {
m_words[i] = ptr->c_str();
}
}
}

static inline void _filterWord(char* word, const char* lowerWord, const char* oldstr)
{
int len = strlen(oldstr);
const char* tmp;
memset(word, '*', len);
word += len;
lowerWord += len;

while((tmp = Index_KMP(lowerWord, oldstr)) != NULL) {
word += (tmp-lowerWord);
memset(word, '*', len);
word += len;
lowerWord = tmp + len;
}
}

void WordFilter::FilterWord(string& word)
{
string tmp(word);
str_tolower(tmp);
const char** p = (const char**)m_words;
const char* dest;
for(uint32 i=0; i<m_count; i++, p++) {
dest = Index_KMP(tmp.c_str(), *p, 0);
if(dest) {
_filterWord((char*)(word.c_str() + (dest-tmp.c_str())), dest, *p);
}
}
}

int WordFilter::Index_KMP(const char* S, const char* T, int pos){
i=pos; j=1;
while(i <= S[0] && j<= T[0]){
if(j == 0 || S[i] == T[j]) { ++i; ++j; }
else j = next[j];
}

if(j>T[0])
return i-T[0];
else
return 0;
}

回复
灵芸 2017-09-08 19:21:32

这里主要涉及到查找, 及对于用户的字符串, 我们要去查找是不是脏词,
1. 把所有的脏词建立成一颗 trie 树(动态查找表, 可以随时插入删除)
2. 然后将这个 trie 改造成 AC自动机进行字符串的匹配, 速度很快, 也省空间哦
3. 使用 hash表 进行查找, 速度快, 但是耗空间

回复
浮生未歇 2017-08-22 17:22:13

DAT啊，Trie树无疑是最高效的了，DAT很省空间
我写的java版本
http://www.co-ding.com/?p=53

论文地址
http://sc.snu.ac.kr/~xuan/spe777ja.pdf

回复
灵芸 2017-07-23 11:57:57

我的想法是基于新颖的，把每个敏感词建立hash表，key是敏感词的打头字。把相同打头字的敏感词放入一个桶中，每个词以链表的形式存在。当然可以按词的使用频道把敏感词链入靠前的位置。
匹配时:
1)把划分好的每个句子，取开头的第一个字做hashcode看是否能映射到hash表中。若能映射再与桶中的词做比较(若桶中的词很多，也可以做成二级、三级hash匹配敏感词的前两个、三个字)。匹配上敏感词后，把待匹配的位置向后移动敏感词长度。
2)若能匹配hashcode，不能匹配桶中的敏感词，则直接认为是要XX掉的，这个看需求了。
3)若不能匹配hashcode，则把待匹配的位置向后移动一个字符长度，这个字没任何问题。

这样是O(1)的？个人愚见。

回复
甜柠檬 2017-06-29 07:07:51

貌似，还有一种方法字典和匹配方式：）
Double-Array Trie 小日本鬼子 有开源的代码
接口有包装，可以方便调用
网上评估说 比较费内存
没有用过 呵呵

回复
偏爱自由 2017-06-15 14:58:41

聊天实际上负载不是很高，因为一个游戏服务器也就几千人在线，太高的话世界频道根本没人看。做关键词匹配优化，不如上贝叶斯自学习，我们实现过分布式的贝叶斯自学习的过滤，对于卖金币的广告过滤效果很高。值得注意的是非技术的几个设计点：

1.客户端和服务器端都要进行发言频率过滤
2.只在客户端实现过滤（这个是能通过审核的)
3.被屏蔽的发言应该本IP仍然可见(新浪评论就是这样的)

附：贝叶斯自学习参考
- 贝叶斯推断及其互联网应用（一）
- 贝叶斯推断及其互联网应用（二）

回复
甜柠檬 2017-06-13 19:07:23

我现在的思路是建立一个过滤词的词典，因为过滤词库在成千上万的时候，对每个过滤词进行比对是很耗时的。通过词典，以最快的速度，先找出那些过滤词是最有可能命中的敏感词，再去用这些可能命中的敏感词去要过滤的话里面查找。
这样的算法复杂度和需要过滤的词成正比，和敏感词库的大小无关。用来做游戏里面的聊天，和昵称过滤正好。

class FilterService{
public function is_safe( $sentence ){
$words_array = split_sentence( $sentence );
foreach( $words_array as $word ){
//从过滤词字典中找出以$word打头的过滤词
$bad_words = HGET filter_words_dict $word;
foreach( $bad_words as $bad_word ){
if( stristr( $word, $bad_words ) )
return false;
}
}

}
}

class FilterDao{
//将所有的过滤词，加载到redis中，key为过滤词的第一个词，value是一个集合，是以相同的词打头的过滤词集。
private init_filter_word_dict(){
.......
HSET filter_words_dict "胡" "胡锦涛";
HSET filter_words_dict "胡" "胡耀邦";
HSET filter_words_dict "温" "温家宝";
.......
}

//将传进来的话分割成一个个字，这里要求中文用utf-8进行编码
public function split_sentence( $sentence ){
$words_array = new array();
//分词
..................
return $words_array;
}

//获取传入的语句的第一个词，第一个词可能是汉字，也有可能是一个英文字母
private function get_first_word($sentence){
.............
return substr( $sentence, $start, $length );
}

}

回复
甜柠檬 2017-03-08 19:04:57

第一次回答问题， 哈， 上面的回答我没仔细看， 说一下我们的做法， 也许跟上面有雷同的

我们的解决方法是用构造一个tire树。 每个节点都存储0- 256个字符。

用脏词字典来构造这个树。

具体实现代码如下：

namespace KGame
{
class WordFilter
{
public:
WordFilter() {}

~WordFilter()
{
Clean(&m_Filter);
}

void AddWord(const char* word)
{
UInt32 len = (UInt32)strlen(word);
Filter* filter = &m_Filter;

for (UInt32 i = 0; i < len; i++)
{
unsigned char c = word[i];
if (i == len - 1)
{
filter->m_NodeArray[c].m_Flag |= FilterNode::NODE_IS_END;
break;
}
else
{
filter->m_NodeArray[c].m_Flag |= FilterNode::NODE_HAS_NEXT;
}

if (filter->m_NodeArray[c].m_NextFilter == NULL)
{
Filter* tmpFilter = XNEW (Filter)();
filter->m_NodeArray[c].m_NextFilter = tmpFilter;
}

filter = (Filter *)filter->m_NodeArray[c].m_NextFilter;
}
}

void AddWords(const std::set<std::string>& wordList)
{
for (std::set<std::string>::const_iterator it = wordList.begin();
it != wordList.end(); it++)
{
AddWord(it->c_str());
}
}

void AddWords(const std::vector<std::string>& wordList)
{
for (std::vector<std::string>::const_iterator it = wordList.begin();
it != wordList.end(); it++)
{
AddWord(it->c_str());
}
}

void AddWords(const KGame::Set<std::string>& worldList)
{
for (KGame::Set<std::string>::Iter* iter = worldList.Begin();
iter != worldList.End(); iter = worldList.Next(iter))
{
AddWord(iter->m_Value.c_str());
}
}

Int32 Check(const char* str)
{
Filter* filter = NULL;
for (Int32 i = 0; i < (int)strlen(str) - 1; i++)
{
filter = &m_Filter;
for (UInt32 j = i; j < strlen(str); j++)
{
unsigned char c = str[j];
if ((c >= 'A' && c <= 'Z'))
{
c += 32;
}

if (filter->m_NodeArray[c].m_Flag == FilterNode::NODE_IS_NULL)
{
break;
}
else if (filter->m_NodeArray[c].m_Flag & FilterNode::NODE_IS_END)
{
return i;
}
else // NODE_HAS_NEXT
{
filter = (Filter*)filter->m_NodeArray[c].m_NextFilter;
}
}
}
return -1;
}

void CheckAndModify(char* str, const char replace = '*')
{
Filter* filter = NULL;
for (Int32 i = 0; i < (int)strlen(str) - 1; i++)
{
filter = &m_Filter;
for (UInt32 j = i; j < strlen(str); j++)
{
unsigned char c = str[j];
if ((c >= 'A' && c <= 'Z'))
{
c += 32;
}

if (filter->m_NodeArray[c].m_Flag == FilterNode::NODE_IS_NULL)
{
break;
}
else if (filter->m_NodeArray[c].m_Flag & FilterNode::NODE_IS_END)
{
for (UInt32 k = i; k <= j; k++)
{
str[k] = replace;
}

if (filter->m_NodeArray[c].m_Flag & FilterNode::NODE_HAS_NEXT)
{
filter = (Filter*)filter->m_NodeArray[c].m_NextFilter;
}
else
{
continue;
}
}
else // NODE_HAS_NEXT
{
filter = (Filter*)filter->m_NodeArray[c].m_NextFilter;
}
}
}
}

void CheckAndModify(std::string& str, const char replace = '*')
{
Filter* filter = NULL;
for (Int32 i = 0; i < (int)str.size() - 1; i++)
{
filter = &m_Filter;
for (UInt32 j = i; j < str.size(); j++)
{
unsigned char c = str[j];
if ((c >= 'A' && c <= 'Z'))
{
c += 32;
}
if (filter->m_NodeArray[c].m_Flag == FilterNode::NODE_IS_NULL)
{
break;
}
else if (filter->m_NodeArray[c].m_Flag & FilterNode::NODE_IS_END)
{
for (UInt32 k = i; k <= j; k++)
{
str[k] = replace;
}

if (filter->m_NodeArray[c].m_Flag & FilterNode::NODE_HAS_NEXT)
{
filter = (Filter*)filter->m_NodeArray[c].m_NextFilter;
}
else
{
continue;
}
}
else // NODE_HAS_NEXT
{
filter = (Filter*)filter->m_NodeArray[c].m_NextFilter;
}
}
}
}

private:

struct FilterNode
{
char m_Flag;
void* m_NextFilter;

enum Flag
{
NODE_IS_NULL = 0x00,
NODE_HAS_NEXT = 0x01,
NODE_IS_END = 0x10,
};
FilterNode() : m_Flag(NODE_IS_NULL), m_NextFilter(NULL) {}
};

struct Filter
{
FilterNode m_NodeArray[256];
} m_Filter;

void Clean(Filter* filter)
{
for (UInt32 i = 0; i < 256; i++)
{
if (filter->m_NodeArray[i].m_NextFilter)
{
Clean((Filter *)filter->m_NodeArray[i].m_NextFilter);
XDELETE((Filter*)filter->m_NodeArray[i].m_NextFilter);
}
}
}
};
} // namespace KGame

回复
晚风撩人 2017-03-04 01:05:06

 class WordFilter
{
public:
WordFilter();
~WordFilter();

void Init();
void FilterWord(string& word);

private:
std::set<string> m_storage;
const char** m_words;
uint32 m_count;
};

WordFilter::WordFilter()
{
m_words = NULL;
m_count = 0;
}

WordFilter::~WordFilter()
{
if(m_words) {
free(m_words);
}
}

void WordFilter::Init()
{
// 把所有屏蔽词都放到m_storage里
m_count = m_storage.size();
if(m_count) {
m_words = (const char**)malloc(sizeof(char*)*m_count);
std::set<string>::iterator ptr;
int i = 0;
for(ptr = m_storage.begin(); ptr != m_storage.end(); ++ptr,i++) {
m_words[i] = ptr->c_str();
}
}
}

static inline void _filterWord(char* word, const char* lowerWord, const char* oldstr)
{
int len = strlen(oldstr);
const char* tmp;
memset(word, '*', len);
word += len;
lowerWord += len;

while((tmp = strstr(lowerWord, oldstr)) != NULL) {
word += (tmp-lowerWord);
memset(word, '*', len);
word += len;
lowerWord = tmp + len;
}
}

void WordFilter::FilterWord(string& word)
{
string tmp(word);
str_tolower(tmp);
const char** p = (const char**)m_words;
const char* dest;
for(uint32 i=0; i<m_count; i++, p++) {
dest = strstr(tmp.c_str(), *p);
if(dest) {
_filterWord((char*)(word.c_str() + (dest-tmp.c_str())), dest, *p);
}
}
}

实现了屏蔽词不区分大小写， 并且没有再申请额外内存，所以效率自认还是蛮高的。

回复
~没有更多了~

关于作者

想挽留

暂无简介

0 文章
0 评论
20372 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

苍风燃霜

文章 0 评论 0

我的黑色迷你裙

文章 0 评论 0

悸初

文章 0 评论 0

撧情箌佬

文章 0 评论 0

森罗

文章 0 评论 0

lyn1245

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文