上一篇【第17篇】查询加速跳表与倒排链求交的艺术下一篇【第19篇】编辑距离有限状态机拼写纠错的底层武器摘要很多人上编译原理课时觉得有限状态机FSM就是考试题工作后八辈子用不上。我当年也这么想直到写搜索引擎才发现分词器、拼写纠错、正则匹配背后全是 FSM 在干活。这一篇先用红绿灯、自动售货机这种生活比喻把 FSM 讲成人话再手画一张状态转移表最后点明它在搜索里的两大主战场把文本切成词的分词器以及容忍拼写错误的模糊匹配。下一篇的编辑距离纠错就是踩在它肩膀上的。一、FSM 是啥用生活比喻说人话有限状态机名字吓人本质特简单一个东西有若干个状态收到不同输入就从一个状态跳到另一个状态跳转规则是固定的。红绿灯就是最直观的 FSM【红绿灯的状态转移】 状态: 红 ──(时间到)──▶ 绿 ──(时间到)──▶ 黄 ──(时间到)──▶ 红 输入: 只有一个时间到信号 规律: 红→绿→黄→红, 永不乱套自动售货机更说明问题你有投币按按钮两种输入状态在待机→已投币→出货之间跳。【自动售货机 FSM】 待机 --投币-- 已投币 --按可乐-- 出货 --取货-- 待机 待机 --按可乐-- 待机(没投币, 不动) 已投币 --投币-- 已投币(余额增加)看明白没FSM 三件套状态集合、输入集合、转移规则。给定当前状态和输入下一状态是唯一确定的。这就是有限的含义状态数有限、规则有限。二、状态转移表把 FSM 画成表把上面的转移规则写成一张表程序员和机器都好用。行是当前状态列是输入格子是下一状态。【自动售货机 状态转移表】 投币 按可乐 取货 待机 已投币 待机 待机 已投币 已投币 出货 已投币 出货 出货 出货 待机搜索引擎里的 FSM 通常还带产出进入某状态或经过某条边时吐出一个词、记一个标记。分词器就是这么干的扫描字符流遇到词的边界就从收集字符状态跳到吐词状态。三、FSM 在搜索的第一战场分词回想我们前几篇用的SimpleAnalyzer按空格和标点切词。那其实是一个极简 FSM在单词内状态和分隔符状态间跳遇到分隔符就把攒下的字符当成一个词吐出来。【英文分词 FSM简化】 状态A(收集词) --字母/数字-- 状态A (继续攒) 状态A(收集词) --非字母数字-- 吐出一个词 → 状态B(跳过分隔) 状态B(跳过分隔) --非字母数字-- 状态B 状态B(跳过分隔) --字母/数字-- 状态A (开始攒新词)中文分词更复杂没有空格但骨架一样用状态机扫描字流结合词典判断这几个字凑成一个词。工业分词器本质是一个带词典的 FSMLucene 的 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}publicListStringtokenize(Stringtext){ListStringtokensnewArrayList();StatestateState.START;StringBuilderbufnewStringBuilder();for(charc:text.toCharArray()){booleanisDigitCharacter.isDigit(c);switch(state){caseSTART:if(isDigit){buf.append(c);stateState.IN_NUMBER;}break;caseIN_NUMBER:if(isDigit){buf.append(c);// 继续攒}else{tokens.add(buf.toString());// 边界到了, 吐词buf.setLength(0);stateState.START;}break;}}if(stateState.IN_NUMBERbuf.length()0){tokens.add(buf.toString());// 收尾}returntokens;}}// 测试: tokenize(价格299元 库存50) - [299, 50]这段代码的switch就是状态转移表的直接翻译START收到数字跳IN_NUMBERIN_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篇】编辑距离有限状态机拼写纠错的底层武器