Shell's Home

Oct 12, 2008 - 1 minute read - Comments

分词算法的具体实践

说到分词算法,可能很多人都很陌生,然而说起百度,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+split@gmail.com,欢迎大家试验并提出意见。