有限状态机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"}; //keys
long outputs={1,3,5,7};                  //values
FST<Long> fst=new FST<>();
for(int i=0;i<inputs.length;i++)
{
    fst.add(inputs[i],outputs[i])
}
//get 
Long value=fst.get("abd");               //得到3
//迭代
BytesRefFSTEnum<Long> 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<String> 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<String, String> newMap = new HashMap<String, String>();
                    newMap.put("isEnd", "0");

                    // 添加到集合
                    nowMap.put(keyChar, newMap);
                    nowMap = newMap;
                }

                // 最后一个
                if (i == word.length() - 1) {
                    nowMap.put("isEnd", "1");
                }
            }
        }

        return wordMap;
    }

     public Set<String> getSensitiveWord(String txt, int matchType) {
        Set<String> sensitiveWordList = new HashSet<String>();

        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<String> set = getSensitiveWord(txt, matchType);
        Iterator<String> 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;
    }

    /**
     * 检查文字中是否包含敏感字符，检查规则如下：<br>
     * 如果存在，则返回敏感词字符的长度，不存在返回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<String> readSensitiveWordFile() {

        Set<String> wordSet = new HashSet<String>(); 
        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 貌似也是一棵树，而不是网状。