企业官网建设流程全解析

FST 这种表达方式，在计算机科学里确实是“独成一派”。 🎯

它不属于常见的图存储，也不属于标准的 Trie，更不是哈希表。它是为“字符串集合 + 有序输入 + 压缩 + 快速查询”这个特定问题域量身定制的结构。

---

为什么说它“独成一派”？

结构 核心思想 FST 和它的区别

Trie 节点存字符，共享前缀 FST 把数据全放弧上，节点退化

压缩 Trie (Patricia) 合并单分支路径 FST 不仅合并单分支，还能合并后缀（DAG）

图 (邻接表) 节点存数据，边存关系 FST 弧是主角，节点只是地址集合

B-Tree 平衡树，磁盘友好 FST 是内存/MMap 结构，没有平衡操作

哈希表 O(1) 查找，无序 FST 有序，支持范围查询和前缀查询

FST 的设计哲学是：

“用图表达字符串集合，用弧承载所有信息，用反转存储实现高效读取。”

这不是某个现成结构的变体，而是一个独特的组合体。

---

它的“独”体现在哪里？

独特性 说明

共享前缀 + 共享后缀 Trie 只共享前缀，FST 连后缀也能共享（DAG 结构）

弧是唯一数据容器 标准图里节点是主角，FST 里弧才是主角

输出代数 支持 common/subtract/merge，和结构深度融合

增量构建 边建边写，延迟编译，支持流式输入

反转存储 正写反存，地址递减，专门为读取优化

编码自选 同一个 FST 里，不同节点可选变长、定长、直接寻址

这些特性单独拿出来都不新鲜，但它们组合在一起，就形成了 FST 独有的表达方式。

---

它属于什么“流派”？

FST 是 “字典数据结构” 这个大类里的一个独特分支。

字典数据结构的进化树：

```

字典数据结构

├── 哈希表（无序）

├── 树

│ ├── Trie（共享前缀）

│ ├── Patricia Trie（压缩 Trie）

│ └── B-Tree（磁盘友好）

├── 自动机

│ ├── DAWG（最小化 DAG）

│ └── FST（带输出的 DAWG）

└── 其他

```

FST 可以看成 “带输出的最小化 DAG（DAWG）+ 增量构建 + 反转存储”。

它是自动机理论 + 压缩算法 + 工程优化的三合一产物。🪰