中文分词方案

最近为了做缺乏标注语料条件下的词库生成、新词发现和分词，虽然是基础中的基础，可是做起来也不那么容易。在面试中也发现，现在许多自然语言处理工程师熟练使用神经网络模型，却没有传统的计算语言学的基本功，甚至有人根本不知道分词为何物，让我十分遗憾。因此整理一下关于中文分词的思考，写成本文。

什么是分词

我不打算从基础的语言学开始讲，不过还是有必要说一下什么是词，什么是分词。

按照定义，词就是由语素构成的最小的能够独立运用的语言单位。所以它的标准很简单：第一，词是能够独立运用的语言单位，一般来说就是指它能够单独成句或者能用做句法成分；第二，词无法拆成更小的独立运用的语言单位。

上面提到了语素，它是最小的有语音有语义的语言单位。一般来说，中文的一个语素对应一个字，比如火、车、铁、路都是语素。但是也有例外，比如葡萄、乒乓、奥林匹克这样的双音节或者多音节语素，几个音节合起来才有意义。

语素的自由度不尽相同，自由语素有灵活的构词能力或者能单独成词，不自由语素则相反。两个以上语素可以构成合成词，例如火车、铁路。两个以上词可以构成词组，例如写博客、乒乓球运动员。

词是语素的概括整合，而不是简单搭配组合。词是凝固的单位，内部语素之间不能插入其他成分。无论从意义还是语法上说，词组都是词的搭配组合，它的结构是松散的。

但是这个凝固与松散的阈值并没有一定的边界，比如说有人认为新词发现这个术语整体是一个词，有人认为新词和发现分别是词，还可能有人认为新词不是词，新和词分别都是词。那么新词发现在分词时应该如何处理，就没有放之四海而皆准的规则，特别是中文自然语言处理中，分词往往只是预处理中的一步。分词的质量和标准需要结合场景和需求来判断。关于分词的困难特别是歧义，网上有许多有趣的例子，这里就不赘述了。

分词思路概览

总的来说，分词的目标就是在上下文 $C$ 中，将连续文本 $S$ 划分为词序列，或者说将连续字序列 $c_1, \ldots, c_m$ 组合为词序列 $w_1, \ldots, w_n$。关键的问题是，如何确定划分或组合的标准，求解

$$\arg\max_{n, w_1, \ldots, w_n} p(w_1, \ldots, w_n|C) \quad s.t. \quad w_1 |\cdots |w_n=S, w_i \in D$$

上式中 $D$ 是理想的完整词典；本文以及传统分词一般不考虑上下文，可以将 $C$ 省略（如果要发文章或者做其它 NLP，还是要注意加入 context-aware 的思想）。

要想在满足 $w_1 |\cdots |w_n=S$ 的约束下，得到 $\max_{n, w_i} p(w_1, \ldots, w_n)$，最理想的情况当然是有语言模型或者有分好词的语料训练语言模型。

最常见的基于词的 ngram 语言模型是单向语言模型

$$\max_{n, w_i} p(w_1)p(w_2|w_1)p(w_3|w_1,w_2)\cdots p(w_n|w_1,\ldots,w_{n-1})$$

考虑马尔可夫性质，简化为一阶马尔可夫模型

$$\max_{n, w_i} p(w_1)p(w_2|w_1)p(w_3|w_2)\cdots p(w_n|w_{n-1})$$

完全忽略上文，进一步简化为独立概率乘积

$$\max_{n, w_i} p(w_1)p(w_2)p(w_3)\cdots p(w_n)$$

另外，基于字的模型也是一种思路，在连续字序列 $c_1, \ldots, c_m$ 中间插入若干个 <seg> 作为词间的分隔字，构成新的字序列 $s_1, \ldots, s_{m’}$，并相应组合为词序列，这样的单向语言模型为

$$\max_{m', s_i} p(s_1) p(s_2|s_1) p(s_3|s_1,s_2) \cdots p(s_{m'}|s_1,\ldots,s_{m'-1})$$

进一步简化为字的 bigram，也就是一阶马尔可夫模型

$$\max_{m', s_i} p(s_1) p(s_2|s_1) p(s_3|s_2) \cdots p(s_{m'}|s_{m'-1})$$

上面的想法都需要词表及相应的概率估计。

如果连概率估计都没有，只有词表。我们可以借助传统的启发式想法，例如：最小划分词数，使划分出来的词序列长度 $n$ 最小；最大单向匹配（分为正向和反向两种情况），使每一步划分出来的词都是剩余序列的最长匹配。显然，这两种启发式分词都只需要一个尽可能完整的词表，以及一个适当的高效进行前缀文本匹配的数据结构。

如果连词表都没有，只有无标注文本，就是纯粹的无监督的词库生成、分词和新词发现。前面已经提到过词的几个基本特征：独立（能够单独运用），自由（能够灵活搭配），凝固（内部搭配固定），最小（不能切分成其他词）。于是，我们可以设法利用出现和共现的统计，找到内部搭配固定、外部搭配自由灵活或者是独立出现的片段，筛出候选的词。

以上各种情况，都要记得利用标点符号作为天然的分隔符，将长句切分为片段来处理。对于字母数字也可以适当做一些格式上的替换和预处理，避免过于稀疏。

词典匹配

从最传统、最基本的词典匹配方法开始，假设我们已经有一个相对完整的词表，先尝试第一种贪心的启发式方法：正向最大匹配（当然反向也很容易如法炮制），每一步找到字串中当前位置开始的最大匹配，如果没有匹配则单字成词。显然这里的最大匹配语句是瓶颈，需要一个高效进行文本匹配的数据结构，例如 Trie 结构。

第二种启发式方法：最小词数，也就是使切分次数最小。复杂度要高一些，这个问题可以采用动态规划解决。同样，利用 Trie 来避免重复低效匹配。在分词里，前缀树结构与动态规划算法是基本功，必须熟练掌握。

举个例子，独立自主和平等互利的原则，如果词表是独立自主, 独立, 自主, 和平, 平等, 互利, 平等互利, 原则，那么正向最大匹配就得到 独立自主/和平/等/互利/的/原则，反向最大匹配或者是最小划分才能正确得到独立自主/和/平等互利/的/原则。

在现代分词工具诞生之前，双向最大匹配曾经是不错的经验方法：分别计算出正向最大匹配和反向最大匹配的结果，取其中词数较少者；若词数相等，优先选取反向最大匹配结果，或其中单字个数较少者。

Trie 还可进一步增加局部匹配的跳转链接，构成 AC 自动机，实现匹配片段全扫描（也就是jieba中的全模式），例如对独立自主和平等互利的原则切分出独立/独立自主/自主/和平/平等/平等互利/互利/原则。

当然，这些匹配方法并不能真正解决歧义。

语言模型

分词的歧义困难主要在于两可的切分位置，例如交集型歧义（同一个字串在不同的切分位置均可成词），组合型歧义（同一个字串切或不切都可成词），仅根据词表无法判断如何切分。

已经分析过，引入语言模型的概率估计，可以依据一个打分函数来选择最可能的切分。最熟悉的传统统计语言模型就是 ngram 模型。例如词的 bigram 也就是一阶马尔科夫关系的 $p(w_1, \ldots, w_n) = p(w_1|BOS)p(w_2|w_1) \cdots p(w_n|w_{n-1}) p(EOS|w_n)$。特别指出，如果是词的 unigram，实际上也就是将依赖关系全都简化，$p(w_1, \ldots, w_n) = p(w_1)\cdots p(w_n)$。

如果我们可以事先估计所有词的概率或频率，最大概率分词容易实现。这实际是某种最短路径问题，可以使用动态规划方法。由于字串的词频查询隐含了是否为词的查询，使用 Trie 之类的结构同样可以带来显著的性能提升。

代码不贴了，参考 nltk 吧。提示一下，需要已经分词的训练语料和适当的平滑方法（比如好用又简单的 Good-Turing 平滑），以免低估未登录词的概率。

对于词的 bigram 或者更大的 ngram，还需要记录条件概率 $p(w_n|w_1,\ldots,w_{n-1})$，或者说是记录多个频率$tf(w_1,\ldots,w_n)$ 和 $tf(w_1,\ldots,w_{n-1})$，对数据结构的存储也提出比较大的要求。

极端情况下，n 为无限大，词的 everygram 就是将语料中所有的片段都记录下来，构成一个无限大的树。这当然是不可能实现的，但是可以用来作为思想实验的出发点。

字转移

前面的方法都是设法将连续文本划分为词序列，但是如果词不在词表中，就只能划分为单字或者错误。一个未登录字串多大程度上构成一个候选词，实际上也是平滑的目的。反过来，若我们考虑如何将连续字序列组合为词，则有望解决未登录词问题。组合的关键是衡量每个字的成词能力。

在字的 bigram 模型中，其他候选的分词结果例如 独立自主/和平/等/互利/的/原则 就对应于 p(独|<seg>)p(立|独)p(自|立)p(主|自) p(<seg>|主) p(和|<seg>) p(平|和) p(<seg>|平) p(等|<seg>) p(<seg>|等) ... p(原|<seg>) p(则|原) p(<seg>|则)。

于是利用词内的字转移概率 p(字1|字2)、词首词尾的转移概率 p(字|<seg>) 和 p(<seg>|字)，同样可以动态规划找到最大概率分词。这些转移概率都可以用分词语料或者带有词频的词表估计。这样我们就找到一种基于字转移概率的分词优化目标。

如果只需要计算转移概率，那么带词频的词表就够用了，有分词语料当然更好。对于类似思路但是更复杂的模型（例如后面提到的biLSTM），如果没有语料，我们可以凑合用词表根据词频随机组合生成一些句子作为伪分词语料，用来训练模型。如果没有词表，只有未分词语料，可以凑合用 p(字) 代替 p(字|<seg>)，省略p(<seg>|字)，这样也可以得出结果，当然不可避免会有很多词的划分不符合我们的习惯。

另外，一个有趣的发现是，形如 p(字1|字2) 的转移概率，实际上正是 word2vec 模型所学到的，确切地说这个概率实际上就是在小窗口 skip-gram 模型预测的结果，可以用字 1 的 IN 向量和字 2 的 OUT 向量的内积来近似。

关于 word2vec 的 IN-OUT 相似度，可以看微软的 Dual Embedding Space Model。简单来说 IN-IN 或者 OUT-OUT 余弦刻画的是词的功能或者类型的相似度（typical），而 IN-OUT 余弦（特别是 CBOW 模式）则是词的文档共现或者话题的相似度（topical）。这一点对信息检索很有用，但分词一般不用它，所以这里就点到为止。

字标注

很显然，上面的转移模型依然不够平滑，每个字都依然是离散的 id 形式，不太可能彻底解决未登录词问题。为解决这一问题，引入隐变量，使离散的字词共享隐状态，是一种常用的手段。举个例子，从此我们可以从大量的例如王明和李刚的训练数据，推测出王刚也是一个词或者人名。

若每个字 id 对应在离散的隐状态上的一个概率分布，加上不同的假设，就构成隐马尔可夫模型 HMM、隐狄利克雷分布 LDA 等等生成模型的基础。若每个字 id 对应一个实值向量表示的隐状态，就是我们熟悉的分布式表示或者嵌入模型。当然，如果仔细思考就能想明白，在 n 个离散隐状态上的概率分布，以及 n 个神经元构成的隐层，两者尽管优化方法不同，背后的思想却是殊途同归。

隐马尔可夫模型 HMM，具体定义不再赘述，简单理解就是序列中每个元素有一个未知的隐状态和一个可观测的值，需要通过可观测的值推测出最可能的隐状态（提示：EM 算法）。以分词为目标的 HMM，每个字的隐状态是一个标注，原理上只需要 B 和 I 两个字母即可，B 表示词首位置，I 表示其它；但由于词尾也有一些可识别的特征，所以引入 E 标记词尾位置也有意义；又因为中文有不少单字词，B 和 E 重合的场景也很多，因此引入单字词的 S 标记也有帮助。还有更复杂的字标注方案，不过大致思路就是如此了。

利用训练数据，估计隐状态的转移概率，以及观测值（每个字）在隐状态（BIES 标注）上的分布（称为发射概率），就可以同样使用动态规划来进行最大概率分词了。

上面的 HMM 模型虽然有用，但是显然有一些缺陷，比如它是单向的、马尔可夫的，观测值只依赖于当前的隐状态，隐状态只依赖于左侧单个字的历史信息，而我们希望它考虑更多的上下文。在统计学习的年代，将隐状态的转移概率由独立改为条件概率、并进行全局归一化的 CRF 是解决上述缺陷的重要手段。现在神经网络大行其道，双向 LSTM 或者 GRU 显然也是应对上述缺陷的合理 baseline（事实上 biLSTM+crf/viterbi 可以解决非常之多的问题）。

要想提出新的思路也很容易，比如类似于基于转移的 parsing，逐字从左向右处理，每一步判断是延长当前词，还是结束当前词并开始新的词。再比如类似于 multi-hop memory network，每一步对上一步结果做 attention，修改错误的切分位置。提出思路很容易，不过重要的不是选择什么模型，而是思考和探索它如何解决问题，能够克服什么局限，又引入什么新的局限。

熵与互信息

最后我们来看一下最困难的情况：假如没有分词训练语料，也没有词频数据，上面的语言模型方法以及字标注方法都不可用（除了上一段提到的用 p(字)凑合代替p(字|<seg>)的估计）；如果没有词库，上面的词典匹配方法也不可用。

当然我们的底线是有未分词的语料。这时候我们还能做些什么？假如在英文语料中去掉所有空格，我们还能识别出英文词吗？假如在中文语料中没有任何标注，我们能识别出中文词吗？

前面已经提到过词的几个基本特征：独立（能够单独运用），自由（能够灵活搭配），凝固（内部搭配固定），最小（不能切分成其他词）。

假设有足够大的语料，足够大的内存和算力，可以将上述的特征翻译为理想化的标准，如何判断一个字串 S 是不是词：

独立：利用标点符号作为天然的分隔符，找到独立出现的片段，这是最为有力的标准，例如一个字串再见的左侧总是标点符号，那么我们就知道这很可能是词的左边界……为此我们需要统计该字串的左右侧是不是分隔符
自由：左右两侧的搭配灵活，如果都能和多个不同的字搭配，意味着它更可能是个自由运用的词；如果只有一侧搭配灵活，另一侧搭配不灵活，那么有可能是更大的词的片段，例如俄罗的左侧搭配灵活，右侧固定搭配斯，是因为它是俄罗斯的一部分……为此我们需要对该字串的左右两侧分别统计邻字的频率，对单侧的邻字 x 计算 $H(S)=-\sum_x p(x|S) \log p(x|S)$，熵越大则外部搭配越灵活，外部搭配不灵活的一侧不太可能是词的边界

凝固：内部搭配固定，不是词或字的随机组合……为此我们需要统计该字串的频率，对 S 的切分 x

y 计算 $\log \frac{p(x,y)}{p(x)p(y)}$ 或者是 $p(x,y) \log \frac{p(x,y)}{p(x)p(y)}$，该值越大则内部搭配越固定，S 整体的凝固程度可以取所有切分方式的 PMI 的最小值

最小：它不是两个或多个词拼接而成的，当然它从形态上可以是更小的词的拼接，但语义上不能是简单的拼接……这一步涉及到语义，在此暂时不细说

总之，设法利用标点符号作为天然的分隔符，找到经常独立出现的片段，利用出现和共现的统计，找到内部搭配固定、外部搭配自由灵活的片段，这些都是候选的词。实际上这也有些类似于 frequent itemset mining 的做法。

凝固度为何用 PMI 衡量呢？想象语料中的两个“字” x 和 y。初始假设 x 和 y 分别是词（频率分别记为 $a$ 和 $b$），然后假设 xy 共现时合并为一个词（xy 共现的频率记为 $q$），在这个过程中（由于 $q$ 很小，其他词频率的变化忽略不计），总的熵的变化近似为

$$\Delta H = a \log a + b \log b - (a-q) \log (a-q) - (b-q) \log (b-q) - q \log q$$

整理得

$$\Delta H = a \log \frac{a}{a-q} + b \log \frac{b}{b-q} - q \log \frac{q}{ab}$$

前两项大于 0 且非常接近 0（因为 $q$ 一般远小于 $a$ 和 $b$），所以我们主要关心最后一项。

上面的方法需要统计 everygram 的频率，并反复计算其前缀、后缀的频率。在现实中，我们会受到一些限制，诸如：ngram 的大小不能太大，否则肯定会爆内存；需要采用适当的数据结构（排序的前缀集、前缀树 Trie）加速左右邻字的频率统计；完全无监督的情况下，阈值不太好确定；有些词的切分会和我们直觉不一致，例如我们可能被切开。

此外，由于内存的限制，很容易想到提前进行剪枝或者过滤，排除掉一些候选。这里提醒一下我踩过的坑：必须要使用前述的信息论的指标来做出判断，例如 俄罗斯 是一个词，而 俄罗 的右邻熵很小，因此可以知道 俄罗 大概不是一个词，它的右边大概不是词边界。但是，绝对不能任意拍脑袋推广，随意排除片段的子片段或者父片段，例如即使知道印度尼西亚是一个词，也不能直接推定印度不是词，反之亦然。更为安全的做法是在最后阶段才进行这种过滤。

在限制 ngram 长度的情况下，如何识别出长词呢？例如 奥斯特洛夫斯基，假如我们只保留 trigram（奥斯特, 斯特洛, ..., 夫斯基），每个 trigram 都是外部至少一侧不太自由、内部较为凝固的。我们需要保证这些子串都在候选列表中，然后再扫描一遍原始语料，尝试将多个不自由但凝固的子串连缀成为一个左右两侧自由的长串。还有一种方法是多轮迭代，每一轮识别出凝固度最高、一定不会切分开的片段，下一轮将它们分别整体代换为一个“字”，如此反复。

按照上面的方法进行词库生成之后，就可以按照前述的基于词库或词表的分词方法再做分词了。当然它不是完全“无监督”的，需要人工评估，效果也未必比得上做人工标注。不过在专业领域仍然是一种有用的方案。

最后贴几个分词方面可以参考的代码库：

nltk
jieba
https://github.com/bojone/word-discovery
https://github.com/Moonshile/ChineseWordSegmentation

Previous Next

sighsmile / 2019-11-15
Published under (CC) BY-NC-SA