有限状态机与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 的事情。
