从Solr源码看自动机的实现

最近在公司被分配了一个任务，看一下Solr通配符查询的实现，主要是因为发现Solr对于通配符查询很慢，于是就哼哧哼哧跑去看源码了。源码看起来很累，大量调用的嵌套、委托模式，一层套一层，不过还是很有收获，今天不谈Solr具体查询的逻辑，谈一谈其查询的实现方式——自动机。对于想自己实现用自动机进行字符串匹配、正则表达式匹配的同学，还是值得一看的。(基于Solr_5.0.0)

自动机的定义

An automaton is a self-operating machine, or a machine or control mechanism designed to follow automatically a predetermined sequence of operations, or respond to predetermined instructions.

“自动机就是自我运行的机器，它的运行机制被设计为自动执行一些预定义好的操作序列，或者对一些预定义好的指令做出反映。”维基百科如是说。此时的自动机，仅仅是停留在机器的字面意思，指的就是物理的机器，例如上发条的机器，上了发条之后，会按照预定义好的逻辑行动。

有限状态自动机

在计算机上运用比较普遍的就是有限状态自动机，简称状态机。所谓状态机，是一种表示若干个状态以及在这些状态之间的转移和动作等行为的数学模型。可以发现，状态自动机为什么称之为自动机，是因为其上的状态和状态之间的转移操作也都是预定义好的。而状态，在计算机程序中，就可以被抽象成很多东西，从而实现很多应用。状态自动机通常包含以下几个部分：

1. 唯一初始状态
2. 中间状态(可能是一个集合)
3. 接收状态(可能是一个集合)
4. 输入符号(可能是一个集合)
5. 转换函数(从一个状态到另一个状态的转换)

来看一个简单的自动机：

其中，初始状态是0，中间状态是1，接收状态是2，{a,b}是输入符号。自动机最主要的一个应用就是用于正则表达式，上面的自动机对应的正则表达式是(a|b)*ab。其实到这里，自动机如何用于正则表达式匹配，就已经可见一斑了。一般过程如下：

1. 对正则表达式生成相应的有限状态自动机
2. 对输入的字符串，根据字符串中的字符，和状态机上的状态转移函数，进行状态转移，直到无法进行转移，或者到达输入的字符串的末尾
3. 无法进行转移或者到达输入字符串的末尾时，判断当前状态是不是可接收状态，如果是的话，则代表该输入的字符串被正则表达式接收，反之则不接收

确定的有限状态自动机(DFA)和不确定的有限状态自动机(NFA)

上面举的自动机就是一个NFA，NFA和DFA的主要区别在于：

1. DFA没有输入空串上的转换操作
2. 对于DFA，一个特定的符号输入，有且只能得到一个状态，而NFA可能得到一个状态集

上面举的NFA的例子，对于状态0，输入符号a，可能得到状态1，也可能得到状态0。至于输入空串上的转换，就是输入空，可以转到下一个状态。输入空通常用希腊字母Epsilon表示，如下图中状态0到状态1的转换。

NFA和DFA具体的区别也很多，NFA也能转化成DFA，这里都不再展开了。

Solr中的自动机实现

好了，终于到了实现自动机的时候了。从上面的自动机概念的介绍可以发现，实现自动机重要的两个组成部分，就是状态以及状态之间的转移。Solr中状态之间的转换用Transition类来表示。Transition类如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Transition {
  /** Sole constructor. */
  public Transition() {
  }
  
  /** Source state. */
  public int source;
  
  /** Destination state. */
  public int dest;
  
  /** Minimum accepted label (inclusive). */
  public int min;
  
  /** Maximum accepted label (inclusive). */
  public int max;
  
  int transitionUpto = -1;
 
  @Override
  public String toString() {
    return source + " --> " + dest + " " + (char) min + "-" + (char) max;
  }
}

可以看到，成员变量主要有代表源状态的source，目标状态的dest，以及转换边上的label。可能会有同学觉得label的概念不是很好理解，可以看一下上面的NFA的实例图，label就是每条转换边上的字母。Solr中用min和max两个变量来指定了label的范围，而且都是int型变量，这是因为Solr会把字符转换成在Unicode字符集里的编号，即Java中的CodePoint。比如某个状态可以接受任意字符，那么用Transition类来表示的话，min=Character.MIN_CODE_POINT, max=Character.MAX_CODE_POINT。

下面就可以看一下自动机类Automaton的实现了，按照上面的思路，Automaton类里面，得包含一个整型数组，保存所有的状态，还得包含一个Transition数组，保存所有状态间的转换。但Solr源码可不是这样实现的，而是用到了一些小trick。

1
2
3
4
5
6
7
8
9
10

/** Index in the transitions array, where this states
 *  leaving transitions are stored, or -1 if this state
 *  has not added any transitions yet, followed by number
 *  of transitions. */
private int[] states;
 
private final BitSet isAccept;

/** Holds toState, min, max for each transition. */
private int[] transitions;

可以看到，代码中用transitions整型数组保存状态间的转移，用states整型数组保存状态信息。transitions数组用三个位置保存一个转换信息，依次是toState、min、max，这样三个一组三个一组，依次保存每一个转换的信息。你可能会好奇，为什么没有保存源状态信息，这就要说到states数组。states数组是两个一组，作为一个状态的信息，第一个位置表示该状态上的转移在transitions数组中的下标，第二个位置表示在该状态上的转移边的数量。这就容易理解了，假设我要知道状态i(假设从0开始)的第j个转移,那么直接访问transitions[states[i*2] + j*3]就可以了。

除此之外，我们还需要一个step函数，用于一步一步执行自动机，源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/**
 * Performs lookup in transitions, assuming determinism.
 * 
 * @param state starting state
 * @param label codepoint to look up
 * @return destination state, -1 if no matching outgoing transition
 */
public int step(int state, int label) {
  assert state >= 0;
  assert label >= 0;
  int trans = states[2*state];
  int limit = trans + 3*states[2*state+1];
  // TODO: we could do bin search; transitions are sorted
  while (trans < limit) {
    int dest = transitions[trans];
    int min = transitions[trans+1];
    int max = transitions[trans+2];
    if (min <= label && label <= max) {
      return dest;
    }
    trans += 3;
  }

  return -1;
}

可以看到，基本逻辑就是根据输入的label，判断label在不在该状态的Transition的min和max之间，在的话，就可以跳到该Transition的dest状态。

其实到这里，这个自动机已经可以跑了，如果你想用于字符串匹配，那么就根据字符串长度构造出相等数量的状态，再根据字符串中的每个字符，添加Transition，初始化好states和transiitons数组，匹配的时候通过step函数一步一步执行即可。Solr中还考虑了很多细节，不再展开叙述。

Solr中自动机的快速执行

由于Solr对于查询的匹配，需要从索引文件中读出很多Term在自动机上进行匹配，所以能够快速执行自动机匹配能够有效降低结果返回的延迟。基本的思想还是用空间换时间。Solr中把每个Automaton类转换成RunAutomaton类，从而快速执行，看一下RunAutomaton类中的变量，就可以了解其实现方式：

1
2
3

final int[] transitions; 
final int[] points; // char interval start points
final int[] classmap; // map from char number to class class

先说一下这个points整型数组的作用，用于保存自动机的所有转换边上的输入，即所有转换边上输入字符的CodePoint，并且是从小到大排序好的。这里的transitions数组不同于Automaton类中的Transition数组，这里的transitions数组看似是一个一维数组，实则是当二维数组来用的，用于保存自动机上的状态经过points数组中保存的输入字符的转换能够到达的状态。如果说状态数是n，那么transitions数组的长度就是n * points.length。如果不存在该输入字符的转换，那么transitions数组上对应位置的元素是-1。可以看到，这样用一个很大的数组保存所有的转换，具有很大的冗余。不过优势在于，只需要生成一次RunAutomaton实例，就可以重复使用。

现在假设我们在状态i，输入字符c，想要知道下一个状态。那么首先需要从points数组中找出字符c对应的CodePoint在points数组中的下标j，那么transitions[i*points.length + j]即代表下一个状态。现在已经很快了，不过还有一个不足的地方，倘若points数组很大，从头到尾遍历需要很长的时间，一种方式是采用二分查找（因为是排好序的，不过Solr并未采用），另一种方式是更极端的用空间换时间，启用classmap整型数组。classmap数组保存的是某个输入字符的CodePoint在points数组中的下标，也就是说，比如输入字符c，其对应的CodePoint是d，那么points[classmap[d]] = d。现在只需要直接访问transitiosn[i*points.length + classmap[d]]就可以知道下一个状态了。