中文分词核心解析：最长匹配、双数组Trie与Viterbi消歧

简介：南京邮电大学自然语言处理课程实验一的实验报告文档，面向正在学习中文分词与句法分析的高校学生及自学者，用于完成词典分词、二元语法分词两项验证性实验并整理实验记录。压缩包内仅含1个doc文件，大小约232KB，内容涵盖实验目的、环境配置、原理说明与结果填写区域，涉及HanLP的segment、parse指令操作、前向最长匹配、后向最长匹配与双向最长匹配的差异对比、DoubleArrayTrieSegment和AhoCorasickDoubleArrayTrieSegment词典分词，以及基于pyhanlp的Python代码实现与输出分析。已有429人学习，适合作为课堂实验的对照模板与代码参考，帮助读者快速理解分词算法差异、依存句法输出格式及常见环境路径问题，减少从零摸索的时间。

1. 词典分词的分歧点：为什么"结婚的和尚未结婚的"能切出两种结果

同一份词典、同一句话，正向扫一遍得到"结婚/的/和尚/未/结婚/的"，反向扫一遍却得到"结婚/的/和/尚未/结婚/的"。两条结果词数一样、单字词一样多，谁也不算错——这正是自然语言处理里最容易被忽略的一件事：分词器并不会"理解"句子，它只是把一套确定的贪心规则或打分规则跑完，然后输出那个规则认为最优的切法。歧义不是模型没训好，而是规则本身在"和尚"和"和/尚未"之间没有足够信息做判断。搞懂这句话为什么能切出两种结果，等于同时搞懂了匹配方向、词典覆盖、路径打分这三个决定中文分词质量的关键变量，后面所有的双数组 Trie、二元语法、Viterbi 解码，都是在给这三个变量补信息。

2. 三种最长匹配：同一份词典为什么切出两个答案

最长匹配是整个中文分词体系里最朴素的一层，朴素到很多人跳过它直接去学统计模型，结果在做未登录词、停用词、自定义词典时反复翻车。它的核心只有一句话：从当前位置出发，在词典里找能匹配上的最长那个词，切下来，指针往前推。区别全在"从哪一端出发"和"两个方向打架时听谁的"。把这个想清楚，后面看任何分词器的词典层都不会再糊涂。

2.1 前向最长匹配：贪心匹配的确定性与它的盲区

前向最长匹配从句子左端出发，每次在词典里试最长的前缀，试到命中就切走。它的行为完全确定，没有任何随机性，给定词典和最大词长，输出永远一样。这份确定性是优点也是缺点：它从左往右"先到先得"，一旦某一步切错，错误会向右传染，后面的切分全部建立在错误前缀之上。

def forward_max_match(text, max_len, wordset): """前向最长匹配 text: 待切分字符串 max_len: 词典中最长词的长度，限制每次试探的上界 wordset: 词典，set 结构保证 O(1) 命中判断 """ result, i, n = [], 0, len(text) while i < n: match = None # 从最长可能长度往短试，第一个命中就是最长匹配 for L in range(min(max_len, n - i), 0, -1): piece = text[i:i + L] if piece in wordset: match = piece break if match is None: # 词典里连单字都没有，退化为单字输出 match = text[i] result.append(match) i += len(match) # 指针按命中长度整体前移 return result

max_len是个容易被忽视的参数：它决定内层循环的试探次数，直接决定分词复杂度上限。取词典里最长词的长度是精确值，取 5 到 7 是常见工程折中，因为中文绝大多数词不超过四字，把上界压下来比优化字符串比较更有效。wordset用集合而不是列表，是因为这一步会被调用 n 次乘以 max_len 次，一次 O(n) 的查找会把这个算法从近似线性拖成平方级。

用它跑"结婚的和尚未结婚的"：i=0处试"结婚的"失败、试"结婚"命中，切走两字；i=2处只剩"的"能命中；i=3处试"和尚未"失败、"和尚"命中——盲区就在这里，词典里同时存在"和尚"和"和"，前向贪心优先选了更长的"和尚"，把"尚未"拆成了"未"。这不是 bug，是贪心的必然结果：它只保证"当前位置切出来的词最长"，不保证"整句最优"。

2.2 后向最长匹配：反向贪心为什么常常更贴近人的直觉

后向最长匹配把方向反过来，从句子右端往左找最长后缀。实现的镜像关系很直接，指针从末尾开始，每次取text[j-L:j]，命中后j减去词长，最后把结果逆序。

def backward_max_match(text, max_len, wordset): """后向最长匹配，逻辑与前向镜像，结果需要反转""" result, j = [], len(text) while j > 0: match = None for L in range(min(max_len, j), 0, -1): piece = text[j - L:j] if piece in wordset: match = piece break if match is None: match = text[j - 1] result.append(match) j -= len(match) return result[::-1] # 反向收集，最后翻回来

同一句话跑后向：j=9处先命中"的"，j=8处试"和尚未结婚"、"尚未结婚"、"未结婚"、"结婚"，最后命中"结婚"，j=6处试到长度 2 时命中"尚未"，j=4处命中"和"，j=3处命中"的"，j=2处命中"结婚"。结果是"结婚/的/和/尚未/结婚/的"。

为什么反向常常更准？中文的偏正结构、动宾结构大多是"修饰语在前、中心词在后"，句尾往往是信息落脚点，从右往左匹配时，先确定的是结构上更"实"的那一端，前面剩下的碎片更容易被正确归并。反过来，前向从左往右时，句子开头的虚词、连词最容易抢先吃掉一个字，把后面的词切碎。这条经验在汉语里成立得相当普遍，但它是统计倾向而不是定理，英文、日文就没有同样的性质，所以别把它当普适规律。

2.3 双向最长匹配：真正在干活的是那条裁决规则

双向最长匹配的做法是：前向跑一遍、后向跑一遍，拿两个候选做比较，选一个更好的。很多人以为它"更聪明"，其实它自己不做任何匹配，全部价值在裁决规则上。常见的裁决顺序是三层：

def bidirectional_match(text, max_len, wordset): f = forward_max_match(text, max_len, wordset) b = backward_max_match(text, max_len, wordset) # 第一层：词数少的赢，切得越少通常越合理 if len(f) != len(b): return f if len(f) < len(b) else b # 第二层：词数相同，单字词少的赢，单字词是切分碎片的信号 sf = sum(1 for w in f if len(w) == 1) sb = sum(1 for w in b if len(w) == 1) if sf != sb: return f if sf < sb else b # 第三层：仍然平局，按实现习惯返回后向结果 return b

回到那句"结婚的和尚未结婚的"：前向 6 个词、后向 6 个词，第一层平局；前向有"的、未、的"三个单字词，后向有"的、和、的"三个单字词，第二层还是平局；于是落到第三层，按习惯返回后向结果。这就是为什么实验里双向的输出和后向完全一致——在这个句子上，双向匹配并没有比后向多做任何事，它只是没能在平局时给出更好的答案。

这个细节值得记住，因为它解释了双向匹配的能力边界：它只能在两个候选之间选，候选本身错了，选择再合理也没用。要真正消掉"和尚/和+尚未"这种歧义，必须引入词典之外的信息——词频、词性、上下文概率，也就是下一层要讲的统计模型。词典层能保证"切出来的每一段都是词"，但保证不了"这一整句是最可能的切法"。

顺带说一个实操细节：max_len在前后向两个函数里必须取同一个值，否则两个候选的可比性就没了。我见过把前向的max_len设成词典最大值、后向设成 4 的写法，结果双向裁决退化成随机挑一个。这类参数不一致的问题在自研分词器里非常常见，它不会报错，只会让效果莫名其妙地差一截。

3. 双数组 Trie：词典压成两个整型数组后，查询靠什么只走一趟

朴素 Trie 的节点是对象，每个节点挂一个哈希表存子节点，指针满天飞，缓存极不友好。中文词典动辄几十万词条，构建出来的 Trie 在内存里是一大片离散对象，每次查询都要跟着指针跳好几次，跳一次就是一次缓存未命中。双数组 Trie 要解决的就是这个问题：把所有节点压进两个整型数组，让一次状态转移变成两次数组下标访问。

3.1 base 和 check：把 Trie 的边编码成整数运算

双数组的核心约定只有一条：状态s读到字符c（先映射成整数code），下一个状态是base[s] + c，再用check数组验证这条边确实属于s。base存的是每个状态的"基址"，check存的是"这个位置是被哪个父状态占用的"，相当于反向指针。

def dat_transition(base, check, state, code): """双数组 Trie 的状态转移 base[s]: 状态 s 的基址 check[t]: 位置 t 被哪个父状态占用，用于冲突校验 code: 字符映射出的整数（通常取字符编码或字母表序号） 返回下一个状态；返回 -1 表示这条边不存在 """ nxt = base[state] + code if 0 <= nxt < len(check) and check[nxt] == state: return nxt # check 对上，说明这条边真实存在 return -1 # 位置越界或 check 不匹配，转移失败

为什么这样能 work？因为构造阶段给每个状态挑base值时，会保证它的所有子节点落在尚未被占用的位置上，然后把这些位置的check全部写成父状态编号。于是"父状态 + 字符"唯一确定一个位置，而"这个位置属于谁"又能通过check反查。冲突不可能发生，因为构造时就避开了；误判也不可能发生，因为check会拦下所有非法跳转。整个结构的信息密度比指针 Trie 高得多，两个int数组连续存放，一次查询的几次跳转大概率都落在同一批缓存行里。

代价在构造端：每加一个状态，都要从候选基址开始试探，找到一组不冲突的位置。这个过程在词典很大时会变慢，所以工程上一般离线构建好、序列化到文件，运行时直接内存映射。这也是为什么那份核心词典路径下的文件是二进制结构而不是纯文本——纯文本那份是给人看的，实际查询用另一份。

3.2 最长匹配搜索器：一次前向扫描，边扫边记候选

光有状态转移还不能分词，还要有"从某个位置出发，找出所有能匹配的词，取最长的那个"。这一步由最长匹配搜索器完成，它的行为是：从起点开始沿base/check一直往下走，每走到一个词尾标记就记下一个候选，走到走不动为止，然后回吐其中最长的那个，指针按这个长度整体前移。

这个策略有个容易忽略的性质：它是前向的、互不重叠的、贪心的。同一段文本里，一旦某个长词被接受，它内部包含的短词就不会再被报告。这个性质决定了它适合做什么、不适合做什么。

停用词替换就是它的典型用法。任务是把一段文本里出现的所有停用词整体替换成占位符，要求命中之间不能重叠、不能漏掉夹在中间的正常文本。

def replace_stopwords(text, replacement, trie): """基于双数组 Trie 的停用词替换 trie: 装载停用词的双数组 Trie replacement: 命中后替换成的占位符 """ offset, out = 0, [] # longest_matches 从左到右产出互不重叠的最长命中，元素为 (起点, 长度) for begin, length in trie.longest_matches(text): if begin > offset: # 命中之间夹着的正常文本原样保留 out.append(text[offset:begin]) out.append(replacement) # 命中区间整体替换 offset = begin + length # 游标推到命中末尾之后 if offset < len(text): # 末尾剩余部分不能丢 out.append(text[offset:]) return ''.join(out)

三个变量构成一个小状态机：begin是本次命中的起点，length是命中长度，offset是"已经处理到哪"。begin > offset这个判断是整段代码的正确性关键——它保证两段命中之间的文本被原样搬过去，如果写成begin >= offset或者漏掉这个分支，正常文字就会整段丢失。最后那个if offset < len(text)同理，漏了它，文本尾部会凭空少一截。这两个丢字问题在自研实现里出现频率极高，而且因为输出依然是合法字符串，肉眼很难第一时间发现。

3.3 AC 自动机版本为什么在这段文本上退化成单字

同一段春分文本，换成另一类分词器，输出变成了一个字符一个元素的长列表，词性全是 null。这个现象乍看像"算法失效"，其实是两类组件的定位差异。

双数组 Trie 解决的是"从固定起点往下走能走多远"，它没有失败回退机制，一旦某个位置往下走不通，只能退回起点重新开始。AC 自动机在 Trie 之上加了 fail 指针：当某个分支走不通时，不是退回起点，而是跳到"最长的、同时也是某个模式后缀的前缀"那个状态继续走。于是它能在一次扫描中找出所有模式的所有出现位置，包括互相重叠的那些。

这两个能力对应两类任务：

至于那段文本为什么全切成单字，机制上的解释很清楚：AC 版组件是一个通用的多模式匹配器，它的职责是"你给词表，我来匹配"，因此实例化时必须显式地把词典灌进去；而双数组版分词器是内置了默认核心词典的分词器，路径由全局配置指定，构造时自动加载。前者没喂词表，匹配器里空无一物，每个字符找不到任何模式，自然只能逐字吐出。这不是算法坏了，是依赖没注入——一个典型到不能再典型的初始化顺序问题。

这也顺带解释了为什么停用词替换用双数组而不是 AC：替换要求命中之间互不重叠（否则"商品和服务"里"和"被替换两次就会破坏结构），最长匹配天然满足这个约束；而敏感词扫描恰恰需要重叠命中，"半角全角混排"这类变形要靠全量扫描才抓得住。选哪个结构，取决于你要的是"切分"还是"枚举"。

4. 二元语法分词：五行语料训练出来的模型，凭什么判定"商品和服务"

词典层的天花板是"切出来的每一段都是词"，它无法回答"哪种切法更可能"。要回答这个问题，必须给词与词之间的搭配关系打一个分。二元语法做的就是这件事：它不看整句，只看相邻两个词一起出现的频率，用这个频率去衡量一条切分路径的合理性。整个过程没有任何"理解"，全是计数和取对数。

4.1 训练代码在做什么：把句子拆成词，再数相邻词对

训练语料只有三行，每行是已经切好、用空格分隔的句子。训练器要做的事分三步：把每行解析成一个词序列、给每个词打上词性标签、扫一遍统计一元频次和二元频次。

def train_bigram(corpus_path, model_path): # 1) 每行按空格切开，转成词序列 sents = CorpusLoader.convert2SentenceList(corpus_path) # 2) 统一打标签：这次只关心分词，词性用同一个占位符 for sent in sents: for word in sent: word.setLabel("n") maker = NatureDictionaryMaker() # 统计器 maker.compute(sents) # 扫一遍，累加一元和二元频次 maker.saveTxtTo(model_path) # 落盘

setLabel("n")这一行是全篇最容易被跳过、也最容易被误解的地方。它把所有词的词性强行设成同一个值，原因是这次训练的目标只有分词：如果不统一，统计器会按词性分别建立一元和二元表，模型文件会膨胀好几倍，而分词阶段根本用不上这些区分。副作用是这份模型拿去跑词性标注会全部输出同一个标签——它不是坏了，是它本来就只学了分词这一件事。

4.2 三个产物文件各自负责什么

跑完训练，目录下会出现三个文件，名字相近但职责完全不同：

拿那三行语料手算一遍就能对上：商品出现在第 1、2 行，频次 2；和出现在第 1、3 行（第 2 行是"和服"，不是"和"），频次 2。这跟实验里查到的两个 2 完全吻合。二元表里商品 和、和 服务、服务 和、和 货币各出现 1 次，商品 和服出现 1 次。这五个计数就是模型全部的"知识"。

加载模型的方式是直接改全局配置里的两个路径，一个指向一元文件，一个指向二元文件：

Config.CoreDictionaryPath = model_path + ".txt" # 一元：词 + 词频 Config.BiGramDictionaryPath = model_path + ".ngram.txt" # 二元：相邻词对频次 segmenter = ViterbiSegment() # 构造时把两份词典读进内存 print(segmenter.seg("商品和服务"))

这里有一个必须讲清的时序问题：ViterbiSegment()在构造的那一刻就把两份词典加载进内存了，之后再改Config里的路径，改的只是一个没人再读的字符串，已经构造好的实例完全不受影响。所以配置注入必须写在实例化之前，而且一元和二元两个路径必须一起改。只改一元不改二元，会出现"词表是新的、词对概率还是旧的"这种半新半旧状态，分词结果会以一种很难解释的方式偏离预期。

4.3 Viterbi 在词图上找最大概率路径：为什么不能贪心

有了词频和词对频次，分词就变成了一个图论问题：把句子每个字符位置当作一个节点，词典里每个能匹配的词当作一条从i到j的边，分词就是从 0 走到 n 的一条路径。每条边的权重由概率决定，我们要找权重和最大的那条路径。

关键在于权重不是固定的。在二元语法下，一个词的概率依赖它的前一个词，也就是说"这条边值多少分"取决于"你是怎么走到这条边起点的"。贪心在这里直接失效：局部看起来概率最高的词，可能把后面的路带进一个很低的概率区间。必须用动态规划，把"以位置 i 结尾、且最后一个词是 w"作为状态，逐位置递推。

import math def viterbi_bigram(sentence, dag, unigram, bigram, total, V=1): """在词图上跑一阶马尔可夫 DP dag[i]: 从位置 i 出发的所有 (词, 结束位置) unigram: 词 -> 频次 bigram: "词A 词B" -> 频次 total: 一元频次总和，用于归一化 V: 词表大小，加一平滑的分母修正项 """ n = len(sentence) NEG = float("-inf") best = [(NEG, -1, None)] * (n + 1) # (累计得分, 上一词起点, 当前词) best[0] = (0.0, -1, None) for i in range(n): if best[i][0] == NEG: continue # 这个位置不可达，跳过 for word, j in dag[i]: prev = best[i][2] # 走到 i 时最后落下的那个词 if prev is None: # 句首，退化成一元概率 p = unigram.get(word, 1) / total else: pair = prev + " " + word # 加一平滑：没见过不代表不可能，只是概率极低 p = (bigram.get(pair, 0) + 1) / (unigram.get(prev, 1) + V) cand = best[i][0] + math.log(p) # 概率连乘取对数变连加 if cand > best[j][0]: # 更优则覆盖，同时记下来路 best[j] = (cand, i, word) # 从末尾回溯出整条路径（此处略去回溯细节，逻辑是顺着 prev 指针倒推） return best[n]

三个设计点值得单独说。第一是取对数：路径概率是各边概率的连乘，几十个词乘下来会下溢成 0，取对数把连乘变成连加，数值上稳定得多，而且单调性不变，最大路径不受影响。第二是加一平滑：商品 和服这对在语料里出现过，商品 和也出现过，但实际文本里必然有大量没见过的词对，直接取 0 会让整条路径概率归零，加一给它留了一条极窄的活路。第三是回溯：DP 只算出"到每个位置的最大得分"，还要靠best[i][1]记下的"上一词起点"从末尾倒推，才能把路径还原成词序列。

拿"商品和服务"验证一下：词典里有"商品、和、和服、服务、货币、物美价廉"。可能的路径有商品/和/服务和商品/和服/务（后者要求词典里有"务"，一般没有），所以主要竞争在商品/和/服务与商品/和服/…之间。语料里商品 和的频次是 1，而商品 和服的频次也是 1，看起来打平，但后一条路径在"和服"之后要继续切"务"，而"务"没有二元搭配记录，平滑后的概率极低，整条路径得分被拉下去。最终商品/和/服务胜出。这就是统计模型比词典层多出来的那点能力：它不保证语法正确，但它用"哪条路走过更多次"这种朴素证据，把明显别扭的切法压下去。

5. 避坑与排查：五条血泪记录

这一节记录的是我在复现这套流程时反复撞上的坑。它们几乎都不是算法问题，全是环境、编码、注入顺序这类"外围"问题，但每一个都能让人在错误方向上排查半天。

5.1 编码类：读文件报 gbk 解码失败

现象：读取停用词表或语料时抛UnicodeDecodeError: 'gbk' codec can't decode byte 0x90 in position 2519，明明文件在编辑器里看着一切正常。

原因：open()不传encoding时会用系统默认编码，中文 Windows 上是 gbk。停用词表这类文件基本都是 UTF-8 存的，用 gbk 去解 UTF-8 的多字节序列，遇到不合法的字节组合就炸。

解决：所有文本读取一律显式写encoding='utf-8'。别依赖默认值，代码换一台机器结果就变。写完顺手在文件头上加一行注释标明编码，省得下一个人再踩。

5.2 注入类：换了模型路径但分词结果完全没变

现象：明明把配置里的词典路径改成了自己训练的小模型，跑出来的分词结果和改之前一模一样。

原因：分词器实例在构造时就把词典读进内存了，构造之后再改全局配置只是一次无人读取的赋值。更隐蔽的情况是只改了一元路径没改二元路径，实例加载的是"新词表 + 旧词对表"，结果既不像新模型也不像旧模型。

解决：把配置赋值集中在实例化之前，一元、二元两个路径成对修改，并且在实例化后立刻查一次词频做自检——查不到预期词就说明路径没生效，比对着分词结果猜要快得多。

5.3 状态类：关掉词性后，同一进程里再也拿不到词性

现象：前面为了输出干净，把词性显示关掉了；后面需要看标注结果，怎么改都还是不带词性。

原因：那个开关是进程级的全局静态状态，不是实例属性。它一改，之后所有分词器输出都不带词性，且不会自动恢复。

解决：把这类全局开关当成"进程启动参数"对待，在脚本开头集中设置一次，中途不改。确实需要切换时，显式改回去再继续，别指望它自己复位。多线程场景下更要小心，它没有任何隔离。

5.4 丢字类：停用词替换后文本短了一截

现象：替换结果整体通顺，但读起来少了几个字，对照原文才发现两处命中之间的文字被吞了。

原因：游标推进逻辑写错。要么漏掉"命中之间夹着的文本原样输出"这一支，要么末尾剩余部分没有兜底，要么begin和offset的比较写成了>=导致相邻命中之间被跳过。

解决：把offset的语义固定成"已消费到的位置"，每次命中先判断begin > offset才拷贝间隔，最后无条件补上text[offset:]。写完拿一段没有停用词的纯文本跑一遍，输出必须和输入完全相等——这个自检能一次抓出所有边界错误。

5.5 依赖类：AC 版分词器把整句切成单字

现象：同样的文本、同样的调用方式，一类分词器正常切词，另一类逐字输出，词性全是 null。

原因：通用多模式匹配器不负责加载默认词典，必须显式把词表灌进去；没灌，匹配器里空无一物，每个字符都找不到模式，只能逐字吐出。

解决：用这类组件前先确认词典是否已注入，注入后用一个必然命中的词做冒烟测试。凡是"看起来算法失效"的现象，先排查依赖是否到位，再怀疑算法本身，顺序反了会浪费大量时间。

6. 设计取舍：词典兜底、统计消歧，还是两个都要

把这套流程拆到底，会发现它其实是三层结构在叠加：词典层保证"切出来的每一段都是词"，统计层负责"在多种合法切法里挑最可能的那个"，后处理层（词性、停用词、实体）负责把结果整理成下游能用的形态。三层各有明确的能力边界，谁也替代不了谁。

真正值得琢磨的取舍是：词典层和统计层要不要同时留着。只留词典，未登录词一出现就退化成单字，专有名词密集的文本会碎成渣；只留统计，训练语料覆盖不到的词对概率极低，模型会把明明合理的切法打下去，而且没法通过加词快速修正。工程上的通行做法是两者都在：词典给统计层提供候选词图（哪些边存在），统计层给词图提供权重（哪条路更优），后处理再按业务需要追加自定义词、停用词、实体规则。

想验证自己的分词器到底哪一层出了问题，可以构造一组小对照集，用两个指标量化：切分总词数、单字词占比。同一批句子分别跑前向、后向、双向、二元语法，如果双向和后向结果高度重合，说明裁决规则基本没起作用，问题在上游词典覆盖；如果二元语法的单字词占比反而比双向高，多半是语料太小、平滑参数把未登录词压得太狠。

我最初做这套实验时，把双向匹配的结果当成"标准答案"去对比，看到它和后向完全一样还以为代码写错了，翻来覆去查了两小时才发现是平局时返回了后向——算法没错，是我对裁决规则的理解错了。从那以后我每次改分词相关代码，都会先用一句已知歧义的短句做冒烟测试，把前向、后向、双向三条结果并排打出来，确认差异符合预期再往下走。这个习惯帮我省掉的排查时间，远比写测试本身花的时间多。希望帮到你。

本文还有配套的精品资源，点击获取