压分游戏

書名：自己動手寫分布式搜索引擎
作者名：羅剛
本章字數： 626字
更新時間： 2020-11-28 15:52:43

2.5.2 編輯距離有限狀態機

編輯距離自動機的基本想法是：構建一個有限狀態自動機，準確地識別出和目標詞在給定的編輯距離內的字符串集合。可以輸入任何詞，然后自動機可以基于是否和目標詞的編輯距離最多不超過給定距離，從而接收或拒絕它。而且，由于FSA的內在特性，可以在O(n)時間內判斷是可以接收或應該拒絕。這里，n是測試字符串的長度。而標準的動態規劃編輯距離計算方法需要O(m*n)時間，這里m和n是兩個輸入單詞的長度。因此編輯距離自動機可以更快地檢查許多單詞和一個目標詞是否在給定的最大距離內。

單詞“food”的編輯距離自動機形成的非確定有限狀態自動機，最大編輯距離是2。開始狀態在左下，狀態使用ne標記風格命名，這里n是目前為止正確匹配的字符數，e是錯誤數量。垂直轉換表示未修改的字符，水平轉換表示插入，兩類對角線轉換表示替換(用*標記的轉換)和刪除(空轉換)，如圖2-7所示。

圖2-7 編輯距離自動機

單詞“food”的長度是4，所以圖2-7有5列。允許2次錯誤，所以有3行。

Levenshtein Automata接收兩個參數，輸入字符串和一個布爾值，說明換位是否可以作為一個編輯操作。如果“GO”可以換位，則可以接收“OG”。使用BasicOperations.run方法測試。

        //換位也可以看成是一個編輯操作
        LevenshteinAutomata builder = new LevenshteinAutomata("GO", true);
        Automaton a = builder.toAutomaton(1); //最大編輯距離是1
        System.out.println(BasicOperations.run(a, "OG")); //輸出true

如果“GO”不能換位，則不能接收“OG”。

        LevenshteinAutomata builder = new LevenshteinAutomata("GO", false);
        Automaton a = builder.toAutomaton(1); //最大編輯距離是1
        System.out.println(BasicOperations.run(a, "OG")); //輸出false

測試最大編輯距離是2的情況。

        LevenshteinAutomata builder = new LevenshteinAutomata("EBER", true);
        Automaton a = builder.toAutomaton(2); //最大編輯距離是2

測試可以接收哪些字符。

        System.out.println(BasicOperations.run(a, "BR")); //輸出true
        System.out.println(BasicOperations.run(a, "EB")); //輸出true
        System.out.println(BasicOperations.run(a, "EBE")); //輸出true
        System.out.println(BasicOperations.run(a, "EBER")); //輸出true

官术网_书友最值得收藏!

自己動手寫分布式搜索引擎

2.5.2 編輯距離有限狀態機