自然语言处理学习笔记（1）——词典分词
一、相关定义（P32）
- 中文分词：将一段文本拆分为一系列单词的过程，这些单词顺序拼接后等于源文本。
- 词典分词：一个确定的查词与输出的规则系统，仅需要一部词典和一套查词典的规则，是最简单、最常见的分词算法（语言是时刻在发展变化的，任何词典都只是某个时间节点拍摄的一张快照）。
- 词的定义：在语言学上，词语是具备独立意义的最小单位。
二、切分算法
1. 完全切分（P36）
- 完全切分指的是：找出一段文本中的所有单词（并不是标准意义上的分词），不考虑效率的话，朴素的完全切分算法非常简单，只需遍历文本中的连续序列，查询该序列是否在词典中。
2. 最长匹配算法（P37）
- 正向最长匹配：在以某个下标为起点递增查词的过程中，优先输出更长的单词，该下标的扫描顺序从前往后。
- 逆向最长匹配：操作与正向最长匹配类似，只不过下标的扫描顺序从后往前。
- 双向最长匹配：同时执行正向和逆向最长匹配，若两者的词数不同，则返回词数更少的那一个；否则，返回两者中单字更少的那一个；当单字数也相同时，优先返回逆向最长匹配的结果。三种匹配规则的效果对比如下图：
-
速度评测：（1）同等条件下，Python 的运行速度比 Java 慢，效率只有 Java 的一半不到；
（2）正向匹配和逆向匹配的速度差不多，是双向的两倍。
三、字典树
1. 定义（P46）
- 字符串集合常用字典树（ tire 树、前缀树）存储，这是一种字符串上的树形数据结构。字典树中每条边都对应一个字，从根节点往下的路径构成一个个字符串，如下图所示：
当词典大小为 n 时，虽然最坏情况下字典树的复杂度依然是 O(logn) ,但它的实际速度比二分查找快。
- 实现及其增删改查的操作见P47-49
2. 双数组字典树（Double Array Tire，DAT）（P55）
- 由 base 和 check 两个数组组成，简称双数组，且满足：
p = base[b] + c
check[p] = base[b]
自然
自然人
自然人 = base[自然] + 人
check[自然人] == base[自然]
- DAT的构造是普通字典上的深度优先遍历问题：为字典树的每个节点分配一个双数组中的下标，并维护双数组的值，其构造算法为递归的过程，代码见 P58。
- DAT每次状态转移的时间复杂度都是常数，但全切分长度为 n 的文本时，复杂度是 O(n2) 。
3. AC自动机（Aho-Corasick）（P60）
- 一次扫描就查询出所有出现过的单词，时间复杂度为 O(n) ,被广泛用于多字符串搜索。
- 给定多个词语（也称模式串，pattern），从母文本中匹配它们的问题称为多模式匹配（multi-pattern matching），AC自动机就是一种常用的多模式匹配算法，适用于中文处理中汉字这种短模式串。
-
AC自动机由 goto 表、fail 表和 output 表组成。
goto 表：也称 success 表，就是是一颗前缀树，用来将每个模式串索引到前缀树上，如下图：
output 表：给定一个状态，需要知道该状态是否对应某个或某些模式串，以决定是否输出模式串以及其对应的值。output 表中的元素有两种，一种是从初始状态到当前状态的路径本身对应的模式串（如下图2号状态），另一种是路径的后缀所对应的模式串（如下图5号状态）。
fail 表：fail 表保存的是状态间的一对一关系，存储状态转移失败后应当回退的最佳状态。最佳状态指的是能记住已匹配上的字符串的最长后缀的那个状态（如下图，匹配 she 后来到状态 5 ，再来一个字符，goto 失败，当前匹配到的字符串为 she，最长后缀为 he，对应路径 0-1-2，因此，状态 2 就是状态 5 fail 的最佳选择）。
4. 基于双数组字典树的AC自动机（ACDAT）（P67）
-
原理：AC自动机的 goto 表本身就是一颗字典树，可以用双数组字典树来替换 goto 表。ACDAT 的构建原理就是为每个状态（ base[i]和check[i] ）构建 output [i] [] 和 fail [i]。
具体来说，分以下三步：
（1）构建一颗普通的字典树，让终止节点记住对应模式串的字典序；
（2）构建双数组字典树，在将每个状态映射到双数组时，让它记住自己在双数组中的下标；
（3）构建AC自动机，此时 fail 表中存储的就是状态的下标；
- 结论：DAT适用于短模式串，ACDAT适用于长模式串。
四、准确率评测（P74）
1. 准确率
- 通俗地讲，准确率（accuracy）是用来衡量一个系统的准确程度（accurate）的值，可以理解为一系列评测指标。在中文分词任务中，一般使用在标准数据集上词语级别的精确率、召回率与F1值来衡量分词器的准确程度。
2. 混淆矩阵与TP/FN/FP/TN
- 混淆矩阵（confusion matrix），用来衡量分类结果的混淆程度，如下图：
上图以姓名性别预测问题为例，记男性为正类（positive，简称 P ，即阳性），女性为负类（negative，简称 N ，即阴性），为每种组合取个名字。
图中“纵坐标”为预测结果，“横坐标”为标准答案，两者的 4 中组合如下：
（1）TP（true positive，真阳）：预测是 P ,答案果然是真的 P 。
（2）FP（false positive，假阳）：预测是 P ,答案是N，因此是假的 P 。
（3）TN（true negative，真阴）：预测是 N ,答案果然是真的 N 。
（4）FN（false negative，假阴）：预测是 N ,答案是P，因此是假的 N 。
混淆矩阵有如下性质：
（1）样本全集 = TP∪FP∪FN∪TN；
（2）任何一个样本属于且只属于 4 个集合中的一个，也就是说它们没有交集。
3. 精确率
-
精确率（precision，简称 P 值）：指的是预测结果中正类数量占全部结果的比率，即：
P = T P T P + F P P=\frac{TP}{TP+FP} P=TP+FPTP
实践中，优先将关注度高的作为正类。
4. 召回率
-
召回率（recall，简称 R 值）：指的是正类样本被找出来的比率，即：
R = T P T P + F N R=\frac{TP}{TP+FN} R=TP+FNTP
在区分 P 值和 R 值的时候，只需记住两者分子都是真阳的样本数，只不过 P 值的分母是预测阳性的数量，而 R 值的分母是答案阳性的数量。
5. F1值
-
F1值：指精确率和召回率的调和平均，即：
F 1 = 2 × P × R P + R F_1=\frac{2\times P\times R}{P+R} F1=P+R2×P×R
这是为了避免商家只拿 100% 的召回率做宣传，对 1% 的精确率避而不谈的一个综合性的指标。这样 P 和 R 必须同时高，才能得到较高得到F1值。
6. 中文分词中的P、R、F1计算
-
对于长为 n 的字符串，分词结果是一系列单词，每个单词按它在文本中的起止位置可记作区间 [ i , j ]，其中1 ≤ i ≤ j ≤ n。那么，标准答案的所以区间构成一个集合 A ，作为正类；此集合之外的所有区间构成另一个集合（A 的补集），作为负类；记分词结果所有单词区间构成集合 B 。则：
T P ⋃ F N = A TP\bigcup FN=A TP⋃FN=A
T P ⋃ F P = B TP\bigcup FP=B TP⋃FP=B
T P = A ⋂ B TP=A\bigcap B TP=A⋂B
相应的，P、R的计算公式如下：
P = ∣ A ⋂ B ∣ ∣ B ∣ P=\frac{|A\bigcap B|}{|B|} P=∣B∣∣A⋂B∣
R = ∣ A ⋂ B ∣ ∣ A ∣ R=\frac{|A\bigcap B|}{|A|} R=∣A∣∣A⋂B∣
7. 其他相关
- 使用颗粒度较大的词典在颗粒度较小的预料上做评测，会导致分值偏低，无法反应分词算法的准确率。
- 本人学习使用的是第二届国际中文分词评测提供的 MSR 语料库以及相应的词典。
- OOV指的是“未登录词”（Out Of Vocabulary），或者“新词”，即词典未收录的词汇
- IV 指的是“登录词”（In Vocabulary），其相应的 IV Recall Rate 指的是词典中的词汇被正确召回的概率（若连词典中的词汇都无法百分之百召回，说明词典分词的消歧能力不好）。
五、字典树的其他应用
- 停用词过滤：汉语中一类没有多少意义的词语，如助词“的”、连词“以及”、副词“甚至”、语气词“吧”，称为停用词，一个句子去掉了停用词并不影响理解。停用词用处有很多，比如在一些网站上的非法的敏感词也视作停用词。
- 简繁转换：指的是简体中文和繁体中文之间的相互转换，且存在“一简对多繁”、“一繁对多简”、“简繁分歧词”等问题。
- 拼音转换：指的是将汉字转换为拼音的过程，涉及输入法行业的应用话题。
六、总结
- 在在这一章中，实现了字典树、双数组字典树、AC自动机以及基于双数组字典树的AC自动机，基于这些高级数据结构，将词典分词的速度推向了千万字每秒的高度。但是，实现的词典分词的准确率并不高，既无法区分歧义，也无法召回新词。