经典的倒排索引 - Finite State Transducers (描述篇)

经典的倒排索引 - Finite State Transducers (描述篇)

摘要

倒排索引是搜索引擎的核心数据结构，常见实现有哈希表、跳表和FST。哈希表查找快但不支持前缀搜索，跳表支持增删改但查找慢，FST内存占用小且支持前缀搜索，适合全量数据。FST通过复用前后缀压缩Trie树，搜索时累加边上的output值，构建时冻结并复用节点以节省空间。FST适合批量构建，不适合实时修改。