今天看到一篇介紹關(guān)于lucene使用有限狀態(tài)機(jī)的文章，http://www.cnblogs.com/LBSer/p/4119841.html ， 剛開始覺得跟trie樹很像，后發(fā)現(xiàn)他們是有區(qū)別的：
trie樹是一個(gè)樹狀結(jié)構(gòu),每個(gè)子節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)，而FST是一個(gè)網(wǎng)狀結(jié)構(gòu)，每個(gè)子節(jié)點(diǎn)，可以有多個(gè)父節(jié)點(diǎn)，所以FST更省空間。

創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),原陽企業(yè)網(wǎng)站建設(shè),原陽品牌網(wǎng)站建設(shè),網(wǎng)站定制,原陽網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,原陽網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

還看到一篇文章，里面也提到了有限狀態(tài)機(jī)的應(yīng)用
https://www.cnblogs.com/dreamroute/p/8484457.html

luence中有限狀態(tài)機(jī)的使用方式

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

這里還有一個(gè)java的例子
https://blog.csdn.net/smorker/article/details/79468489
看起來很簡(jiǎn)單， 如果更簡(jiǎn)化可以使用一個(gè)map來實(shí)現(xiàn)，就像lucene中使用的那樣。

這里還有有效狀態(tài)機(jī)的一個(gè)變種，DFA，全稱為：Deterministic Finite Automaton,即確定有窮自動(dòng)機(jī)。可以用來過濾敏感詞

代碼如下：

public class All {

    private Map sensitiveWordMap = null;

    private Map addSensitiveWordToHashMap(Set wordSet) {

        // 初始化敏感詞容器，減少擴(kuò)容操作
        Map wordMap = new HashMap(wordSet.size());

        for (String word : wordSet) {
            Map nowMap = wordMap;
            for (int i = 0; i < word.length(); i++) {

                // 轉(zhuǎn)換成char型
                char keyChar = word.charAt(i);

                // 獲取
                Object tempMap = nowMap.get(keyChar);

                // 如果存在該key，直接賦值
                if (tempMap != null) {
                    nowMap = (Map) tempMap;
                }

                // 不存在則，則構(gòu)建一個(gè)map，同時(shí)將isEnd設(shè)置為0，因?yàn)樗皇亲詈笠粋€(gè)
                else {

                    // 設(shè)置標(biāo)志位
                    Map newMap = new HashMap();
                    newMap.put("isEnd", "0");

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

                // 最后一個(gè)
                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的原因，是因?yàn)閒or會(huì)自增
                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;
    }

    /**
     * 檢查文字中是否包含敏感字符，檢查規(guī)則如下：

     * 如果存在，則返回敏感詞字符的長(zhǎng)度，不存在返回0
     * 
     * @param txt
     * @param beginIndex
     * @param matchType
     * @return
     */
    public int CheckSensitiveWord(String txt, int beginIndex, int matchType) {

        // 敏感詞結(jié)束標(biāo)識(shí)位：用于敏感詞只有1位的情況
        boolean flag = false;

        // 匹配標(biāo)識(shí)數(shù)默認(rèn)為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);

            // 存在，則判斷是否為最后一個(gè)
            if (nowMap != null) {

                // 找到相應(yīng)key，匹配標(biāo)識(shí)+1
                matchFlag++;

                // 如果為最后一個(gè)匹配規(guī)則,結(jié)束循環(huán)，返回匹配標(biāo)識(shí)數(shù)
                if ("1".equals(nowMap.get("isEnd"))) {

                    // 結(jié)束標(biāo)志位為true
                    flag = true;

                    // 最小規(guī)則，直接返回,最大規(guī)則還需繼續(xù)查找
                    if (1 == matchType) {
                        break;
                    }
                }
            }

            // 不存在，直接返回
            else {
                break;
            }
        }
        // 長(zhǎng)度必須大于等于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);
    }

}

感覺這個(gè)跟以前寫的trie樹非常相似，DFA 貌似也是一棵樹，而不是網(wǎng)狀。