1. 从“最大概率”四个字说起中文分词到底在分什么很多人第一次接触中文分词脑子里冒出来的问题是“这有什么难的不就是把句子切开吗”。真上手写一遍才会发现切分这件事本身没有唯一答案。拿“最大概率中文分词”这个标题来说如果让一个不懂算法的人来切他可能切成“最大 / 概率 / 中文 / 分词”也可能切成“最大概率 / 中文 / 分词”甚至“最 / 大概率 / 中文 / 分词”。三种切法单看字面都说得通但只有一种在统计意义上最合理。分词算法要做的就是从这些候选切法里挑出那个“最合理”的。“最大概率”这三个字点明了这类方法的核心思路把分词看成一个概率问题。一句话的每一种切分方式都对应一个概率值概率最大的那种切法就是最终结果。这个思路听起来简单但它背后牵扯到几个必须想清楚的问题——概率从哪来、怎么算、算的时候会不会爆炸、遇到没见过的词怎么办。这几个问题串起来就是整个最大概率分词算法的骨架。我写这篇文章的出发点很直接网上讲中文分词的资料不少但大多停在“用现成库调个接口”的层面真正把最大概率分词的推导过程、工程实现、踩坑细节讲透的不多。所以下面我会从原理一路讲到能跑起来的代码中间穿插我自己在实现时踩过的坑。适合两类人看一类是想搞明白分词底层原理的学生或转行者另一类是想自己动手实现一个分词器、不想只会调库的开发者。读完你应该能独立写出一个可用的最大概率分词器并且知道它在什么情况下会失效、怎么补救。2. 把一句话拆成一张图最大概率分词的数学骨架2.1 为什么是“概率最大”而不是“词数最少”在讲数学之前先回答一个容易被忽略的问题为什么选概率最大而不是选切出来的词最少、或者词最长早期确实有人用“最大匹配”的思路也就是每次尽量匹配最长的词。但最大匹配有个致命问题它只看局部不看全局。比如“研究生命的起源”最大匹配可能切成“研究生 / 命 / 的 / 起源”因为“研究生”是个词。但正确切法应该是“研究 / 生命 / 的 / 起源”。最大匹配在这里翻车是因为它贪心地选了局部最长的词牺牲了整句的合理性。最大概率分词换了个思路不贪心而是把所有可能的切法都列出来算每种切法的整体概率选最高的那个。这就把局部决策变成了全局决策。代价是计算量变大但换来的是准确率明显提升。这个取舍在工程上很常见——用可接受的计算成本换更好的结果。2.2 用有向无环图表示所有切分可能一句话的所有切分方式可以用一张有向无环图DAG来表示。图里的每个节点是句子中的一个位置从0到nn是句子长度每条边代表一个词。比如“最大概率”这四个字位置0到位置2有一条边代表“最大”位置0到位置4有一条边代表“最大概率”位置2到位置4有一条边代表“概率”。从位置0走到位置n的每一条路径就是一种完整的切分方案。用图来表示的好处是所有切分方案被统一组织起来了接下来只需要在这张图上找一条“最优路径”。这里的“最优”就是概率最大。所以最大概率分词的本质是在DAG上求一条概率最大的路径。这个问题可以用动态规划在O(n²)的时间内解决n是句子长度实际用起来非常快。2.3 概率怎么算从联合概率到二元语言模型现在到了最关键的一步一条路径的概率怎么算假设一种切分方案切出了词序列 w₁, w₂, ..., wₖ那这个方案的概率就是 P(w₁, w₂, ..., wₖ)。直接算这个联合概率是不现实的因为词的组合是无穷的。所以要做近似最常见的是用二元语言模型BigramP(w₁, w₂, ..., wₖ) ≈ P(w₁) × P(w₂|w₁) × P(w₃|w₂) × ... × P(wₖ|wₖ₋₁)也就是说每个词出现的概率只和它前面一个词有关。这个假设当然不完美但它把参数量从指数级降到了可控范围。实际工程里二元模型已经能给出相当不错的分词效果再往上用三元模型提升有限但计算和存储成本涨得很快所以二元是性价比最高的选择。这里有个细节要注意P(w₁) 是句首词的概率通常用 P(w₁|BOS) 表示BOS是句首标记。同理句尾要加EOS标记。这些边界处理不做好的话句首句尾的词概率会算错进而影响整句的切分结果。2.4 取对数把连乘变成连加避免数值下溢上面那个公式是一串概率相乘。每个概率都是小于1的数一句话十几个词乘下来结果会小到浮点数表示不了直接变成0。这就是数值下溢。解决办法是取对数把连乘变成连加log P(路径) log P(w₁|BOS) log P(w₂|w₁) ... log P(EOS|wₖ)对数函数是单调递增的所以概率最大的路径取对数后也是最大的。这样一来动态规划里比较的就是对数值之和既避免了下溢计算也更快加法比乘法快。这个技巧在所有基于概率的序列模型里都会用到是必须掌握的工程常识。3. 动态规划求解从后往前推的那一步3.1 状态定义与转移方程在DAG上求最优路径标准做法是动态规划。定义 dp[i] 为从位置 i 到句尾的最优路径的对数概率那么转移方程是dp[i] max over j ( log P(word(i,j)) dp[j] )其中 word(i,j) 是从位置 i 到位置 j 的子串如果这个子串是个词的话。dp[n] 0句尾。最终答案是 dp[0]。这个方程的意思是从位置 i 出发枚举所有以 i 开头的词选一个词加上它后面那段的最优值取最大的那个。为什么从后往前推而不是从前往后其实两个方向都可以但从后往前有个好处dp[i] 只依赖 dp[j]j i所以计算 dp[i] 时它依赖的所有值都已经算好了不需要递归直接倒着循环一遍就行。从前往后则需要记录前驱稍微麻烦一点。工程实现里从后往前更顺手。3.2 记录路径光有分数不够还要知道怎么切dp数组只存了最优分数但我们需要的是具体的切分方案。所以还要一个额外的数组来记录“在位置 i 处最优的那个词结束在哪个位置”。通常叫 route 数组或者 next 数组。route[i] j 表示从 i 出发的最优选择是词 word(i,j)。算完 dp 之后从位置0开始顺着 route 一路跳就得到了完整的切分路径。这个“分数数组路径数组”的组合是动态规划求具体方案的标配。很多人第一次写的时候只算了分数忘了记路径最后只能拿到一个概率值拿不到切分结果还得回头重写。3.3 一个手算例子把“最大概率”跑一遍拿“最大概率”举例假设词典和概率如下数值是编的只为演示词概率对数最-3.0最大-2.5最大概率-4.0大-3.5大概-3.2概率-2.8位置0到4。dp[4]0。算dp[3]位置3是“率”只有“率”这个词假设dp[3] logP(率) dp[4] -3.0。算dp[2]位置2是“概”有“概率”到位置4dp[2] logP(概率) dp[4] -2.8。算dp[1]位置1是“大”有“大”到2、“大概”到3、“大概率”到4假设有这个词。分别算logP(大)dp[2] -3.5 (-2.8) -6.3logP(大概)dp[3] -3.2 (-3.0) -6.2logP(大概率)dp[4] -3.8。最大是-3.8所以route[1]4。算dp[0]有“最”到1、“最大”到2、“最大概率”到4。logP(最)dp[1] -3.0 (-3.8) -6.8logP(最大)dp[2] -2.5 (-2.8) -5.3logP(最大概率)dp[4] -4.0。最大是-4.0route[0]4。所以最优路径是“最大概率”整词。这个例子说明即使“最大概率”这个词本身概率不高但如果它作为整体出现可能比拆开更优。4. 概率从哪来词典构建与平滑处理4.1 词典和概率表是分不开的最大概率分词需要两样东西一个词典哪些是词一张概率表每个词的概率、每个词对的条件概率。这两样东西通常从大规模语料里统计出来。流程是先拿一个已经分好词的语料库统计每个词出现的次数除以总词数得到词概率再统计相邻词对出现的次数除以第一个词的出现次数得到条件概率。这里有个容易踩的坑语料库的分词标准要和你的应用场景一致。比如新闻语料和口语语料的分词习惯差别很大用新闻语料训练出来的模型去切口语文本效果会打折扣。所以选语料的时候要想清楚你的目标场景是什么。4.2 未登录词词典里没有的词怎么办真实文本里总有词典里没有的词比如新词、人名、地名、专业术语。这些叫未登录词OOV。最大概率分词遇到未登录词时如果直接跳过那个位置就没有边路径可能断掉。常见处理办法是给单字一个兜底概率保证任何位置都至少有一条边每个字单独成词。这样路径一定存在只是切出来的结果可能不理想。更进阶的做法是加一个“新词发现”模块用统计指标比如互信息、左右邻接熵从语料里自动发现可能的新词补进词典。但这属于另一个话题了本文不展开。实际工程里单字兜底加上一个还不错的词典已经能覆盖大部分场景。4.3 平滑没见过不代表不可能即使有兜底还是会有词对在训练语料里没见过。比如“概率”后面跟“分布”很常见但“概率”后面跟某个生僻词可能一次都没出现过。这时候条件概率是0取对数变成负无穷整条路径就废了。所以必须做平滑给没见过的词对一个很小的非零概率。最简单的平滑是加一平滑Add-one分子加1分母加词表大小。但它对高频词影响太大实际用得更多的是Kneser-Ney或者简单点的插值平滑。工程上如果不想搞太复杂可以用一个固定的小概率值兜底比如所有零概率词对统一给一个1e-8。效果不如正规平滑但实现简单对分词这种任务够用了。5. 动手实现一个能跑的最大概率分词器5.1 整体结构设计我习惯把分词器拆成三个模块词典加载、DAG构建、动态规划求解。词典加载负责把词和概率读进内存用字典存查询O(1)。DAG构建负责对输入句子生成所有可能的词边。动态规划负责在DAG上找最优路径。三个模块职责清晰方便单独测试和替换。数据结构上词典用一个dictkey是词value是词频或概率。条件概率用一个嵌套dict外层key是前一个词内层key是当前词。为了省内存条件概率可以只存对数概率反正后面都是加法。5.2 核心代码逐段拆解先看DAG构建。对句子每个起始位置i从i开始往后扩展只要当前子串在词典里就记一条边。这里有个优化如果子串长度超过词典里最长词的长度就可以停了不用继续扩展。这个剪枝能省不少时间。def build_dag(sentence, word_dict, max_word_len): dag {} n len(sentence) for i in range(n): dag[i] [] for j in range(i 1, min(i max_word_len, n) 1): word sentence[i:j] if word in word_dict: dag[i].append(j) if not dag[i]: dag[i].append(i 1) # 单字兜底 return dag然后是动态规划。从后往前算dp同时记route。import math def max_prob_segment(sentence, word_dict, bigram_prob, max_word_len): dag build_dag(sentence, word_dict, max_word_len) n len(sentence) dp [0.0] * (n 1) route [0] * (n 1) dp[n] 0.0 for i in range(n - 1, -1, -1): best_score -float(inf) best_j i 1 for j in dag[i]: word sentence[i:j] # 这里简化处理只用词概率实际应结合前一个词 score math.log(word_dict.get(word, 1e-8)) dp[j] if score best_score: best_score score best_j j dp[i] best_score route[i] best_j # 回溯路径 result [] i 0 while i n: j route[i] result.append(sentence[i:j]) i j return result上面这段代码为了讲清楚主干把二元条件概率简化成了一元词概率。真正要用二元模型的话dp的状态需要带上“前一个词是什么”状态空间会变大。工程上常见的折中是先用一元模型切一遍再对结果做局部调整。或者用维特比算法在词格上跑状态是“当前位置当前词”这样能正确处理二元依赖。维特比的实现比上面这段复杂一些但思路是一样的都是动态规划。5.3 实测效果与性能我用一段几百字的新闻文本测过纯Python实现词典大概十万词切一千字大概几十毫秒。瓶颈主要在DAG构建时的字符串切片和字典查询。如果换成C或者用Trie树优化词典查询速度还能再快一个数量级。对于大部分离线处理场景Python版本完全够用。准确率方面在标准测试集上最大概率分词配合好的词典F1值能到95%以上。错误主要集中在未登录词和歧义切分上。比如“乒乓球拍卖完了”正确切法是“乒乓球 / 拍卖 / 完 / 了”但算法可能切成“乒乓球拍 / 卖 / 完 / 了”。这种歧义靠一元或二元模型很难完全解决需要更高阶的模型或者外部知识。6. 那些文档里不会写的坑6.1 词典里最长词的长度必须提前算好build_dag里用到了max_word_len这个值必须提前从词典里统计出来。我见过有人图省事写死一个值比如10结果词典里有个12字的词永远切不出来。这个bug很隐蔽因为大部分句子不受影响只有碰到那个长词才出错。正确做法是加载词典时顺便算一下最长词长度。6.2 对数概率的底数要统一log可以是自然对数、以2为底、以10为底只要全程统一就行。但如果你从不同来源拿到的概率表底数不一样混着用就全乱了。我建议统一用自然对数Python的math.log默认就是省得换算。6.3 空字符串和纯标点的处理输入是空字符串时上面的代码会返回空列表没问题。但输入是纯标点比如“。。。”时如果词典里没有标点会走单字兜底每个标点单独成词。这通常不是想要的结果实际应用里一般会把连续标点合并成一个token。这个逻辑要单独加不能指望分词算法自己处理。6.4 内存条件概率表可能非常大二元条件概率表的规模是词表大小的平方级别。十万词的词表理论上有一百亿个词对虽然大部分是零但存起来还是很占内存。实际做法是只存出现过的词对用稀疏存储。即使这样大语料训出来的表也可能几个G。如果内存吃紧可以退回到一元模型或者用剪枝只保留高频词对。7. 从最大概率往外延伸还能怎么优化最大概率分词是个很好的起点但它不是终点。如果想让分词效果更好有几个方向可以走。一是换更强的语言模型比如三元甚至神经网络语言模型但计算成本会上去。二是引入词性信息用词性标注和分词联合建模互相约束。三是针对特定领域做词典和概率的领域适配比如医疗、法律这些专业领域通用词典效果很差必须用领域语料重新统计。还有一个容易被忽视的点是解码时的后处理。比如数字、英文、日期这些模式化的串用规则处理比统计模型更靠谱。实际系统里通常是统计模型加规则后处理两者结合才能达到生产可用的水平。我自己在实际项目里的体会是最大概率分词的价值不仅在于它能用更在于它把分词的框架讲清楚了。理解了DAG、动态规划、语言模型这三件套再去看更复杂的序列标注方法比如基于CRF或BiLSTM的分词会发现底层思路是相通的只是打分函数换了。所以把这个基础打牢后面学什么都快。
1. 从“最大概率”四个字说起中文分词到底在分什么很多人第一次接触中文分词脑子里冒出来的问题是“这有什么难的不就是把句子切开吗”。真上手写一遍才会发现切分这件事本身没有唯一答案。拿“最大概率中文分词”这个标题来说如果让一个不懂算法的人来切他可能切成“最大 / 概率 / 中文 / 分词”也可能切成“最大概率 / 中文 / 分词”甚至“最 / 大概率 / 中文 / 分词”。三种切法单看字面都说得通但只有一种在统计意义上最合理。分词算法要做的就是从这些候选切法里挑出那个“最合理”的。“最大概率”这三个字点明了这类方法的核心思路把分词看成一个概率问题。一句话的每一种切分方式都对应一个概率值概率最大的那种切法就是最终结果。这个思路听起来简单但它背后牵扯到几个必须想清楚的问题——概率从哪来、怎么算、算的时候会不会爆炸、遇到没见过的词怎么办。这几个问题串起来就是整个最大概率分词算法的骨架。我写这篇文章的出发点很直接网上讲中文分词的资料不少但大多停在“用现成库调个接口”的层面真正把最大概率分词的推导过程、工程实现、踩坑细节讲透的不多。所以下面我会从原理一路讲到能跑起来的代码中间穿插我自己在实现时踩过的坑。适合两类人看一类是想搞明白分词底层原理的学生或转行者另一类是想自己动手实现一个分词器、不想只会调库的开发者。读完你应该能独立写出一个可用的最大概率分词器并且知道它在什么情况下会失效、怎么补救。2. 把一句话拆成一张图最大概率分词的数学骨架2.1 为什么是“概率最大”而不是“词数最少”在讲数学之前先回答一个容易被忽略的问题为什么选概率最大而不是选切出来的词最少、或者词最长早期确实有人用“最大匹配”的思路也就是每次尽量匹配最长的词。但最大匹配有个致命问题它只看局部不看全局。比如“研究生命的起源”最大匹配可能切成“研究生 / 命 / 的 / 起源”因为“研究生”是个词。但正确切法应该是“研究 / 生命 / 的 / 起源”。最大匹配在这里翻车是因为它贪心地选了局部最长的词牺牲了整句的合理性。最大概率分词换了个思路不贪心而是把所有可能的切法都列出来算每种切法的整体概率选最高的那个。这就把局部决策变成了全局决策。代价是计算量变大但换来的是准确率明显提升。这个取舍在工程上很常见——用可接受的计算成本换更好的结果。2.2 用有向无环图表示所有切分可能一句话的所有切分方式可以用一张有向无环图DAG来表示。图里的每个节点是句子中的一个位置从0到nn是句子长度每条边代表一个词。比如“最大概率”这四个字位置0到位置2有一条边代表“最大”位置0到位置4有一条边代表“最大概率”位置2到位置4有一条边代表“概率”。从位置0走到位置n的每一条路径就是一种完整的切分方案。用图来表示的好处是所有切分方案被统一组织起来了接下来只需要在这张图上找一条“最优路径”。这里的“最优”就是概率最大。所以最大概率分词的本质是在DAG上求一条概率最大的路径。这个问题可以用动态规划在O(n²)的时间内解决n是句子长度实际用起来非常快。2.3 概率怎么算从联合概率到二元语言模型现在到了最关键的一步一条路径的概率怎么算假设一种切分方案切出了词序列 w₁, w₂, ..., wₖ那这个方案的概率就是 P(w₁, w₂, ..., wₖ)。直接算这个联合概率是不现实的因为词的组合是无穷的。所以要做近似最常见的是用二元语言模型BigramP(w₁, w₂, ..., wₖ) ≈ P(w₁) × P(w₂|w₁) × P(w₃|w₂) × ... × P(wₖ|wₖ₋₁)也就是说每个词出现的概率只和它前面一个词有关。这个假设当然不完美但它把参数量从指数级降到了可控范围。实际工程里二元模型已经能给出相当不错的分词效果再往上用三元模型提升有限但计算和存储成本涨得很快所以二元是性价比最高的选择。这里有个细节要注意P(w₁) 是句首词的概率通常用 P(w₁|BOS) 表示BOS是句首标记。同理句尾要加EOS标记。这些边界处理不做好的话句首句尾的词概率会算错进而影响整句的切分结果。2.4 取对数把连乘变成连加避免数值下溢上面那个公式是一串概率相乘。每个概率都是小于1的数一句话十几个词乘下来结果会小到浮点数表示不了直接变成0。这就是数值下溢。解决办法是取对数把连乘变成连加log P(路径) log P(w₁|BOS) log P(w₂|w₁) ... log P(EOS|wₖ)对数函数是单调递增的所以概率最大的路径取对数后也是最大的。这样一来动态规划里比较的就是对数值之和既避免了下溢计算也更快加法比乘法快。这个技巧在所有基于概率的序列模型里都会用到是必须掌握的工程常识。3. 动态规划求解从后往前推的那一步3.1 状态定义与转移方程在DAG上求最优路径标准做法是动态规划。定义 dp[i] 为从位置 i 到句尾的最优路径的对数概率那么转移方程是dp[i] max over j ( log P(word(i,j)) dp[j] )其中 word(i,j) 是从位置 i 到位置 j 的子串如果这个子串是个词的话。dp[n] 0句尾。最终答案是 dp[0]。这个方程的意思是从位置 i 出发枚举所有以 i 开头的词选一个词加上它后面那段的最优值取最大的那个。为什么从后往前推而不是从前往后其实两个方向都可以但从后往前有个好处dp[i] 只依赖 dp[j]j i所以计算 dp[i] 时它依赖的所有值都已经算好了不需要递归直接倒着循环一遍就行。从前往后则需要记录前驱稍微麻烦一点。工程实现里从后往前更顺手。3.2 记录路径光有分数不够还要知道怎么切dp数组只存了最优分数但我们需要的是具体的切分方案。所以还要一个额外的数组来记录“在位置 i 处最优的那个词结束在哪个位置”。通常叫 route 数组或者 next 数组。route[i] j 表示从 i 出发的最优选择是词 word(i,j)。算完 dp 之后从位置0开始顺着 route 一路跳就得到了完整的切分路径。这个“分数数组路径数组”的组合是动态规划求具体方案的标配。很多人第一次写的时候只算了分数忘了记路径最后只能拿到一个概率值拿不到切分结果还得回头重写。3.3 一个手算例子把“最大概率”跑一遍拿“最大概率”举例假设词典和概率如下数值是编的只为演示词概率对数最-3.0最大-2.5最大概率-4.0大-3.5大概-3.2概率-2.8位置0到4。dp[4]0。算dp[3]位置3是“率”只有“率”这个词假设dp[3] logP(率) dp[4] -3.0。算dp[2]位置2是“概”有“概率”到位置4dp[2] logP(概率) dp[4] -2.8。算dp[1]位置1是“大”有“大”到2、“大概”到3、“大概率”到4假设有这个词。分别算logP(大)dp[2] -3.5 (-2.8) -6.3logP(大概)dp[3] -3.2 (-3.0) -6.2logP(大概率)dp[4] -3.8。最大是-3.8所以route[1]4。算dp[0]有“最”到1、“最大”到2、“最大概率”到4。logP(最)dp[1] -3.0 (-3.8) -6.8logP(最大)dp[2] -2.5 (-2.8) -5.3logP(最大概率)dp[4] -4.0。最大是-4.0route[0]4。所以最优路径是“最大概率”整词。这个例子说明即使“最大概率”这个词本身概率不高但如果它作为整体出现可能比拆开更优。4. 概率从哪来词典构建与平滑处理4.1 词典和概率表是分不开的最大概率分词需要两样东西一个词典哪些是词一张概率表每个词的概率、每个词对的条件概率。这两样东西通常从大规模语料里统计出来。流程是先拿一个已经分好词的语料库统计每个词出现的次数除以总词数得到词概率再统计相邻词对出现的次数除以第一个词的出现次数得到条件概率。这里有个容易踩的坑语料库的分词标准要和你的应用场景一致。比如新闻语料和口语语料的分词习惯差别很大用新闻语料训练出来的模型去切口语文本效果会打折扣。所以选语料的时候要想清楚你的目标场景是什么。4.2 未登录词词典里没有的词怎么办真实文本里总有词典里没有的词比如新词、人名、地名、专业术语。这些叫未登录词OOV。最大概率分词遇到未登录词时如果直接跳过那个位置就没有边路径可能断掉。常见处理办法是给单字一个兜底概率保证任何位置都至少有一条边每个字单独成词。这样路径一定存在只是切出来的结果可能不理想。更进阶的做法是加一个“新词发现”模块用统计指标比如互信息、左右邻接熵从语料里自动发现可能的新词补进词典。但这属于另一个话题了本文不展开。实际工程里单字兜底加上一个还不错的词典已经能覆盖大部分场景。4.3 平滑没见过不代表不可能即使有兜底还是会有词对在训练语料里没见过。比如“概率”后面跟“分布”很常见但“概率”后面跟某个生僻词可能一次都没出现过。这时候条件概率是0取对数变成负无穷整条路径就废了。所以必须做平滑给没见过的词对一个很小的非零概率。最简单的平滑是加一平滑Add-one分子加1分母加词表大小。但它对高频词影响太大实际用得更多的是Kneser-Ney或者简单点的插值平滑。工程上如果不想搞太复杂可以用一个固定的小概率值兜底比如所有零概率词对统一给一个1e-8。效果不如正规平滑但实现简单对分词这种任务够用了。5. 动手实现一个能跑的最大概率分词器5.1 整体结构设计我习惯把分词器拆成三个模块词典加载、DAG构建、动态规划求解。词典加载负责把词和概率读进内存用字典存查询O(1)。DAG构建负责对输入句子生成所有可能的词边。动态规划负责在DAG上找最优路径。三个模块职责清晰方便单独测试和替换。数据结构上词典用一个dictkey是词value是词频或概率。条件概率用一个嵌套dict外层key是前一个词内层key是当前词。为了省内存条件概率可以只存对数概率反正后面都是加法。5.2 核心代码逐段拆解先看DAG构建。对句子每个起始位置i从i开始往后扩展只要当前子串在词典里就记一条边。这里有个优化如果子串长度超过词典里最长词的长度就可以停了不用继续扩展。这个剪枝能省不少时间。def build_dag(sentence, word_dict, max_word_len): dag {} n len(sentence) for i in range(n): dag[i] [] for j in range(i 1, min(i max_word_len, n) 1): word sentence[i:j] if word in word_dict: dag[i].append(j) if not dag[i]: dag[i].append(i 1) # 单字兜底 return dag然后是动态规划。从后往前算dp同时记route。import math def max_prob_segment(sentence, word_dict, bigram_prob, max_word_len): dag build_dag(sentence, word_dict, max_word_len) n len(sentence) dp [0.0] * (n 1) route [0] * (n 1) dp[n] 0.0 for i in range(n - 1, -1, -1): best_score -float(inf) best_j i 1 for j in dag[i]: word sentence[i:j] # 这里简化处理只用词概率实际应结合前一个词 score math.log(word_dict.get(word, 1e-8)) dp[j] if score best_score: best_score score best_j j dp[i] best_score route[i] best_j # 回溯路径 result [] i 0 while i n: j route[i] result.append(sentence[i:j]) i j return result上面这段代码为了讲清楚主干把二元条件概率简化成了一元词概率。真正要用二元模型的话dp的状态需要带上“前一个词是什么”状态空间会变大。工程上常见的折中是先用一元模型切一遍再对结果做局部调整。或者用维特比算法在词格上跑状态是“当前位置当前词”这样能正确处理二元依赖。维特比的实现比上面这段复杂一些但思路是一样的都是动态规划。5.3 实测效果与性能我用一段几百字的新闻文本测过纯Python实现词典大概十万词切一千字大概几十毫秒。瓶颈主要在DAG构建时的字符串切片和字典查询。如果换成C或者用Trie树优化词典查询速度还能再快一个数量级。对于大部分离线处理场景Python版本完全够用。准确率方面在标准测试集上最大概率分词配合好的词典F1值能到95%以上。错误主要集中在未登录词和歧义切分上。比如“乒乓球拍卖完了”正确切法是“乒乓球 / 拍卖 / 完 / 了”但算法可能切成“乒乓球拍 / 卖 / 完 / 了”。这种歧义靠一元或二元模型很难完全解决需要更高阶的模型或者外部知识。6. 那些文档里不会写的坑6.1 词典里最长词的长度必须提前算好build_dag里用到了max_word_len这个值必须提前从词典里统计出来。我见过有人图省事写死一个值比如10结果词典里有个12字的词永远切不出来。这个bug很隐蔽因为大部分句子不受影响只有碰到那个长词才出错。正确做法是加载词典时顺便算一下最长词长度。6.2 对数概率的底数要统一log可以是自然对数、以2为底、以10为底只要全程统一就行。但如果你从不同来源拿到的概率表底数不一样混着用就全乱了。我建议统一用自然对数Python的math.log默认就是省得换算。6.3 空字符串和纯标点的处理输入是空字符串时上面的代码会返回空列表没问题。但输入是纯标点比如“。。。”时如果词典里没有标点会走单字兜底每个标点单独成词。这通常不是想要的结果实际应用里一般会把连续标点合并成一个token。这个逻辑要单独加不能指望分词算法自己处理。6.4 内存条件概率表可能非常大二元条件概率表的规模是词表大小的平方级别。十万词的词表理论上有一百亿个词对虽然大部分是零但存起来还是很占内存。实际做法是只存出现过的词对用稀疏存储。即使这样大语料训出来的表也可能几个G。如果内存吃紧可以退回到一元模型或者用剪枝只保留高频词对。7. 从最大概率往外延伸还能怎么优化最大概率分词是个很好的起点但它不是终点。如果想让分词效果更好有几个方向可以走。一是换更强的语言模型比如三元甚至神经网络语言模型但计算成本会上去。二是引入词性信息用词性标注和分词联合建模互相约束。三是针对特定领域做词典和概率的领域适配比如医疗、法律这些专业领域通用词典效果很差必须用领域语料重新统计。还有一个容易被忽视的点是解码时的后处理。比如数字、英文、日期这些模式化的串用规则处理比统计模型更靠谱。实际系统里通常是统计模型加规则后处理两者结合才能达到生产可用的水平。我自己在实际项目里的体会是最大概率分词的价值不仅在于它能用更在于它把分词的框架讲清楚了。理解了DAG、动态规划、语言模型这三件套再去看更复杂的序列标注方法比如基于CRF或BiLSTM的分词会发现底层思路是相通的只是打分函数换了。所以把这个基础打牢后面学什么都快。
