有限狀態機與Lucene的那些事（開篇）
- 2019 年 11 月 11 日
- 筆記
確定有限狀態機（deterministic finite automaton/dfa）是一個數學計算模型，組成部分是一個5元組：
- 有限的狀態集Q
- 有限的輸入符號S，又被稱作alphabet（跟我們熟知的英文字母表應該不一樣，是個引申）
- 狀態變換函數F，F：S ? Q -> Q
- 初始狀態s0，s0 ∈ Q
- 接納狀態集Z，Z ⊆ Q
假設有一個字元串（符號序列）w=a(0)|a(1)|a(2)|a(3)|…|a(n)，且w ⊆ S，另有r=r(0)|r(1)|r(2)|r(3)|…|r(n)的一個狀態序列，當w和r符合如下條件時認為狀態機M接納w：
- r0 = s0，初始狀態為狀態機的初始狀態
- r(i+1) = F(r(i), a(i+1)), for i = 0,…,n-1；當前狀態r(i)輸入a(i+1)後進行變換後的下一個狀態為r(i+1)，這裡F變換後的狀態必然屬於Q
- r(n) ∈ Z，變換後的最終狀態為終態Z之一
確定有限狀態機和不確定有限狀態機（nondeterministic finite automaton/nfa）的區別在於，dfa一對源狀態和輸入符號可以唯一確定一個變換操作，且每個狀態變換操作都需要一個輸入符號，而nfa不做這個限制（比如前述dfa的組成第三條，在nfa，狀態變換函數可以是F: S ? Q-> P(Q)，可以從一個狀態變換為若干個其他狀態），dfa是一種特殊狀態下的nfa。
如圖，這裡表示了一個^A(B*)A$的正則匹配，當輸入為A，到達S2狀態，S2狀態接受輸入A或B，輸入B狀態不變，輸入A跳轉到狀態S1，為接納狀態。
有限狀態機在處理文字匹配上有非常好的優勢，Lucene 4.0之前的模糊查詢（fuzzy query）用了簡單粗暴的遍曆法：遍歷索引中全部term並依次計算與輸入詞的編輯距離，可以解決問題，但是有很高的演算法複雜度，在4.0之後Lucene引入了有限狀態機來提高模糊查詢的性能，據說提升達到了百倍之多 （http://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is-100-times-faster.html）
Lucene中與自動機相關的主要是 org.apache.lucene.util.automaton 包以及 org.apache.lucene.search 包下與 Automata/Automaton 相關的類。
以前綴查詢為例，首先將檢索詞構建為一個有限狀態機，比如用前綴 "/Computer" 匹配欄位 category，可以構建為一個 state 和 transition 都是11的有限狀態機，並將末尾的r字元設置為接納狀態（accept=true）：
如圖，值得一提的是Lucene中的Automaton封裝了toDot()方法，可以將狀態機輸出為graphviz可識別的描述符，通過graphviz的命令行工具dot可以輸出為png格式圖片。
最後一個變換是指在到達接納狀態之後的任意輸入依然滿足接納條件（也就是表達了前綴查詢的意思）。
這裡說說遇到的一個坑，Lucene 7.0 版本前存在一個 bug (https://issues.apache.org/jira/browse/LUCENE-7914)，在遇到 regex/prefix 等查詢時（後端用 Automata/AutomatonQuery 實現），而構建 Automata 的過程中會用 Operations 的 isFinite() 方法判斷構建完成後的狀態機是否為 DFA，坑就坑在 isFinite() 方法存在遞歸，當 regex 用了如下類似的 regex 查詢，或者是一個非常長的prefix查詢，都有可能會因為遞歸過度而報 StackOverFlow 異常。
POST /test/_search { "query": { "regexp": { "test": "t{1,9500}" } } }
請注意，這個操作會導致執行查詢的全部 node 上 ES 主進程異常退出，如果這個索引恰巧分布在集群內的全部 node 上，那麼此類查詢相當於引爆了一顆核彈。。
當然 Lucene 7.0 之後修復了這個問題，相應的 Es6.0 之後版本也就不存在類似的問題了，主要的解決方法就是在 isFinite() 方法遞歸中限制了最大遞歸深度。
說了這麼多，現在就寫點程式碼，簡單實現一個 prefix 查詢示例：
public void testPrefixQuery() throws Exception { String[] categories = new String[] {"/Computers", "/Computers/Mac", "/Computers/Windows"}; IndexWriterConfig config = new IndexWriterConfig(); try (Directory directory = new RAMDirectory(); IndexWriter writer = new IndexWriter(directory, config)) { for (int i = 0; i < categories.length; i++) { Document doc = new Document(); doc.add(newStringField("category", categories[i], Field.Store.YES)); writer.addDocument(doc); } try (IndexReader reader = DirectoryReader.open(writer)) { PrefixQuery query = new PrefixQuery(new Term("category", "/Computers")); IndexSearcher searcher = new IndexSearcher(reader); ScoreDoc[] hits = searcher.search(query, 1000).scoreDocs; System.out.println(Arrays.toString(hits)); } } }
輸出：
[doc=0 score=1.0 shardIndex=0, doc=1 score=1.0 shardIndex=0, doc=2 score=1.0 shardIndex=0]
最後要補充的是，如果對 Lucene 程式碼介面比較感興趣，可以好好研究一下 Lucene 源碼中的單元測試，在 Lucene/Solr 源程式碼中包含了非常豐富的單元測試，功能點覆蓋面也非常全，非常值得我們學習，軟體測試和品質保障理應是軟體開發者作為 owner 的事情。
