FST

与数组相比

• 性能：几十到上百倍
• .fst 文件：一半大小

我觉得应该是前缀树，结果还真是。但为什么有个这么怪的名字

感觉他这个视频没讲清晰啊。

评论补充：

• 字典树和状态机完全是两码事 。大叔想表达的应该是针对单词这个特定场景下：字母驱动的状态机
• fst和trie类似，不过fst是用状态机，这东西elasticsearch里lucene用的，才会卷到面试里去。前几年不卷的时候，熟练运用es对这算法都是闻所未闻

动画演示：https://www.cs.usfca.edu/~galles/visualization/Trie.html

应用场景：词典、黑名单白名单。但是一般用得不多