游戏中的敏感词算法初探

在游戏中起名和聊天需要服务器判断是否含有敏感词，从而拒绝或屏蔽敏感词显示，这里枚举一些常用的算法和实际效果。

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实现，不同开发语言和字库效果可能都不同，选最合适的即可。