1701009261
我和数学有约：趣味数学及算法解析 [:1701004246]
1701009262
我和数学有约：趣味数学及算法解析 7.7 中文自动分词方法
1701009263
1701009264
自动分词在互联网有着极其广泛的应用。当你在搜索引擎中搜索“我和数学有约”时，搜索引擎通常会帮你找出同时含有“我和”、“数学”和“有约”的网页，即使这三个词在输入时中间有空格。一个好的新闻网站通常会有“相关文章推荐”的功能，这也要依赖于自动分词的算法。不过，要想让计算机准确切分一句话，并不是那么容易。
1701009265
1701009266
我就曾经看到过，某网站报道西南交大学生怎么样怎么样，结果相关文章里列出的全是西南交通大学的新闻。这多半是分词算法错误地把标题中的“西南交大学生”当成了一个词。
1701009267
1701009268
中文自动分词技术是以“词”为基础，但汉语书面语不是像西方文字那样有天然的分隔符（空格），而是在语句中以汉字为单位，词与词之间没有明显的界限。因此，对于一段汉字，人可以通过自己的知识来明白哪些是词，哪些不是词，但如何让计算机也能理解？其处理过程词，就要应用到中文自动分词技术。
1701009269
1701009270
【问题】那么，如何让计算机准确地切分一句话呢？
1701009271
1701009272
【分析】
1701009273
1701009274
自动分词的主要困难在于分词歧义。“结婚的和尚未结婚的”，应该分成“结婚／的／和／尚未／结婚／的”，还是“结婚／的／和尚／未／结婚／的”？
1701009275
1701009276
我们来判断很容易，要交给计算机来处理就麻烦了。
1701009277
1701009278
问题的关键就是，“和尚未”里的“和尚”也是一个词，“尚未”也是一个词。从计算机的角度看上去，两者似乎都有可能。对于计算机来说，这样的分词困境就叫做“交集型歧义”。
1701009279
1701009280
有时候，交集型歧义的“歧义链”有可能会更长。
1701009281
1701009282
“中外科学名著”里，“中外”、“外科”、“科学”、“学名”、“名著”全是词，光从词库的角度来看，随便切几刀下去，得出的切分都是合理的。类似的例子数不胜数，“提高产品质量”、“鞭炮声响彻夜空”、“努力学习语法规则”和“中国企业主要求解决”等句子都有这样的现象。在这些极端例子下，分词算法谁优谁劣可谓是一试便知。
1701009283
1701009284
最简单的，也是最容易想到的自动分词算法，便是“最大匹配法”了。也就是说，从句子左端开始不断匹配最长的词（组不了词的单字则单独划开），直到把句子划分完。算法的理由很简单：人在阅读时也是从左往右逐字读入的，最大匹配法是与人的习惯相符的。而在大多数情况下，这种算法也的确能侥幸成功。不过，这种算法并不可靠，构造反例可以不费吹灰之力。例如，“西南交通大学生前来应聘”本应是“西南交通／大学生／前来／应聘”，却会被误分成“西南交通大学／生前／来／应聘”。
1701009285
1701009286
还有一个适用范围相当广的特殊规则，这个强大的规则能修正很多交集型歧义的划分错误。首先我们要维护一个一般不单独成词的字表，比如“民”、“尘”、“伟”和“习”等；这些字通常不会单独划出来，都要跟旁边的字一块儿组成一个词。在分词过程中，一旦发现这些字被孤立出来，都要重新考虑它与前面的字组词的可能性。例如，在用最大匹配法切分“为人民服务”时，算法会先划出“为人”一词，而后发现“民”字只能单独成词了。查表却发现，“民”并不能单独划出，于是考虑进行修正——把“为人”的“人”字分配给“民”字。碰巧这下“为”和“人民”正好都能成词，据此便可得出正确的划分“为／人民／服务”。
1701009287
1701009288
不过，上述算法归根结底都是在像人一样从左到右地扫描文字。为了把问题变得更加形式化，充分利用计算机的优势，我们还有一种与人的阅读习惯完全不同的算法思路：把句子作为一个整体来考虑，从全局的角度评价一个句子划分方案的好坏。设计自动分词算法的问题，也就变成了如何评估分词方案优劣的问题。最初所用的办法就是，寻找词数最少的划分。
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