1701009289
1701009290
1701009291
注意：每次都匹配最长的词，得出的划分不见得是词数最少的，错误的贪心很可能会不慎错过一些更优的方案。
1701009292
1701009293
因而，在有的情况下，最少词数法比最大匹配法效果更好。若用最大匹配法来划分，“独立自主和平等互利的原则”将被分成“独立自主／和平／等／互利／的／原则”，一共有6个词；但词数更少的方案则是“独立自主／和／平等互利／的／原则”，一共只有5个词。
1701009294
1701009295
当然，最少词数法也有出错的时候。“为人民办公益”的最大匹配划分和最少词数划分都是“为人／民办／公益”，而正确的划分则是“为／人民／办／公益”。同时，很多句子也有不止一个词数最少的分词方案，最少词数法并不能从中选出一个最佳答案。不过，把之前提到的“不成词字表”装备到最少词数法上，我们就有了一种简明而强大的算法：对于一种分词方案，里面有多少词，就罚多少分；每出现一个不成词的单字，就加罚一分。最好的分词方案，也就是罚分最少的方案。
1701009296
1701009297
需要指出的是，这个算法并不需要穷举所有的划分可能。整个问题可以转化为图论中的最短路问题，利用一种叫做“动态规划”的技巧则会获得更高的效率。
1701009298
1701009299
算法还有进一步优化的余地。大家或许已经想到了，“字不成词”有一个程度的问题。“民”是一个不成词的语素，它是不能单独成词的。“鸭”一般不单独成词，但在儿歌童谣和科技语体中除外。“见”则是一个可以单独成词的语素，只是平时我们不常说罢了。换句话说，每个字成词都有一定的概率，每个词出现的概率也是不同的。
1701009300
1701009301
【问题】何不用每个词出现的概率，来衡量分词的优劣？
1701009302
1701009303
【分析】
1701009304
1701009305
于是我们有了一个更标准、更连续和更自动的改进算法，即最大概率法：先统计大量真实语料中各个词出现的概率，然后把每种分词方案中各词的出现概率乘起来作为这种方案的得分。最后，选出得分最高的方案，当作分词的结果。
1701009306
1701009307
以“有意见分歧”为例，让我们看看最大概率法是如何工作的。查表可知，在大量真实语料中，“有”、“有意”、“意见”、“见”、“分歧”的出现概率分别是0.0181、0.0005、0.0010、0.0002、0.0001，因此“有／意见／分歧”的得分为1.8×10-9，但有“意／见／分歧”的得分只有1.0×10-11，正确方案完胜。
1701009308
1701009309
这里的假设是，用词造句无非是随机选词连在一块儿，是一个简单的一元过程。显然，这个假设理想得有点不合理，必然会有很多问题。考虑下面这句话：
1701009310
1701009311
这／事／的确／定／不／下来
1701009312
1701009313
但是概率算法却会把这个句子分成：
1701009314
1701009315
这／事／的／确定／不／下来
1701009316
1701009317
原因是，“的”字出现的概率太高了，它几乎总会从“的确”中挣脱出来。
1701009318
1701009319
其实，以上所有的分词算法都还有一个共同的大缺陷：它们虽然已经能很好地处理交集型歧义的问题，却完全无法解决另外一种被称为“组合型歧义”的问题。所谓组合型歧义，就是指同一个字串既可合又可分。比如说，“个人恩怨”中的“个人”就是一个词，“这个人”里的“个人”就必须拆开；“这扇门的把手”中的“把手”就是一个词，“把手抬起来”中的“把手”就必须拆开；“学生会宣传部”中的“学生会”就是一个词，“学生会主动完成作业”里的“学生会”就必须拆开。这样的例子非常多，“难过”、“马上”、“将来”、“才能”、“过人”、“研究所”和“原子能”都有此问题。究竟是合还是分，还得取决于它两侧的词语。
1701009320
1701009321
到目前为止，所有算法对划分方案的评价标准都是基于每个词的固有性质，完全不考虑相邻词语之间的影响，因而一旦涉及组合型歧义的问题，最大匹配、最少词数和概率最大等所有策略都不能实现，具体情况具体分析。
1701009322
1701009323
1701009324
1701009325
1701009326
于是，我们不得不跳出一元假设，把人类语言抽象成一个二元模型。对于任意两个词语w1和w2，统计在语料库中词语w1后面恰好是w2的概率P（w1，w2）。这样便会生成一个很大的二维表。再定义一个句子的划分方案的得分为…，其中w1，w2，……，wn依次表示分出的词，表示句子开头是w1的概率。我们同样可以利用动态规划求出得分最高的分词方案。这真是一个天才的模型，这个模型一并解决了词类标注和语音识别等各类自然语言处理问题。
1701009327
1701009328
至此，中文自动分词算是有了一个漂亮而实用的算法。
1701009329
1701009330
但是，随便拿份报纸读读，你就会发现我们之前给出的测试用例都太理想了，简直就是用来喂给计算机的。在中文分词中，还有一个比分词歧义更令人头疼的东西一一未登录词。
1701009331
1701009332
【问题】中文没有首字母大写，专名号也被取消了，这叫计算机如何辨认人名地名之类的东西？
1701009333
1701009334
【分析】
1701009335
1701009336
最近十年来，中文分词领域都在集中攻克这一难关。
1701009337
1701009338
在汉语的未定义词中，规律最强的要数中国人名了。根据统计，汉语姓氏大约有1000多个，其中“王”、“陈”、“李”、“张”和“刘”五大姓氏的覆盖率高达32％，前400个姓氏覆盖率高达99％。人名的用字也比较集中，“英”、“华”、“玉”、“秀”、“明”和“珍”六个字的覆盖率就有10.35％，最常用的400字则有90％的覆盖率。虽然这些字分布在包括文言虚词在内的各种词类里，但就用字的感情色彩来看，人名多用褒义字和中性字，少有不雅用字，因此规律性还是非常强的。根据这些信息，我们足以计算一个字符串能成为名字的概率，结合预先设置的阐值便能很好地识别出可能的人名。