## 一、FST 是什么
**FST（有限状态转换器）** 是一种**带输出的有限状态自动机**（Finite State Automaton, FSA），它的主要作用是：
> **在保持词典查找功能的同时，压缩存储空间，并为每个 term 映射一个输出值（通常是倒排表的地址或 ID）。**
简单理解：
| 传统方式 | FST |
| --------------------------- | ----------------- |
| 一条条存 term → 对应 posting list | 构建紧凑状态机，共享前缀与后缀路径 |
| 查找时 O(logN) 树搜索 | 查找时 O(L)（term长度） |
| 存储量大 | 存储压缩（常减半以上） |
---
## 二、FST 的作用（在 ES 中）
在 **Elasticsearch / Lucene** 的倒排索引中：
* 每个字段会构建一个 **Term Dictionary**（词典）；
* 词典需要支持：
* term → postings list offset 的查找；
* term range 查询（前缀匹配、范围扫描）；
* 高效存储（因为 term 数可能是千万级）。
Lucene 使用 **FST** 来压缩这个词典：
* 将所有 term（有序）构造成一棵状态机；
* 每个节点表示一个字符状态；
* 每个路径（从根到叶）代表一个 term；
* 每条边上可以携带一个 **输出值（output）**，比如 term 对应的倒排文件偏移量。
举个例子（简化）：
```
Terms:
cat -> 1
car -> 2
dog -> 3
```
构建 FST：
```
(root)
└─ c ─ a ─ ─┬─ t [1]
└─ r [2]
└─ d ─ o ─ g [3]
```
可以看到前缀 "ca" 被**合并共享**了。
---
## 三、为何 FST 压缩率高
因为自然语言词汇中前缀（或后缀）相似度很高（如 “compute”, “computer”, “computing”），
FST 通过**共享路径**避免重复存储，从而压缩数据。
此外，Lucene 的实现使用了：
* **最小化（minimized）有向无环图 DAG**；
* **字典序输入构建算法**（构建过程中状态可直接复用）；
* **delta 编码**和**VarInt 编码**进一步节省空间。
---
## 四、FST 如何用于 term 查找
查找一个 term（例如 `"cat"`）时：
1. 从 root 开始，依次读取每个字符；
2. 按照边的字母匹配转移；
3. 到达终止状态时输出对应的倒排偏移；
4. 若中途无边可转移，则说明 term 不存在。
查找复杂度是 **O(L)**（term 的长度），与 term 总数无关，性能非常稳定。
---
## 五、ES/Lucene 实现简要说明
在 Lucene 源码中（`org.apache.lucene.util.fst`）：
* 核心类：
* `FST<T>`：通用的有输出有限状态机；
* `Builder<T>`：用于从 term 列表构建最小化 FST；
* `PositiveIntOutputs`、`ByteSequenceOutputs`：定义输出值类型；
* `Util.get()`：用于 term 查找。
Lucene 的 FST 主要应用在：
* `Lucene50PostingsFormat` → Term dictionary；
* `Suggest` 模块 → 前缀自动补全；
* 某些内部索引结构（如 norms、doc values 的前缀压缩）。
---
## 六、一个简单的 Go 实现示例（演示思想）
虽然 Lucene 的 FST 很复杂，但可以在 Go 中模拟一个**最小自动机构建**思路：
```go
package main
import (
"fmt"
)
type Node struct {
edges map[rune]*Node
output int
isFinal bool
}
func NewNode() *Node {
return &Node{edges: make(map[rune]*Node)}
}
// 简单构建前缀共享树（非最小化 FST）
func Insert(root *Node, term string, value int) {
node := root
for _, ch := range term {
if node.edges[ch] == nil {
node.edges[ch] = NewNode()
}
node = node.edges[ch]
}
node.isFinal = true
node.output = value
}
func Search(root *Node, term string) (int, bool) {
node := root
for _, ch := range term {
next := node.edges[ch]
if next == nil {
return 0, false
}
node = next
}
if node.isFinal {
return node.output, true
}
return 0, false
}
func main() {
root := NewNode()
Insert(root, "cat", 1)
Insert(root, "car", 2)
Insert(root, "dog", 3)
if v, ok := Search(root, "car"); ok {
fmt.Println("Found:", v)
}
}
```
这只是 FST 的雏形：
* 实际实现会做 **状态最小化**、**压缩序列化**，甚至存储在磁盘上（如 `.tim` 文件）。
---
## 七、总结
| 项目 | 说明 |
| --------- | ------------------------------------------------ |
| 名称 | FST（Finite State Transducer）有限状态转换器 |
| 主要用途 | 压缩 term dictionary（词典），映射 term → postings offset |
| 优点 | 高压缩率、快速查找、支持范围扫描 |
| 在 ES 中的位置 | Lucene 底层的 `.tim` 文件（Term Dictionary 部分） |
| 查找复杂度 | O(term 长度) |
