Automaton

     在介绍 Automation 类之前先介绍下有穷自动机的概念,有穷自动机分为确定型有穷自动机(DFA)跟不确定型有穷自动机(NFA)。由于本篇文章是为介绍 TermRangeQuery 作准备的,所以只介绍确定性有穷自动机。

确定型有穷自动机(Deterministic Finite Automaton)

     这种自动机在读任何输入序列后只能处在一个状态中,术语“确定型”是指这样的事实:在每个输入上存在且仅存在一个状态,自动机可以从当前状态转移到这个状态。

确定型有穷自动机的定义

  • 一个确定型有穷自动机包括:一个有穷的状态集合,通常记作Q。
  • 一个有穷的 输入符号 集合,通常记作 \sum。
  • 一个转移函数,以一个状态和一个输入符号作为变量,返回一个状态。转移函数通常记作\delta。在表示自动机的图中,用状态之间的箭弧和箭弧上的标记来表示\delta。如果q是一个状态,a是一个输入符号,则\delta(q, a)是这样的状态p,使得从p到q有带a标记的箭弧。
  • 一个初始状态,是Q中状态之一。
  • 一个终结状态或接受状态的集合F。集合F是Q的子集。

     通常用缩写 DFA 来指示确定型有穷自动机。最紧凑的 DFA 表示是列出上面 5 个部分,DFA 可以用西面的五元组表示:

A = (Q,

\sum,\delta,q_0,F)

     其中 A 是 DFA 的名称,Q是状态集合,\sum是输入符号,\delta是转移函数,q_0是初始状态,F是接受状态集合。

DFA 如何处理串

     关于 DFA 需要理解的第一件事情是,DFA 如何决定是否“接受”输入符号序列。DFA 的"语言"是这个 DFA 接受的所有的串的集合。假设a_1a_2…a_n是输入序列。让这个 DFA 从初始状态q_0开始运行。查询转移函数\delta,比如说\delta(q_0,a_1) = q_1,以找出 DFA A 在处理第一个输入符号a_1之后进入的状态。处理下一个输入符号a_2,求\delta(q_1,a_2) 的值,假设这个状态是q_2,以这种方式继续下去,找出状态q_3,q_4,…,q_n,使得对每个i, \delta(q_{i-1},a_i) = q_i。如果q_n属于F,则接受输入a_1a_2…a_n,否则就“拒绝”。

例子

     形式化地规定一个 DFA,接受所有仅在串中某个地方有 01 序列的 0 和 1 组成的串,可以把这个语言 L 写成:

{w | w形如 x01y, x 和 y 是只包含 0 和 1 的两个串}

     这个语言中的串的例子包括 01、11010 和 100011。不属于这个语言的串的例子包括 0、1000、111000。

     对于接受这个语言 L 的自动机,我们知道些什么?首先,输入字母是\sum = {0,1}。有某个状态集合Q,其中一个状态(如q_0)是初始转态。这个自动机需要记住这样的重要事实:至此看到了什么样的输入。为了判定 01 是不是这个输入的一个字串,A 需要记住:

  1. 是否已经看到了 01?如果是,就接受后续输入的每个序列,即从现在起只处在接受状态中。
  2. 是否还没有看到 01,但上一个输入是 0,所以如果现在看到 1,就看到 01.并且接受从此开始看到的所有东西?
  3. 是否还没有看到 01,但上一个输入要么不存在(刚开始运行),要么上次看到 1?在这种情况下,A 直到先看到 0 然后立即看到 1 才接受。

     这三个条件每个都能用一个状态表示。条件(3)用初始状态q_0来表示。的确,在刚开始时,需要看到一个 0 然后看到一个 1,但是如果在状态q_0下接着看到一个 1,就并没有更接近于看到 01,所以必须停留在状态q_0中。即,\delta(q_0,1) = q_0。

     但是,如果在状态 q_0下接着看到 0,就处在条件(2)中,也就是说,还没有看到 01,但看到了 0。因此,用 q_2来表示条件(2)。在输入 0 上从 q_0出发的转移是\delta(q_0,0) = q_2。

     现在,来考虑从状态 q_2出发的转移。如果看到 0,就并没有取得任何进展,但也没有任何退步。还没有看到 01,但 0 是上一个符号,所以还在等待 1。状态 q_2完美地描述了这种局面,所以希望\delta(q_2,0) = q_2。如果在状态q_2看到 1 输入,现在就知道有一个 0 后面跟着 1.就可以进入接受状态,把接受状态称为q_1,q_1对应上面的条件(1)。就是说,\delta(q_2,1) = q_1。

     最后,必须设计状态q_1的转移。在这个状态下,已经看到了 01 序列,所以无论发生上面事情,都还是处在这样的局面下:已经看到 01。也就是说,\delta(q_1,0)==\delta(q_1,1)=q_1。

     因此,Q = {q_0,q_1,q_2},已经说过,q_0是初始状态,唯一的接受状态是q_1,也就是说,F = {q_1}。接受语言 L(有 01 字串的串的语言)的自动机 A 的完整描述是

A = ({q_0,q_1,q_2}, {0,1}, \delta,q_0,{q_1})

其中\delta是上面描述的转移函数。

转移图

根据上面的例子,生成的转移图如下:

图 1:

蓝色圆圈表示当前状态只处在接受状态

DFA 在 Lucene 中的应用

在 Lucene,跟 DFA 相关功能有 通配符查询(WildcardQuery)、正则表达式(Regular Expression)、范围查询 TermRangeQuery 等。本篇文章中仅介绍 TermRangeQuery。

TermRangeQuery 中的 DFA

TermRangeQuery 利用 DFA 来使得在查询阶段能获得查询范围的所有 term,或者说所有的域值。我们直接通过一个例子来介绍 DFA。

例子

索引阶段的数据:

图 2:

查询条件:

图 3:

生成 DFA 的过程本篇文章不会详细介绍,理由是如果能弄明白上面提到的 DFA 的概念,然后再去根据我注释的源码,相信很快能明白其逻辑过程。生成 DFA 全部过程的源码都在 Automata.java 文件中的 Automaton makeBinaryInterval(…)方法中。GitHub 地址: https://github.com/luxugang/Lucene-7.5.0/blob/master/solr-7.5.0/lucene/core/src/java/org/apache/lucene/util/automaton/Automata.java

转移图:

图 4:

上图中 数字为 ASCII

接受语言 L(域值大于等于"bc"并且小于等于"gch")的自动机 A 的完整描述是

A = ({0,1,2,3,4,5}, {0,… ,255}, \delta,0,{0,5})

筛选满足查询范围要求的域值

由于我们在 TermRangeQuery 中指定的域名为“content”,所以 Lucene 会按照从小到大的顺序遍历所有域名为"content"的域值,即"a"、“bcd”、“ga”、“gc”、“gch”、“gchb”,然后对这些域值逐个的去 DFA 中查找,比如说"bcd", 总是从状态 0 开始,检查每一个字符"b"、“c”、“d"能否在 DFA 中通过转移分别找到各自的状态,或者找到一个可接受的状态(蓝色圆圈的状态),如果前面两个条件之一满足,那么我们认为"bcd"是满足在范围"bc”~“gch"中的。

转移函数

状态 0 的转移函数

状态 0 有到状态 1、状态 2、状态 3 一共三种转移方式,转移函数为:

\delta(0,ASCII)\begin{cases}1,\qquad 99(c) ≤ ASCII ≤ 102(f)\\2,\qquad ASCII = 98(b)\\3,\qquad ASCII = 103(g)\end{cases}

状态 1 的转移函数

状态 1 是一个可接受状态,转移函数为:

\delta(1,ASCII) = 1,\qquad 所有的ASCII

状态 2 的转移函数

状态 2 有到状态 1 的一种转移方式,转移函数为: