这是一个创建于 3004 天前的主题，其中的信息可能已经有所发展或是发生改变。
非法关键词日积月累会越来越多
不可能写个 for 循环，遍历所有关键词，然后再查找“内容”中有没有这个关键词吧？效率低
当然我知道一些东西 Spark 可以分布式计算 还不太会用，只是了解了功能可能会用上
但是有没有更好的算法呢？
我目前想到的一些主要思路：
[需求]
需要过滤的 “内容” 和 “非法关键字”
第一步
非法关键字把首字进行 md5 取第一位 如：
SB 这个词 每个字符 md5 只拿 md5 中的 第一位 如：
SB
13
第二步
把内容中的每个字符 md5 只拿 md5 中的 第一位 如：
每个字符进行 md5 并且取 md5 的第一位
你是 SB 就注定无泪无悔
a 1 13 4 5 3 3 b x c
然后每个字符都有一个 0-9a-f 对应
把得到的字符 组合为下列方式，存储为一个数组：
a1
11
13
34
45
53
33
3b
bx
xc
第三步
把非法关键字分散到 256 个字典中
00
01
02
..
ff
第四步
for 循环 第二步得到的数组，去查询非法关键字的 256 个字典
得到 可能的所有非法关键字
第五步
详细对比 content.IndexOf(第四步中得到的词)
不可能写个 for 循环，遍历所有关键词，然后再查找“内容”中有没有这个关键词吧？效率低
当然我知道一些东西 Spark 可以分布式计算 还不太会用，只是了解了功能可能会用上
但是有没有更好的算法呢？
我目前想到的一些主要思路：
[需求]
需要过滤的 “内容” 和 “非法关键字”
第一步
非法关键字把首字进行 md5 取第一位 如：
SB 这个词 每个字符 md5 只拿 md5 中的 第一位 如：
SB
13
第二步
把内容中的每个字符 md5 只拿 md5 中的 第一位 如：
每个字符进行 md5 并且取 md5 的第一位
你是 SB 就注定无泪无悔
a 1 13 4 5 3 3 b x c
然后每个字符都有一个 0-9a-f 对应
把得到的字符 组合为下列方式，存储为一个数组：
a1
11
13
34
45
53
33
3b
bx
xc
第三步
把非法关键字分散到 256 个字典中
00
01
02
..
ff
第四步
for 循环 第二步得到的数组，去查询非法关键字的 256 个字典
得到 可能的所有非法关键字
第五步
详细对比 content.IndexOf(第四步中得到的词)
 |
1
ShadowStar 2016-08-26 11:47:42 +08:00  1
bloom-filter
|
 |
2
scnace 2016-08-26 12:21:26 +08:00 via Android
bloom filter +1
|
 |
3
holyghost 2016-08-26 12:24:21 +08:00
DAT
|
 |
4
nobodyhere 2016-08-26 12:50:46 +08:00
内容长度为 n ，关键词个数为 m ，这个单次过滤的复杂度为 O(n*m)，做离线过滤还可以勉强凑合，放线上应对 QPS 就惨了
标准做法是做出 O(n*1)，用 trie 树 |
 |
5
UnisandK 2016-08-26 12:58:08 +08:00
对内容中每个字符取 md5 会爽到飞起吧
|
 |
6
SourceMan 2016-08-26 13:04:41 +08:00
https://github.com/imaben/php-akm 只有个 PHP 版的，可以参考实现
|
 |
7
shakoon 2016-08-26 13:19:35 +08:00
每个字符都去算 md5 ……我觉得这不会比每个关键字都去 like 一遍节约资源
|
 |
8
NeinChn 2016-08-26 13:22:04 +08:00
有 TRIE 还是用 TRIE 吧，比 BloomFilter 靠谱
|
 |
9
mayokaze 2016-08-26 13:38:30 +08:00
ac 自动机
|
 |
10
dbfox OP |
Select Language