有限状态转换器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。对于abc，a、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：终止

转移表这样写（只列关键行，ε表示空输出）：

这张表里有个细节值得停一下：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, weight=0): """把一条 输入串 -> 输出串 的映射加入图，共用已存在的前缀""" 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 常见问题速查

这张表里我想特别强调最后一条。FST 的只读属性不是建议，是硬约束。一旦图构建完成，任何并发写都会导致状态不一致，而且这种不一致是概率性的、难以复现的。我见过有人为了"支持热更新"，在图结构上直接打补丁，结果上线后偶发返回错误的词，排查了两天才定位到是并发写的问题。正确做法是构建新图、原子替换引用，旧图等引用计数归零后自然回收。

再说一个实操上的小技巧：调试 FST 的时候，别急着写复杂代码，先写一个把图导出成文本的函数，把状态、弧、标签全部打印出来。对着文本眼看一遍，很多逻辑错误肉眼就能发现，比单步调试快得多。图小的时候尤其有效，几十个状态的图，印出来铺在桌上看，十分钟就能找出问题在哪。图大了再上工具。

最后分享一个我在实际项目里养成的习惯：每次改完 FST 的构建逻辑，先拿一个 500 条左右的小词表跑一遍，把导出结果和自己的预期逐行对照，确认无误再换全量数据。全量构建动辄几分钟，用小样本做快速验证能把迭代周期从分钟压到秒，这个习惯帮我省下的时间相当可观。