1. 先弄明白 FST 到底在解决什么问题FST 这个全称——有限状态转换器Finite State Transducers——第一次看到的时候多数人脑子里冒出来的是编译原理课本里那堆圆圈和箭头。我第一次接触它是在做一个词典类功能的索引压缩当时的需求很朴素几十万条词条、每条词条带一个词频和一个释义指针用哈希表存内存吃不住用普通前缀树存后缀又浪费得离谱后来有人丢给我一句你试试 FST。折腾了几天才明白这东西本质上是把输入串到输出串的映射压成一张带权重的有向图然后把这张图序列化进内存或者磁盘查的时候照着图走一遍就出结果。它能做的事情很集中在一个巨大的键值集合里用极小的内存占用完成精确查找、前缀遍历、模糊扩展和按权重排序。注意这四个能力是绑在一起的这也是它比哈希表和普通树结构更值得研究的原因。哈希表查得快但没法做前缀遍历也没法按热门程度返回 TopN普通 Trie 能做前缀但空间开销随词条长度线性膨胀而且每个节点上挂 metadata 的做法一遇到百万级词条就会失控。FST 把共享前缀、共享后缀、输出延迟、权重排序这几件事塞进了同一个结构里。适合谁看这篇三类人。一类是做搜索、输入法、词典、纠错这类词表驱动功能的工程师你迟早会撞上 FST一类是正在啃编译原理或者自然语言处理课程被形式语言那套符号绕晕的同学我这里会用大白话把它拆开还有一类是纯粹被有限状态四个字吓住、想搞清楚它到底能不能落地的人。全文不预设你懂自动机理论但会假设你写过代码、知道什么是字典、能手画一张流程图。2. 把 FST 拆开看五个零件和两条铁律2.1 从自动售货机说起状态、转移和标签先扔掉所有数学符号。想象一台老式自动售货机它只有三个状态待机、已投币、出货中。你投一枚硬币它从待机走到已投币你再按一下按钮它从已投币走到出货中。这里面有两个东西在动一个是状态机器现在处在哪一步一个是转移什么动作让它从这一步跳到下一步。FST 的骨架就是这个。它由五样东西组成一组状态图上那些圆圈、一组转移弧带方向的箭头、弧上的输入标签、弧上的输出标签、以及一个初始状态和若干个终止状态。读一个字符串的时候从初始状态出发每读一个字符就沿着标有该字符的弧走一步走完整串之后如果落在终止状态上那么这个串是被接受的同时把沿途所有输出标签拼起来就是转换结果。真正的区别在于——每根箭头上贴着两个标签一个进、一个出。这就是转换器transducer和普通接受器acceptor的分水岭。普通有限状态机只回答这个串合不合法是或否转换器还要回答如果合法它对应的是什么。所以你可以把它理解成一台会记账的状态机走一步记一笔。我用一个具体例子固定这个概念。假设要做一个极简的词形还原映射把英文复数还原成单数。设计成这样读到c走一条弧输出空读到a输出空读到t输出空读到s的时候输出空然后落到终止状态。等等这样输出全是空的什么也没换。正确的做法是把输出标签往后挪——所有字母一路欠着直到读完s、确认这是个复数形式才在最后一条弧上一次性吐出cat。这个技巧叫输出延迟output delay是 FST 最核心的工程思想之一后面第 3 节会专门展开。2.2 铁律一同一个状态下同样的输入只能走一条路这是确定性determinism的要求。如果某个状态上有两条弧都标着字母a那读到a的时候机器就不知道该走哪条了得回溯、得试错性能直接崩掉。所以工业界用的基本都是确定性 FST任何一个状态对任何一个输入符号最多只有一条出弧。这条约束听起来很严但它恰恰是性能的来源。确定性意味着查找一个长度 n 的串复杂度严格是 O(n)走 n 步每步做一次查表找弧的操作没有分支、没有回溯、没有指数爆炸。这也是为什么 FST 敢号称内存换时间的反面——它同时省内存和省时间。要实现确定性构建阶段就得把非确定性的部分消掉。常见做法是先构造一棵非确定性的树或者直接用词表排序后批量构建然后在构建过程中做确定化把同一状态下的相同输入标签合并和最小化把等价的状态合并成一个。这两个步骤是 FST 构建里最费工夫的部分也是内存和构建时间的主要消耗点。实际工程中如果你的词表是静态的、一批一批离线导入的那构建慢点无所谓如果是动态插入的就得考虑用增量构建或者分片重建的策略。2.3 铁律二输出标签挂在哪条弧上决定了结果的正确性这条是新手最容易翻车的地方。看一个反例把ab映射成x把abc映射成y。如果按直觉设计读完a输出x读完b也输出空然后为了区分ab和abc再分叉出c那条路输出y。这么设计在产品上就是灾难——因为ab读完之后机器已经落在终止状态并吐出了x用户再多输入一个c结果变成了xy而不是y。正确的做法是把输出往后压ab这条路径上的输出全部为空只在最后一步、也就是确认输入结束的那条弧上吐x。对于abca、b两步输出空走到c的时候吐y。这样两个串共享了前两步的路径既不冲突又省空间。这个例子说明了一件事输出标签的位置不是随便放的它必须和信息确认的时机对齐。什么时候你才知道该输出什么只有当你读完了决定性的那一段输入之后。凡是读了前缀但还没法确定最终结果的场合输出就该往后拖。这也是为什么 FST 构建算法里会有把输出标签沿路径向下推的规范化步骤——推到一个所有后续路径都一致的位置为止。2.4 权重一个被低估的附加维度每条弧除了输入输出标签还可以挂一个权重。这个权重可以是词频、可以是分数、可以是任意可加的度量。有了权重FST 就不只是个查找结构了它变成了一个带排序的查找结构。举个实际场景拼写纠错。用户输入recieve拼错了你要给出候选。做法是把正确词库建成 FST然后用编辑距离的思路在图上做扩展搜索允许插入、删除、替换、换位。每走一步弧累加权重。搜索结束后你把所有落在终止状态上的路径按累计权重从小到大排个序取前几个就是候选词。热门词权重低冷僻词权重高排出来自然就是常用词优先。再比如搜索建议把所有查询词建 FST权重用历史点击量。用户输入前缀智能手你在图上走到这个前缀对应的状态然后从这个状态往下做深度优先遍历把所有能到达终止状态的路径捡回来按权重排序取 Top10。整个过程中你一次都没有扫描全量数据只走了图上的局部。3. 手工造一台 FST从需求到跑通的完整流程3.1 第一步把业务问题翻译成输入串到输出串的映射动手之前先想清楚一件事你的输入是什么形态输出是什么形态两者是不是一一对应。这一步做不好后面全白搭。我拿一个具体的小需求做演示一个日期格式的规整器。输入是形如2024-1-5、2024-01-05、2024/1/5这种不统一的写法输出统一成20240105八位数字。词表规模不大但足够把 FST 的机制讲透。先做映射分析。输入串的字符集合是{0-9, -, /}输出字符集合是{0-9}。注意这里有一对多和多对一的关系输入-和/都输出空被吃掉输入2024这段要原样透传输入月份1要补成01。这种部分原样、部分变形的情况单纯靠一张映射表是没法表达的必须靠状态来区分我现在读到的是年份、月份还是日期。这就是关键洞察FST 的状态不仅是进度标记它还承载了上下文语义。同一个字符1在年份位置和月份位置上的处理逻辑完全不同所以图上的位置也必须不同。设计状态的时候本质上是在回答读到第几段了。3.2 第二步把思路画成状态图再整理成转移表状态定义如下S0起始读年份S1读完年份等待分隔符S2读月份第一位S3读完月份等待分隔符S4读日期第一位S5读完日期第一位等日期第二位S6终止转移表这样写只列关键行ε表示空输出当前状态输入输出下一状态说明S00-9同字符S0年份四位原样透传S0- 或 /εS1分隔符吃掉S10-90 同字符S2月份补零输出S2- 或 /εS3第二个分隔符S30-90 同字符S5日期补零输出S50-9同字符S6日期第二位S6结束ε—终止这张表里有个细节值得停一下S1读到数字时输出的是0加上这个数字本身也就是一次转移输出两个字符。这在实现上完全合法——输出标签不必是单字符可以是一个串。很多人写代码的时候喜欢把输出限制成单个字符结果就是被迫多加状态来拆解白白膨胀了图的大小。允许输出串是控制状态数的一招实用技巧。还有S5到S6的那一步。为什么日期第二位不补零因为日期第二位已经是个位数字05的5就是原样。但如果用户输入的是2024-1-5月份和日期都只有一位那走S1 - S2的时候已经补了零S2之后直接遇到分隔符再走S3 - S5还是只处理一位。这套设计对一位或两位两种输入都成立靠的就是遇到分隔符就跳段的短路逻辑。3.3 第三步用代码把表变成可执行的东西下面是我自己手写的一个极简 FST不做最小化只做确定性构建目的是让读的人能看清数据结构长什么样。生产环境当然不该这么写但教学上这个版本最直白。from collections import defaultdict class FST: def __init__(self): # transitions[state][input_char] (next_state, output_str, weight) self.transitions defaultdict(dict) self.finals {} # state - 累积输出终止状态上的收尾输出 self.start 0 self._next_id 1 def new_state(self): s self._next_id self._next_id 1 return s def add_path(self, in_str, out_str, weight0): 把一条 输入串 - 输出串 的映射加入图共用已存在的前缀 state self.start # 关键输出延迟 —— 只在需要分叉的地方吐出输出 pending out_str for i, ch in enumerate(in_str): is_last (i len(in_str) - 1) if ch in self.transitions[state]: nxt, existing_out, w self.transitions[state][ch] # 已有弧把共同前缀输出留在弧上分歧部分下推 common _common_prefix(existing_out, pending) if common ! existing_out: self.transitions[state][ch] (nxt, common, w) # 把原本的输出重新挂到 nxt 的出边上简化处理 _push_down(self.transitions, nxt, existing_out[len(common):]) pending pending[len(common):] state nxt else: nxt self.new_state() if not is_last else self.new_state() if is_last: self.transitions[state][ch] (nxt, pending, weight) self.finals[nxt] else: self.transitions[state][ch] (nxt, , weight) state nxt pending def lookup(self, in_str): state self.start out [] for ch in in_str: if ch not in self.transitions[state]: return None nxt, o, _ self.transitions[state][ch] out.append(o) state nxt if state not in self.finals: return None out.append(self.finals[state]) return .join(out) def _common_prefix(a, b): n min(len(a), len(b)) i 0 while i n and a[i] b[i]: i 1 return a[:i] def _push_down(transitions, state, suffix): 把待输出的后缀沿路径下推简化版直接挂在第一条出弧上 if not suffix: return for ch, (nxt, o, w) in transitions[state].items(): transitions[state][ch] (nxt, suffix o, w) return跑一下fst FST() fst.add_path(2024-1-5, 20240105) fst.add_path(2024-01-05, 20240105) fst.add_path(2024/1/5, 20240105) print(fst.lookup(2024-1-5)) # 20240105 print(fst.lookup(2024/1/5)) # 20240105 print(fst.lookup(2024-02-30)) # None最后一行返回None是符合预期的——2024-02-30这条路径根本不在图里因为构建时只加了三条合法样例。这引出一个必须说清楚的点FST 只能识别你喂给它的东西它不是一个规则引擎。想让它处理任意合法日期你得把规则展开成状态而不是靠几条样例糊上去。上面这个 demo 只适合讲解机制。3.4 第四步验证、压缩与落盘功能跑通只是第一步。真正上线前还有三件事要做。第一是穷举验证。构造一批边界输入空串、超长串、只差一个字符的近似串、包含图外字符的串。每一条都要确认返回的是正确结果或者正确拒绝不能出现返回了一个看起来像那么回事但实际错误的结果。这类静默错误在 FST 场景下特别难查因为图走通了但输出错了程序不报错。第二是最小化。手写的图里一定有大量等价状态可以合并。合并之后图变小、缓存命中率上升、遍历更快。最小化的算法核心是不断把状态按出边签名分组签名相同的归为一类直到分组稳定。这个过程是纯离线计算不影响线上查询逻辑。第三是序列化。FST 一旦构建完成就是只读的所以最省内存的做法是把它按特定顺序排布成一段连续字节然后整个映射进内存查的时候直接按偏移量跳转完全不做对象分配。这也是为什么很多检索系统偏爱 FST——它天生适合内存映射冷启动快多进程共享同一份物理内存。4. 工程落地FST 的四个典型落点4.1 词典与词库的压缩索引这是 FST 最经典的用法。一个百万级词条的词典如果每条都存完整字符串光字符串本身就要占几十兆到上百兆再加上每个词挂的元数据词性、词频、释义偏移内存压力很大。用 FST 之后前缀和后缀都能共享。英文单词里-ing、-tion、-ness这类后缀重复率极高中文虽然没这么规整但地名、机构名里的市区有限公司同样高度重复。共享带来的压缩比通常在 5 到 20 倍之间取决于词表本身的重复度。加载完之后查一个词就是走 n 步每步一次数组下标访问速度快到可以忽略。元数据怎么挂常见做法是把词表按字典序排好每条元数据放在一个平行的数组里FST 上每个终止状态存一个整数下标指过去即可。这样 FST 只管词在不在、在哪具体内容交给外部数组职责清晰也方便单独更新元数据而不重建图。4.2 分词与形态还原中的规则表达中文分词器里有个环节叫词典匹配最朴素的实现是拿词典里的词去文本里逐个尝试。用 FST 之后可以把从某个位置开始能匹配到哪些词这件事变成一次图遍历从初始状态出发沿着文本字符一直走每走一步就检查当前状态是不是终止状态是的话就记录一个候选词。这个过程的复杂度只和能匹配上的最长前缀长度有关和词典总规模无关。文本里某个位置后面接的是生僻字走一步就断了立刻停下接的是常见组合就多走几步。这种自适应的特性让它在长文本上的表现非常稳。形态还原是另一个方向。英语的动词变位、名词复数德语的格变化阿拉伯语的词根派生这些规则的共同点是从一个词形到另一个词形中间经历一串可枚举的变化。用 FST 表达的好处是双向的——正向可以做词形生成给词根和语法特征产出词形反向可以做词形分析给词形产出一组可能的词根和特征。反向的时候因为可能有多条路径需要按权重排序取最可能的那个。4.3 输入法与拼写纠错里的模糊扩展输入法的核心是用户敲了一串按键我要给出猜他想打什么。这天然是个加权转换问题按键序列是输入串候选词是输出串每个候选带一个概率权重。FST 在这个场景下的价值在于它能同时表达多种变形规则。比如拼音输入里zh和z可以互通、n和l在部分方言里互通、前后鼻音可以混淆。这些规则不需要写成一堆 if-else而是直接在图上开分支——同一个状态上放两条不同标签的弧指向同一个目标状态读哪一个都行。当然这就破坏了确定性需要在构建时把这种可选编码成确定结构或者干脆用非确定性图配合权重搜索。拼写纠错同理。编辑距离的四种操作插入、删除、替换、换位对应到图上就是四种扩展方式每扩展一步累加一个惩罚权重。搜索的终止条件是累计权重超过阈值或者已到达深度上限这样能有效剪枝避免在全图上乱跑。4.4 和倒排索引、向量检索的配合方式有人会问现在向量检索这么火FST 还有用吗有用但角色变了。倒排索引解决的是文档里有没有这个词FST 解决的是这个词本身合不合法、它的前缀是什么、它的近似词有哪些。两者是上下游关系用户输入一个查询先用 FST 做拼写检查、前缀补全、同义词扩展产出一组规范化的查询词再丢给倒排索引去召回文档。少了前面这一步用户拼错一个字母就只能拿到零结果。和向量检索配合也是类似逻辑。向量检索擅长语义相近但对精确的专有名词、编号、代号往往不敏感甚至会把完全不同的两个编号判成相似。这时候用 FST 做一层精确匹配优先的兜底命中就直接返回没命中再走向量召回能显著减少答非所问的情况。5. 性能与内存调优时绕不开的几个参数5.1 状态数和弧数哪个才是真正的瓶颈构建完 FST 之后第一件事是看两个数字状态总数和弧总数。很多人只盯状态数其实弧数往往才是内存占用的主导因素因为每条弧都要存标签、目标状态偏移、输出、权重这几项。经验值是如果平均每个状态的出弧数超过 5就要警惕了说明图的分支结构偏碎可能有大量可以合并的状态。处理方法有两个方向一是把输出标签往深处推减少因为输出不同而被迫分开的状态二是把多个短词合并成一条长弧用输出串表达多个字符减少中间状态。另一个反直觉的点是图的绝对大小不如缓存局部性重要。一个 20MB 但访问模式高度聚集的 FST实际查询性能可能超过一个 10MB 但访问分散的实现。所以排布顺序很关键——把高频词对应的状态尽量放在相邻的字节区域能让 CPU 缓存发挥最大作用。5.2 构建耗时为什么要接受离线慢、线上快构建一个百万级词条的 FST包含确定化和最小化耗时从几秒到几分钟不等取决于实现质量。这个时间在线上是不可接受的所以标准做法是离线构建、线上只读。离线构建的工程要点是把词表先按字典序排好再喂给构建器这样能大幅减少中间状态的数量构建过程也更线性。如果词表是动态增长的不要每次插入都重建全图而是维护一个增量小图加一个全量主图查询时两边都查合并结果等到增量图积累到一定规模再合并回主图。5.3 内存映射与冷启动的实际收益把 FST 序列化成字节数组后用内存映射方式加载收益主要体现在两点一是进程启动时不需要反序列化直接把文件映射进来就能用冷启动时间从几百毫秒降到几毫秒二是多个进程可以共享同一份物理内存部署多实例时不额外占内存。代价是访问路径上的每个操作都不能做对象分配必须直接按偏移读字节。这意味着序列化的格式要精心设计字段对齐、变长编码、偏移量计算都要提前算清楚。这块的实现复杂度不低如果你只是做个中小规模的应用普通的内存结构可能更省心只有到了千万级词条、多实例部署的场景内存映射的收益才真正显现出来。6. 踩坑实录与排查清单6.1 输出错位最难查的一类静默 bug我碰到过最难受的一次问题症状是大部分词的查询结果正确但有零星几十个词返回的输出串多了一截或者少了一截。没有报错没有异常就是结果不对。查了大半天根因是输出标签在构建时没有推到正确的位置。具体来说当两个词共享前缀、但在某个分叉点之后输出不同的时候共享段的输出如果还留在前一条弧上那么走另一条路径的时候就会把这段输出也带出来。表现出来就是结果里混进了别的词的片段。排查方法很土但有效写个脚本随机采样一万个词逐个查询把结果和预期做比对把不一致的挑出来。然后针对每个不一致的词找它和词表里其他词的最长公共前缀看分叉点在哪检查分叉点前后的输出标签是否对称。只要这个检查做一遍问题基本都能定位。预防的办法是在构建完成后立刻做一次全量自检覆盖率 100%不要抽样。全量自检的耗时通常远小于构建本身性价比极高。6.2 状态爆炸为什么你的图比预想的大十倍状态爆炸通常有三个来源。第一个是输出冗余。上面说过了输出标签放错位置会导致本该合并的状态被迫分开。检查方法把全图的输出标签全部清空重新跑一次最小化看状态数下降多少。如果下降超过 30%说明输出的放置方式有问题。第二个是字符集过大。如果你的输入标签是完整的 Unicode 字符那每个状态的出边数量会非常恐怖。解决办法是做字符类编码——把功能等价的字符归为一类比如把所有数字归成一类所有汉字归成一类用类标签代替具体字符图的规模立刻下来。第三个是没有做后缀共享。普通前缀树只共享前缀FST 还能共享后缀这是它比 Trie 强的地方。如果你的实现只做了确定化没做最小化那后缀就全浪费了。确认一下最小化步骤有没有真的执行很多时候是配置里关掉了。6.3 常见问题速查症状高概率原因处理动作查询返回 None 但词明明在词表里构建时该路径未标记终止状态检查add_path最后一步是否设置 final输出多了或少了几个字符输出标签位置错误全量比对 检查分叉点输出内存占用远超预期未做最小化或字符集未归类开启最小化对字符做类编码构建时间长得离谱词表未排序插入顺序随机先按字典序排序再构建前缀遍历返回结果顺序乱权重未设置或全为 0给每条路径配置合理权重冷启动慢每次启动都反序列化改内存映射或做常驻服务并发查询偶发结果错乱共享结构被写操作污染FST 构建后必须只读写操作走副本这张表里我想特别强调最后一条。FST 的只读属性不是建议是硬约束。一旦图构建完成任何并发写都会导致状态不一致而且这种不一致是概率性的、难以复现的。我见过有人为了支持热更新在图结构上直接打补丁结果上线后偶发返回错误的词排查了两天才定位到是并发写的问题。正确做法是构建新图、原子替换引用旧图等引用计数归零后自然回收。再说一个实操上的小技巧调试 FST 的时候别急着写复杂代码先写一个把图导出成文本的函数把状态、弧、标签全部打印出来。对着文本眼看一遍很多逻辑错误肉眼就能发现比单步调试快得多。图小的时候尤其有效几十个状态的图印出来铺在桌上看十分钟就能找出问题在哪。图大了再上工具。最后分享一个我在实际项目里养成的习惯每次改完 FST 的构建逻辑先拿一个 500 条左右的小词表跑一遍把导出结果和自己的预期逐行对照确认无误再换全量数据。全量构建动辄几分钟用小样本做快速验证能把迭代周期从分钟压到秒这个习惯帮我省下的时间相当可观。 
长河君 · 2026/10/31 8:36:34 · 阅读 1.2k 有限状态转换器FST原理、工程落地与性能调优实战
1. 先弄明白 FST 到底在解决什么问题FST 这个全称——有限状态转换器Finite State Transducers——第一次看到的时候多数人脑子里冒出来的是编译原理课本里那堆圆圈和箭头。我第一次接触它是在做一个词典类功能的索引压缩当时的需求很朴素几十万条词条、每条词条带一个词频和一个释义指针用哈希表存内存吃不住用普通前缀树存后缀又浪费得离谱后来有人丢给我一句你试试 FST。折腾了几天才明白这东西本质上是把输入串到输出串的映射压成一张带权重的有向图然后把这张图序列化进内存或者磁盘查的时候照着图走一遍就出结果。它能做的事情很集中在一个巨大的键值集合里用极小的内存占用完成精确查找、前缀遍历、模糊扩展和按权重排序。注意这四个能力是绑在一起的这也是它比哈希表和普通树结构更值得研究的原因。哈希表查得快但没法做前缀遍历也没法按热门程度返回 TopN普通 Trie 能做前缀但空间开销随词条长度线性膨胀而且每个节点上挂 metadata 的做法一遇到百万级词条就会失控。FST 把共享前缀、共享后缀、输出延迟、权重排序这几件事塞进了同一个结构里。适合谁看这篇三类人。一类是做搜索、输入法、词典、纠错这类词表驱动功能的工程师你迟早会撞上 FST一类是正在啃编译原理或者自然语言处理课程被形式语言那套符号绕晕的同学我这里会用大白话把它拆开还有一类是纯粹被有限状态四个字吓住、想搞清楚它到底能不能落地的人。全文不预设你懂自动机理论但会假设你写过代码、知道什么是字典、能手画一张流程图。2. 把 FST 拆开看五个零件和两条铁律2.1 从自动售货机说起状态、转移和标签先扔掉所有数学符号。想象一台老式自动售货机它只有三个状态待机、已投币、出货中。你投一枚硬币它从待机走到已投币你再按一下按钮它从已投币走到出货中。这里面有两个东西在动一个是状态机器现在处在哪一步一个是转移什么动作让它从这一步跳到下一步。FST 的骨架就是这个。它由五样东西组成一组状态图上那些圆圈、一组转移弧带方向的箭头、弧上的输入标签、弧上的输出标签、以及一个初始状态和若干个终止状态。读一个字符串的时候从初始状态出发每读一个字符就沿着标有该字符的弧走一步走完整串之后如果落在终止状态上那么这个串是被接受的同时把沿途所有输出标签拼起来就是转换结果。真正的区别在于——每根箭头上贴着两个标签一个进、一个出。这就是转换器transducer和普通接受器acceptor的分水岭。普通有限状态机只回答这个串合不合法是或否转换器还要回答如果合法它对应的是什么。所以你可以把它理解成一台会记账的状态机走一步记一笔。我用一个具体例子固定这个概念。假设要做一个极简的词形还原映射把英文复数还原成单数。设计成这样读到c走一条弧输出空读到a输出空读到t输出空读到s的时候输出空然后落到终止状态。等等这样输出全是空的什么也没换。正确的做法是把输出标签往后挪——所有字母一路欠着直到读完s、确认这是个复数形式才在最后一条弧上一次性吐出cat。这个技巧叫输出延迟output delay是 FST 最核心的工程思想之一后面第 3 节会专门展开。2.2 铁律一同一个状态下同样的输入只能走一条路这是确定性determinism的要求。如果某个状态上有两条弧都标着字母a那读到a的时候机器就不知道该走哪条了得回溯、得试错性能直接崩掉。所以工业界用的基本都是确定性 FST任何一个状态对任何一个输入符号最多只有一条出弧。这条约束听起来很严但它恰恰是性能的来源。确定性意味着查找一个长度 n 的串复杂度严格是 O(n)走 n 步每步做一次查表找弧的操作没有分支、没有回溯、没有指数爆炸。这也是为什么 FST 敢号称内存换时间的反面——它同时省内存和省时间。要实现确定性构建阶段就得把非确定性的部分消掉。常见做法是先构造一棵非确定性的树或者直接用词表排序后批量构建然后在构建过程中做确定化把同一状态下的相同输入标签合并和最小化把等价的状态合并成一个。这两个步骤是 FST 构建里最费工夫的部分也是内存和构建时间的主要消耗点。实际工程中如果你的词表是静态的、一批一批离线导入的那构建慢点无所谓如果是动态插入的就得考虑用增量构建或者分片重建的策略。2.3 铁律二输出标签挂在哪条弧上决定了结果的正确性这条是新手最容易翻车的地方。看一个反例把ab映射成x把abc映射成y。如果按直觉设计读完a输出x读完b也输出空然后为了区分ab和abc再分叉出c那条路输出y。这么设计在产品上就是灾难——因为ab读完之后机器已经落在终止状态并吐出了x用户再多输入一个c结果变成了xy而不是y。正确的做法是把输出往后压ab这条路径上的输出全部为空只在最后一步、也就是确认输入结束的那条弧上吐x。对于abca、b两步输出空走到c的时候吐y。这样两个串共享了前两步的路径既不冲突又省空间。这个例子说明了一件事输出标签的位置不是随便放的它必须和信息确认的时机对齐。什么时候你才知道该输出什么只有当你读完了决定性的那一段输入之后。凡是读了前缀但还没法确定最终结果的场合输出就该往后拖。这也是为什么 FST 构建算法里会有把输出标签沿路径向下推的规范化步骤——推到一个所有后续路径都一致的位置为止。2.4 权重一个被低估的附加维度每条弧除了输入输出标签还可以挂一个权重。这个权重可以是词频、可以是分数、可以是任意可加的度量。有了权重FST 就不只是个查找结构了它变成了一个带排序的查找结构。举个实际场景拼写纠错。用户输入recieve拼错了你要给出候选。做法是把正确词库建成 FST然后用编辑距离的思路在图上做扩展搜索允许插入、删除、替换、换位。每走一步弧累加权重。搜索结束后你把所有落在终止状态上的路径按累计权重从小到大排个序取前几个就是候选词。热门词权重低冷僻词权重高排出来自然就是常用词优先。再比如搜索建议把所有查询词建 FST权重用历史点击量。用户输入前缀智能手你在图上走到这个前缀对应的状态然后从这个状态往下做深度优先遍历把所有能到达终止状态的路径捡回来按权重排序取 Top10。整个过程中你一次都没有扫描全量数据只走了图上的局部。3. 手工造一台 FST从需求到跑通的完整流程3.1 第一步把业务问题翻译成输入串到输出串的映射动手之前先想清楚一件事你的输入是什么形态输出是什么形态两者是不是一一对应。这一步做不好后面全白搭。我拿一个具体的小需求做演示一个日期格式的规整器。输入是形如2024-1-5、2024-01-05、2024/1/5这种不统一的写法输出统一成20240105八位数字。词表规模不大但足够把 FST 的机制讲透。先做映射分析。输入串的字符集合是{0-9, -, /}输出字符集合是{0-9}。注意这里有一对多和多对一的关系输入-和/都输出空被吃掉输入2024这段要原样透传输入月份1要补成01。这种部分原样、部分变形的情况单纯靠一张映射表是没法表达的必须靠状态来区分我现在读到的是年份、月份还是日期。这就是关键洞察FST 的状态不仅是进度标记它还承载了上下文语义。同一个字符1在年份位置和月份位置上的处理逻辑完全不同所以图上的位置也必须不同。设计状态的时候本质上是在回答读到第几段了。3.2 第二步把思路画成状态图再整理成转移表状态定义如下S0起始读年份S1读完年份等待分隔符S2读月份第一位S3读完月份等待分隔符S4读日期第一位S5读完日期第一位等日期第二位S6终止转移表这样写只列关键行ε表示空输出当前状态输入输出下一状态说明S00-9同字符S0年份四位原样透传S0- 或 /εS1分隔符吃掉S10-90 同字符S2月份补零输出S2- 或 /εS3第二个分隔符S30-90 同字符S5日期补零输出S50-9同字符S6日期第二位S6结束ε—终止这张表里有个细节值得停一下S1读到数字时输出的是0加上这个数字本身也就是一次转移输出两个字符。这在实现上完全合法——输出标签不必是单字符可以是一个串。很多人写代码的时候喜欢把输出限制成单个字符结果就是被迫多加状态来拆解白白膨胀了图的大小。允许输出串是控制状态数的一招实用技巧。还有S5到S6的那一步。为什么日期第二位不补零因为日期第二位已经是个位数字05的5就是原样。但如果用户输入的是2024-1-5月份和日期都只有一位那走S1 - S2的时候已经补了零S2之后直接遇到分隔符再走S3 - S5还是只处理一位。这套设计对一位或两位两种输入都成立靠的就是遇到分隔符就跳段的短路逻辑。3.3 第三步用代码把表变成可执行的东西下面是我自己手写的一个极简 FST不做最小化只做确定性构建目的是让读的人能看清数据结构长什么样。生产环境当然不该这么写但教学上这个版本最直白。from collections import defaultdict class FST: def __init__(self): # transitions[state][input_char] (next_state, output_str, weight) self.transitions defaultdict(dict) self.finals {} # state - 累积输出终止状态上的收尾输出 self.start 0 self._next_id 1 def new_state(self): s self._next_id self._next_id 1 return s def add_path(self, in_str, out_str, weight0): 把一条 输入串 - 输出串 的映射加入图共用已存在的前缀 state self.start # 关键输出延迟 —— 只在需要分叉的地方吐出输出 pending out_str for i, ch in enumerate(in_str): is_last (i len(in_str) - 1) if ch in self.transitions[state]: nxt, existing_out, w self.transitions[state][ch] # 已有弧把共同前缀输出留在弧上分歧部分下推 common _common_prefix(existing_out, pending) if common ! existing_out: self.transitions[state][ch] (nxt, common, w) # 把原本的输出重新挂到 nxt 的出边上简化处理 _push_down(self.transitions, nxt, existing_out[len(common):]) pending pending[len(common):] state nxt else: nxt self.new_state() if not is_last else self.new_state() if is_last: self.transitions[state][ch] (nxt, pending, weight) self.finals[nxt] else: self.transitions[state][ch] (nxt, , weight) state nxt pending def lookup(self, in_str): state self.start out [] for ch in in_str: if ch not in self.transitions[state]: return None nxt, o, _ self.transitions[state][ch] out.append(o) state nxt if state not in self.finals: return None out.append(self.finals[state]) return .join(out) def _common_prefix(a, b): n min(len(a), len(b)) i 0 while i n and a[i] b[i]: i 1 return a[:i] def _push_down(transitions, state, suffix): 把待输出的后缀沿路径下推简化版直接挂在第一条出弧上 if not suffix: return for ch, (nxt, o, w) in transitions[state].items(): transitions[state][ch] (nxt, suffix o, w) return跑一下fst FST() fst.add_path(2024-1-5, 20240105) fst.add_path(2024-01-05, 20240105) fst.add_path(2024/1/5, 20240105) print(fst.lookup(2024-1-5)) # 20240105 print(fst.lookup(2024/1/5)) # 20240105 print(fst.lookup(2024-02-30)) # None最后一行返回None是符合预期的——2024-02-30这条路径根本不在图里因为构建时只加了三条合法样例。这引出一个必须说清楚的点FST 只能识别你喂给它的东西它不是一个规则引擎。想让它处理任意合法日期你得把规则展开成状态而不是靠几条样例糊上去。上面这个 demo 只适合讲解机制。3.4 第四步验证、压缩与落盘功能跑通只是第一步。真正上线前还有三件事要做。第一是穷举验证。构造一批边界输入空串、超长串、只差一个字符的近似串、包含图外字符的串。每一条都要确认返回的是正确结果或者正确拒绝不能出现返回了一个看起来像那么回事但实际错误的结果。这类静默错误在 FST 场景下特别难查因为图走通了但输出错了程序不报错。第二是最小化。手写的图里一定有大量等价状态可以合并。合并之后图变小、缓存命中率上升、遍历更快。最小化的算法核心是不断把状态按出边签名分组签名相同的归为一类直到分组稳定。这个过程是纯离线计算不影响线上查询逻辑。第三是序列化。FST 一旦构建完成就是只读的所以最省内存的做法是把它按特定顺序排布成一段连续字节然后整个映射进内存查的时候直接按偏移量跳转完全不做对象分配。这也是为什么很多检索系统偏爱 FST——它天生适合内存映射冷启动快多进程共享同一份物理内存。4. 工程落地FST 的四个典型落点4.1 词典与词库的压缩索引这是 FST 最经典的用法。一个百万级词条的词典如果每条都存完整字符串光字符串本身就要占几十兆到上百兆再加上每个词挂的元数据词性、词频、释义偏移内存压力很大。用 FST 之后前缀和后缀都能共享。英文单词里-ing、-tion、-ness这类后缀重复率极高中文虽然没这么规整但地名、机构名里的市区有限公司同样高度重复。共享带来的压缩比通常在 5 到 20 倍之间取决于词表本身的重复度。加载完之后查一个词就是走 n 步每步一次数组下标访问速度快到可以忽略。元数据怎么挂常见做法是把词表按字典序排好每条元数据放在一个平行的数组里FST 上每个终止状态存一个整数下标指过去即可。这样 FST 只管词在不在、在哪具体内容交给外部数组职责清晰也方便单独更新元数据而不重建图。4.2 分词与形态还原中的规则表达中文分词器里有个环节叫词典匹配最朴素的实现是拿词典里的词去文本里逐个尝试。用 FST 之后可以把从某个位置开始能匹配到哪些词这件事变成一次图遍历从初始状态出发沿着文本字符一直走每走一步就检查当前状态是不是终止状态是的话就记录一个候选词。这个过程的复杂度只和能匹配上的最长前缀长度有关和词典总规模无关。文本里某个位置后面接的是生僻字走一步就断了立刻停下接的是常见组合就多走几步。这种自适应的特性让它在长文本上的表现非常稳。形态还原是另一个方向。英语的动词变位、名词复数德语的格变化阿拉伯语的词根派生这些规则的共同点是从一个词形到另一个词形中间经历一串可枚举的变化。用 FST 表达的好处是双向的——正向可以做词形生成给词根和语法特征产出词形反向可以做词形分析给词形产出一组可能的词根和特征。反向的时候因为可能有多条路径需要按权重排序取最可能的那个。4.3 输入法与拼写纠错里的模糊扩展输入法的核心是用户敲了一串按键我要给出猜他想打什么。这天然是个加权转换问题按键序列是输入串候选词是输出串每个候选带一个概率权重。FST 在这个场景下的价值在于它能同时表达多种变形规则。比如拼音输入里zh和z可以互通、n和l在部分方言里互通、前后鼻音可以混淆。这些规则不需要写成一堆 if-else而是直接在图上开分支——同一个状态上放两条不同标签的弧指向同一个目标状态读哪一个都行。当然这就破坏了确定性需要在构建时把这种可选编码成确定结构或者干脆用非确定性图配合权重搜索。拼写纠错同理。编辑距离的四种操作插入、删除、替换、换位对应到图上就是四种扩展方式每扩展一步累加一个惩罚权重。搜索的终止条件是累计权重超过阈值或者已到达深度上限这样能有效剪枝避免在全图上乱跑。4.4 和倒排索引、向量检索的配合方式有人会问现在向量检索这么火FST 还有用吗有用但角色变了。倒排索引解决的是文档里有没有这个词FST 解决的是这个词本身合不合法、它的前缀是什么、它的近似词有哪些。两者是上下游关系用户输入一个查询先用 FST 做拼写检查、前缀补全、同义词扩展产出一组规范化的查询词再丢给倒排索引去召回文档。少了前面这一步用户拼错一个字母就只能拿到零结果。和向量检索配合也是类似逻辑。向量检索擅长语义相近但对精确的专有名词、编号、代号往往不敏感甚至会把完全不同的两个编号判成相似。这时候用 FST 做一层精确匹配优先的兜底命中就直接返回没命中再走向量召回能显著减少答非所问的情况。5. 性能与内存调优时绕不开的几个参数5.1 状态数和弧数哪个才是真正的瓶颈构建完 FST 之后第一件事是看两个数字状态总数和弧总数。很多人只盯状态数其实弧数往往才是内存占用的主导因素因为每条弧都要存标签、目标状态偏移、输出、权重这几项。经验值是如果平均每个状态的出弧数超过 5就要警惕了说明图的分支结构偏碎可能有大量可以合并的状态。处理方法有两个方向一是把输出标签往深处推减少因为输出不同而被迫分开的状态二是把多个短词合并成一条长弧用输出串表达多个字符减少中间状态。另一个反直觉的点是图的绝对大小不如缓存局部性重要。一个 20MB 但访问模式高度聚集的 FST实际查询性能可能超过一个 10MB 但访问分散的实现。所以排布顺序很关键——把高频词对应的状态尽量放在相邻的字节区域能让 CPU 缓存发挥最大作用。5.2 构建耗时为什么要接受离线慢、线上快构建一个百万级词条的 FST包含确定化和最小化耗时从几秒到几分钟不等取决于实现质量。这个时间在线上是不可接受的所以标准做法是离线构建、线上只读。离线构建的工程要点是把词表先按字典序排好再喂给构建器这样能大幅减少中间状态的数量构建过程也更线性。如果词表是动态增长的不要每次插入都重建全图而是维护一个增量小图加一个全量主图查询时两边都查合并结果等到增量图积累到一定规模再合并回主图。5.3 内存映射与冷启动的实际收益把 FST 序列化成字节数组后用内存映射方式加载收益主要体现在两点一是进程启动时不需要反序列化直接把文件映射进来就能用冷启动时间从几百毫秒降到几毫秒二是多个进程可以共享同一份物理内存部署多实例时不额外占内存。代价是访问路径上的每个操作都不能做对象分配必须直接按偏移读字节。这意味着序列化的格式要精心设计字段对齐、变长编码、偏移量计算都要提前算清楚。这块的实现复杂度不低如果你只是做个中小规模的应用普通的内存结构可能更省心只有到了千万级词条、多实例部署的场景内存映射的收益才真正显现出来。6. 踩坑实录与排查清单6.1 输出错位最难查的一类静默 bug我碰到过最难受的一次问题症状是大部分词的查询结果正确但有零星几十个词返回的输出串多了一截或者少了一截。没有报错没有异常就是结果不对。查了大半天根因是输出标签在构建时没有推到正确的位置。具体来说当两个词共享前缀、但在某个分叉点之后输出不同的时候共享段的输出如果还留在前一条弧上那么走另一条路径的时候就会把这段输出也带出来。表现出来就是结果里混进了别的词的片段。排查方法很土但有效写个脚本随机采样一万个词逐个查询把结果和预期做比对把不一致的挑出来。然后针对每个不一致的词找它和词表里其他词的最长公共前缀看分叉点在哪检查分叉点前后的输出标签是否对称。只要这个检查做一遍问题基本都能定位。预防的办法是在构建完成后立刻做一次全量自检覆盖率 100%不要抽样。全量自检的耗时通常远小于构建本身性价比极高。6.2 状态爆炸为什么你的图比预想的大十倍状态爆炸通常有三个来源。第一个是输出冗余。上面说过了输出标签放错位置会导致本该合并的状态被迫分开。检查方法把全图的输出标签全部清空重新跑一次最小化看状态数下降多少。如果下降超过 30%说明输出的放置方式有问题。第二个是字符集过大。如果你的输入标签是完整的 Unicode 字符那每个状态的出边数量会非常恐怖。解决办法是做字符类编码——把功能等价的字符归为一类比如把所有数字归成一类所有汉字归成一类用类标签代替具体字符图的规模立刻下来。第三个是没有做后缀共享。普通前缀树只共享前缀FST 还能共享后缀这是它比 Trie 强的地方。如果你的实现只做了确定化没做最小化那后缀就全浪费了。确认一下最小化步骤有没有真的执行很多时候是配置里关掉了。6.3 常见问题速查症状高概率原因处理动作查询返回 None 但词明明在词表里构建时该路径未标记终止状态检查add_path最后一步是否设置 final输出多了或少了几个字符输出标签位置错误全量比对 检查分叉点输出内存占用远超预期未做最小化或字符集未归类开启最小化对字符做类编码构建时间长得离谱词表未排序插入顺序随机先按字典序排序再构建前缀遍历返回结果顺序乱权重未设置或全为 0给每条路径配置合理权重冷启动慢每次启动都反序列化改内存映射或做常驻服务并发查询偶发结果错乱共享结构被写操作污染FST 构建后必须只读写操作走副本这张表里我想特别强调最后一条。FST 的只读属性不是建议是硬约束。一旦图构建完成任何并发写都会导致状态不一致而且这种不一致是概率性的、难以复现的。我见过有人为了支持热更新在图结构上直接打补丁结果上线后偶发返回错误的词排查了两天才定位到是并发写的问题。正确做法是构建新图、原子替换引用旧图等引用计数归零后自然回收。再说一个实操上的小技巧调试 FST 的时候别急着写复杂代码先写一个把图导出成文本的函数把状态、弧、标签全部打印出来。对着文本眼看一遍很多逻辑错误肉眼就能发现比单步调试快得多。图小的时候尤其有效几十个状态的图印出来铺在桌上看十分钟就能找出问题在哪。图大了再上工具。最后分享一个我在实际项目里养成的习惯每次改完 FST 的构建逻辑先拿一个 500 条左右的小词表跑一遍把导出结果和自己的预期逐行对照确认无误再换全量数据。全量构建动辄几分钟用小样本做快速验证能把迭代周期从分钟压到秒这个习惯帮我省下的时间相当可观。