中文分词就是将中文语句中的词汇按照使用时的含义切分出来的过程，也就是将一个汉字序列切分成一个个有单独含义的词语。自20世纪80年代以来，中文自动分词就一直是一个研究热点，由于中文语言的复杂性使之一直处于发展阶段。目前，分词主要包含细粒度分词和粗粒度分词两种，在不同的应用场景需要用到不同的粒度。细粒度分词是指将原始语句切分成最基本的词语，而粗粒度分词是指将原始语句中的多个基本词组合起来切成一个词，进而组成语义相对明确的实体。
对于中文而言，词是承载语义的最小单元，由词构成语句，又由语句构成篇章。但是，中文文本是由连续的字序列构成，词与词之间是没有天然的分隔符。在自然语言处理领域，国外已经做出了很多卓有成效的研究，但是那些研究大多基于英文（存在天然的分隔符），也就是说是以正确切分出单词为前提的。于是，NLP对于中文而言要想取得较好的科研成果，就需要准确识别词与词之间的边界，也就是分词。
接下来我们就以搜索为例，具体的阐述一下分词的重要性与必要性。大家都知道，目前的搜素引擎是基于一种叫做倒排索引的结构，以什么作为索引的key值，直接影响到整个搜索引擎的准确度、召回率以及性能。
在知道分词的重要性之后，那么我们会面临一个新的问题，如何才能把一个字序列准确的切分成词序列，就像下面的例子会有不止一种的切分方式。
原始字符串：结婚的和尚未结婚的
上文提到的歧义词例子，有学者试图通过逆向匹配来解决。但是，碰到这句“结合成分子”时，采用逆向匹配，则会分成“结合/成分/子时”。一般当一个字可以同时作为两个词的组成部分，当这两个词按序同时出现时，就可能会出现歧义现象。目前的歧义一般分为三种：交叉歧义，组合歧义，真歧义。
从上世纪80年代开始对中文自动分词进行研究，在过去的近40年中，中文分词的发展过程基本上可分为以下三个阶段，如下图所示：
我们讨论的分词算法可分为三大类：
中文自动分词第一阶段，从80年代到90年代中，以基于词典和人工规则的方法为主，典型的方法有：正向最大匹配，逆向最大匹配，最少词切分法，双向匹配法。这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短）匹配；常用的几种机械分词方法如下：
最大正向匹配法(MM,MaximumMatchingMethod,MM)
通常简称为MM法。其基本思想为：假定分词词典中的最长词有i个汉字字符，则用被处理文档的当前字串中的前i个字作为匹配字段，查找字典。若字典中存在这样的一个i字词，则匹配成功，匹配字段被作为一个词切分出来。如果词典中找不到这样的一个i字词，则匹配失败，将匹配字段中的最后一个字去掉，对剩下的字串重新进行匹配处理……如此进行下去，直到匹配成功，即切分出一个词或剩余字串的长度为零为止。这样就完成了一轮匹配，然后取下一个i字字串进行匹配处理，直到文档被扫描完为止。其算法描述如下：
举个例子：我们对“南京市长江大桥”这个句子进行分词，根据正向最大匹配的原则。先从句子中拿出前5个字符“南京市长江”，把这5个字符到词典中匹配，发现没有这个词，那就缩短取字个数，取前四个“南京市长”，发现词库有这个词，就把该词切下来；对剩余三个字“江大桥”再次进行正向最大匹配，会切成“江/大桥”；整个句子切分完成为：“京市长/江/大桥。”
逆向最大匹配法(ReverseMaximumMatchingMethod,RMM)
通常简称为RMM法。RMM法的基本原理与MM法相同,不同的是分词切分的方向与MM法相反，而且使用的分词辞典也不同。逆向最大匹配法从被处理文档的末端开始匹配扫描，每次取最末端的2i个字符（i字字串）作为匹配字段，若匹配失败，则去掉匹配字段最前面的一个字，继续匹配。相应地，它使用的分词词典是逆序词典，其中的每个词条都将按逆序方式存放。在实际处理时，先将文档进行倒排处理，生成逆序文档。然后，根据逆序词典，对逆序文档用正向最大匹配法处理即可。
还是那个例子：取出“南京市长江大桥”的后四个字“长江大桥”，发现词典中有匹配，切割下来；对剩余的“南京市”进行分词，整体结果为：“南京市/江大桥”
由于汉语中偏正结构较多，若从后向前匹配，可以适当提高精确度。所以，逆向最大匹配法比正向最大匹配法的误差要小。统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245。
例如切分字段“硕士研究生产”，正向最大匹配法的结果会是“硕士研究生/产”，而逆向最大匹配法利用逆向扫描，可得到正确的分词结果“硕士/研究/生产”。但这种精度还远远不能满足实际的需要。实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过利用各种其它的语言信息来进一步提高切分的准确率。
双向最大匹配法(Bi-directctionMatchingmethod,BM)
双向最大匹配法是将正向最大匹配法得到的分词结果和逆向最大匹配法的到的结果进行比较，从而决定正确的分词方法。据SunM.S.和BenjaminK.T.（1995）的研究表明，中文中90.0%左右的句子，正向最大匹配法和逆向最大匹配法完全重合且正确，只有大概9.0%的句子两种切分方法得到的结果不一样，但其中必有一个是正确的（歧义检测成功），只有不到1.0%的句子，或者正向最大匹配法和逆向最大匹配法的切分虽重合却是错的，或者正向最大匹配法和逆向最大匹配法切分不同但两个都不对（歧义检测失败）。这正是双向最大匹配法在实用中文信息处理系统中得以广泛使用的原因所在。
还是那个例子：双向的最大匹配，即把所有可能的最大词都分出来，上面的句子可以分为：南京市、南京市长、长江大桥、江、大桥
最少切分法
使每一句中切出的词数最小。
由于汉语单字成词的特点，正向最小匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。
中文自动分词第二阶段，从90年代中到03年，分词算法开始引入基于语料库的统计学习方法，最典型的方法就是基于词典全切分加上最大概率路径。首先，介绍一下全切分方法，它是基于词的频度统计的分词方法的基础。全切分顾名思义就是获取原字序列的所有可能成词的切分结果，这样就不会遗漏可能正确的切分方式。所以建立在部分切分基础上的分词方法不管采取何种歧义纠正策略，都可能会遗漏正确的切分，造成分词错误或失败。而建立在全切分基础上的分词方法，由于全切分取得了所有可能的切分形式，因而从根本上避免了可能切分形式的遗漏，克服了部分切分方法的缺陷。
将全切分的结构构件一个有向无环图，比如“杭州亚运会”的全切分有向无环图如下所示。
其中，w值是指用全切分方法切分出来的词语。基于全切分最大概率路径的切分算法也是需要依赖词典，全切分在实际使用过程，一般会通过词典将所有成词的切分方式找出来构成有向无环图。第一阶段的中文分词相比，它也是无法完成识别新词，但是歧义词识别的问题基本被解决。在实际使用的工业分词系统中，词典中的词一般会带有词频属性。同时，还会有一份词与词之间的跳转频率表，最大概率的计算往往是基于词频和词之间的跳转频率进行的。
全切分算法能取得所有可能的切分形式，它的句子覆盖率和分词覆盖率均为100%，但全切分分词并没有在文本处理中广泛地采用，原因有以下几点：
全切分这种方法存在两个致命的缺陷：一个缺陷是参数空间过大，不可能实用化；另外一个缺陷是数据稀疏严重。为了解决这个问题，我们引入了马尔科夫假设：一个词的出现仅仅依赖于它前面出现的有限的一个或者几个词。如果一个词的出现仅依赖于它前面出现的一个词，那么我们就称之为bigram。即
P(T)=P(W1W2W3…Wn)=P(W1)P(W2|W1)P(W3|W1W2)…P(Wn|W1W2…Wn-1)≈P(W1)P(W2|W1)P(W3|W2)…P(Wn|Wn-1)
HMM模型示意图
HMM模型介绍
HMM的典型介绍就是这个模型是一个五元组:
HMM模型可以用来解决三种问题：
其中，第三种问题最玄乎也最不常用，第二种问题最常用，中文分词、语音识别、新词发现、词性标注都有它的一席之地。这里主要介绍第二种问题，即viterbi算法求解状态值序列的方法。
五元组参数在中文分词中的具体含义：
状态值集合为(B,M,E,S):{B:begin,M:middle,E:end,S:single}。分别代表每个状态代表的是该字在词语中的位置，B代表该字是词语中的起始字，M代表是词语中的中间字，E代表是词语中的结束字，S则代表是单字成词。观察值集合为就是所有汉字，甚至包括标点符号所组成的集合。
状态值也就是我们要求的值，在HMM模型中文分词中，我们的输入是一个句子(也就是观察值序列)，输出是这个句子中每个字的状态值。
比如：小明硕士毕业于中国科学院计算所
同时我们可以注意到：B后面只可能接(MorE)，不可能接(BorS)。而M后面也只可能接(MorE)，不可能接(B,S)。
上文只介绍了五元组中的两元StatusSet、ObservedSet，下文介绍剩下的三元InitStatus、TransProbMatrix、EmitProbMatrix。这五元的关系是通过一个叫Viterbi的算法串接起来，ObservedSet序列值是Viterbi的输入，而StatusSet序列值是Viterbi的输出，输入和输出之间Viterbi算法还需要借助三个模型参数，分别是InitStatus,TransProbMatrix,EmitProbMatrix。
InitStatus
初始状态概率分布是最好理解的，可以示例如下：
-0.26268660809250016-3.14e+100-3.14e+100-1.4652633398537678示例数值是对概率值取对数之后的结果(可以让概率相乘的计算变成对数相加)，其中-3.14e+100作为负无穷，也就是对应的概率值是0。也就是句子的第一个字属于{B,E,M,S}这四种状态的概率，如上可以看出，E和M的概率都是0，这和实际相符合，开头的第一个字只可能是词语的首字(B)，或者是单字成词(S)。
TransProbMatrix
回过头看TransProbMatrix，其实就是一个4×4(4就是状态值集合的大小)的二维矩阵，示例如下：
矩阵的横坐标和纵坐标顺序是BEMSxBEMS
-3.14e+100-0.510825623765990-0.916290731874155-3.14e+100-0.5897149736854513-3.14e+100-3.14e+100-0.8085250474669937-3.14e+100-0.33344856811948514-1.2603623820268226-3.14e+100-0.7211965654669841-3.14e+100-3.14e+100-0.6658631448798212比如TransProbMatrix[0][0]代表的含义就是从状态B转移到状态B的概率，由TransProbMatrix[0][0]=-3.14e+100可知，这个转移概率是0，这符合常理。由状态各自的含义可知，状态B的下一个状态只可能是ME，不可能是BS，所以不可能的转移对应的概率都是0，也就是对数值负无穷，在此记为-3.14e+100。
由上TransProbMatrix矩阵可知，对于各个状态可能转移的下一状态，且转移概率对应如下：
#E:-0.510825623765990,M:-0.916290731874155#B:-0.5897149736854513,S:-0.8085250474669937#E:-0.33344856811948514,M:-1.2603623820268226#B:-0.7211965654669841,S:-0.6658631448798212EmitProbMatrix
这里的发射概率(EmitProb)其实也是一个条件概率而已，根据HMM模型三个基本假设里的观察值独立性假设，观察值只取决于当前状态值，也就是：P(Observed[i],Status[j])=P(Status[j])*P(Observed[i]|Status[j])。其中P(Observed[i]|Status[j])这个值就是从EmitProbMatrix中获取。
EmitProbMatrix示例如下：
Viterbi算法
输入样例：小明硕士毕业于中国科学院计算所
Viterbi算法计算过程如下：
1、定义变量
二维数组weight[4][15]，4是状态数(0:B,1:E,2:M,3:S)，15是输入句子的字数。比如weight[0][2]代表状态B的条件下，出现’硕’这个字的可能性。
二维数组path[4][15]，4是状态数(0:B,1:E,2:M,3:S)，15是输入句子的字数。比如path[0][2]代表weight[0][2]取到最大时，前一个字的状态，比如path[0][2]=1,则代表weight[0][2]取到最大时，前一个字(也就是明)的状态是E。记录前一个字的状态是为了使用viterbi算法计算完整个weight[4][15]之后，能对输入句子从右向左地回溯回来，找出对应的状态序列。
2、使用InitStatus对weight二维数组进行初始化
已知InitStatus如下:
-0.26268660809250016-3.14e+100-3.14e+100-1.4652633398537678且由EmitProbMatrix可以得出
Status(B)->Observed(小):-5.79545Status(E)->Observed(小):-7.36797Status(M)->Observed(小):-5.09518Status(S)->Observed(小):-6.2475所以可以初始化weight[i][0]的值如下：
weight[0][0]=-0.26268660809250016+-5.79545=-6.05814weight[1][0]=-3.14e+100+-7.36797=-3.14e+100weight[2][0]=-3.14e+100+-5.09518=-3.14e+100weight[3][0]=-1.4652633398537678+-6.2475=-7.71276注意上式计算的时候是相加而不是相乘，因为之前取过对数的原因。
3、遍历句子计算整个weight二维数组
4、确定边界条件和路径回溯
边界条件如下：对于每个句子，最后一个字的状态只可能是E或者S，不可能是M或者B。
所以在本文的例子中我们只需要比较weight[1(E)][14]和weight[3(S)][14]的大小即可。在本例中：
weight[1][14]=-102.492;weight[3][14]=-101.632;所以S>E，也就是对于路径回溯的起点是path[3][14]。
到此，一个HMM模型中文分词算法过程就阐述完毕了。也就是给定我们一个模型，我们对模型进行载入完毕之后，只要运行一遍Viterbi算法，就可以找出每个字对应的状态，根据状态也就可以对句子进行分词。
模型的训练问题
以上讲的前提是基于模型来进行切词，也就是假设我们手头上的HMM模型已经是被训练好了的(也就是InitStatus,TransProbMatrix,EmitProbMatrix这三个模型的关键参数都是已知的)，没有涉及到这三个参数是如何得到的。这三个参数其实也是基于已分词完毕的语料进行统计计算，计算出相应的频率和条件概率就可以算出这三个参数。
HMM模型的三个基本假设如下：
2001年Lafferty在最大熵模型（MEM）和隐马尔科夫模型（HMM）的基础上提出来了一种无向图模型–条件随机场（CRF）模型，它能在给定需要标记的观察序列的条件下，最大程度提高标记序列的联合概率。常用于切分和标注序列化数据的统计模型。
不同概率模型之间的关系及演化图
以CRF为例，它把分词看作是对一个字序列进行标注的过程，一般会标记为4种状态：词首(B)、词中(M)、词尾(E)、单独成词(S)。例如，对于一个输入序列“我来到网易杭州研究院”会标记为“我/S来/B到/E网/B易/E杭/B州/E研/B究/M院/E”，根据标注结果就得到最终的分词结果。CRF模型的最优函数形式如下所示：
其中，Z是归一化函数，f是特征函数，前面是特征对应的权重。CRF分词的过程就是找到一个标注序列使得其最优函数达到最大值。由于CRF模型不是基于词典的，可以有效的识别新词。同时，其分词的准确率也已经达到工业界使用的要求。但是，CRF分词的效率和一致性会存在一定问题。一致性问题是指同一个待切分片段会随着上下文的不同可能做成完全不同的切分结果，所以在搜索业务中在召回层面使用是不合适的。当前CRF的主流用法是在线进行人名识别和歧义片段解析，并使用词典来保持分词结果的一致性，以及离线识别新词补充至词典。
结巴中文分词采用的算法
目前结巴分词支持三种分词模式：
项目地址：
IKAnalyzer是一个开源的，基于java语言开发的轻量级的中文分词工具包。从2006年12月推出1.0版开始，IKAnalyzer已经推出了3个大版本。最初，它是以开源项目Luence为应用主体的，结合词典分词和文法分析算法的中文分词组件。新版本的IKAnalyzer3.0则发展为面向Java的公用分词组件，独立于Lucene项目，同时提供了对Lucene的默认优化实现。
IKAnalyzer采用的算法：
IKAnalyzer支持的分词模式：
NLPIR分词系统前身为2000年发布的ICTCLAS词法分析系统，从2009年开始，为了和以前工作进行大的区隔，并推广NLPIR自然语言处理与信息检索共享平台，调整命名为NLPIR分词系统。NLPIR支持的功能：全文精准检索、新词发现、分词标注、统计分析与术语翻译、大数据聚类及热点分析、大数据分类过滤、自动摘要、关键词提取、文档去重、HTML正文提取、编码自动识别与转换等。
NLPIR使用的算法：
Ansj是一个开源的Java中文分词工具，基于中科院的ictclas中文分词算法。目前实现了中文分词、中文姓名识别、用户自定义词典、关键字提取、自动摘要、关键字标记等功能。
Ansj使用的算法：
分词效果速度都超过开源版的ICTCLAS
MMSeg是蔡志浩（Chih-HaoTsai）提出的基于字符串匹配的中文分词算法。以正向最大匹配为主，多种消除歧义的规则为辅。根据作者在原文中的阐述，对MMSEG的解释分为“匹配算法（Matchingalgorithm）”和“消除歧义的规则（Ambiguityresolutionrules）”这两部分。“匹配算法”是说如何根据词典里保存的词语，对要切分的语句进行匹配；“消除歧义的规则”是说当一句话可以这样分，也可以那样分的时候，用什么规则来判定使用哪中分法，比如“设施和服务”这个短语，可以分成“设施/和服/务”，也可以分成“设施/和/服务”，选择哪个分词结果，就是“消除歧义的规则”的功能。
MMSeg的字符串匹配算法分为两种：
在complex分词算法中，MMSeg将切分的相邻三个词作为词块（chunk），应用如下四个歧义规则：
这个四个过滤规则中，如果使用simple的匹配方法，只能使用第一个规则过滤，如果使用complex的匹配方法，则四个规则都可以使用。实际使用中，一般都是使用complex的匹配方法＋四个规则过滤。
MMSeg算法说明
Chunk中的4个属性只有在需要该属性的值时才进行计算，而且只计算一次。
其次来理解一下规则(Rule)，它是MMSeg分词算法中的又一个关键的概念。实际上我们可以将规则理解为一个过滤器(Filter)，过滤掉不符合要求的chunk。MMSeg分词算法中涉及了4个规则：
这4个规则符合汉语成词的基本习惯。
再来理解一下匹配方式复杂最大匹配(Complexmaximummatching)：复杂最大匹配先使用规则1来过滤chunks，如果过滤后的结果多于或等于2，则使用规则2继续过滤，否则终止过滤过程。如果使用规则2得到的过滤结果多于或等于2，则使用规则3继续过滤，否则终止过滤过程。如果使用规则3得到的过滤结果多于或等于2，则使用规则4继续过滤，否则终止过滤过程。如果使用规则4得到的过滤结果多于或等于2，则抛出一个表示歧义的异常，否则终止过滤过程。
最后通过一个例句–“研究生命起源”来简述一下复杂最大匹配的分词过程。MMSeg分词算法会得到7个chunk，分别为：
编号chunk长度0研_究_生31研_究_生命42研究_生_命43研究_生命_起54研究_生命_起源65研究生_命_起56研究生_命_起源6使用规则1过滤后得到2个chunk，如下：
编号chunk长度4研究_生命_起源66研究生_命_起源6计算平均长度后为：
编号chunk长度平均长度4研究_生命_起源626研究生_命_起源62使用规则2过滤后得到2个chunk，如下：
编号chunk长度平均长度4研究_生命_起源626研究生_命_起源62计算标准差的平方后为：
编号chunk长度平均长度标准差的平方4研究_生命_起源6206研究生_命_起源624/9使用规则3过滤后得到1个chunk，如下：
编号chunk长度平均长度标准差的平方4研究_生命_起源620匹配过程终止。最终取“研究”成词，以相同的方法继续处理“生命起源”。
分词效果:
目前考拉海淘使用的分词是基于ansj开源分词进行二次开发的版本，目的是优化ansj原有的分词策略以及增加适合电商的策略。
召回问题
通过日志以及用户反馈，我们发现对于同一商品往往存在不同表述，这可能会导致某种描述无法召回结果。例如，对于商品“扫地机器人”来说，有人会用“扫地机器”这样的query去查询，也有人会用“扫地机”去查询。但是按照最大概率路径分词策略，会把商品切分成”扫地”和”机器人”来进行建立索引。为了保证召回的准确性，底层NDIR是采用全匹配的方式来进行召回，也就是query中的所有词都必须出现在同一个文档中。对于上面的两种query，分词结果分别是“扫地/机器”，“扫地/机”，自然就无法召回用户所希望的商品。我们采用多路径切分的方式，来保证所有在词典的词语都出现在路径中，同时，对所有的路径进行索引建立。我们会把“扫地机器人”切分成“扫地/机器人”、“扫地/机器/人”、“扫地机/器/人”三条路径，这样就解决了无法召回的问题。
词性问题
当用户输入的query比较详细时，可能考拉并没有此款商品，却有同品牌或者其他相似的商品，这个时候就需要用到关键词提取。例如，query为”耐克黑色球鞋詹姆斯同款”时，因为无货而无法召回商品，当我们提取关键词“耐克黑色篮球鞋”时可能会召回商品，当然这个关键词提取的粒度是需要控制的。在ansj原有词典的基础上，我们补充了电商品牌词典和电商类词典，分词过程中会给出相应的标记为”耐克/brand黑色/adj球鞋/ecom詹姆斯/nrf同款/nz”，根据词性是可以进行关键词初步识别的。
分词粒度问题
当词典较大时，会面临一个新的问题，那就是分词的粒度问题。对于query为“耐克鞋”来说，词典中是包含这个实体词的，分词的切分结果就是“耐克鞋”。但是，考拉用来建索引的商品描述中，这三个字是没有连续出现的，自然就没有“耐克鞋”对应的文档，这个时候就无法召回结果。那么，这时候你会说那就使用最小粒度的分词就解决这个问题了。比如，某一款商品可能有“参数表”这三个字，如果有最小粒度的分词策略，分词的结果为“参数/表”。很不幸，当query为“表”时，你会发现会召回莫名其妙的结果。目前，是使用词频表来进行粒度控制，基本可以解决绝大多数问题。
新词问题
未来工作的方向
根据考拉海淘搜索的现状，接下来会针对解决关键词提取/新词发现以及实体识别所带来的问题。打算开发一套termweight的关键词识别系统，利用词法依存关系以及词性等知识给切分后每一个词语进行一个打分，其应用场景会非常广泛。另外一个方向是解决新词发现所涉及的问题，会根据用户日志以及新商品的信息，利用词频统计以及CRF序列标注等方案来定期离线自动化补充新词。
知乎在重构知乎搜索的时候，权衡标注工作量和性能，以及代码实现的复杂程度，采用基于字符串匹配的分词方法。除了标注量，准确率和效果的考量，分词粒度也是一个需要考虑的指标。
案例：“团购网站的本质是什么？”
在这个例子中，如果使用单一粒度分词，会有：“团购”、“团购网”、“网站”、“团购网站”、“本质”、“是”、“什么”
按最大匹配分词结果是：“团购网站/的/本质/是/什么”。当用户输入“团购网的本质”，分词结果是“团购网/的/本质”，团购网这个词显然是没有匹配的。按最小匹配分词的结果也会出现问题。
因此，知乎考虑基于字符串匹配的分词方法最好能够匹配出多粒度的结果，即能分出“团购网站/团购/团购网/网站/的/本质/是/什么”这样多粒度的结果。