从零开始实现 Go 搜索引擎（二）-FST 构造算法

作者：geange

2023-12-12
广东
本文字数：2893 字
阅读完需：约 9 分钟

缘由

最近 N+1 了，年底也没打算怎么找工作（现在爽是真的爽，估计明年就要自闭了🐶）。

空闲之余捣鼓下开源项目，在紧锣密鼓实现 Golang 版本的 FST，欢迎大佬观摩（还没开发完，暂不支持 PR😂），https://github.com/geange/lucene-go。

什么是 FST

FST 是 Trie 树的一种。下图可见，FST 是一种可以共享前缀/后缀的 Trie 树。

FST 的优点在于可以使用更紧凑的空间存储大量的数据。

思考

由于 lucene 中数据结构复杂，希望读者能专注于 FST 的构建算法。

结构

构建 FST 之前，需要先了解构建 FST 的时候有哪些关键的数据结构。

Label：输入值中的一个字符，对于MOP这个单词，存在 3 个字符，即 3 个 Label
Arc：连接节点（Node），存储 Label 和 Output 数据
Output：你可以将 FST 理解为一个 KV 存储结构。Output 就是这个 KV 存储的值（Value）。在 FST 中，一条路径下对于一个 Key 值，而这条路径上所有 Arc 上存储的 Output 之和才是这个 Key 对应的 Value。
Node：节点，它的作用是用于容纳 Arc，你认为它就是一个容器即可。

下面 2 条路径可以看做 key="MOP"，value=100。

在 FST 中，一条路径下对于一个 Key 值，而这条路径上所有 Arc 上存储的 Output 之和才是这个 Key 对应的 Value。

Flag 标记

这里的标记有一个概念即可，后续的流程中会穿插介绍 Flag 的使用的实际场景。

算法

我们使用一个例子来讲解 FST 的构建。

场景

上面我们讲过 FST 实际上可以理解为一个 map。我们向这个 KV 写入以下数据：

需要注意点是，输入的 Key 都是已经排序的

重现

写入 MOP=100

方格块对应的是字节数组，FST 使用字节数组存储数据（即冻结）。构建完成后数组不再变动。

写入 MOTH=91

由于MOP和MOTH存在前缀MO，且路径对应的 Output 是 Arc 的 Output 之和，因此 N1->N2 的 Output=91，而 N3->P 的 Output=9，保证了MOP=100和MOTH=91。

写入 POP=72 前，节点冻结

处理 END 节点

终止节点返回值为固定值-1，并更新 lastFrozenNode 为 -1。

处理 N4 节点/H

在写入POP=72前，需要将部分节点持久化到内存中。由于POP和MOTH没有相同的前缀，因此，需要将 N2 到 N4 的节点进行冻结（存储到字节数组中）。处理的顺序从后往前，所以先处理 N4。处理完 N4 后，lastFronzenNode=N4。

index=2 存储的是 flag，当前 H 的 flag 满足以下几个条件：

15 = BIT_LAST_ARC(2) + BIT_TARGET_NEXT(4) + BIT_FINAL_ARC(1) + BIT_STOP_NODE(8)

BIT_LAST_ARC：它是 N4 中的最后一个 arc
BIT_TARGET_NEXT：arc 的目标节点为END，因此认为跟 lastFrozenNode 一致都为-1（lastFrozenNode 默认初始值为-1）
BIT_FINAL_ARC：H为MOTH的最后一个字符
BIT_STOP_NODE：arc 的目标节点是一个终止节点（BIT_STOP_NODE）

处理 N3 节点

因为 N3 有 2 个 Arc，需要从下往上处理。处理完 N3 节点后，lastFronzenNode=N3

处理 ARC=T

一个节点如果存在多个 Arc，就从下往上处理。这里处理 Arc=T 的。

T对应的 arc，满足以下几个 flag：

6 = BIT_LAST_ARC(2) + BIT_TARGET_NEXT(4)

BIT_LAST_ARC(2)：它是 N3 中的最后一个 arc
BIT_TARGET_NEXT(4)：arc 的 target 节点的值为 N4，而最新的 lastFronzenNode 的值是 N4 对应生成的，故满足 BIT_TARGET_NEXT

处理 ARC=P

因为 Arc=P 存在 Output=9，因此 index=5 的值为 9。

P对应的 arc，满足以下几个 flag，因此 index=7 的值为 25：

25 = BIT_FINAL_ARC(1) + BIT_STOP_NODE(8) + BIT_ARC_HAS_OUTPUT(16)

BIT_FINAL_ARC(1)：P是MOP的最后一个字符
BIT_STOP_NODE(8)：arc 的目标节点是一个终止节点（nil）
BIT_ARC_HAS_OUTPUT(16)：arc 有 output 值

处理 N2 节点/O

O对应的 arc 满足以下几个 flag：

6 = BIT_LAST_ARC(2) + BIT_TARGET_NEXT(4)

BIT_LAST_ARC(2)：arc 是 Node2 节点中的最后一个 arc

BIT_TARGET_NEXT(4)：arc 的目标节点为 N3，而最新的 lastFronzenNode 的值是 N3 对应生成的，故满足

写入 POP=72

上一步处理完 N2 节点后，获取字节数组的当前游标的位置为 9，因此 Arc=M/91 的目标位置为 9。