有限狀態機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 貌似也是一棵樹，而不是網狀。