咱们现在有这样一组 字典排序 的分词：

Term Value
ab 9
abd 15
abgl 6
acd 2
msbc 21
mst 66
wl 99

咱们暂时忽略Value的出处，仅单纯考虑Term和Value的关系即可。

基本结构

一个FST基本由两个要素组成：

  1. 节点，Node。Node 分为两类：
    1. uncompiledNode，“未编译”的Node，理解为“未处理的”即可
    2. compiledNode，“已编译”的Node，理解未“已处理的”即可
  2. 出度，Arc。这个类常用的属性有四个：
    1. label，保存出路的Key值，通常是Term里的一个字符。但是存储是用二进制存储的（ACSII码或者其他以数字形式存储的方式）
    2. output，Key值对应的SubValue。注意，这里特地使用SubValue，主要是为了说明Arc.output是针对label的Value，并不是Term的Value。比如说：ab一个Term的Value为9，但是在Arc:a中，它的SubValue为3、Arc:b中，它的SubValue为6，两个字符之和为Term:ab的Value。
    3. target，保存出路指向的节点，即Node。
    4. flag，保存了这条出路的一些属性。比如，这个出路是不是最后一个出路？这个出路指向的节点是不是终止节点？等等。

此外FST是一个最终落盘的结构，在构造FST之前，会由一个包含BytesStore current和UncompiledNode[] frontier两个属性的类——Builder来代替处理。所以后续的逐步分析，都是基于落盘是，FST结构的变化：

UncompiledNode存于frontier中；CompiledNode存于current。存入current中后，这个节点就算是“冻结”了。

逐步分析

在一个步骤中，新增的Node用红色来表示；已存在的Node用蓝色来表示；粗线框表示这个Node是终点Node，象征一个词的结束；蓝色线框表示这个Node已经被处理了，进入了current中。

Step1：输入ab

点击查看【processon】
我们注意几个点：

  1. Entry是一个空的点，主要用来标记开始。
  2. 出路a 属于 Entry 节点的，换句话说：Entry节点的出路是a
  3. 因为Term:ab的Value为9，所以在arc:a上指示了当前出路的Output Value。
  4. 因为此时无法判断ab这个前缀是否已经结束，所以不会执行“尾部冻结”。也就是不会处理，并放到current中

Step2：输入abd

点击查看【processon】

  1. 新增了一个节点Node:d
  2. 因为此时无法判断abd这个前缀是否已经结束（ab也无法判断），所以不会执行“尾部冻结”。也就是不会处理，并放到current中。
  3. 因为Term:abd的Value为15，所以arc:a + arc:d得等于 15。（这一块属于最小通用算法，害）

Step3：输入abgl

点击查看【processon】

Step4：输入acd

点击查看【processon】
这张图显示了输入acd后的各节点关系，下面将展示如何处理这些节点：
点击查看【processon】

  1. 先处理Stop节点，因为Stop节点的出路为0，所以FST#addNode()直接会返回FINAL_END_NODE，该常量值的数值为 -1，该返回值会被赋值给lastFrozenNode。
  2. 因为Node:g是从后往前数的第一个节点，所以先处理Node:g，即Arc:l的flags属性：
    1. Arc:l是不是某个Term的最后一个字符？是的，是abgl的最后一个字符。BIT_FINAL_ARC: true
    2. Arc:l是不是当前节点的最后一个出度，即Node:g的最后一个出度？是的，Arc:l是最后一个出度。BIT_LAST_ARC: true
    3. Arc:l的Target 与 lastFrozenNode是否相等？是的，Arc:l的Target 就是Stop节点。所以BIT_TARGET_NEXT: true
    4. Arc:l的target是不是终止节点，即Stop节点？是的，Arc:l的Target是Stop节点。所以BIT_STOP_NODE: true。
    5. Arc:l是不是有Output Value？没有。
    6. Arc:l是否有Final Output Value？没有

所以最终，Arc:l的flags属性值为 15。

  1. 其次处理Node:b，因为这是从后往前数第二个新增的节点：
    1. Arc:g是不是某个Term的最后一个字符？不是。
    2. Arc:g是不是当前节点的最后一个出度？即Node:b的最后一个出度？是最后一个出度（Arc:d在Arc:g之前被加入的，所以Arc:g是最后一个出度）
    3. Arc:g的Target 与 lastFrozenNode是否相等？是的，上一个被freeze的节点是Node:g，而Arc:g的Target正好也是Node:g
    4. Arc:g的Target是不是终止节点？不是。
    5. Arc:g是不是有Output Value？是的，它的Output Value = 4
    6. Arc:g是否有Final Output Value？没有。

所以最终，Arc:g的falgs属性值为22。

  1. 最后处理Node:b的另外一个出度——Arc:d：
    1. Arc:d是不是某个Term的最后一个字符？是的，是abd的最后一个字符
    2. Arc:d是不是当前节点的最后一个出度？不是。
    3. Arc:d的Target 与 lastFrozenNode是否相等？不是。（本来BIT_NEXT_TARGET:false，应该在current中生成index属性的，但是因为lastFrozenNode，即Arc:g 就在这个节点的后边，就没必要再生成index属性了）
    4. Arc:d的Target是不是终止节点？是。
    5. Arc:d是不是有Output Value？是的，它的Output Value = 13
    6. Arc:d是否有Final Output Value？没有。

所以最终，Arc:g的falgs属性值为25。
至此，acd的输入造成的尾部冻结就已经结束了。

Step5：输入msbc

点击查看【processon】
这张图展示了各个节点的关系，下面这个图展示了各个节点处理后的结果，处理逻辑跟在后面：
点击查看【processon】

  1. 先处理Stop节点，因为Stop节点的出路为0，所以FST#addNode()直接会返回FINAL_END_NODE，该常量值的数值为 -1，该返回值会被赋值给lastFrozenNode。
  2. 因为在剩下未处理的节点中，node:d在插入顺序中是从后往前数第一个（也就是最后被插入的），所以先计算Arc:d的flags值：
    1. Arc:d是不是某个Term的最后一个字符？是的，是acd的最后一个字符。BIT_FINAL_ARC: true
    2. Arc:d是不是当前节点的最后一个出度，即Node:g的最后一个出度？是的，Arc:d是最后一个出度。BIT_LAST_ARC: true
    3. Arc:d的Target 与 lastFrozenNode是否相等？是的，Arc:d的Target 就是Stop节点。所以BIT_TARGET_NEXT: true
    4. Arc:d的target是不是终止节点，即Stop节点？是的，Arc:d的Target是Stop节点。所以BIT_STOP_NODE: true。
    5. Arc:d是不是有Output Value？没有。
    6. Arc:d是否有Final Output Value？没有

所以Arc:d的flags属性为15。

  1. 随后，要处理Arc:c，计算Arc:c的flags值为：
    1. Arc:c是不是某个Term的最后一个字符？不是。
    2. Arc:c是不是当前节点的最后一个出度，即Node:a的最后一个出度？是的。对于Node:a来说，先插的Arc:b，再插的Arc:c，所以Arc:c是最后一个出度。BIT_LAST_ARC:true
    3. Arc:c的Target 与 lastFrozenNode是否相等？是的，Arc:c的Target 就是Node:c节点，该节点前一步刚被冻结。所以BIT_TARGET_NEXT: true
    4. Arc:c的target是不是终止节点，即Stop节点？不是的，看图说话。
    5. Arc:c是不是有Output Value？没有。
    6. Arc:c是否有Final Output Value？没有

所以Arc:c的flags属性为6

  1. 最后，处理Arc:b，因为这货是最早建立，所以处理要最迟处理：
    1. Arc:b是不是某个Term的最后一个字符？是。
    2. Arc:b是不是当前节点的最后一个出度，即Node:a的最后一个出度？不是。最后一个出度是Arc:c
    3. Arc:b的Target 与 lastFrozenNode是否相等？不是。lastFrozenNode是Node:a
    4. Arc:b的target是不是终止节点，即Stop节点？是的，看图说话。
    5. Arc:b是不是有Output Value？没有。
    6. Arc:b是否有Final Output Value？有。

所以Arc:b的falgs属性为41。

Step6：输入mst

点击查看【processon】
这张图展示了各个节点的关系，下面这个图展示了各个节点处理后的结果，处理逻辑跟在后面：
点击查看【processon】

  1. 先处理Stop节点，因为Stop节点的出路为0，所以FST#addNode()直接会返回FINAL_END_NODE，该常量值的数值为 -1，该返回值会被赋值给lastFrozenNode。
  2. 因为在剩下未处理的节点中，node:b在插入顺序中是从后往前数第一个（也就是最后被插入的），所以先计算Arc:c的flags值：
    1. Arc:c是不是某个Term的最后一个字符？是的，是msbc的最后一个字符。BIT_FINAL_ARC: true
    2. Arc:c是不是当前节点的最后一个出度，即Node:b的最后一个出度？是的，Arc:b是最后一个出度。BIT_LAST_ARC: true
    3. Arc:c的Target 与 lastFrozenNode是否相等？是的，Arc:c的Target 就是Stop节点。所以BIT_TARGET_NEXT: true
    4. Arc:c的target是不是终止节点，即Stop节点？是的，Arc:c的Target是Stop节点。所以BIT_STOP_NODE: true。
    5. Arc:c是不是有Output Value？没有。
    6. Arc:c是否有Final Output Value？没有

所以Arc:d的flags属性为15。

Step7：输入wl

点击查看【processon】

  1. 先处理Stop节点，因为Stop节点的出路为0，所以FST#addNode()直接会返回FINAL_END_NODE，该常量值的数值为 -1，该返回值会被赋值给lastFrozenNode。
  2. 因为在剩下未处理的节点中，node:s在插入顺序中是从后往前数第一个（也就是最后被插入的），所以先计算Arc:t的flags值：
    1. Arc:t是mst的最后一个字符，所以BIT_FINAL_ARC: true
    2. Arc:t是当前节点的最后一个出度，所以BIT_LAST_ARC: true
    3. Arc:t的Target 等于 lastFrozenNode，所以 BIT_NEXT_TARGET: true
    4. Arc:t的target是终止节点，所以BIT_STOP_NODE: true。
    5. Arc:t有Output Value，所以BIT_HAS_OUTPUT: true

所以Arc:d的flags属性为31。

  1. 随后处理node:s的Arc:b分支，因为它啥都不满足，所以Arc:d的flags属性为0。
  2. 最后处理node:m，所以计算Arc:s的flags值：
    1. Arc:s是当前节点Node:m的最后一个出度，所以BIT_LAST_ARC: true
    2. Arc:s的Target 等于 lastFrozenNode，所以 BIT_NEXT_TARGET: true

所以Arc:d的flags属性为6。
处理结果如下所示：
点击查看【processon】

Step8：结束

点击查看【processon】
按照以下顺序逐个去冻结，具体的计算流程就不再书写了，这里给出最终结果：

  1. 先处理Stop节点，因为Stop节点的出路为0，所以FST#addNode()直接会返回FINAL_END_NODE，该常量值的数值为 -1，该返回值会被赋值给lastFrozenNode。
  2. Arc:l：
    1. BIT_FINAL_ARC
    2. BIT_LAST_ARC
    3. BIT_TARGET_NEXT
    4. BIT_STOP_NODE

所以Arc:l的flag属性值为15

  1. Arc:w：
    1. BIT_LAST_ARC
    2. BIT_TARGET_NEXT
    3. BIT_ARC_HAS_OUTPUT

所以Arc:w的flag属性值为22

  1. Arc:m：
    1. BIT_ARC_HAS_OUTPUT

所以Arc:m的flag属性值为16

  1. Arc:a：
    1. BIT_ARC_HAS_OUTPUT

所以Arc:a的flag属性值为16
最后的current结果如下所示：
点击查看【processon】

解疑

BIT_TARGET_NEXT

新增一个节点的过程：
FSTCompilerBuilder#compileNode() -> FST#addNode()
在FSTCompilerBuilder#compileNode()中有这样一段代码来决定lastFrozenNode的值：

  1. private CompiledNode compileNode(UnCompiledNode<T> nodeIn, int tailLength) throws IOException {
  2.     ...    // 省略了一些代码
  3.     if (nodeIn.numArcs == 0) {
  4.          node = fst.addNode(this, nodeIn);
  5.          lastFrozenNode = node;
  6.     }
  7.     ...
  8.     if (bytesPosEnd != bytesPosStart) {
  9.       // The FST added a new node:
  10.       assert bytesPosEnd > bytesPosStart;
  11.       lastFrozenNode = node;
  12.     }
  13.     ...
  14.   }

然后我们看看FST#addNode()：

  1. long addNode(FSTCompiler<T> fstCompiler, FSTCompiler.UnCompiledNode<T> nodeIn)
  2.       throws IOException {
  3.     ...
  4.     if (nodeIn.numArcs == 0) {
  5.       if (nodeIn.isFinal) {
  6.         return FINAL_END_NODE;            // 值是 -1
  7.       } else {
  8.         return NON_FINAL_END_NODE;
  9.       }
  10.     }
  11.     ...
  12. }

BIT_NEXT_TARGET

该属性主要解释了，当前这个Arc是否指向了lastFrozenNode，如果不是则说明当前这个节点和lastFrozenNode不连接；所以在BIT_NEXT_TARGET:false的情况下，我们需要给定一个index值，让当前的Node知道下一个节点的位置在哪里。

总结

这整个构建过程都是基于一定规则的：

  1. 因为尾部冻结的机制。current整体是倒过来存储的，比如acd这个字符，它肯定是先存d，再存c，最后存a。
  2. 构建过程可以分为两个部分，一部分正处于frontier数组中的数据，一部分正在处理后往curretn中放
  3. 在处理时，只有不存在BIT_NEXT_TARGET时，才会增加index属性，帮助当前节点甄别下一个节点。
  4. 数据的读取是从末尾到首部的
  5. output的值是需要遵守最小化公用算法的。
  6. Entry这个节点实际不存在，主要方便可视化。
  7. Stop这个节点实际也不存在，主要方便可视化。
  8. 只有当前缀确定不会变更了后，才会处理冻结。是否变更，主要由字典序来保证，字典序已经保证了顺序。