第2章笔记：词法、形态与子词算法

本章任务

掌握正则、有限状态机、形态学、中文分词、BPE、Unigram与WFST。 先用一条能人工判断的短文本、标签序列、语法树或检索集合建立基准，再让代码输出完整中间证据，最后在真实语料、困难语言切片和生产约束下验收。

七节连接

• 正则表达式与文本模式：正则适合局部形式模式，不具备任意嵌套语言能力；贪婪、回溯和Unicode类别影响正确性与成本。 核心关系：match set={spans accepted by declared pattern and flags}。 算例：模式数字+可匹配“2026”，但若未加边界也会匹配“abc2026x”的子串。 边界：用正则解析任意嵌套括号；忽略全角数字和Unicode边界。
• 有限状态自动机与词法识别：DFA/NFA以状态和转移识别正则语言；确定化与最小化改变实现规模，不改变接受语言。 核心关系：extended transition delta*(q,string) determines accept state。 算例：从q0读a到q1、再读b到q2且q2接受，则串ab被接受。 边界：把缺失转移默认为接受；epsilon闭包遗漏导致语言变小。
• 形态学、词干与词形还原：屈折改变语法特征，派生改变词义/词类；stemming是表面截断，lemmatization需词性和词典/模型。 核心关系：surface=form(lemma,morphological features)。 算例：英语saw若作名词词元saw，若作动词过去式词元see，必须看上下文词性。 边界：把better机械还原为bett；不同语言照搬英语后缀规则。
• 中文分词与动态规划：中文词边界不显式，可把句子看成词图，在词典/统计代价下寻找最优路径。 核心关系：best[i]=min_j(best[j]+cost(text[j:i]))。 算例：“研究生命”可切“研究/生命”或“研究生/命”，不同词频代价给不同最优路径。 边界：最长匹配当普遍最优；新词出现时词图无可行边。
• BPE子词学习：BPE从字符开始迭代合并最高频相邻对，以词表规模换序列长度；合并表必须固定并按顺序应用。 核心关系：vocab size≈initial symbols+merge count。 算例：初始100字符符号，执行500次有效新合并，词表约600。 边界：在测试集继续学合并造成泄漏；不同Unicode规范用同一表。
• Unigram子词模型与分词概率：Unigram模型从大候选词表出发，以token概率给每种切分评分并迭代剪枝。 核心关系：P(segmentation)=product P(token_i)，use log-sum for stability。 算例：切分A概率.4×.2=.08，切分B概率.1×.9=.09，B更优。 边界：直接连乘长序列下溢；剪掉唯一可覆盖字符的token。
• 加权有限状态转换与分词解码：WFST把输入、输出和权重统一为路径，可组合词典、形态和语言模型；权重半环决定求和/最短路语义。 核心关系：best output=shortest/maximum-weight path under declared semiring。 算例：两路径代价2.3和1.8，最短路选择1.8，不等于概率直接相加。 边界：混用负对数和概率方向；epsilon环导致无限路径。

实验要求

运行本章两道Python语言算法实验的四组测试，并新增空文本、Unicode边界、未知词、非法标签、句法歧义、否定、长上下文、低资源语言、域外、证据冲突或提示注入中的至少一种。保存原文hash/offset、Tokenizer、数据与模型版本、随机种子、中间格表/结构/概率、输出、证据和首个偏差。

错题闭环

按字符/token/offset、规范化、概率分母、动态规划状态、标签约束、句法结构、语义作用域、训练测试泄漏、检索召回、引用蕴含、校准、隐私和工具授权分类。更换一个词频、上下文、标签、阈值、候选数、语言或证据版本重做阶段卷；能先预测变化方向，再复算并解释失效，才算掌握。