非法关键词过滤系统该怎么做？有没有更好的思路？

[dbfox]

非法关键词日积月累会越来越多
不可能写个 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(第四步中得到的词)

[ShadowStar]

bloom-filter

[scnace]

bloom filter +1

[holyghost]

DAT

[nobodyhere]

内容长度为 n ，关键词个数为 m ，这个单次过滤的复杂度为 O(n*m)，做离线过滤还可以勉强凑合，放线上应对 QPS 就惨了
标准做法是做出 O(n*1)，用 trie 树

[UnisandK]

对内容中每个字符取 md5 会爽到飞起吧

[SourceMan]

https://github.com/imaben/php-akm 只有个 PHP 版的，可以参考实现

[shakoon]

每个字符都去算 md5 ……我觉得这不会比每个关键字都去 like 一遍节约资源

[NeinChn]

有 TRIE 还是用 TRIE 吧，比 BloomFilter 靠谱

[mayokaze]

ac 自动机

[dbfox]

@ShadowStar
@NeinChn
@scnace
@holyghost
这么多人推荐 BloomFilter ，有空去试试 DAT 是什么？

[holyghost]

@dbfox double array trie