有限状态机FST

今天看到一篇介绍关于lucene使用有限状态机的文章，http://www.cnblogs.com/LBSer/p/4119841.html ， 刚开始觉得跟trie树很像，后发现他们是有区别的：
trie树是一个树状结构,每个子节点只有一个父节点，而FST是一个网状结构，每个子节点，可以有多个父节点，所以FST更省空间。

还看到一篇文章，里面也提到了有限状态机的应用
https://www.cnblogs.com/dreamroute/p/8484457.html

luence中有限状态机的使用方式

String inputs={"abc","abd","acf","acg"}; //keyslong outputs={1,3,5,7};                  //valuesFST fst=new FST<>();for(int i=0;i iterator=new BytesRefFSTEnum<>(fst);while(iterator.next!=null){...}

这里还有一个java的例子
https://blog.csdn.net/smorker/article/details/79468489
看起来很简单， 如果更简化可以使用一个map来实现，就像lucene中使用的那样。

这里还有有效状态机的一个变种，DFA，全称为：Deterministic Finite Automaton,即确定有穷自动机。可以用来过滤敏感词

代码如下：

public class All {    private Map sensitiveWordMap = null;    private Map addSensitiveWordToHashMap(Set wordSet) {        // 初始化敏感词容器，减少扩容操作        Map wordMap = new HashMap(wordSet.size());        for (String word : wordSet) {            Map nowMap = wordMap;            for (int i = 0; i < word.length(); i++) {                // 转换成char型                char keyChar = word.charAt(i);                // 获取                Object tempMap = nowMap.get(keyChar);                // 如果存在该key，直接赋值                if (tempMap != null) {                    nowMap = (Map) tempMap;                }                // 不存在则，则构建一个map，同时将isEnd设置为0，因为他不是最后一个                else {                    // 设置标志位                    Map newMap = new HashMap();                    newMap.put("isEnd", "0");                    // 添加到集合                    nowMap.put(keyChar, newMap);                    nowMap = newMap;                }                // 最后一个                if (i == word.length() - 1) {                    nowMap.put("isEnd", "1");                }            }        }        return wordMap;    }     public Set getSensitiveWord(String txt, int matchType) {        Set sensitiveWordList = new HashSet();        for (int i = 0; i < txt.length(); i++) {            // 判断是否包含敏感字符            int length = CheckSensitiveWord(txt, i, matchType);            // 存在,加入list中            if (length > 0) {                sensitiveWordList.add(txt.substring(i, i + length));                // 减1的原因，是因为for会自增                i = i + length - 1;            }        }        return sensitiveWordList;    }    /**     * 替换敏感字字符     *      * @param txt     * @param matchType     * @param replaceChar     * @return     */    public String replaceSensitiveWord(String txt, int matchType, String replaceChar) {        String resultTxt = txt;        // 获取所有的敏感词        Set set = getSensitiveWord(txt, matchType);        Iterator iterator = set.iterator();        String word = null;        String replaceString = null;        while (iterator.hasNext()) {            word = iterator.next();            replaceString = getReplaceChars(replaceChar, word.length());            resultTxt = resultTxt.replaceAll(word, replaceString);        }        return resultTxt;    }    /**     * 获取替换字符串     *      * @param replaceChar     * @param length     * @return     */    private String getReplaceChars(String replaceChar, int length) {        String resultReplace = replaceChar;        for (int i = 1; i < length; i++) {            resultReplace += replaceChar;        }        return resultReplace;    }    /**     * 检查文字中是否包含敏感字符，检查规则如下：
     * 如果存在，则返回敏感词字符的长度，不存在返回0     *      * @param txt     * @param beginIndex     * @param matchType     * @return     */    public int CheckSensitiveWord(String txt, int beginIndex, int matchType) {        // 敏感词结束标识位：用于敏感词只有1位的情况        boolean flag = false;        // 匹配标识数默认为0        int matchFlag = 0;        Map nowMap = this.sensitiveWordMap;        for (int i = beginIndex; i < txt.length(); i++) {            char word = txt.charAt(i);            // 获取指定key            nowMap = (Map) nowMap.get(word);            // 存在，则判断是否为最后一个            if (nowMap != null) {                // 找到相应key，匹配标识+1                matchFlag++;                // 如果为最后一个匹配规则,结束循环，返回匹配标识数                if ("1".equals(nowMap.get("isEnd"))) {                    // 结束标志位为true                    flag = true;                    // 最小规则，直接返回,最大规则还需继续查找                    if (1 == matchType) {                        break;                    }                }            }            // 不存在，直接返回            else {                break;            }        }        // 长度必须大于等于1，为词        if (matchFlag < 2 || !flag) {            matchFlag = 0;        }        return matchFlag;    }    private Set readSensitiveWordFile() {        Set wordSet = new HashSet();         wordSet.add("×××");        wordSet.add("×××");        wordSet.add("王八");        wordSet.add("王八蛋");        return wordSet;    }    public static void main(String[] args) {        All all=new All();        all.sensitiveWordMap=all.addSensitiveWordToHashMap(all.readSensitiveWordFile());        String txt = "×××";        String hou = all.replaceSensitiveWord(txt, 1, "*");        System.out.println("替换前的文字为：" + txt);        System.out.println("替换后的文字为：" + hou);    }}

感觉这个跟以前写的trie树非常相似，DFA 貌似也是一棵树，而不是网状。