Automaton（二）（Lucene 8.4.0）

在文章Automaton中我们介绍了确定型有穷自动机(Deterministic Finite Automaton)的概念，以及在TermRangeQuery中如何根据查询条件生成一个转移图，本文依旧根据该文章中的例子，介绍在Lucene中如何构建DFA，即生成图2的转移图，以及存储状态（state）、转移（transition）函数的数据结构。

我们再次给出文章Automaton中的例子：

图1的第79行代码描述了TermRangQuery的查询范围为["bc"，"gch"]，下文中会用minValue来描述下界"bc"、maxValue来描述上界"gch"，根据minValue、maxValue构建的DFA如下所示：

图2中，接受语言L完整描述是 A = ({0，1，2，3，4，5}， {0，… ，255}，，0，{1，3，4，5})：

{0，1，2，3，4，5}：描述的是有穷的状态（State）集合，即有0~5共6个状态
{0，… ，255}：描述的是有穷的输入符号集合，即输入的符号是256种ASCII码
：描述的是转移函数，Lucene中用两个int类型的数组transitions、states描述，下文会展开介绍
0：描述的是初始状态，即状态0
{1，3，4，5}：描述的是可接受状态或终结状态

上述内容如果没看明白请先阅读文章Automaton。

构建DFA的流程图

为了便于介绍Lucene中构建DFA的流程，图3中描述的流程是根据图1的例子给出的，即一个特例DFA的构建过程，实际的构建流程基于边界问题（例如maxValue的值为null、minValue的值跟maxValue是相等），非确定性（non-deterministic）自动机等一些条件会导致相当复杂的分支流程，故无法一一列出，不过在掌握了图3的流程实现后，再根据源码来了解全面的构建流程就变得十分简单了。

在介绍图3的流程之前，我们先介绍下Lucene是如何描述（存储）转移函数的。

Lucene通过两个int类型的数组transitions、states来描述转移函数：

transitions数组：数组中使用固定的连续的三个数组元素来描述一个转移函数的三个信息
- 目标状态dest，描述的是当前状态转移到下一个状态，该状态即目标状态dest
- 输入符号的最小值min，描述的是当前转移可接受的最小输入符号
- 输入符号的最大值max，描述的是当前转移可接受的最大输入符号
states数组：数组中使用固定的连续的两个数组元素来描述当前状态的两个信息
- 第一个信息：当前状态的第一个转移函数信息在transitions数组中的起始位置
- 第二个信息：当前状态的转移函数的数量

我们以状态0为例，由图2可知，它包含了三个转移函数，如下所示：

，

上述公式是如何得出见文章Automaton中的介绍，该公式的转移函数信息用transitions、states数组存储如下所示：

图4中，状态0的状态值为0，即curState = 0，根据公式跟分别获得states[ ]数组的两个下标值，这两个下标值对应的数组元素分别描述了状态0的第一个转移函数信息在transitions数组中的起始位置，以及状态0的转移函数的数量，由于transitions数组中用固定数量的数组元素描述一个转移函数的信息，故length的值为；对于状态0的第一个转移函数，dest描述了转移到下一个状态的状态值，即状态2，并且接受最小值min为98（ASCII码，对应字符"b"）、最大值max为98的输入符号，也就说状态0到状态2的转移只接受字符"b"。

另外状态0的三个转移函数是根据min值进行排序的，其目的是在读取阶段能更快的判断term是否在查询条件范围内，具体过程在介绍TermRangeQuery时再展开。

构建sinkState、startState的转移函数

sinkState为可接受状态，即图1中的状态1，由于我们处理的term是ASCII码，所以该状态可接受的输入符号为0~255，即所有的ASCII码，startState为初始化状态，即图1中的状态0，由于查询条件的上下界minValue、maxValue分别为"bc"、"gch"，根据这两个值的第一个字符"b"、"g"，那么我们需要创建三个转移函数：