Lucene 倒排索fst引原理与实现

越飞语

2023-12-01

整理下几篇博客

1 Lucene 4.X 倒排索引原理与实现: (3) Term Dictionary和Index文件 (FST详细解析)

https://www.cnblogs.com/forfuture1978/p/3945755.html

2 关于Lucene的词典FST深入剖析

https://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/

FST类似一种TRIE树。

使用FSM(Finite State Machines)作为数据结构
FSM(Finite State Machines)有限状态机: 表示有限个状态（State）集合以及这些状态之间转移和动作的数学模型。其中一个状态被标记为开始状态，0个或更多的状态被标记为final状态。
一个FSM同一时间只处于1个状态。FSM很通用，可以用来表示多种处理过程，下面的FSM描述了《小猫咪的一天》。

总结
FST，不但能共享前缀还能共享后缀。不但能判断查找的key是否存在，还能给出响应的输入output。它在时间复杂度和空间复杂度上都做了最大程度的优化，使得Lucene能够将Term Dictionary完全加载到内存，快速的定位Term找到响应的output（posting倒排列表）

场景大概有以下：

自动联想：suggester
charFilter: mappingcharFilter
同义词过滤器
hunspell拼写检查词典

3 Lucene BKD树-动态磁盘优化BSP树

https://www.shenyanchao.cn/blog/2018/12/04/lucene-bkd/

4 FST（一）Lucene 8.4.0

flag
由于构建FST后，所有的信息都存在current[ ]数组中，这过程实际是一个编码过程，在构建阶段，需要生成flag，使得在读取阶段，能根据flag的值进行解码

https://www.amazingkoala.com.cn/Lucene/yasuocunchu/2019/0220/35.html

链接备份：down

5 FST（二）（Lucene 8.4.0）

fst的解析

https://www.amazingkoala.com.cn/Lucene/yasuocunchu/2020/1009/168.html

6 lucene字典实现原理

https://www.cnblogs.com/LBSer/p/4119841.html

下面简单描述下FST的构造过程（动态工具演示：http://examples.mikemccandless.com/fst.py?terms=&cmd=Build+it%21）

很多数据结构均能完成字典功能，总结如下。

数据结构	优缺点
排序列表Array/List	使用二分法查找，不平衡
HashMap/TreeMap	性能高，内存消耗大，几乎是原始数据的三倍
Skip List	跳跃表，可快速查找词语，在lucene、redis、Hbase等均有实现。相对于TreeMap等结构，特别适合高并发场景（Skip List介绍）
Trie	适合英文词典，如果系统中存在大量字符串且这些字符串基本没有公共前缀，则相应的trie树将非常消耗内存（数据结构之trie树）
Double Array Trie	适合做中文词典，内存占用小，很多分词工具均采用此种算法（深入双数组Trie）
Ternary Search Tree	三叉树，每一个node有3个节点，兼具省空间和查询快的优点（Ternary Search Tree）
Finite State Transducers (FST)	一种有限状态转移机，Lucene 4有开源实现，并大量使用