背景与相关资料

还是继续阅读Luence的Codec的部分，在分析tim、tip、tmd相关文件的生成逻辑的过程中，我们需首先理解倒排索引字典构建的一些基本知识。我们在此前的文章中我们讨论了Burst Tries的相关的原理，我们还需要补充一下关于FST（Finite State Transducers）的相关知识才能更好的理解的codec部分的内容。

搜罗了一下网络上的资料并且结合luenece-9.0.0的代码实现，梳理这部分的实现和自己的一些理解，

先罗列一些很棒的网络上的资料，通过这些资料，可以非常好的理解FST的数据结构特点和Luence的实现原理。

• 关于FST高效序列化的论证过程的论文：

Sheng_Yu_Implementation_and_Application_of_Auto-with-cover-page-v2.pdf

• 一片讲述FST的由来和构建过程的很棒的博客

www.shenyanchao.cn/blog/2018/1…

• 解析luenece的实现逻辑，并包含了序列化和反序列化的方案

www.amazingkoala.com.cn/Lucene/yasu…

www.amazingkoala.com.cn/Lucene/yasu…

FST结构特性和构建过程

首先我们需要理解FST是一种什么样的结构，以及适配于什么样的场景？

FST，可以理解为一种KV结构，一般结构不同的是，FST会最小化Key的占用空间，类似于Tries但是不止会共享前缀也会共享后缀，因此可以支持一些kv之外的匹配功能。在构造和序列化的过程中需要保证key是按照顺序构造的。

比如我们有如下的kv数据结构：假如我们需要将其构成一个FST的数据结构其最终展示形态大概如下所示：

a:100
ab:91
abc:72
dec:88
dfc:99

在lucene的实现中，最后会将整个map序列化到一种FSTStore的数据结构中，可以简单的理解他们为一个byte[]数组。以byte[]的形式去看这个FST的结果中，会最终生成如下的序列化结果，稍后我们会详细的描述这个图的构造过程和下面的序列化结果的写入和读取方式。

图的构造过程

首先FST的一些基本概念可以通过这篇文章来理解，这里我们只总结一些基本的概念，并且将重点放到lucene的实现方式上：

首先我们都知道，FST描述的是状态流转过程，节点不带有具体信息，使用边来标识具体的label和output。比如我们现在将第一个输入a=100放入FST中，就得到了一个最初的FST状态

在lucene的实现中将output分成了2种，一种为普通的output，可以理解为这种output是位于主路径上的，他的数值是由所有的后续节点所共享的。

另一种可以称为nextFinalOutput，这种output可以理解为只针对当前节点生效，对后续节点并不生效。

为什么需要区分这2种情况呢？我的理解是为了解决我们例子中的第二个输入的产生的问题，比如我们现在需要输入ab:91。这时候会发现a的长度小于ab的，但是out值是大于ab的。为了解决这个问题，lucene将a:100拆分成output=91和nextFinalOutput=9，2个部分，而b的output和nextFinalOutput分别等于0。这样我们就获得到了第二种input输入之后的FST如下所示：

然后我们继续看如果有第三个值abc=72输入呢？这时候我们发现同样的情况出现了。我们需要继续对a和b的output进行拆分；这三个output的common的值是72，而100(a.output)-72=28，91(b.output)-72-19，这样我们就很容易获得到了一种更合理的分配方式，从而获得到了第三个FST图

接下来我们开始尝试新的输入def:88，这时候我们发现abc的所属链路和def并没有什么相同的前缀，所以我们需要开一个新的链路。因此我们将(d,88,0)->(e,0,0)->(c,0,0)放入FST中，很显然5-S节点和3-S节点并没有什么区别 ，按照FST的后缀合并的原则，我们将使用3节点替换掉5节点。

为了实现这部分功能，很显然我们需要一种数据结构去识别到相同的节点，这里也是一个有意思地方。在后续的章节中再讨论。

另外由于输入是有序的，所以既然已经没有与abc共同前缀的输入，这说明我们可以将abc的的节点冻结掉，已经冻结的节点不会再改变因此这部分数据可以进入序列化的流程，采用红色标注。

最后，我们将dfc:99放入节点，类比之前的逻辑，我们知道，可以公用4节点和3节点，我们可以获取到如下的FST，这时候我们知道所有的节点都已经输入完毕，我们可以将全部节点冻结，并序列化掉。

序列化的写与读

序列化的过程可以视为将一个图转换为byte[]数组的过程，为了实现这一点，首先我们需要考虑重数据中恢复一个图需要一些什么东西？以及整体的操作流程是什么样的。

首先我们考虑我们需要序列化的到底是什么，因为FST的节点实际上附带任何信息，因此虽然我们是以节点的粒度去序列化，但实际上我们序列化的是节点所对应的边，而边的信息包括label、output，因此这2点一定会被序列化的。一个比较重要的信息是当前边的target是否是终止节点，这不仅仅标识一个term的终止也会指导我们如何寻找下一个label的位置。

首先我们考虑整体序列化的的顺序如何确定？上一小节曾经说到，当前一个节点被冻结之后就不会再改变了。这种情况下我们可以对数据进行序列化，因此我们可以理解为被冻结的节点可以开始序列化的过程，在实现上lucene采用从终止节点向起始节逐个序列化的顺序进行序列化。lucene采用一个lastFrozenNode的概念去记录上一个序列化的节点。

由于是描述图的场景因此一定存在已被序列化的节点在会被重新引用的情况，比如在后缀合并的场景，这时候我们还需要一些map结构来找到这些已经被序列化的点，同时记录他们在序列化场景下的idx位置。因此在某些情况下我们还需要记录next场景的

其次的问题是需要考虑如何区分出不同边的类型，在lucene中使用下面的一些flag来区分不同的边，具体的说：

	flag
BIT_FINAL_ARC	1	当前边所对应的label是一个term的最后一一个字母。
BIT_LAST_ARC	2	当前边是所对应节点的最后一个边。
BIT_TARGET_NEXT	4	这个边实际上用来指示下一个label是通过按bytes数组的顺序读取下一个节点，还是通过读取idx的值来读取下一个节点。也就是当前边的target和lastFrozenNode的值是不是相同的
BIT_STOP_NODE	8	当前边的target是否是终止节点。
BIT_ARC_HAS_OUTPUT	16	当前边是否包含有output。对应output
BIT_ARC_HAS_FINAL_OUTPUT	32	当前的边是否包含有仅仅针对于当前节点生效的output。对应nextFinalOutput

综上所述，一个节点需要序列化的内容其实主要包括以下一些内容：

• 当前节点的：label
• 当前节点的：output和nextFinalOutput
• 当前节点的类型：flag信息
• 如何读取下一个边或者节点：flag信息+index

单纯从含义和逻辑出发还是太过抽象了，我们还是通过一个具体的例子来说明问题更好，更详细的完备的逻辑推理需要读者自己去看代码实现或者阅读下相关论述的论文了。

写入和读取的例子

• 写入a：100

这时写入a:100，此时并没有节点被冻结，但是为了避免一些term为空字符之类的特殊场景bytes数组里面永远会写入一个0到idx=0的位置。

• 写入ab：91

此时，同样没有节点被冻结，但是1节点和2节点的output发生了变化

• 写入abc：72

此时，同样没有节点被序列化，但是节点1，2，3的output发生了变化

• 写入dec：88

此时，我们发现已经没有a->b->c链路上的数据，因此我们可以按顺序将S->3->2节点进行序列化。

首先针对终止节点S，由于其没有任何output，因此其不会在bytes上写入和数据，但是会更新lastFrozenNode的值为-1，用于标识终止节点已经被序列化掉。

其次针对节点3，首先label=c（99），output和nextFinalOutput=0都是很清晰的，主要的问题在flag上，其值应该是BIT_FINAL_ARC（1，是abc的最后一个label）+BIT_LAST_ARC（2，是节点3的最后一个边）+BIT_TARGET_NEXT（4，target的值==lastFrozenNode==-1）+BIT_STOP_NODE（是终止节点）=15。因此按照顺序我们写入图中黄色的部分。同时需要更新lastFrozenNode为2

最后针对节点2，首先label=b（98），output=0，nextFinalOutput=19，而flag的值，BIT_FINAL_ARC（1，是ab的最后一个label）+BIT_LAST_ARC（2，是节点2的最后一个边）+BIT_TARGET_NEXT（4，target的值==lastFrozenNode==2，不需要走idx）+BIT_ARC_HAS_FINAL_OUTPUT（32，包含有nextFinalOutput的值）=39，因此我们按顺序写入图中粉红色的部分。

可能有同学有疑问为什么边a不会被序列化？其实这道理就是此前提到的，我们序列化的是以节点为维度，但是写入的数据实际上是边的数据，在当前节点1并没有被序列化，因此边a并不会被序列化，其实理解的FST的原理后就很好理解，首节点的序列化过程一定是放到最后的，也就当输入都结束之后才进行序列化操作。

• 写入dfc：99

当前节点写入后，节点4新增一个边，label=f，output-11，target是已经被序列化的节点3，序列化层面没有任何变动

• compile阶段

这个节点我们所有的输入都结束之后，最后会执行compile阶段，会将所有的节点都序列化掉。

首先我们需要从4节点开始序列化，

1. 序列化4-f的边

label=(f,102)，output=11，nextFinalOutput=0，flag= BIT_LAST_ARC（2，是节点4的最后一个边）+BIT_ARC_HAS_OUTPUT（16，包含output的值）=18。因为没有BIT_TARGET_NEXT的标识（因为 lastFrozenNode的值是边2-b，而当前边的target是3），所以需要通过一个index的值来找到下一个label的值，所以我们还需写入一个index=2的值，用来标识下一个label的flag值的位置。如图中紫色的部分。

1. 序列化4-e的边

label=(e,101)，output=nextFinalOutput=0，flag=0。同样没有因为没有BIT_TARGET_NEXT的标识（因为 lastFrozenNode的值是边4-f，而当前边的target是3），所以我们还需写入一个index=2的值，用来标识下一个label的flag值的位置。如图中蓝色的部分。

1. 序列化1-d的边

label=(d,100)，output=88，nextFinalOutput=0，flag= BIT_LAST_ARC（2，是节点1的最后一个边）+BIT_TARGET_NEXT（4，当前taget的是上一个序列化的节点4）+BIT_ARC_HAS_OUTPUT（16，包含output的值）=22。如图中绿色的部分。

1. 序列化1-a的边

label=(a,97)，output=72，nextFinalOutput=28，flag= BIT_FINAL_ARC（1，是term=a的最后一个label）+BIT_ARC_HAS_OUTPUT（16，包含output的值）+BIT_ARC_HAS_FINAL_OUTPUT（32，包含有nextFinalOutput的值）=49。同样没有因为没有BIT_TARGET_NEXT的标识（因为 lastFrozenNode的值是边1-d，而当前边的target是2）所以需要通过一个index的值来找到下一个label的值，所以我们还需写入一个index=5的值，用来标识下一个label=b的flag值的位置。如图中红色的部分。

至此，我们整体的序列化动作完整。读取的过程是相反的，这里就不讨论了，有兴趣的可以去看下代码。

如何判断重复节点

这部分代码其实没有仔细阅读，后续有时间的话我再想办法补充下这里的内容，仅仅从思路上简单梳理一下。

首先，对于一个未冻结的节点，我们想要计算其hash值是非常困难的，lucene在这方面我理解是没有什么黑科技的，但是反过来想我们真的需要计算未冻结的节点的hash，其实我们在构造FST的过程中并不需要知道节点是不是有后缀部分可以重复利用，我们只需要在compile节点的时候再去判断就行，lucene在实现中也是这样的。如果当前的节点没有被序列化，我们只要将其进行序列化即可。

我们只需要维护一个类似hash的结构将一个节点所有的边包含的信息进行hash后放入一个table里面在必要的时候进行扩缩容之类即可。所以虽然看起来是个复杂的问题，但是只要想清楚我们只针对冻结后的节点进行hash很多事情就容易了很多。

结语

其实luceneFST这里还有很多有意思的部分，后续有时间还可以逐步学习和研究。

• 如何判断重复节点
• 一些新的特性：Binary search和prune特性
• 比如一些output的类型和作用
• 一些corner case：例如如何处理term为空的input，如何处理相同term的重复输入output的merge
• 比如一些超大的字典的FSTStore实现等等