中国做爰网站,学校官网网页设计,五金技术支持东莞网站建设,域名查询网入口在游戏中起名和聊天需要服务器判断是否含有敏感词#xff0c;从而拒绝或屏蔽敏感词显示#xff0c;这里枚举一些常用的算法和实际效果。 1.字符串匹配算法 常用的有KMP#xff0c;核心就是预处理出next数组#xff0c;也就是失配信息#xff0c;时间复杂度在O(mn) 。还有个…在游戏中起名和聊天需要服务器判断是否含有敏感词从而拒绝或屏蔽敏感词显示这里枚举一些常用的算法和实际效果。 1.字符串匹配算法 常用的有KMP核心就是预处理出next数组也就是失配信息时间复杂度在O(mn) 。还有个比较有趣的算法我之前也用过叫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.2.AC自动机 著名的多模匹配算法Trie和KMP的结合实现比较复杂游戏中也不适用。 3.Map 一般语言都带有Map结构底层一般是散列表把屏蔽字库预处理成map结构然后O(m*m)的去查询因为游戏中屏蔽字都比较短且需要检测的语句都不会很长所以效率很可观。之前用lua做过性能测试结果还是这个方法效率最高很出乎我的意料。 4.总结 个人感觉需要做敏感词检测的话最好是有会NLP的同学支持因为屏蔽字库其实也很死板。游戏中各种广告敏感词都在日新月异只有AI不断学习才能打败它们。要求不高的话可以尝试Trie树和Map实现不同开发语言和字库效果可能都不同选最合适的即可。
