MMSeg

by Yan Sheng

MMSeg 算法是由 Chih-Hao Tsai 提出的一种基于最大匹配的分词算法。算法以最大匹配为基础，通过几条规则的修正，达到了很高的精确度。按照作者的说法，在一个 1013 的词的测试输入中，词语的正确识别率达到了 98.41% 。

MMSEG 算法主要分为两种：simple 和 complex 。simple 算法就是前面提到的最简单的正向最大匹配算法。为了解决 simple 算法的不足，MMSEG 又提供了另一种选择：complex 算法。该算法使用了 Chen K. J. 和 Liu S. H. 于 1992 年在 Word identification for Mandarin Chinese sentences 中提出的一种最大匹配算法的变种。

这种算法的基本思想是：找到所有从当前位置开始的三个连续词语的块，总长度最大的块是最优解。例如，分割“眼看就要来了”这个句子，从“眼”字开始，可能构成的三个连续词的块有（注意每一个单字通常都可以独立成词）：

眼 看 就 眼 看 就要 眼看 就 要 眼看 就要 来 眼看 就要 来了

总长度最大的块就是最后一行的三词块，即最优分解。当然这只是“经验公式”，比如，分割“如果一个人生三子则得奖”这个句子，在处理到“人”字的时候，以下两种选择：

人 生 三 人生 三 子

应当是前者是最优分解，然而后者才是总长度最大的块。在使用 complex 算法的时候，即使用了最大匹配，有时候还是会得到多个结果，例如，假如到了文本的末尾有“国际化”这个词，三个选择：

国际化 国际 化 国 际 化

拥有同样的最大长度。为了在这种情况下选出一个最有分割，使用了一个最大平均长度的规则（Largest average word length）：即选择块里平均词语长度最大的块。这条规则只有在文本末尾，无法构成三个词的块时才有用，如果所有的块都是三个词的话，他们的平均长度必然是一样的（经过由最大匹配算法之后留下的块必定都是总长度最大的）。虽然如此，这仍然是一条非常有用的规则，因为文本末尾不仅会出现在文件的末尾，一个句子的末尾（由标点符号标识）也会构成文本末尾。

但是光凭这条规则不足以解决所有的歧义，所以 MMSEG 还使用了另外两条规则：

  1. 词语长度变化最小的原则（Smallest variance of word lengths）。例如前面举过的“研究生命起源”的例子就可以用这种方法选出“研究 生命 起源”这个最优的分割，因为三个词的长度都是 2 ，长度变化是 0 。
  2. Largest sum of degree of morphemic freedom of one-character words 规则。通过各个单字在平时被使用的频率数据，就可以用于在不同的块中选出频率最高的一个块。例如“主要是因为”的两个分割“主要 是 因为”和“主要是因为”，由于单字“是”比单字“主”出现的频率要高，因此可以选出“主要 是 因为”这个分割，通常这也就是最优分割。

通过三个额外的解决歧义的规则，complex 算法通常比 simple 算法具有更高的精确度。

理论一大堆, 这个算法还是比较传统的. 但普遍使用, 而且现成实现也比较多. 所以选用这个. 外加还有python接口, 非常简单的就能在自己的程序中调用.

简单用法如下:

def get_terms(descrip):
    """分词
    """
    from pymmseg import mmseg
    mmseg.dict_load_defaults()
    algor = mmseg.Algorithm(descrip.strip())
    for tk in algor:
        yield tk.text

那这里用到的pymmseg是对mmseg套了个python接口, 原来的mmseg是c++实现. 其工程地址: http://code.google.com/p/pymmseg-cpp/

分词简单搞定. 不过这里还需要做一步分词之后的去除停用词. 那么, 整个中文搜索引擎就架设起来了....哈哈.

Python