如何设计高效的聊天过滤词算法?

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

小白
小白
1776
编辑于2012-03-15
评论 (0)链接2011-09-09 

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

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

附:贝叶斯自学习参考
- 贝叶斯推断及其互联网应用(一)
- 贝叶斯推断及其互联网应用(二)

Geo5
Geo5
463
编辑于 2011-10-14
该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (3)链接 • 2011-10-14
  • 0 支持
    数学的东西出来果然不一样~ – 黄文彬 2011-10-14
  • 0 支持
    我觉得这个可以辅助在一起,因为单个请求的相应时间过长,会导致性能发生抖动。 – 黄新颖 2011-10-14
  • 0 支持
    很多知名邮箱都采用了贝叶斯推断,除了文中提到的词出现概率,还加上词序、标点符号的使用等等,进行一些优化,就能够分化成广告邮件判断系统、垃圾邮件判断系统。 – 卢虹呈 2013-05-29

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

  
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 );
}

}
小白
小白
1776
编辑于 2011-09-16
该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2011-09-16

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

我们的解决方法是用构造一个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
该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (2)链接 • 2012-04-12
  • 0 支持
    本来以为你的算法挺好的的,可是细看之后发现,在效率和内存方面都比较慢。1.效率方面,你是一个字符一个字符去比较的。2.在内存方面,每个屏蔽字符都对应265个字符位。 – zhangwu 2012-08-06
  • 0 支持
    不错,用UTF8编码在做Trie树的Key,这样每级保存一个数组就可以了。
    查询效率倍增,但是内存倍增,不过对于服务器,感觉是比较好的。
    还有,楼上注意,过滤的是敏感词。
    – Siryang 2012-12-26
  
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);
}
}
}

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

至尊宝
至尊宝
1149
编辑于 2011-09-13
该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (1)链接 • 2011-09-13
  • 0 支持
    这个答案不是最优的,因为关键词库很大的情况下,while((tmp = strstr(lowerWord, oldstr)) != NULL) .这个会执行很多次。算法的复杂度为O(n), n为过滤词条的数量。我想要找到一个O(1)的算法。 – 黄新颖 2011-09-13

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

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

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2011-10-14

bloomfilter wikipedia.org
bloomfilter 中文介绍文章

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

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

Geo5
Geo5
463
编辑于 2011-09-28
该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (6)链接 • 2011-09-28
  • 0 支持
    有没有php版本的呀!难道不懂c++全是浮云? – 李水祥 2011-09-28
  • 1 支持
    有PHP版,但首先要装一个 bitset,http://code.google.com/p/php-bloom-filter/ – 冯绍昌 2011-10-13
  • 1 支持
    是否是C++并不重要,语言背后的东西,如数据结构、算法、计算机体系结构等才是最重要的. – 黄文彬 2011-10-14
  • 0 支持
    只是C++的使用更容易接触这些东西。 – 黄文彬 2011-10-14
显示更多隐藏的评论

聊天过滤词算法的解决思路
提高过滤的算法个人认为主要从两个方面考虑:(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;
}
陈彦旭
编辑于 2011-09-15
该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (2)链接 • 2011-09-15
  • 1 支持
    你的Index_KMP算法不全, 并且语义与strstr不同,不能直接替换。
    另外,strstr是系统库函数,可能内部使用汇编优化,也不见得比KMP慢。
    – 李振春 2011-09-15
  • 0 支持
    李老师说得很对,微软现在的strstr是经过算法优化的,不一定比KMP慢。我做过一个全文检索系统,其中高亮显示查找字符串的时候,用的KMP的改进版(好像是moon平滑算法),速度反而慢了很多倍。 – 黄文彬 2011-10-14

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

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (1)链接 • 2011-10-24
  • 1 支持
    DAT是为了解决普通的Trie树耗内存,而产生的,貌似不是日本人写的,我看的论文是kr域名,应该是韩国的http://sc.snu.ac.kr/~xuan/spe777ja.pdf – 丁亚光 2012-09-14

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

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

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2012-09-14

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

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2012-11-04

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

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2012-08-06

不是您所需,查看更多相关问题与答案

德问是一个专业的编程问答社区,请 登录注册 后再提交答案