当前位置：首页 > news >正文

游戏中的敏感词算法初探

news 2025/7/20 14:21:32

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

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 of0 ->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 of0 -> query_trie(T, Next, -1, Trie);_ -> query_trie(T, Next, 0, Trie)end.