分词算法的具体实践

说到分词算法，可能很多人都很陌生，然而说起百度，google，很多人却是耳熟能详。google，百度在搜索的时候，输入关键词后瞬间就可以得到结果，如果用通用数据库是无法做到的。实行这个加速的关键就是分词算法。例如"项羽是萝莉控"这句句子，我们一般搜索都是搜索项羽，或者萝莉控，萝莉。你见过有去搜"是萝"这个关键字的么？因此系统通过分词，将句子分解为"项羽/是/萝莉控"，去处单字常见词"是"(如果要索引"是"，可以想像有多少文章没有"是"的)，我们就得到了项羽和萝莉控两个词。再通过反向关联，建立项羽，萝莉控指向文章的连接，就可以完成瞬间的搜索了(具体原理不说了，只要有一定数据库基础的人都应当能想明白原理)。并且通过关联性，某种程度上也可以提供"是萝"的搜索(带"是"的词，带"萝"的词，相关度最高)。
那么，如何来计算分词呢？方法很多，大家可以在网络上搜索下，贝壳就不赘述了。贝壳现在要说的是这次贝壳主要试验的方向，基于词典的机械分词中的最大分词算法。
机械分词算法是当今的主流，关键原因在于速度问题。虽然正确的分词很有价值，然而如果速度太慢，一样没有什么用处。机械分词一般可以保证 98%-99.5%以上的正确率，同时提供极高的分词速度。而机械分词一般来说，都是基于词典的。主要有正向分词算法，逆向分词算法，最大匹配分词算法。其中最大匹配分词算法具备最高的灵活性，只要你能评价一个切分的优秀程度，算法能把所有可能算出来让你评价。然而大家可以想像，这个是非常耗费CPU的。贝壳在这个基础上，做了一个具体的实现和细化加速。并且有准备做为一个开源项目来长期运作(只要有人有意向接手合作)。
首先我们先说贝壳这个算法的评价原则。贝壳认为，评价原则应当有以下几点。同时也必须要说明，以下原则是无法正确评价所有情况的。不过以下原则在原则正确的基础上比较便于优化。一、无法分析的词最少(这是全局最大匹配的理论核心)。二、匹配出的原子最少(这是保证分词优秀性的指标)。三、匹配出原子的出现概率和最高(这是纯粹没有办法了从概率上提高匹配正确的可能)。
当我们分析一句话的时候，我们可以想像，这句话应当是正常的，可被理解的。换句话说，句子中应当都是有意义的词。那么，在匹配后无法理解的词是什么呢？一种是匹配错误，一种是新单词，一种是单字成词和无意义助词。单字成词的例子有上面的"是"，我们可以通过一个比较小的词典去除。那么，假定词典够大的情况下，无法理解和分析的词越少的组合越正确。而同样一句话，匹配出的原子越少，在搜索的时候效率越高。因此我们有规定了原子最少原则。至于最后一个，在无法分析词一致，原子个数一致的情况下，我们只能通过出现概率来猜测可能性。
然后，现在让我们分析一下分词的特点，并且做一定的优化。首先就从最著名的例子，"长春/市长/春节/致辞"开始。
>>>长春市长春节致辞
首先，匹配算法一定要先搜索到一个出现的词，有词才有匹配优化问题。没有词的话，你试试看分词"嗡嘛呢呗咪吽"。根本无法可分。因此首先我们要计算出一个出现的单词。贝壳是从正向开始计算的(主要是因为词典的加速方法是头索引的)。
>>>*长春*{市长春节致辞}
>>>*长春市*{长春节致辞}
好的，我们匹配到了两个，不过这就是全部可能么？不是，否则就变成了正向最大搜索。你可以看看"有意见分歧"。如果从头一个匹配到开始计算，无论如何都是"有意/见/分歧"，而事实是"有/意见/分歧"。因此我们还有一种可能，在头一个匹配到的位置，其实并不匹配。不匹配多长呢？最大长度不会超过最短的匹配词。为什么？我们来看下面一个例子。
>>>*长春*{市长春节致辞}
>>>*长/春/(这两个字不是词，而是两个无法理解的字){市长春节致辞}
很明显，后一种分法违背了我们的第一原则，无法分析的词最少。无论后面怎么计算，其最优结果是相同的。在后续结果相同的情况下，头一次匹配到词后，所有可能的跳空(搜索可能的不匹配)最大长度严格小于最短匹配词的长度。
那么是否所有跳空都要搜索呢？也不，我们可以继续剪枝。对于情况"有意见分歧"来说，这个路径是必须搜索的。但是对于我们的例子来说，是无需搜索的。为什么呢？我们看以下计算。
>>>*长/{春市长春节致辞}(下一个匹配是什么？总不会是春市吧，所以应当是"市长")
>>>*长/春/市长*{春节致辞}
>>>*长春*{市长春节致辞}
大家可以看到，其实这个路径是无需计算的。那什么情况下需要计算呢？
一旦跳空，其跳空后寻找到的下个词的位置必须严格小于最短词的词尾位置。否则就没有搜索价值。具体可以看以下示例。
XXXXXXXNNNNNNNNNNN(X是词，N是无关紧要的)
SSSSSSSXXNNNNNNNNN(S是跳空或者跳空后形成的无法理解字，X是词，在这种情况下，无论后面怎么评价，都不影响该匹配被剔除)
OK，我们回到例子，刚刚我们说了，有"长"的匹配。但是通过刚刚的剪枝，又被剪了出去。我们下面分别计算两个情况。
>>>市长春节致辞
>>>*市/{长春节致辞}
>>>*市长*{春节致辞}
>>>长春节致辞
好，我们先不计算下去了。通过上面的计算，我们发现，在计算过程中经常需要计算同一内容的结果。我们可以想一下，同样的分词，同样的算法，出现的应当是同样的结果。就是说，分词函数是状态无关的算法。通过分解一个单词，得到一个最优结果。那么，我们对于同样的数据，何必需要计算两次呢？贝壳上文中提到过记忆函数，这次就用上了。根据贝壳的试验结果，如果记忆全部词的分解结果，会造成大量的记忆-释放，而内容基本没有用到，造成效率下降。如果只记忆长词的分解结果，往往又会因为太长，大多数句子无法达到长度而根本没用。这中间有个平衡值，具体多少贝壳就不说了。我们可以按照上文的方法计算以下两个过程，得到结果。大家可以自行验证。
>>>春节致辞
>>>*春节*致辞*
>>>长春节致辞
>>>*长/春节*致辞*
>>>*长春*节/致辞*
结合上面的过程，我们推算得到结果。
>>>*长春*{市长春节致辞}
>>>*长春*市长*春节*致辞*
>>>*长春市*{长春节致辞}
>>>*长春市*长/春节*致辞*
>>>*长春市*长春*节/致辞*
按照上面的评价原则，我们得到了正确的结果。
大家可以看看其他例子，这里着重说一下"有意见分歧"。
>>>有意见分歧
>>>*有*意见*分歧*
>>>*有意*见/分歧*
注意，有是单字成词，见可不是。如果见单字成词，做看见讲，那这句话就彻底成歧义句了。可以理解为，有意的要看到(或者让其表现出)分歧。这一般是古文语法。由此也可以看出上述原则在理解古文的时候往往会出现问题。同时还要指出的是，在匹配"长春市长春药店"的时候，会出现以下结果。
>>>长春市长春药店
>>>*长春*市长*春药店*
>>>*长春市*长春*药店*
两者的无法理解词都没有，切分数一致，最后硬是因为春药店出现概率低而被筛掉。可见系统有的时候是依赖概率和人品在工作的。
经过上面的原则和算法，贝壳实现了一个python的分词程序，1000行代码，原型系统。90W条词情况下，在AMD MK36上(2G主频)分词效率66K/s上下，具体看分词的选项(例如顺序分词就比较节约资源，分词排除重复就比较慢，启用多线程后在单CPU 机器上更慢)，内存使用114M。使用C++写的核心词典后，90W条词的情况下分词速度80K/s，比python的核心词典快了20%，内存70M，节约内存40%。不过可惜，这个核心词典是公司产权，贝壳无权公布。并且贝壳做了一些工作，准备使用分词程序来生成分词词表。这个么贝壳就不准备讲了。前面讲的内容贝壳准备放到试验型站点 http://shell909090.3322.org/split_word/split_show/上面去，08年内有效。有兴趣联系我的可以发 mail给我，shell909090@gmail.com，欢迎大家试验并提出意见。