注册 登录
编程论坛 数据结构与算法

求屏蔽词判断算法!!!

clowder 发布于 2010-04-14 08:16, 1346 次点击
假设有一个很长的屏蔽词数组 string[] badwords={};
对网络任意输入的文本strText,希望将strText文本中包含屏蔽词数组中的词语的替换成"**";
请求高效算法!因为该屏蔽词数组实在庞大,如果做到最高效是关键,而此应用应该是到处都有,请行家高手指点!
public string ConvertText( string[] badwords, string text )
{
    //算法
}
5 回复
#2
mywaylgh2010-04-14 11:37
对这样的问题,个人只有map, hash_map以及unordered_map 的经验
更好的算法也同样期待
#3
clowder2010-04-14 11:49
回复 2楼 mywaylgh
说说你的思路,如何使用map等东西来处理这个问题?
#4
mywaylgh2010-04-14 13:15
估计不是你想要的结果

以 map为例,基本算法如下,从速度看,unorder_map最快,不过....很多编译器并不支持
1.按badword中词汇长度存为哈希表。
  如: map <string,int> badword_2;//存入两个字的词组
       map <string,ing> badword_3;//存入三个自的词组
       存入方式为如   badword_2["词组“] = 1;....

2.两个字,三个字。。。的扫描文本并判断是否是badword
  如,两个字扫描时,用:
  if(badword_2.find(c)==badword_2.end()) 表示非badword
  else 替换

3.输出文本

你可以试试,看看效率如何。
#5
cnfarer2010-04-14 21:00
建议看看:LUCENE(来自开源项目),它可能给你帮助!!!
#6
asdjc2010-04-16 07:12
我倒是有一个思路:
1.先对badwords={}进行霍夫曼编码(用树形结构显示,首字符编码,次字符编码...);
2.对string[]进行匹配划分为各个字符串(根据语义吧);
3.对string[]逐个字符串提取并与1.中的树形结构进行比对。比对成功改*****,失败比对下一个;
这是我的思路,参考哈。
1