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 可以看成 “带输出的最小化 DAGDAWG 增量构建 反转存储”。它是自动机理论 压缩算法 工程优化的三合一产物。