上一篇【第17篇】查询加速：跳表与倒排链求交的艺术
下一篇【第19篇】编辑距离有限状态机：拼写纠错的底层武器
摘要
很多人上编译原理课时觉得有限状态机（FSM）就是考试题，工作后八辈子用不上。我当年也这么想，直到写搜索引擎才发现：分词器、拼写纠错、正则匹配，背后全是 FSM 在干活。这一篇先用红绿灯、自动售货机这种生活比喻把 FSM 讲成人话，再手画一张状态转移表，最后点明它在搜索里的两大主战场：把文本切成词的分词器，以及容忍拼写错误的模糊匹配。下一篇的编辑距离纠错，就是踩在它肩膀上的。
一、FSM 是啥：用生活比喻说人话
有限状态机，名字吓人，本质特简单：一个东西有若干个"状态"，收到不同"输入"就从一个状态跳到另一个状态，跳转规则是固定的。
红绿灯就是最直观的 FSM：
【红绿灯的状态转移】 状态: 红 ──(时间到)──▶ 绿 ──(时间到)──▶ 黄 ──(时间到)──▶ 红 输入: 只有一个"时间到"信号 规律: 红→绿→黄→红, 永不乱套自动售货机更说明问题：你有"投币""按按钮"两种输入，状态在"待机→已投币→出货"之间跳。
【自动售货机 FSM】 待机 --投币--> 已投币 --按可乐--> 出货 --取货--> 待机 待机 --按可乐--> 待机(没投币, 不动) 已投币 --投币--> 已投币(余额增加)看明白没？FSM 三件套：状态集合、输入集合、转移规则。给定当前状态和输入，下一状态是唯一确定的。这就是"有限"的含义：状态数有限、规则有限。
二、状态转移表：把 FSM 画成表
把上面的转移规则写成一张表，程序员和机器都好用。行是当前状态，列是输入，格子是下一状态。
【自动售货机 状态转移表】 投币 按可乐 取货 待机 已投币 待机 待机 已投币 已投币 出货 已投币 出货 出货 出货 待机搜索引擎里的 FSM 通常还带"产出"：进入某状态（或经过某条边）时吐出一个词、记一个标记。分词器就是这么干的：扫描字符流，遇到"词的边界"就从"收集字符"状态跳到"吐词"状态。
三、FSM 在搜索的第一战场：分词
回想我们前几篇用的SimpleAnalyzer，按空格和标点切词。那其实是一个极简 FSM：在"单词内"状态和"分隔符"状态间跳，遇到分隔符就把攒下的字符当成一个词吐出来。
【英文分词 FSM（简化）】 状态A(收集词) --字母/数字--> 状态A (继续攒) 状态A(收集词) --非字母数字--> 吐出一个词 → 状态B(跳过分隔) 状态B(跳过分隔) --非字母数字--> 状态B 状态B(跳过分隔) --字母/数字--> 状态A (开始攒新词)中文分词更复杂（没有空格），但骨架一样：用状态机扫描字流，结合词典判断"这几个字凑成一个词"。工业分词器本质是一个带词典的 FSM，Lucene 的 Analyzer 流水线里每个 TokenFilter 也可以看成状态处理的一环。你写自己的 Analyzer 时，脑子里想的就是"我现在在哪个状态、看到这个字该跳哪"。
四、FSM 在搜索的第二战场：模糊匹配
FSM 第二个大用场是"模式匹配"。正则表达式引擎底层就是 NFA/DFA（非确定/确定有限自动机），本质都是 FSM。搜索引擎里，模糊匹配（比如"以什么前缀开头"“匹配某种模式”）同样能用 FSM 表达。
【匹配"以 '手机' 开头"的 FSM】 起始 --手--> S1 --机--> 命中(后续任意字符都留在命中) S1 之前收到非"手" → 失败更妙的是，后面要讲的编辑距离纠错，可以把"允许错 k 个字符的所有字符串"直接建成一个 FSM，查询时顺着 FSM 走，走得到的就是可纠错的候选。这就把"模糊"这件事变成了"在自动机里走一遍"，比暴力枚举快得多。
五、动手画一个：识别"数字词"的 FSM
光说不练假把式，写个小 FSM 识别连续数字并当成词吐出来。
importjava.util.*;/** 一个迷你 FSM：从字符流里抠出连续数字当作"数字词" */publicclassNumberTokenizer{enumState{START,IN_NUMBER}publicList<String>tokenize(Stringtext){List<String>tokens=newArrayList<>();Statestate=State.START;StringBuilderbuf=newStringBuilder();for(charc:text.toCharArray()){booleanisDigit=Character.isDigit(c);switch(state){caseSTART:if(isDigit){buf.append(c);state=State.IN_NUMBER;}break;caseIN_NUMBER:if(isDigit){buf.append(c);// 继续攒}else{tokens.add(buf.toString());// 边界到了, 吐词buf.setLength(0);state=State.START;}break;}}if(state==State.IN_NUMBER&&buf.length()>0){tokens.add(buf.toString());// 收尾}returntokens;}}// 测试: tokenize("价格299元 库存50") -> ["299", "50"]这段代码的switch就是状态转移表的直接翻译：START收到数字跳IN_NUMBER，IN_NUMBER收到非数字就吐词跳回START。FSA 落地就是这么朴实。
六、为什么搜索引擎离不开 FSM
回到全文视角，FSM 在搜索引擎里扮演的是"确定性处理器"：同样的输入永远走出同样的路径，可预测、可测试、可优化。分词要保证"同一个字符串永远切成同样的词"，模糊匹配要保证"容错规则一致"。这种确定性，正是 FSM 的强项。
【FSM 在搜索引擎里的位置】 建索引: 文本 → [分词FSM] → 词项流 → 倒排 查 query: 文本 → [分词FSM] → 词项 → 查倒排 纠错: 错词 → [编辑距离FSM] → 候选正确词下一篇，我们把 FSM 推到更刺激的用处：编辑距离纠错。你会看到，把"允许错几次"建成一个自动机，拼写纠错能从暴力枚举的灾难复杂度里被解救出来。
七、NFA 与 DFA：同一个意思的两种写法
聊深一点，FSM 分两种。NFA（非确定有限自动机）允许一个状态遇到同一个输入"有多个去处"，甚至能"不消耗输入就跳转"（ε 转移），表达灵活。DFA（确定有限自动机）则规定每个状态对每个输入只有唯一去向，没有歧义，运行更快但可能状态数爆炸。
正则表达式引擎通常是先把正则转成 NFA，再（按需）转成 DFA 来执行。分词器、纠错自动机也在这个谱系里。我们手写版用的是"确定型"的状态机（switch 语句，一个输入一个去处），最简单也最好调试。理解 NFA/DFA 的取舍，你再看 Lucene 的 TokenStream 状态流转会觉得格外顺。
八、为什么正则匹配有时很慢
有个反直觉的点：写得不好的正则能让匹配慢到卡死。原因是某些正则（带嵌套量词如(a+)+）会构造出指数级路径的 NFA，回溯时组合爆炸。这提醒我们，FSM 虽强，表达式的写法直接决定它的复杂度。搜索引擎里的查询解析、分词规则，都得避免这种"回溯地狱"。把规则写成严格的状态机，而不是泛泛的正则，往往更稳更可预测。
九、FSM 给你的一层直觉
学完这一篇，我希望你带走一个直觉：很多"看似智能"的文本处理，底层都是"状态 + 转移"的确定性机器。分词是，纠错是，甚至你每天用的输入框联想也是。当你把问题建模成 FSM，它就从"玄学"变成了"画张状态表就能验证"的 engineering。下一篇的编辑距离纠错，正是用这台机器把模糊匹配变得可计算。
本篇小结
有限状态机不是考试玩具，它由"状态、输入、转移规则"三件套组成，红绿灯、售货机都是它的生活化身。在搜索引擎里 FSM 干两件大事：分词器靠状态跳转切词，模糊匹配靠自动机走通模式；后面编辑距离纠错同样建立在 FSM 上。动手写的数字分词器，本质就是状态转移表的直接翻译。下一篇，我们把 FSM 用在编辑距离纠错这个硬骨头上。
上一篇【第17篇】查询加速：跳表与倒排链求交的艺术
下一篇【第19篇】编辑距离有限状态机：拼写纠错的底层武器
