最长匹配每一步都选当前最长词，却可能把后半句切成未知字符。本文把词典装进 Trie，从字符串末尾向前展开动态规划状态，以“未知字符最少、词数最少”为双重目标，给出 Python 完整实现、路径还原和反例测试，说明局部选择为何不能替代全局比较。
看到“研究生命起源”，从左往右最长匹配会先拿走“研究生”，剩下“命起源”。如果词典没有单独的“命”，算法只能把它当未知字符；选择较短的“研究”，反而可以接上“生命”和“起源”。这个四字交界处，是检验分词算法是否只会贪心的好样本。
画面一：Trie 负责枚举，不负责决定
词典中有大量共享前缀。若从每个位置尝试每个词，匹配成本会重复；Trie 把相同前缀合并成路径。从位置 i 出发沿字符向下走，每遇到词尾就得到一个候选切分终点。Trie 回答“有哪些词能从这里开始”，但选择哪一个仍需全局目标。
本文的目标按字典序比较两个量：先最小化未知字符数，再最小化总词数。这样一条完全由词典覆盖但词稍多的路径，优先于含未知字符的短路径。若两个指标都相同，再按切分序列字典序稳定决胜，保证多次运行结果一致。
画面二：从终点倒着点亮格子
令 dp[i] 表示后缀 text[i:] 的最优结果，包括代价 (未知字符数, 词数) 和切分列表。dp[n] 是空后缀，代价为 (0,0)。计算 dp[i] 时有两类边：
- 把当前单个字符当未知项，转移到
dp[i+1]，未知数加一、词数加一。 - 沿 Trie 找到每个词尾
j，把该词接到dp[j+1]前，未知数不增、词数加一。
因为所有转移都走向更大的下标，从右向左计算时依赖已经就绪。
from dataclasses import dataclass, field
@dataclass
class TrieNode:
children: dict = field(default_factory=dict)
is_word: bool = False
def build_trie(words):
root = TrieNode()
for word in words:
if not word:
raise ValueError("词典不能包含空词")
node = root
for char in word:
node = node.children.setdefault(char, TrieNode())
node.is_word = True
return root
def best_split(text, words):
root = build_trie(words)
n = len(text)
# 每项为 ((未知字符数, 词数), 切分元组)
dp = [None] * (n + 1)
dp[n] = ((0, 0), ())
for i in range(n - 1, -1, -1):
suffix_cost, suffix_tokens = dp[i + 1]
best = (
(suffix_cost[0] + 1, suffix_cost[1] + 1),
(text[i],) + suffix_tokens,
)
node = root
for j in range(i, n):
node = node.children.get(text[j])
if node is None:
break
if node.is_word:
tail_cost, tail_tokens = dp[j + 1]
candidate = (
(tail_cost[0], tail_cost[1] + 1),
(text[i:j + 1],) + tail_tokens,
)
if candidate < best:
best = candidate
dp[i] = best
return dp[0]
if __name__ == "__main__":
dictionary = {
"研究", "研究生", "生命", "起源"}
cost, tokens = best_split("研究生命起源", dictionary)
print(cost, "/".join(tokens))
assert cost == (0, 3)
assert tokens == ("研究", "生命", "起源")
cost2, tokens2 = best_split("研究X", dictionary)
assert cost2 == (1, 2)
assert tokens2 == ("研究", "X")
print("tokenizer tests passed")
画面三：把反例逐格还原
终点格 dp[6] 是空。向左计算“起源”时，Trie 能走到完整词，因此这段代价为 (0,1)。到“生命起源”开头时，“生命”接上已有结果得到 (0,2)。回到下标 0，候选“研究生”之后是未知“命”再接“起源”，代价至少 (1,3)；候选“研究”之后直接接 dp[2]，得到 (0,3)。比较第一维后，算法选择后者，无需任何特判。
这也是动态规划优于最长匹配的核心：最长匹配只看到当前词长，dp 把后缀质量带回了当前位置。若业务认为词频更重要，可以把代价换成负对数概率；若需要返回多个候选，可在每个格子保留前 k 条路径，形成简化的 beam search。
复杂度透视
设文本长度为 n，词典最长词长为 L。每个起点最多沿 Trie 走 L 步，时间复杂度为 O(nL)；Trie 空间为词典所有字符总数，dp 保存切分元组时最坏可能产生 O(n^2) 复制。生产实现可只保存下一跳和代价，将空间降到 O(n)，最后再沿指针还原一次路径。
边界条件
- 空文本返回零代价和空切分，这是递推基座。
- 空词会制造不前进的转移，必须拒绝。
- 全部字符不在词典时，每个字符都作为未知项，未知数等于文本长度。
- Unicode 字符按 Python 码点迭代；表情组合和规范化等更复杂文本应先统一规范。
- 词典中重复词不影响 Trie，但加载阶段可先去重减少工作。
常见错误
只保存最少词数会偏爱一个超长未知片段；把所有未知连续字符合并又不计长度，会让未知内容几乎没有惩罚；从左到右填写却读取尚未计算的后缀，会得到偶发空值；路径相同代价时不设稳定规则，会受字典集合迭代顺序影响。目标函数必须先于代码被写清楚。
可复制测试
保存为 tokenizer.py 并执行 python tokenizer.py。第一行应显示 (0, 3) 研究/生命/起源，最后一行是 tokenizer tests passed。删除词典中的“生命”，预期结果包含一个未知“命”；加入完整词“研究生命起源”，预期词数降为一且未知数仍为零。
把路径复制改成下一跳
示例把完整切分元组放进每个 dp 格，代码直观，但长文本会重复复制后缀。更节省的实现让 dp[i] 只保存代价、下一个下标和当前词。计算结束后从下标零开始沿下一跳移动，依次收集词项，直到文本末尾。这样每个格子只占常数信息，路径只在最后构造一次。
稳定决胜也可以在不复制整条路径的情况下实现。若业务只要求固定结果，可在代价相等时优先更长词、词典编号更小或终点更靠后。若必须按完整切分序列的字典序比较，则需要持久化链、排名压缩或延迟比较，复杂度会提高。决胜规则应服务于业务，而不是为了数学形式增加无谓成本。
词频怎样进入动态规划
真实分词往往不只区分“词典内外”。可以给每个词一个概率，把路径代价设为负对数概率之和，乘法概率就变成可累加分数。未知字符使用一个平滑概率，既不会完全禁止新词，也会让已知高频组合更有优势。此时 dp 的结构不变，只是边权从二元计数换成浮点分数。
浮点比较要设置稳定策略，不能把极小误差当成显著差异。可以将语料计数和总量转成高精度对数，或在分数差小于阈值时启用次级规则。测试除固定样例外，还应验证所有边权非负或确认算法允许负权；本文 DAG 式下标前进没有环，即使使用任意有限边权也能递推。
前向最大匹配仍有用武之地
动态规划更全局，不代表每个场景都必须使用。词典很小、文本极短、错误代价低时，最长匹配实现简单且延迟稳定；协议关键字解析若语法本身规定最长词素，贪心甚至就是正确规则。算法选择要依据目标性质，而不是把动态规划视为更高级的固定替代品。
可以把最长匹配作为基线和回退：先运行快速贪心，若出现未知字符、歧义前缀或低置信度，再启动动态规划。这样普通输入走短路径，困难输入得到全局比较。无论采用哪种组合，都要保留“研究生命起源”这类最小反例，防止优化后悄悄退回错误局部选择。
词典更新与线上一致性
词典版本变化会改变同一文本的切分，进而影响搜索索引、特征统计和缓存键。更新时应给 Trie 标记版本，让离线索引与在线查询使用同一快照；不能在处理一个请求过程中替换词典根。热更新可以先构建新 Trie，完成校验后原子切换引用，旧请求继续使用旧版本。
测试集也应按领域分层：通用词、专有名词、数字字母混合、表情、繁简体和故意拼写错误。只报告总体准确率会掩盖未知词集中爆发。记录未知字符率、平均词数和路径分数分布，更容易发现词典加载失败或某次更新造成的系统性漂移。
还要检查输入文本是否被意外修改。分词器应返回原文中的连续片段，所有词项拼接后必须与规范化后的输入完全相同；这条简单不变量能抓住漏字符、重复字符和下标越界，也是随机生成文本时最值得保留的属性断言。
收束画面
Trie 缩短了候选枚举路径，动态规划负责比较完整切分，两者承担不同职责。遇到分词、路径拼接或协议解析问题时，先找一个能击穿局部贪心的短反例，再决定状态和代价，往往比背模板更快接近正确实现。
标签： Trie 动态规划 Python 分词算法 字符串
