自然语言处理基础-中文分词

中文分词问题介绍

词是自然语言中能够独立运用的最小单位，是信息处理的基本单位。自然语言处理的对象是一个个的句子，拿到句子之后一般要对句子进行分词。分词就是利用计算机识别出文本中词的过程。大部分的印欧语言，词与词之间有空格之类的显示标志指示词的边界。因此，利用很容易切分出句子中的词。而与大部分的印欧语言不同，中文语句中词与词之间没有空格标志指示，所以，需要专门的方法去实现中文分词。分词是文本挖掘的基础，通常用于自然语言处理、搜索引擎、推荐等领域。

中文分词的难点主要有：

• 歧义无处不在
• 新词层出不穷
• 需求多种多样

(1) 歧义无处不在

分词的歧义主要包括如下几个方面：

• 交集型歧义，例如：

  研究/生命/的/起源

  研究生/命/的/起源

• 组合型歧义，例如：

  门/把/手/弄/坏/了

  门/把手/弄/坏/了

• 真歧义，例如：

  乒乓球/拍/卖/完了

  乒乓球/拍卖/完了

(2) 新词层出不穷

• 人名、地名、机构名
• 网名
• 公司名、产品名

(3) 需求多种多样

• 切分速度:搜索引擎vs单集版语音合成
• 结果呈现：
  • 切分粒度的要求不同；
  • 分词重点要求不同；
  • 唯一结果vs多结果；
  • 新词敏感程度不同；
• 处理对象：书面文本(规范/非规范)vs口语文本
• 硬件平台：嵌入式vs单机版vs服务器版

本文只介绍分词相关的基本算法原理及思想，其他的暂时不介绍。

中文分词算法

目前，中文分词技术已经非常成熟，学者们研究出了很多的分词方法，这些方法大致可以分为三类。第一类是基于字符串匹配的，即扫描字符串，如果发现字符串的子串和词典中的词相同，就算匹配，比如机械分词方法。这类分词方法通常会加入一些启发式规则，例如，正向最大匹配、反向最大匹配、长词优先等。第二类时基于统计的分词方法，它们基于人工标注的词性和统计特征，对中文进行建模，即根据观测到的数据（标注好的语料）对模型参数进行训练，在分词阶段再通过模型计算各种分词出现的概率，将概率最大的分词结果作为最终结果。常见的序列标注模型有HMM和CRF。这类分词算法能够很好的处理歧义和未登录词问题，效果要比前一类效果好，但是需要大量的人工标注数据，且分词速度较慢。第三类是理解分词，通过让计算机模拟人对句子的理解，达到识别词的效果。由于汉语语义的复杂性，难以将各种语言信息组织成机器能够识别的形式，目前这种分词系统还处于试验阶段。

基于字符串匹配的方法

这一类方法也叫基于词表的分词方法，基本思路是首先存在一份字典，对于要分词的文本从左至右或从右至左扫描一遍，遇到字典里有最长的词就标识出来，遇到不认识的字串就分割成单字词。常见的方法有：

• 正向最大匹配法(forward maximum matching method,FMM)
• 逆向最大匹配法(backward maximum matching method, BMM)
• N-最短路径方法

正向最大匹配法指从左到右对一个字符串进行匹配，所匹配的词越长越好，比如“中国科学院计算机研究所”，按照词典中最长匹配的切分原则切分的结果是：“中国科学院/计算研究所”，而不是”中国/科学院/计算/研究所”。但是，正向匹配会存在一些bad case，常见的例子如：”他从东经过我家”，使用正向最大匹配会得到错误的结果：”他/从/东经/过/我/家”

逆向最大匹配法是从右向左倒着匹配，如果能够匹配到更长的词，则优先选择，上面的”他从东经过我家”逆向最大匹配能够得到正确的结果，”他/从/东/经过/我/家”。但是，逆向最大匹配同样也存在bad case：“他们昨日本应该回来”，逆向匹配会得到错误的结果”他们/昨/日本/应该/回来”

针对正向逆向匹配的问题，将双向切分的结果进行比较，选择切分词语数量最少的结果。但是最少切分结果同样有bad case，比如：”他将来上海”，正确的切分结果是”他/将/来/上海”，有4个词，而最少切分结果“他/将来/中国”只有3个词。

基于字符串匹配的方法的优点如下：

• 程序简单易行，开发周期短；
• 没有任何复杂计算，分词速度快；

不足：

• 不能处理歧义；
• 不能识别新词；
• 分词准确率不高，不能满足实际的需要；

N-最短路径方法的基本思想是：设待分字串$S=c_1c_2…c_n$，其中$c_i(i=1,2,…,n)$为单个字，n为串的长度，$n \geq 1$。建立一个结点数为n+1的切分有向无环图G，各结点编号依次为$V_0,V_1,V_2,…,V_n$。如下图所示：

其算法如下：

（1） 相邻结点$v_{k-1},v_k$之间建立有向边$$，边对应的词默认为$c_k(k=1,2,..,n)$

（2） 如果$w=c_ic_{i+1}…c_j(0 < i $，边对应的词为w。

（3） 重复上述步骤(2)，直到没有新的路径（词序列）产生。

（4） 从产生的所有路径中，选择路径最短的（词数最少的）作为最终的分词结果。

例如：输入的字串：他只会诊断一般的疾病。

可能的输出：

• 他/只会/诊断/一般/的/疾病。
• 他/只/会诊/断/一般/的/疾病。

最终的分词结果为：他/只会/诊断/一般/的/疾病。

N-最短路径方法，采用的原则（切分出来的次数最少）符合汉语自身的规律；同时，需要的语言资源（词表）也不多。但是，它对许多歧义字段难以区分，最短路径有多条时，选择最终的输出结果缺乏应有的标准。当字符串长度较大和选取的最短路径数增大时，长度相同的路径数急剧增加，选择最终正确的结果困难越来越大。

基于N-gram语言模型的分词方法

基于N-gram语言模型的方法是一个典型的生成式模型，早期很多统计分词均是以它为基本模型，然后配合其他未登录词识别模块进行扩展。其基本思想是：首先根据词典对句子进行简单匹配，找出所有可能的词典词，然后将它们和所有单个字作为结点，构造n元切分词图，图中的结点表示可能的此候选，边表示路径，边上的n元概率表示代价，最后利用相关搜索算法从中找到代价最小的路径作为最后的分词结果。

假设随机变量S为一个汉字序列，W是S上所有可能切分路径，对于分词，实际上就是求解使条件概率$P(W|S)$最大的切分路径$\hat W$，即:
$$\hat W=arg max_W P(W|s)$$
根据贝叶斯公式：
$$\hat W =arg max_W \frac {P(W)P(S|W)}{P(S)} $$
由于P(S)为归一化因子，P(S|W)恒为1，因此只需要求解P(W)。P(W)使用N-gram语言模型建模，定义如下(以Bi-gram为例)：
$$P(W) = P(w_1w_2…w_T)=P(w_1)P(w_2|w_1)…P(w_T|w_{T-1})$$
这样，各种切分路径的好坏程度(条件概率P(W|S))可以求解。简单的，可以根据DAG枚举全路径，暴力求解最优路径；也可以使用动态规划的方法的求解，jieba分词中不带HMM新词发现的分词，就是DAG+Uni-gram语言模型+后向动态规划的方式进行求解的。

基于N-gram语言模型的分词方法的优点如下：

• 减少了很多手工标注知识库（语义词典、规则等）的工作；
• 在训练语料规模足够大和覆盖领域足够多的情况下，可以获得较高的切分正确率；

缺点：

• 训练语料的规模和覆盖领域不好把握；
• 计算量较大；
• 很难进行分词发现；

基于序列标注的分词方法

针对基于词典的机械分词所面对的问题，尤其是未登录词识别问题，使用基于统计模型的分词方式能够取得更好的结果。基于统计模型的分词方法，简单来说就是一个序列标注问题。在一句文本中，可以将每个字按照它们在词中的位置进行标注，常用的标记有如下四种：

• B：表示词开始的字；
• M：表示词中间的字；
• E：表示词结尾的字；
• S：表示单字成词

分词的过程就是序列标注的过程，将一句文本输入，然后得到相应的标记序列，然后根据标记序列进行分词。举例来说“他只会诊断一般的疾病”，经过模型后得到的理想标注序列是：“SBEBEBESBE”，最终还原分词结果是“他/只会/诊断/一般/的/疾病”。
在NLP领域中，解决序列标注问题的常见模型主要有HMM模型和CRF模型。

基于HMM模型分词

一般而言，一个HMM模型可以用一个5元组表示$\mu=(Q,V,A,B,\pi)$，其中：

• Q：所有可能的状态集合；
• V：所有可能的观测集合；
• A：状态转移矩阵；
• B：发射概率；
• $\pi$：初始概率分布；

HMM模型的三个基本问题：

• 概率计算问题：给定一个观察序列$O=O_1,O_2,…,O_t$和模型$\mu=(A,B,\pi)$，计算观察序列O的概率；
• 学习问题：给定一个观察序列$O=O_1,O_2,…,O_t$，估计模型$\mu=(A,B,\pi)$参数，使得在该模型下观测序列概率$P(O|\mu)$最大，即用极大似然估计方法估计参数；
• 预测问题：也称为解码问题。已知模型$\mu=(A,B,\pi)$和观测序列$O=O_1,O_2,…,O_t$，求出对于给定观测序列条件概率$P(I|O)$最大的状态序列$I={i_1,i_2,…,i_t}$，即给定观察序列，求最有可能对应的状态序列。

HMM模型概率计算问题可以通过前向、后向的动态规划算法来求解；学习问题可以通过EM算法求解；预测问题可以通过viterbi算法求解。通过足够的语料数据，可以方便快速地学习HMM模型。

利用HMM模型求解分词的基本思路是根据观测值（词序列）找到真正的隐藏状态值序列。在分词中，一句文本的每个字符可以看做是一个观测值，而这个字符的标记可以看做是隐藏状态。使用HMM分词，通过对标注语料进行统计，可以得到模型的：初始概率分布、转移概率矩阵、发射概率矩阵、观察值集合、状态值集合。在概率矩阵中，起始概率矩阵表示序列的第一个状态值的概率，在中文分词中，理论上M和E的概率为0,。转移概率矩阵表示状态间的概率，比如B->M的概率，E->S的概率等等。而发射概率是一个条件概率，表示当前这个状态下，出现某个字的概率，比如P(人|B)表示在状态为B的情况下”人”字的概率。

HMM模型的参数从标注数据学习好之后，HMM问题最终转化成求解隐藏状态序列最大值的问题，求解这个问题使用的是Viterbi算法。具体可以参照Itenyh版-用HMM做中文分词。

基于CRF模型分词

CRF也是求解序列标注问题的一种比较常用的模型，和HMM模型不同，CRF是一种判别式模型，CRF模型通过定义条件概率$P(Y|X)$来描述模型。基于CRF的分词方法与传统的分类模型求解很相似，即给定feature（字级别的各种信息）输出label。具体的CRF的基本原理就不具体介绍了。分词所使用的是Linear-CRF，它由一组特征函数组成，包括权重$\lambda$和特征函数$f$，特征函数$f$的输入是整个句子S、当前位置i、前一个字的标记$y_{i-1}$和当前字的标记$y_i$。对于分词这个任务，同样是使用BMES来标记一句话，X表示观测到句子，通过利用CRF模型的解码来，来求出最大的$P(Y|X)$，Y即是BMES组成的序列，然后用Y序列得到实际的分词结果。与HMM模型相比，CRF存在以下优点：

• CRF可以使用输入文本的全局特征，而HMM只能看到输入文本在当前位置的局部特征；
• CRF是判别式模型，直接对序列标注建模，HMM则引入了不必要的先验信息。

采用HMM模型的分词方法，属于生成式分词，其优点如下：

• 在训练语料规模足够大和覆盖领域足够多的情况下，可以获得较高的切分正确率；

不足：

• 需要很大的训练语料；
• 新词识别能力弱；
• 解码速度相对较慢；

基于CRF的分词方法，属于判别式的分词，其优点如下：

• 解码速度快；
• 分词精度高；
• 新词识别能力强；
• 所需学习样本少；

不足：

• 训练速度慢；
• 需要高配置的机器训练；

基于深度学习端到端的分词方法

基于深度神经网络的序列标注算法在词性标注、命名实体识别问题上取得了不错的结果。词性标注、命名实体识别都属于序列标注问题，这些端到端的方法可以迁移到分词问题上，免去CRF的特征模板配置问题。但与所有深度学习的方法一样，它需要较大的训练语料才能体现优势。

BiLSTM-CRF的网络结构如上图所示，输入层是一个embedding层，经过双向LSTM网络编码，输出层是一个CRF层。下图是BiLSTM-CRF各层的物理含义，可以看见经过双向LSTM网络输出的实际上是当前位置对于各词性的得分，CRF层的意义是对词性得分加上前一位置的词性概率转移的约束，其好处是引入一些语法规则的先验信息。利用此网络结构可以完成序列标注问题，同样分词任务也可以尝试这个思路。

总结一下：

中文分词工具

目前，存在多种中文分词工具供使用。比较具有代表性的有jieba分词、SnowNLP、THULAC、NLPIR和LTP，这些分词工具均提供Python库，可以很方便的使用。

jieba分词

结巴分词是我比较常用的分词工具，Github库为：https://github.com/fxsjy/jieba，分词效果较好。它支持三种分词模式：

• 精确模式：试图将句子最精确地切开，适合文本分析；
• 全模式：将句子中所有的可能成词的词语都扫描出来，速度非常快，但是不能解决歧义问题；
• 搜索引擎模式：在精确模式的基础之上，对长词再次切分，提高召回率，适用于搜索引擎分词；

另外，jieba分词还支持繁体分词，支持用户自定义词典。其使用的算法是基于统计的分词方法，主要有如下几种：

• 基于前缀词典实现高效的词图扫描，生成句子中所有可能成词情况构成有向无环图(DAG);
• 采用了动态规划查找最大概率路径，找出基于词频的最大切分组合；
• 对于未登录词，采用了基于汉字成词能力的HMM模型，使用了Viterbi算法；

其使用方法如下：

# encoding=utf-8
import jieba

seg_list = jieba.cut("我来到北京清华大学", cut_all=True)
print("Full Mode: " + "/ ".join(seg_list))  # 全模式

seg_list = jieba.cut("我来到北京清华大学", cut_all=False)
print("Default Mode: " + "/ ".join(seg_list))  # 精确模式

seg_list = jieba.cut("他来到了网易杭研大厦")  # 默认是精确模式
print(", ".join(seg_list))

seg_list = jieba.cut_for_search("小明硕士毕业于中国科学院计算所，后在日本京都大学深造")  # 搜索引擎模式
print(", ".join(seg_list))

输出结果：

【全模式】: 我/ 来到/ 北京/ 清华/ 清华大学/ 华大/ 大学

【精确模式】: 我/ 来到/ 北京/ 清华大学

【新词识别】：他, 来到, 了, 网易, 杭研, 大厦    (此处，“杭研”并没有在词典中，但是也被Viterbi算法识别出来了)

【搜索引擎模式】： 小明, 硕士, 毕业, 于, 中国, 科学, 学院, 科学院, 中国科学院, 计算, 计算所, 后, 在, 日本, 京都, 大学, 日本京都大学, 深造

除了基本的分词功能，jieba分词还提供了关键词抽取、词性标注等功能，具体的使用参照github上的文档。Python中文分词模块结巴分词算法过程的理解和分析对于jieba分词的源码进行了解析，有兴趣的可以看一下。

SnowNLP

SnowNLP:Simplified Chinese Text Processing，可以方便的处理中文文本内容，是受到TextBlob的启发而写的，由于大部分的自然语言处理库基本上是针对英文的，于是写了一个方便处理中文的类库，并且和TextBlob不同的是，这里没有用NLTK，所有的算法都是自己实现，并且自带了一些训练好的词典。GitHub地址为：https://github.com/isnowfy/snownlp。SnowNLP的分词是基于Character-Based Generative Model 来实现的，论文地址：http://aclweb.org/anthology//Y/Y09/Y09-2047.pdf

THULAC

THULAC(THU Lexical Analyzer for Chinese)是由清华大学自然语言与社会人文计算实验室推出的一套中文分词工具包。Github的地址为：https://github.com/thunlp/THULAC-Python，具有中文分词和词性标注功能。THULAC具有如下几个特点：

• 能力强:利用集成的目前世界上规模最大的人工分词和词性标注中文语料（约含5800万字）训练而成，模型标注能力强大；
• 准确率高:该工具包在标准数据集Chinese Treebank（CTB5）上分词的F1值可达97.3％，词性标注的F1值可达到92.9％，与该数据集上最好方法效果相当；
• 速度较快:同时进行分词和词性标注速度为300KB/s，每秒可处理约15万字。只进行分词速度可达到1.3MB/s；

NLPIR

NLPIR 分词系统，前身为2000年发布的 ICTCLAS 词法分析系统，Github地址：https://github.com/NLPIR-team/NLPIR，是由北京理工大学张华平博士研发的中文分词系统，经过十余年的不断完善，拥有丰富的功能和强大的性能。NLPIR是一整套对原始文本集进行处理和加工的软件，提供了中间件处理效果的可视化展示，也可以作为小规模数据的处理加工工具。主要功能包括：中文分词，词性标注，命名实体识别，用户词典、新词发现与关键词提取等功能。另外对于分词功能，它有 Python 实现的版本，Github地址为：https://github.com/tsroten/pynlpir。

LTP

语言技术平台（Language Technology Platform，LTP）是哈工大社会计算与信息检索研究中心历时十年开发的一整套中文语言处理系统。LTP制定了基于XML的语言处理结果表示，并在此基础上提供了一整套自底向上的丰富而且高效的中文语言处理模块（包括词法、句法、语义等6项中文处理核心技术），以及基于动态链接库（Dynamic Link Library, DLL）的应用程序接口、可视化工具，并且能够以网络服务（Web Service）的形式进行使用。
LTP 有 Python 版本，GitHub地址：https://github.com/HIT-SCIR/pyltp，另外运行的时候需要下载模型，模型还比较大，下载地址：http://ltp.ai/download.html。

总结

目前，分词算法已经非常成熟，并且存在很多的分词工具。虽然，不用我们自己去实现各种分词算法，但是还是有必要去了解各种分词算法的原理的。从最初的基于字符串匹配的分词方法到把分词任务转化为序列标注问题，以及将深度学习用于分词等，这些基本的研究方法可以为自然语言处理的其他任务的解决提供了思路，值的我们去学习和思考。

参考文献

• 中文分词一席谈；
• https://zhuanlan.zhihu.com/p/33261835
• http://www.cnblogs.com/sxron/articles/6391926.html
• 统计自然语言处理-宗庆成
• Lample G, Ballesteros M, Subramanian S, et al. Neural Architectures for Named Entity Recognition[J]. 2016:260-270.
• Itenyh版-用HMM做中文分词