7、Lucene中FST的源码实现
7.1 FST中重要的存储对象及参数
本节我们通过源码来分析一下Lucene是如何把Term Dictionary构建为FST并且保存在BytesStore对象里的。之前我们提过，Lucene在使用Builder构建FST的过程中，创建了以下几个类型或对象：
UnCompiledNode：保存挂起的节点，尚未serialized的节点。
CompiledNode：当Node的出度信息完全写入到BytesStore/current数组之后，Node会从frontier中摘下，状态变为CompiledNode。例如在图6-1的时候，输入term:abd，此时生成了四个UnCompiledNode对象以及三个Arc对象，其代码定义如下：
public static final class UnCompiledNode<T> implements Node { final Builder<T> owner; public int numArcs; public Arc<T>[] arcs; // TODO: instead of recording isFinal/output on the // node, maybe we should use -1 arc to mean "end" (like // we do when reading the FST). Would simplify much // code here... public T output; public boolean isFinal; public long inputCount; /** This node's depth, starting from the automaton root. */ public final int depth; ... }
由此我们可以看出，每个UnCompiledNode包含若干个Arc，并且用output表示点解节点的输出值，isFinal表示当前是否是终止节点。
public static final class Arc<T> { private int label; private T output; private long target; private byte flags; private T nextFinalOutput; private long nextArc; // 节点标头标志。仅有意义的是检查值是否为 FST.ARCS_FOR_BINARY_SEARCH或FST.ARCS_FOR_DIRECT_ADDRESSING （bytesPerArc == 0时的其他值）。 private byte nodeFlags; // 如果此Arc是具有固定长度出度的节点的一部分，则为非零值，这意味着该节点的所有Arc均以固定数量的字节编码，以便我们进行二进制搜索或直接地址。当有足够多的出度边离开一个节点时，我们会做。它浪费一些字节，但是提供了更快的查找。 private int bytesPerArc; // 数组中第一个出度边的起始位置；仅在bytesPerArc！= 0时有效 private long posArcsStart; private int arcIdx; // 多少Arc；仅当bytesPerArc！= 0（固定长度Arc）时才有效。对于设计用于二进制搜索的节点，这是阵列大小。对于设计用于直接寻址的节点，这是标签范围。 private int numArcs; private long bitTableStart; private int firstLabel; private int presenceIndex; ... }
UnCompiledNode[] frontier：用来存放UnCompiledNode，待处理的节点Arc
BytesStore bytes（current[]）：存储CompiledNode出度Arc的二进制数组对象。
Arc：描述FST构建的重要类型，其中我们要着重理解的包括label、output、target和flags四个属性，其他属性我这里都已经做了详细的中文注释，这里我们来把刚才说的四个属性重点讲解一下。
label：描述当前输入词项中的一个字符，FST最终存储的是label对应字符的ASCLL的二进制。
output：存储Arc对象的附加值或者叫做输出值，output和finalOutput都属于output。
target：如果当前的祖父不是输入值的最后一个字符，target会存储当前字符的下一个字符在current数组中的flag值在current数组中的index即索引值。
flags：通用最小化算法要求任何对数据的压缩都要可以逆向运算，即数据可编码解码，因此在对于FST进行压缩的时候，flags的作用是以最小的代价标记若干个状态值，这里采用了一种位移算法，以实现其通用最小化的目的。
这里label和output都很容易理解，但是target和flags相对难以理解。target的含义我们在FST的写入过程中给大家做详细介绍，但是这flags的含义我们有必要在这里展开来详细的讲解一下。
lastFrozenNode：当节点从frontier[]数组中摘下来的时候，节点和它包含的Arcs信息会被写入到current[]数组中，lastFrozenNode会记录当前被处理的节点的第一个Arc在current数组中的起始坐标，即flag的坐标。如果当前节点是终止节点，因为终止节点没有出度Arc，因此lastFrozenNode会输出-1。当lastFrozenNode的值和当前处理的Arc指向的target node在current数组的起始坐标不相同并且当前处理的Arc的target node不是Stop node（因为没有出度Arc）的时候，也就意味着最终构建的FST对象存储的current[]数组在读取的时候，当前Arc对应的label在数组中的下一个Arc不是当前term的下一个label，就需要记录当前Arc的下一个Arc在current数组中的坐标，此时flag就不会标记BIT_TARGET_NEXT值。这段描述需要读者多加揣摩和理解。
首先我们先看一下flags在Lucene-FST中的使用场景：
long addNode(Builder<T> builder, Builder.UnCompiledNode<T> nodeIn) throws IOException { ... for(int arcIdx=0; arcIdx < nodeIn.numArcs; arcIdx++) { final Builder.Arc<T> arc = nodeIn.arcs[arcIdx]; final Builder.CompiledNode target = (Builder.CompiledNode) arc.target; int flags = 0; //当前的arc是当前节点的最后一个出度 if (arcIdx == lastArc) { flags += BIT_LAST_ARC; } //下一个节点就是目标节点，也就是下一条arc对应的节点 if (builder.lastFrozenNode == target.node && !doFixedLengthArcs) { flags += BIT_TARGET_NEXT; } //当前arc是当前输入term的最后一个字符 if (arc.isFinal) { flags += BIT_FINAL_ARC; //如果有finalOutPut值 前提当前arc是term的最后一个arc if (arc.nextFinalOutput != NO_OUTPUT) { flags += BIT_ARC_HAS_FINAL_OUTPUT; } } else { assert arc.nextFinalOutput == NO_OUTPUT; } boolean targetHasArcs = target.node > 0; //arc对应的node是一个终止节点 if (!targetHasArcs) { flags += BIT_STOP_NODE; } //当前arc对应节点有output值 if (arc.output != NO_OUTPUT) { flags += BIT_ARC_HAS_OUTPUT; } ... }
我上面已经提过，flags是用来记录状态值的，但是这里不难发现，flags符合某种状态条件的时候，使用了”+=“这种操作，难道状态也可以累加吗？没错，的确可以，那到底是如何做到呢？我们先看一下flags累加的这几种状态的定义：
public final class FST<T> implements Accountable { ... // arc对应的label是某个term的最后一个字符 private static final int BIT_FINAL_ARC = 1 << 0; // arc是Node节点中的最后一个Arc，一个UnCompiledNode状态的Node可以包含多个arc static final int BIT_LAST_ARC = 1 << 1; // 当前Arc的Target节点就是上一个处理的节点 或者理解为 // 存储FST的二进制数组中紧邻的下一个字符区间数据是不是当前字符的下一个字符 static final int BIT_TARGET_NEXT = 1 << 2; // TODO: we can free up a bit if we can nuke this: // arc的target是一个终止节点 private static final int BIT_STOP_NODE = 1 << 3; /** This flag is set if the arc has an output. */ // arc有Output value public static final int BIT_ARC_HAS_OUTPUT = 1 << 4; // arc有Final Output value private static final int BIT_ARC_HAS_FINAL_OUTPUT = 1 << 5; ... }
在源码中我们可以清楚的看到，flags的累加值一共有六种，分别是1 << 0、1 << 1、1 << 2、1 << 3、1 << 4、1 << 5。<<代表位移方向，后面数字代表位移的bit数。比如1<<1代表十进制1转换二进制之后每个bit位左移一个bit位。Lucene-FST中的flags使用了一个Byte来存储，1的二进制就是0 0 0 0 0 0 0 1，左移一位就是0 0 0 0 0 0 1 0，十进制就是2，以此方式计算，flags做＋=运算的结果，有且仅有一种flags的组合，也就达到了以最小代价存储多个状态信息的目的。当前六个flags的值和其所对应的状态含义如下表：
到这里，几个Lucene中构建FST的几个重要的对象都已经做了响应的介绍，下面来详细介绍一下构建的具体过程。
首先创建Builder对象，BytesStore bytes，并写入一个0，用来标记FST的结束（读取的时候是反向的）。同时初始化一个长度为10的UnCompiledNode[] frontier。Builder对象会在每次输入的时候，调用add(IntsRef input, T output)方法，其主要包含四个步骤：
计算当前输入term与上一个term的公共前缀，公共前缀最终指向的节点暂且叫做公共节点。
调用freezeTail方法，从尾部开始到公共节点为止，冻结所有已经确定状态的节点，UnCompiledNode状态变为CompiledNode。将已冻结节点的出度和节点信息写入BytesStore或者current[]中，最后更新lastFrozenNode。
将当前输入写入frontier[]数组中，把对应信息写入Arc对象，Node的状态为UnCompiledNode。
调整当前输入对应Arc的output值。
7.2 FST源码实现
我们以[ab/9 abd/15 abgl/6 acd/2 msbc/21 mst/66 wl/99]为例，结合Lucene源码来演示一下FST的存储过程。
1：首先输入term:ab
此时由于ab为第一个term，未发生任何节点冻结，因此开始执行第二个term输入，如上图7-2所示
2：因此开始执行第二个 term:abd 的输入
此时公共前缀为“ab”，虽然node a和node b都是终止节点，但是无法确定其是否会发生改变（即新增出度或者target节点，因为还有可能会有以ab或者abd为前缀的term调add添加进来），所以未发生freezeTail。终止节点没有出度，即不包含Arc，返回-1，lastFrozenNode=-1）。将节点arc：d对应节点node d写入frontier数组中。15（9+6）>9，取公共部分9 => 最小法则 目的是生成最小化FST，这个也是遵循数据结构的通用最小化算法法则。
3：输入term:abgl，如图7-4所示：
公共前缀：term:ab，freezeTail：arc:d=>node d(终止节点，不会发生改变了，lastFrozenNode=-1)，同样，node b和node l 都无法确定是否还会有变化，即无法确定后面是否还有以ab或abgl为前缀的term，将arc g、arc l对应节点node g和node l 写入frontier数组中，15（9+6）>9，取公共部分9 => 最小靠前法则 目的是生成最小化FST，这个也是遵循数据结构的通用最小化算法法则。
此时Arc-d并未马上写入current[]的bytes对象中，因为出度d的target虽然是node d但它是node b的出度，只有当node b被冻结的时候，node b的所有出度才会被写入字节数组。换句话说，判断一个Arc写入current字节数组的时机，就是出度对应的node的所有（最后一个）出度确定的时候。
4：输入term:acd，如图7-5：
此时公共前缀为’a’，调用freezeTail冻结了Step 3中的node b、node d、node g、node l，出度分别是Arc-d Arc-g Arc-l，要注意这里的Arc-b必须要在node a的最后一个出度确定之后才能处理，显然这里不能确定Arc-c就是node a的最后一个出度，因为只要还有以’a’开头的term，node a就可能还有新的出度。将节点Arc：d对应节点node d写入frontier数组中。最后更新output，逻辑同上。
处理顺序：节点从后往前，Stop Node => node g（arc：l）=> node b（arc：d、g）
1：处理Stop node：
返回 lastFrozenNode = -1
2：处理node g：
处理Arc l： BIT_FINAL_ARC：1 l是abgl的最后一个字符 BIT_LAST_ARC：2 l是node g的最后一个出度 BIT_TARGET_NEXT：4 l指向的node是Stop Node，而lastFrozenNode是Stop Node输出的 BIT_STOP_NODE：8 l的target是一个Stop Node flags = 15
Current[] 如下表所示：
3：处理node b
处理Arc g BIT_LAST_ARC：2 g是node b的最后一个出度 BIT_TARGET_NEXT：4 g的targetNode即node g即，当前lastFrozenNode是由处理node g后更新的，值为-1 BIT_ARC_HAS_OUTPUT: 16 g有output值 flags = 15 处理Arc d BIT_FINAL_ARC：1 d是abd的最后一个字符 BIT_STOP_NODE：8 d的target是一个Stop Node BIT_ARC_HAS_OUTPUT: 16 d有output值 注意，由于Arc d指向终止节点，而此时lastFrozenNode由node g产生，因此BIT_TARGET_NEXT=0。flags = 25
上图7-7为将node n的Arcs信息写入current[]数组后的结果，此时node b的其实位置为Arc d的起始位置，即d的flag坐标：8，因此lastFrozenNode此时会被更新为8，即：lastFrozenNode = 8。
这里需要注意，我在描述lastFrozenNode的概念的时候说过，当前处理的Arc d指向的节点在current数组中的起始位置和astFrozenNode的值不相同的时候并且Arc d指向的节点不是Stop node的时候，需要记录当前Arc的下一个Arc（按照label在term中的顺序）在current数组中的坐标：target index，但是当前处理的Arc d指向的节点是Stop node，因此也就不必记录target index。
5：输入term:msbc，如图7-8：
此时，Entry节点产生了第二个出度，调用freezeTail方法冻结了Step 4中的node a、node c（这里指的是图中蓝色的node c）、node d，出度分别是Arc-c Arc-d，要注意这里的Arc-c可以确定是node a的最后一个出度，所以node a后面的所有Arc将开始处理。同样m无法确定是entry的最后一个出度，所以 Arc a不能处理。图中红色的出度标示之前已经被处理。
处理顺序：节点从后往前，Stop Node => node c（arc：d）=> node a（arc：b、c）
1：处理Stop node：返回 lastFrozenNode = -1
2：处理node c：
处理Arc d BIT_FINAL_ARC：1 d是acd的最后一个字符 BIT_LAST_ARC：2 d是node c的最后一个出度 BIT_TARGET_NEXT：4 此时的lastFrozenNode由Stop node产生，而Arc d指向的即Stop node BIT_STOP_NODE：8 d的target是一个Stop Node flags = 15 将node c的Arcs信息写入current[]数组后如下图7-9所示：
3.处理node a
处理Arc c BIT_LAST_ARC：2 c是node a的最后一个出度 BIT_TARGET_NEXT：4 c指向的node是Stop node，值都是-1 flags = 6 处理Arc b BIT_FINAL_ARC：1 b是ab的最后一个字符 BIT_STOP_NODE：8 b的target是一个Stop Node BIT_ARC_HAS_FINAL_OUTPUT: 32 b有final output值
注意：当前的lastFrozenNode是node c产生的，b指向的node b而非node c，并且node b不是Stop node，此时需要记录Arc b的target index值，即node的第一个出度在current[]数组中的起始位置，即：
8，最终结果如下图7-10所示：
6.输入term:mst，如图7-11：
此时，公共前缀为"ms"，调用freezeTail方法冻结了Step 5中的node b2和node c，此时node s的出度Arc b并不会写入current，因为node s的尚未确定所有出度，但是nodeb2后面的出度是可以写入字节数组的，因为node b2的所有出度都已经确认了
处理顺序：节点从后往前，Stop Node => node b2（arc：c）
1：处理Stop node：
返回 lastFrozenNode = -1
2：处理node b2：
处理Arc c BIT_FINAL_ARC: 1 c是msbc的最后一个字符 BIT_LAST_ARC：2 c是node b2的最后一个出度 BIT_TARGET_NEXT：4 同上 BIT_STOP_NODE: 8 c指向的是终止节点 flags = 15
处理完成之后current[]如下图：
7.输入term:wl，如下图7-13：
此时，公共前缀为：ms，调用freezeTail方法冻结了Step 6中的node s和node m。
处理顺序：节点从后往前，Stop Node => node s（arc：b、t）=> node m（arc：s）
1：处理Stop node：
返回 lastFrozenNode = -1
2：处理node s：
处理Arc t BIT_FINAL_ARC：1 t是mst的最后一个字符 BIT_LAST_ARC：2 t是node b的最后一个出度 BIT_TARGET_NEXT：4 同上 BIT_STOP_NODE：8 t指向的是终止节点 BIT_ARC_HAS_OUTPUT：16 t有output flags = 31 处理Arc b flags = 0 此时，lastFrozenNode是由Stop node产生的，Arc b的target node不是Stop node，此时记录Arc b的target index，即node b2的第一个出度Arc c的flag在current数组中坐标，即：index = 18
3：处理node m：
处理Arc s BIT_LAST_ARC：2 s是node m的最后一个出度 BIT_TARGET_NEXT：4 同上 flags = 6
处理完成之后current[]如下图7-14：
因为term:wl是Term Dictionary中的最后一个term，所以此时node w和在frontier中的node s（图7-13中红色node s）以及Entry node也都可以确定不会再有新的出度产生，因此会被冻结，即如图7-15所示：
处理顺序：节点从后往前，Stop Node => node w（arc：l）=> Entry node（arc：w、m、a）
1：处理Stop node：
返回 lastFrozenNode = -1
2：处理node w：
处理Arc l BIT_FINAL_ARC：1 l是wl的最后一个字符 BIT_LAST_ARC：2 l是node w的最后一个出度 BIT_TARGET_NEXT：4 同上 BIT_STOP_NODE：8 l指向的节点是Stop node flags = 15 此时lastFrozenNode = 28
3：处理Entry node
处理Arc w BIT_LAST_ARC：2 w是Entry node的最后一个出度 BIT_TARGET_NEXT：4 同上 BIT_ARC_HAS_OUTPUT: 16 w有output值 flags = 22 处理Arc m BIT_TARGET_NEXT：4 同上 BIT_ARC_HAS_OUTPUT: 16 w有output值 flags = 20 lastFrozenNode此时的值由node w产生，m的target node是node m，第一个出度为Arc s，因此记录target index：26 处理Arc a BIT_ARC_HAS_OUTPUT: 16 a有output值 flags =16 lastFrozenNode此时的值由node w产生，m的target node是node a，第一个出度为Arc b，因此记录target index：16
处理完成之后current[]如下图7-16：
此时完整的FST对象已经构建完毕并写入current[]数组，图中展示的为十进制数字是为了方便读者理解，实际存储的完全为二进制。
7.3 FST的逆向解码过程
下面是如何从current中读取完整的Term Dictionary：
读取操作是从后往前的，即：
- 从index:39开始，此时key = ‘a’，当读到index : 36，此时target index指向16，index : 16的位置存储的label为’b’，此时key = “ab”，final output = 7即可判断当前为终止节点，这里就不用计算flags了，即此时读取到term:ab，此时Term Dictionary中包含一个term:ab，value = 2+7，即：term:ab/9。
- 由于index : 16中index指向index : 8，此时key = abd，flags = 27，27有唯一的flag组合：16 + 8 + 2 + 1，即BIT_ARC_HAS_OUTPUT、BIT_STOP_NODE、BIT_LAST_ARC、BIT_FINAL_ARC的组合，由BIT_STOP_NODE可得当前是终止节点，所以此时读取到term:abd，value = 2 + 13 = 15 ，即：term:abd/15。此时Term Dictionary中包含两个元素：term:ab/9、term:abd/15。
- 由于index : 8的Arc d没有target index，因此继续沿着数组往下读，即读取index : 5，即Arc g，通过前面的flags值计算可得此时key = “abg”， Arc g仍然没有target index，因此继续读取index : 2，同理可得此时key = “abgl”，继续读或者通过flags都可以判断当前是一个终止节点，所以此时得到term:abgl，value = 2 + 4 = 6，即term:abgl/6。此时Term Dictionary中包含三个元素：term:ab/9、term:abd/15、term:abgl/6。
- 此时node a的第一个出度Arc b已经遍历完毕，即index : 16后面的数据已经读取完毕，此时读取’b’在current数组中的顺序数据，即index : 12，原理同上，读至index : 10，由flags可得当前为终止节点，此时得到term:acd/2。此时Term Dictionary中包含四个元素：term:ab/9、term:abd/15、term:abgl/6、term:acd/2。
- 此时Entry的第一个出度Arc a的所有信息都已经遍历完成，即index : 39的target index后面的数据以及读取完毕，按照current数组顺序读取至index : 35，根据其target index : 26读取到Arc s，顺序读至index : 24，根据其target index读至index : 18，再根据当前Arc c的flag的到term:msbc，value = 21。即：term:msbc/21。此时Term Dictionary中包含五个元素：term:ab/9、term:abd/15、term:abgl/6、term:acd/2、term:msbc/21。
- 此时node s的第一个出度Arc b遍历完毕，沿着Arc b顺序读取至index : 21，计算flags可得当前节点为Stop node，即得到term:mst，value = 21 + 45 = 66，即term:mst/66。此时Term Dictionary中包含六个元素：term:ab/9、term:abd/15、term:abgl/6、term:acd/2、term:msbc/21、term:mst/66。
- 此时Entry的第二个出度Arc m的所有信息已经读取完毕，沿着index : 35继续往后顺序读取，读取index : 31，然后顺序读取至index : 28，通过计算flags可得当前节点为终止节点，即得到term:wl，value = 99，即term:wl/99，此时Term Dictionary中包含七个元素：term:ab/9、term:abd/15、term:abgl/6、term:acd/2、term:msbc/21、term:mst/66、term:wl/99。
至此，已经完成了对current[]数组的数据读取并还原了Term Dictionary的数据。
