敏感词过滤功能在很多地方都会用到，理论上在Web应用中，只要涉及用户输入的地方，都需要进行文本校验，如：XSS校验、SQL注入检验、敏感词过滤等。今天着重讲讲如何优雅高效地实现敏感词过滤。
敏感词过滤方案一
先讲讲笔者在上家公司是如何实现敏感词过滤的。当时毕竟还年轻，所以使用的是最简单的过滤方案。简单来说就是对于要进行检测的文本，遍历所有敏感词，逐个检测输入的文本中是否含有指定的敏感词。这种方式是最简单的敏感词过滤方案了，实现起来不难，示例代码如下：
@Test
public void test1(){
Set<String> sensitiveWords=new HashSet<>();
sensitiveWords.add("shit");
sensitiveWords.add("傻逼");
sensitiveWords.add("笨蛋");
String text="你是傻逼啊";
for(String sensitiveWord:sensitiveWords){
if(text.contains(sensitiveWord)){
System.out.println("输入的文本存在敏感词。——"+sensitiveWord);
break;
}
}
}
代码十分简单，也确实能够满足要求。但是这个方案有一个很大的问题是，随着敏感词数量的增多，敏感词检测的时间会呈线性增长。由于之前的项目的敏感词数量只有几十个，所以使用这种方案不会存在太大的性能问题。但是如果项目中有成千上万个敏感词，使用这种方案就会很耗CPU了。
敏感词过滤方案二
在网上查了下敏感词过滤方案，找到了一种名为DFA的算法，即Deterministic Finite Automaton算法，翻译成中文就是确定有穷自动机算法。它的基本思想是基于状态转移来检索敏感词，只需要扫描一次待检测文本，就能对所有敏感词进行检测，所以效率比方案一高不少。
假设我们有以下5个敏感词需要检测：傻逼、傻子、傻大个、坏蛋、坏人。那么我们可以先把敏感词中有相同前缀的词组合成一个树形结构，不同前缀的词分属不同树形分支，以上述5个敏感词为例，可以初始化成如下2棵树：
把敏感词组成成树形结构有什么好处呢？最大的好处就是可以减少检索次数，我们只需要遍历一次待检测文本，然后在敏感词库中检索出有没有该字符对应的子树就行了，如果没有相应的子树，说明当前检测的字符不在敏感词库中，则直接跳过继续检测下一个字符；如果有相应的子树，则接着检查下一个字符是不是前一个字符对应的子树的子节点，这样迭代下去，就能找出待检测文本中是否包含敏感词了。
我们以文本“你是不是傻逼”为例，我们依次检测每个字符，因为前4个字符都不在敏感词库里，找不到相应的子树，所以直接跳过。当检测到“傻”字时，发现敏感词库中有相应的子树，我们把他记为tree-1，接着再搜索下一个字符“逼”是不是子树tree-1的子节点，发现恰好是，接下来再判断“逼”这个字符是不是叶子节点，如果是，则说明匹配到了一个敏感词了，在这里“逼”这个字符刚好是tree-1的叶子节点，所以成功检索到了敏感词：“傻逼”。大家发现了没有，在我们的搜索过程中，我们只需要扫描一次被检测文本就行了，而且对于被检测文本中不存在的敏感词，如这个例子中的“坏蛋”和“坏人”，我们完全不会扫描到，因此相比方案一效率大大提升了。
在Java中，我们可以用HashMap来存储上述的树形结构，还是以上述敏感词为例，我们把每个敏感词字符串拆散成字符，再存储到HashMap中，可以这样存：
{
"傻": {
"逼": {
"isEnd": "Y"
},
"子": {
"isEnd": "Y"
},
"大": {
"个": {
"isEnd": "Y"
}
}
}
}
首先将每个词的第一个字符作为key，value则是另一个HashMap，value对应的HashMap的key为第二个字符，如果还有第三个字符，则存储到以第二个字符为key的value中，当然这个value还是一个HashMap，以此类推下去，直到最后一个字符，当然最后一个字符对应的value也是HashMap，只不过这个HashMap只需要存储一个结束标志就行了，像上述的例子中，我们就存了一个{"isEnd","Y"}的HashMap，来表示这个value对应的key是敏感词的最后一个字符。
同理，“坏人”和“坏蛋”这2个敏感词也是按这样的方式存储起来，这里就不罗列出来了。
用HashMap存储有什么好处呢？我们知道HashMap在理想情况下可以以O(1)的时间复杂度进行查询，所以我们在遍历待检测字符串的过程中，可以以O(1)的时间复杂度检索出当前字符是否在敏感词库中，效率比方案一提升太多了。
接下来上代码。
首先是初始化敏感词库：
private Map<Object,Object> sensitiveWordsMap;
private static final String END_FLAG="end";
private void initSensitiveWordsMap(Set<String> sensitiveWords){
if(sensitiveWords==null||sensitiveWords.isEmpty()){
throw new IllegalArgumentException("Senditive words must not be empty!");
}
sensitiveWordsMap=new HashMap<>(sensitiveWords.size());
String currentWord;
Map<Object,Object> currentMap;
Map<Object,Object> subMap;
Iterator<String> iterator = sensitiveWords.iterator();
while (iterator.hasNext()){
currentWord=iterator.next();
if(currentWord==null||currentWord.trim().length()<2){ //敏感词长度必须大于等于2
continue;
}
currentMap=sensitiveWordsMap;
for(int i=0;i<currentWord.length();i++){
char c=currentWord.charAt(i);
subMap=(Map<Object, Object>) currentMap.get(c);
if(subMap==null){
subMap=new HashMap<>();
currentMap.put(c,subMap);
currentMap=subMap;
}else {
currentMap= subMap;
}
if(i==currentWord.length()-1){
//如果是最后一个字符，则put一个结束标志，这里只需要保存key就行了，value为null可以节省空间。
//如果不是最后一个字符，则不需要存这个结束标志，同样也是为了节省空间。
currentMap.put(END_FLAG,null);
}
}
}
}
代码的逻辑上面已经说过了，就是循环敏感词集合，将他们放到HashMap中，这里不再赘述。
接下来是敏感词的扫描：
public enum MatchType {
MIN_MATCH("最小匹配规则"),MAX_MATCH("最大匹配规则");
String desc;
MatchType(String desc) {
this.desc = desc;
}
}
public Set<String> getSensitiveWords(String text,MatchType matchType){
if(text==null||text.trim().length()==0){
throw new IllegalArgumentException("The input text must not be empty.");
}
Set<String> sensitiveWords=new HashSet<>();
for(int i=0;i<text.length();i++){
int sensitiveWordLength = getSensitiveWordLength(text, i, matchType);
if(sensitiveWordLength>0){
String sensitiveWord = text.substring(i, i + sensitiveWordLength);
sensitiveWords.add(sensitiveWord);
if(matchType==MatchType.MIN_MATCH){
break;
}
i=i+sensitiveWordLength-1;
}
}
return sensitiveWords;
}
public int getSensitiveWordLength(String text,int startIndex,MatchType matchType){
if(text==null||text.trim().length()==0){
throw new IllegalArgumentException("The input text must not be empty.");
}
char currentChar;
Map<Object,Object> currentMap=sensitiveWordsMap;
int wordLength=0;
boolean endFlag=false;
for(int i=startIndex;i<text.length();i++){
currentChar=text.charAt(i);
Map<Object,Object> subMap=(Map<Object,Object>) currentMap.get(currentChar);
if(subMap==null){
break;
}else {
wordLength++;
if(subMap.containsKey(END_FLAG)){
endFlag=true;
if(matchType==MatchType.MIN_MATCH){
break;
}else {
currentMap=subMap;
}
}else {
currentMap=subMap;
}
}
}
if(!endFlag){
wordLength=0;
}
return wordLength;
}
其中，MatchType表示匹配规则，有时候我们只需要找到一个敏感词就可以了，有时候则需要知道待检测文本中到底包含多少个敏感词，前者对应的是最小匹配原则，后者则是最大匹配原则。
getSensitiveWordLength方法的作用是根据给定的待检测文本及起始下标，还有匹配规则，计算出待检测文本中的敏感词长度，如果不存在，则返回0，存在则返回匹配到的敏感词长度。
getSensitiveWords方法则是扫描一遍待检测文本，逐个检测每个字符是否在敏感词库中，然后将检测到的敏感词截取出来放到集合中返回给客户端。
最后写个测试用例测一下：
public static void main(String[] args) {
Set<String> sensitiveWords=new HashSet<>();
sensitiveWords.add("你是傻逼");
sensitiveWords.add("你是傻逼啊");
sensitiveWords.add("你是坏蛋");
sensitiveWords.add("你个大笨蛋");
sensitiveWords.add("我去年买了个表");
sensitiveWords.add("shit");
TextFilter textFilter=new TextFilter();
textFilter.initSensitiveWordsMap(sensitiveWords);
String text="你你你你是傻逼啊你，说你呢，你个大笨蛋。";
System.out.println(textFilter.getSensitiveWords(text,MatchType.MAX_MATCH));
}
结果输出如下：
可以看到，我们成功地过滤出了敏感词。
敏感词过滤方案三
方案二在性能上已经可以满足需求了，但是却很容易被破解，比如说，我在待检测文本中的敏感词中间加个空格，就可以成功绕过了。要解决这个问题也不难，有一个简单的方法是初始化一个无效字符库，比如：空格、*、#、@等字符，然后在检测文本前，先将待检测文本中的无效字符去除，这样的话被检测字符就不存在这些无效字符了，因此还是可以继续用方案二进行过滤。只要被检测文本不要太长，那么我们只要在方案二的基础上再多扫描一次被检测文本去除无效字符就行了，这个性能损耗也还是可以接受的。
如果敏感词是英文，则还要考虑大小写的问题。有一个比较简单的解决方案是在初始化敏感词时，将敏感词都以小写形式存储。同时，在检测文本时，也统一将待检测文本转化为小写，这样就能解决大小写的问题了。
比较棘手的是中文跟拼音混合的情况，比如“傻逼”这个敏感词，可以通过“sha逼”这种中文跟拼音混合的方式轻松绕过，对于这种情况我目前还没想到比较好的解决方案，有想法的读者可以在文末留言。
原文发布时间为：2018-08-05
本文作者：黄泽杰
本文来自云栖社区合作伙伴“Java架构沉思录”，了解相关信息可以关注“Java架构沉思录”
