有限状態マシンFCT

今日はluceneが有限状態機を使うことについて紹介した文章を見ました.http://www.cnblogs.com/LBSer/p/4119841.html trieツリーはツリー構造であり、各サブノードは親ノードのみであり、FCTはメッシュ構造であり、各サブノードは複数の親ノードを有してもよい.だからFCTは空間をもっと節約します.
また一つの文章を見ました.中には有限状態機の応用についても言及しました.https://www.cnblogs.com/dreamroute/p/8484457.html
luenceにおける有限状態機の使い方

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){...}

ここにjavaの例があります.https://blog.csdn.net/smorker/article/details/79468489簡単に見えますが、もっと簡略化すれば、一つのmapを使って実現できます.luceneで使われているように.
ここには有効な状態マシンのバリエーションがあります.DFAは、すべて「Deterministic Finite Automatototomaton」と呼ばれています.つまり、貧乏自动机があると確定します.敏感語のフィルタリングに使用できます.
コードは以下の通りです

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も網状ではなく木のようです.