算法简介与场景介绍
DFA算法，中文全称为确定性有穷自动机。它的基本思想是构建一个有穷自动机，当用户输入文本时，通过自动机的状态转换来快速匹配敏感词。具体特征是，有一个有效状态的集合和一些从一个状态通向另一个状态的边，每条边上标记一个符号，其中一些状态是初态，一些状态是终态。只有从初态经过正确的状态转移到终态的词才能被认定为敏感词。当然我们也可以将整个DFA模型看成是树型结构，终态对应的都是叶子节点，初态可以看成是某个根节点，只有完全匹配到叶子节点才算匹配成功。最近我在设计我们线上刷题网站的时候，有一个社区讨论模块，大家可以在上面发布动态、发布评论回复，这就难免涉及到一些敏感词的评论，为了构建和谐健康的讨论社区，我们在这边需要对用户发布的评论回复内容进行敏感词的检测。那么在这种场景下，我们就考虑到了使用DFA算法来进行敏感词的快速匹配。
算法实现
DFA模型的构建
模型的构建可以看成是一棵树的构建，树的每个节点都是敏感词中的一个字符，我们以词“傻波一”为例，来构建一个DFA：
1.初始状态：S0
2.状态S1匹配到"傻"
3.状态S2匹配到"波"
4.状态S3匹配到"一"
这里我们只在谈DFA模型构建大体思路，具体使用的数据结构在这里并没有给出，说是树型结构是为了更好地理解这里面敏感词的转换逻辑。我们给出一个示意图来更直观地展示这一过程：
这是一个有两个简单敏感词地DFA模型，当匹配到的词是"傻"时进入左边的S0状态，等待下一个状态的转换触发条件，比如出现"子"或者"波"进入下一个状态，在等待状态转移的过程中，如果出现的不是"子"或者"波"那么就会回退到初态，也就是顶层节点，等待进入左边节点的S0或者右边的S0，一直到出现"子"或者连着出现了"波"和"一"这样就匹配到了终态，判定当前的词为敏感词。
代码的构建
在这里，我们将实现构建DFA的方法、删除词库中的敏感词的方法以及使用DFA算法匹配敏感词的方法，帮助大家进一步理解。首先来说一下我们构建DFA用到的数据结构，这边主要使用一个Map集合来标示词节点，键表示为词节点，值为这个词节点后续的词节点的信息，也是同样的Map集合来存储，这个Map集合的形式和前面说的也是一致的，这就像是树节点一样：一个树的根节点是TreeNode类型，有左右孩子，然后它的左右孩子也是TreeNode。这边的思想与这个是一致的。
首先是敏感词的DFA构建，根据上面的描述，算法代码如下显示：
public class DFAFilter {
private final Map<Character, Map> wordMap = new HashMap<>();
public void addWord(String word) {
Map<Character, Map> nowMap = wordMap;
for (int i = 0; i < word.length(); i++) {
char keyChar = word.charAt(i);
Map<Character, Map> newWordMap = nowMap.get(keyChar);
if (newWordMap == null) {
newWordMap = new HashMap<>();
nowMap.put(keyChar, newWordMap);
}
nowMap = newWordMap;
}
nowMap.put(' ', new HashMap<>()); // 使用空格字符表示 isEnd 标志
}
}其次是敏感词的检测，我们这边直接将输入的文本中的敏感词用*代替了，更符合显示场景的需求：
public String containsSensitiveWord(String text){
StringBuilder stringBuilder = new StringBuilder(text);
List<String> result=new ArrayList<>();
for(int i=0;i<stringBuilder.length();i++){
Map<Character, Map> cur = wordMap;
int startIndex=i;
for(int j=i;j<stringBuilder.length();j++){
char c = stringBuilder.charAt(j);
cur=cur.get(c);
if(cur==null)
break;
if(cur.containsKey(' ')){
String substring = stringBuilder.substring(startIndex, j + 1);
if(!result.contains(substring))
result.add(substring);
i=j;
for(int k=startIndex;k<=j;k++){
stringBuilder.replace(k,k+1,"*");
}
}
}
}
return stringBuilder.toString();
}当然如果我们需要删除之前录入的敏感词，核心思想就是遍历这个Map集合，删除敏感词的最后一个词，然后回溯删除不必要的词，删除逻辑是删除那些没有后续字符并且没有终止标识符的词：
public void removeWord(Collection<String> wordList) {
if (wordList == null || wordList.isEmpty()) {
return;
}
for (String word : wordList) {
Map<Character, Map> nowMap = wordMap;
Stack<Map<Character, Map>> stack = new Stack<>();
Stack<Character> charStack = new Stack<>();
for (int i = 0; i < word.length(); i++) {
char keyChar = word.charAt(i);
Map<Character, Map> nextMap = nowMap.get(keyChar);
if (nextMap == null) {
// 敏感词不存在
return;
}
stack.push(nowMap);
charStack.push(keyChar);
nowMap = nextMap;
}
if (nowMap.containsKey(' ')) {
nowMap.remove(' ');
}
// 回溯清理无用节点
for (int i = word.length() - 1; i >= 0; i--) {
Map<Character, Map> currentMap = stack.pop();
char currentChar = charStack.pop();
// 如果当前字符对应的 Map 为空，则删除该字符节点
if (nowMap.isEmpty()) {
currentMap.remove(currentChar);
}
nowMap = currentMap;
}
}
}那么我们完成了DFA模型的构建、利用DFA模型的状态转换思想进行敏感词检测以及删除敏感词方法。
总结
DFA算法在敏感词检测场景有着比较好的展现效果，其核心思想在于对给定敏感词构建确定性有穷自动机，这边以Map集合的形式构建了一个类似于树型结构的DFA,包括初态中间态以及终态，根据是否出现满足状态转移的条件来推进下一个状态，到达终态判定为敏感词。在我们的刷题网站中的社区模块里，用户发布动态内容和评论回复的敏感词检测就使用到了DFA算法。上面给出了我们实现的DFA算法的核心功能。
