中文机械分词算法入门

中文机械分词算法入门2007/06/04

作者：Sunny from Hour41 (www.hour41.com )

这几天因为要负责新的搜索系统中的分词，所以看了一些入门级的分词算法。其中主要是机械分词方法，趁这个机会总结下。

机械分词方法又叫基于字符串匹配的分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行区配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短）匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下：
    1）正向最大匹配法（由左到右的方向）；
    2）逆向最大匹配法（由右到左的方向）；
    3）最少切分（使每一句中切出的词数最小）。

这几种分词方法的基本原理相同， 1和2基本上只是一个方向的区别，而由于我们习惯都是正向的来理解句子，所以反向分词的匹配的错误率会稍小。据网上的统计数据表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245。但有时候正向分出的结果却比反向更优，所以通过需要通过计算总的概率来选择最优的分词结果：
 比如： 中国是世界上5个常任理事国之一
 反向： 中/国是/世界/上/5/个/常任/理事国/之一/
 正向： 中国/是/世界/上/5/个/常任/理事国/之一/

方法3就是在在前两种方法的结果基础上用统计方法找出切出词最小的匹配方法。

下面我们来看看一个机械分词算法的基本实现。首先，需要有一个词库。用来在其中对搜索串中可能为词的子串进行一个搜索，如果找到则表明是一个词。让计算机能够按照语言习惯进行切分，往往需要机器有一个比较丰富的词库才能够比较准确的识别出语句中的单词。理论上来说，词库越大越好。但由于考虑到加载后的速度问题，一般的词库都保持在几十万字的水平。一般应用中词库都是预先加载至内存中。下面是我看到的几种常见的字典加载的方法（当然词库的建法都是与后面的具体算法对应的）：

l ）直接建一个链表(LinkedList)加载，可用于二分查找匹配。
2）对字典建一个哈希表(HashTable)或键值对(Map)，可以建立首字哈希搜索，也可以加入权重值进行搜索时的权重控制。还可以用值来标明匹配时目前的匹配是否有“潜力”成为一个词。
3）树形字典： 树的每个节点包含一个字. 比方  中国   中国人  中华民族  中华人民共和国  几个词,构成的树的结构:
  
                 中
           国^    华
      人^        人    民
                   民       族^
                   共
                   和
                   国^
树中结点标明匹配到这一点是否已经成词，否则说明继续往下（添加输入字）才可成词。
4）将字典构造为一个对象后，将其序列化再写入文件，直接将字典作为一个对象来进行操作。

加载了词库后，主要的算法步骤如下（正向最大匹配）：
1， 待处理的短语为S;
2， 测试S.substring(0,k)是否是词语，如果是，保存其长度max=k。否则将k加1后继续在字典中匹配，重复此步骤。这里k为2到字典的词语的最大长度。
3， 得到一个最大词语，长为max。
4， 返回2，继续处理S = S.substring(max)，即余下的字符。

反向匹配与此类似， 如下（最大匹配）：
1， 得到搜索串中的一个子串S（0，k）;
2， 测试S.substring(0,k)是否是词语，如果是，保存其长度max=k。否则继续在字典中匹配S.substring(1,k)，重复此步骤。这里k为2到字典的词语的最大长度。
3， 得到一个最大词语，长为max。
4， 如果max=k，返回1以取得新的子串进行匹配；否则返回2，继续处理S = S.substring(0，k-max)，即余下的字符。

实际应用中，这种算法的精度还远远不能满足需要。实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过利用各种其它的语言信息来进一步提高切分的准确率。公司文档中提出的一种办法是增加辅助切分词语。这些词语并不是词语，它们是词语组合。它们来辅助的进行词语切分。比如，对于短语“吃面的地方”来说，当后向切词的时候，它会被切分为：吃、面的、地方。显然这是不对的。所以，可以增加一个辅助切词短语：“吃面的”，这个短语固定切分为：吃面、的。当发现某些短语切分不准确的时候，可以通过增加辅助切词词语来修正切分。当然这就需要一个额外的辅助切词短语的短语库，网上有没有现成的我还没有找过。

下面是一些网上找到的具体算法实现：

Ø http://www.iteye.com/topic/58701
Ø http://sourceforge.net/projects/wordsegment/
Ø http://www.solol.org/technologic/java/j-lucene2/index.html#top
Ø http://www.iteye.com/topic/59121