敏感词过滤算法 —— DFA

DFA，全称 Deterministic Finite Automaton 即确定有穷自动机：从一个状态通过一系列的事件转换到另一个状态，即 state -> event -> state。

确定：状态以及引起状态转换的事件都是可确定的，不存在“意外”。
有穷：状态以及事件的数量都是可穷举的。

计算机操作系统中的进程状态与切换可以作为 DFA 算法的一种近似理解。如上图所示，其中椭圆表示状态，状态之间的连线表示事件，进程的状态以及事件都是可确定的，且都可以穷举。

数据结构：

图1. DFA算法数据结构

观察图1，如果对Trie树（前缀树）数据结构有了解的话，就可以发现DFA本质上是构造一颗Trie树。如果抛开root节点的话，实际上是一个森林，每一个节点都的数据结构如下：图2 DFA节点结构

DFA算法的核心就是围绕这一颗树展开的。

匹配过程：

以图1 为例子，讲解一下DFA算法的匹配过程：假设有个input={他是个超凡脱俗的人}，在DFA算法中具体是如何匹配的呢？

index = 0，event= {他} ==> exist={false}
index = 1，event= {是} ==> exist={false}
index = 2，event= {个} ==> exist={false}
index = 3，event= {超} ==> exist={true},isEnd={false}，state={超}
index = 4，event= {凡}，state= {超} ==> exist{true} ，isEnd = {false}，state={超凡}
index = 5，event= {脱}，state= {超凡} ==> exist{true} ，isEnd = {false}，state={超凡脱}
index = 6，event= {俗}，state= {超凡脱} ==> exist{true} ，isEnd = {end}，state={超凡脱俗}，匹配成功
index = 7，event= {的} ==> exist={false}
index = 8，event= {人} ==> exist={false}
end，output={超凡脱俗}

翻译一下上面流程就是：

循环遍历需要匹配的字符串，根据当前下标的字（ text.charAt(index) ）去判断Trie树中是否存在该节点，在上述例子中，直到第四步才匹配到 “超” 字，这表示存在以“超”开头的敏感词，由于isEnd={false}表明这只是个中间态，而不是一个完整词，所以还不能说命中了敏感词 “超”
下标右移动,当前词为“凡”，然后在Trie树中判断以“超”节点为起始节点，“凡” 为事件，匹配到状态“超凡”这个节点，由于 “超凡”的isEnd={false}，所以不算命中。
直到第7步，以“超凡脱”为起始节点，“俗”为事件，匹配到状态“超凡脱俗”这个节点，并且isEnd={true},表明为终止态，说明已经是一个完整的词，所以命中敏感词 “超凡脱俗”。

图3. DFA匹配过程

复杂度分析

时间复杂度由于底层使用的是Trie树，所有分支的存储是使用HashMap，查找单个字符（Map.get()）的时间复杂度为O(1) ；但是对于输入的字符串，需要进行一次完整的遍历，所以对应的时间复杂度为O(n)。
空间复杂度查询时，无需额外的空间

具体实现

1.Trie树每个节点： DictionaryTreeState

/**
 * 表示DFA/字典树中的状态节点
 */
public class  {
    // 是否是终止状态
    boolean isEnd;
    // 可走的边，key为边的条件，value为下一个状态
    Map<String, DictionaryTreeState> edges;
 
    public DictionaryTreeState() {
        this.isEnd = false;
        edges = new HashMap<>();
    }
 
    public void addEdge(String key, DictionaryTreeState nextDictionaryTreeState) {
        this.edges.put(key, nextDictionaryTreeState);
    }
 
    public void addEdge(char key, DictionaryTreeState nextDictionaryTreeState) {
        addEdge(String.valueOf(key), nextDictionaryTreeState);
    }
 
    /**
     * 根据 key 找到下一个状态
     *
     * @param key
     * @return
     */
    public DictionaryTreeState getTrieState(String key) {
        return this.edges.get(key);
    }
 
    /**
     * 根据 key 找到下一个状态
     *
     * @param key
     * @return
     */
    public DictionaryTreeState getTrieState(char key) {
        return getTrieState(String.valueOf(key));
    }
 
    /**
     * 是否是结束状态
     *
     * @return
     */
    public boolean isEnd() {
        return this.isEnd;
    }
 
    public void setEnd(boolean isEnd) {
        this.isEnd = isEnd;
    }
 
    /**
     * 是否是终止（叶子）节点
     *
     * @return
     */
    public boolean isTerminal() {
        return this.edges.isEmpty();
    }
 
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("{"").append("isEnd":").append(isEnd)
                .append(",");
        for (Map.Entry<String, DictionaryTreeState> entry : edges.entrySet()) {
            sb.append(""").append(entry.getKey()).append("":").append(entry.getValue()).append(",");
        }
        sb.setLength(sb.length() - 1);
        sb.append("}");
        return sb.toString();
    }
}

2.构造Trie树 DictionaryTreeBuilder

public class DictionaryTreeBuilder {
    private final List<String> words;
 
    public DictionaryTreeBuilder() {
        this.words = new ArrayList<>();
    }
 
    public DictionaryTreeBuilder addWords(Collection<String> words) {
        this.words.addAll(words);
        return this;
    }
 
    public DictionaryTreeBuilder addWords(String... words) {
        return this.addWords(Arrays.asList(words));
    }
 
    public DictionaryTreeState build() {
        if (words.size() == 0) {
            return null;
        }
 
        DictionaryTreeState root = new DictionaryTreeState();
        for (String word : words) {
            if (word == null || "".equals(word)) {
                continue;
            }
            DictionaryTreeState current = root;
            for (char c : word.toCharArray()) {
                DictionaryTreeState next = current.getTrieState(c);
                if (next == null) {
                    next = new DictionaryTreeState();
                    current.addEdge(c, next);
                }
                current = next;
            }
            current.setEnd(true);
        }
 
        return root;
    }
}

3.敏感词检测 SensitiveWordsCheckUtil

public class SensitiveWordsCheckUtil {
    private final DictionaryTreeState root;
 
    public SensitiveWordsCheckUtil(DictionaryTreeState root) {
        this.root = root;
    }
 
    public Set<String> check(String text) {
        if (text == null || "".equals(text)) {
            return null;
        }
        Set<String> illWords = new LinkedHashSet<>();
        for (int i = 0; i < text.length(); i++) {
            StringBuilder stringBuilder = new StringBuilder();
            char c = text.charAt(i);
            DictionaryTreeState start = root.getTrieState(c);
            if (start == null) {
                continue;
            }
 
            stringBuilder.append(c);
            int j = i;
            DictionaryTreeState next = start;
            // 记录最近匹配成功的敏感词，主要是为了实现最大匹配
            String illWord = null;
            while (true) {
                j++;
                if (j == text.length()) {
                    break;
                }
                c = text.charAt(j);
                next = next.getTrieState(c);
                stringBuilder.append(c);
                if (next == null) {
                    break;
                }
                if (next.isEnd()) {
                    illWord = stringBuilder.toString();
                }
                if (next.isTerminal()) {
                    break;
                }
            }
            if (illWord != null && !"".equals(illWord)) {
                illWords.add(illWord);
            }
        }
 
        return illWords;
    }
}