阅读量:6
在游戏中起名和聊天需要服务器判断是否含有敏感词，从而拒绝或屏蔽敏感词显示，这里枚举一些常用的算法和实际效果。
1.字符串匹配算法
常用的有KMP，核心就是预处理出next数组，也就是失配信息，时间复杂度在O(m+n) 。还有个比较有趣的算法，我之前也用过，叫Sunday算法，实现很简单，但是不稳定，时间复杂度最差也是O(m*n)。显然这些都是单字符串匹配的，一般游戏中都是有上万行的屏蔽字库。
2.Trie树
字典树，很实用的算法，把屏蔽字预处理成树状结构，就跟翻字典一样，相同前缀的同根，所以也叫前缀树，预处理完查询就是O(n)的效率。但是对于游戏来说不太适用，因为屏蔽词前缀相同的太少。这样导致构建出来的Trie树内存占用比较严重，查询效率也比较差。最近一直在用erlang，所以用map结构写了一版出来，具体实现可以参考
trie_test() -> trie_test(33000, #{tot => 0}). trie_test(0, Trie) -> Trie; trie_test(N, Trie) -> Rand = integer_to_list(random_int(1, 999999)), trie_test(N - 1, build_trie(Rand, 0, Trie)). build_trie(Word) -> build_trie(Word, 0, #{tot => 0}). build_trie([], Index, Trie) -> CurNode = maps:get(Index, Trie, #{next => #{}, v => 0}), Trie#{Index => CurNode#{v => 0}}; build_trie([H | T], Index, Trie) -> Tot = maps:get(tot, Trie), CurNode = maps:get(Index, Trie, #{next => #{}, v => 0}), NextNode = maps:get(next, CurNode, #{}), Next = maps:get(H, NextNode, 0), {NewNum, NewTrie} = case Next of 0 -> TempNode = maps:get(Tot + 1, Trie, #{next => #{}, v => 0}), Trie1 = Trie#{Tot + 1 => TempNode#{v => -1}}, CurNodeNext = maps:get(next, CurNode, #{}), {Tot + 1, Trie1#{Index => CurNode#{next => CurNodeNext#{H => Tot + 1}}}}; Num -> {Num, Trie} end, build_trie(T, NewNum, NewTrie#{tot => Tot + 1}). query_trie(Word, Trie) -> query_trie(Word, 0, 0, Trie). query_trie(_, _, -1, _) -> -1; query_trie([], Index, _Exist, Trie) -> #{v := V} = maps:get(Index, Trie, #{next => #{}, v => 0}), V; query_trie([H | T], Index, _Exist, Trie) -> CurNode = maps:get(Index, Trie, #{next => #{}, v => 0}), NextNode = maps:get(next, CurNode, #{}), Next = maps:get(H, NextNode, 0), case Next of 0 -> query_trie(T, Next, -1, Trie); _ -> query_trie(T, Next, 0, Trie) end. 2.AC自动机
著名的多模匹配算法，Trie和KMP的结合，实现比较复杂，游戏中也不适用。
3.Map
一般语言都带有Map结构，底层一般是散列表，把屏蔽字库预处理成map结构，然后O(m*m)的去查询，因为游戏中屏蔽字都比较短且需要检测的语句都不会很长，所以效率很可观。之前用lua做过性能测试，结果还是这个方法效率最高，很出乎我的意料。
4.总结
个人感觉需要做敏感词检测的话，最好是有会NLP的同学支持，因为屏蔽字库其实也很死板。游戏中各种广告敏感词都在日新月异，只有AI不断学习才能打败它们。要求不高的话，可以尝试Trie树和Map实现，不同开发语言和字库效果可能都不同，选最合适的即可。
