分享

更多

   

关于MMSEG分词算法

2014-07-16  watkins604

关于MMSEG分词算法

MMSEG是中文分词中一个常见的、基于词典的分词算法(作者主页:http://chtsai.org/index_tw.html),简单、效果相对较好。由于它的简易直观性,实现起来不是很复杂,运行速度也比较快。关于算法的原文,可以参 见:http://technology.chtsai.org/mmseg/

总的来说现在的中文分词算法,大概可以笼统的分为两大类:一种基于词典的,一种是非基于词典的。

基于词典的分词算法比较常见,比如正向/逆向最大匹配,最小切分(使一句话中的词语数量最少)等。具体使用的时候,通常是多种算法合用,或者一种为主、多种为辅,同时还会加入词性、词频等属性来辅助处理(运用某些简单的数学模型)。

非 基于词典的算法,一般主要是运用概率统计、机器学习等方面的方法,目前常见的是CRF(Conditional random field, http://en.wikipedia.org/wiki/Conditional_random_field)。此类方法可以让计算机根据现成的资 料,“学习”如何分词。具体的实现可参考(http://nlp.stanford.edu/software/segmenter.shtml)。

一般来说,这两类方法各有优缺点:基于词典的方法,实现、部署比较容易,但是分词精度有限,且对于未登录 词(词典里没有的词语)识别较差;非基于词 典的方法,速度较快,对未登录词识别效果较好,能够根据使用领域达到较高的分词精度,但是实现比较复杂,通常需要大量的前期工作。

MMSEG是一种基于词典的分词算法,以正向最大匹配为主,多种消除歧义的规则为辅。下面来具体看一下:

根 据作者在原文中的阐述,对MMSEG的解释分为“匹配算法(Matching algorithm)”和“消除歧义的规则(Ambiguity resolution rules)”这两部分。“匹配算法”是说如何根据词典里保存的词语,对要切分的语句进行匹配(正向?逆向?粒度?);“消除歧义的规则”是说当一句话可 以这样分,也可以那样分的时候,用什么规则来判定使用哪中分法,比如“设施和服务”这个短语,可以分成“设施_和服_务”,也可以分成“设施_和_服 务”,选择哪个分词结果,就是“消除歧义的规则”的功能。

MMSEG的“匹配方法”有两种:

1.Simple方法,即简单的正向匹配,根据开头的字,列出所有可能的结果。比如“一个劲儿的说话”,可以得到

一个

一个劲

一个劲儿

一个劲儿的

这四个匹配结果(假设这四个词都包含在词典里)。

2.Complex方法,匹配出所有的“三个词的词组”(原文中使用了chunk,这里感觉用“词组”比较合适),即从某一既定的字为起始位置,得到所有可能的“以三个词为一组”的所有组合。比如“研究生命起源”,可以得到

研_究_生

研_究_生命

研究生_命_起源

研究_生命_起源

这些“词组”(根据词典,可能远不止这些,仅此举例)

“消除歧义的规则”有四个,使用中依次用这四个规则进行过滤,直到只有一种结果或者第四个规则使用完毕。这个四个规则分别是:

1.Maximum matching (最大匹配),有两种情况,分别对应于使用“simple”和“complex”的匹配方法。对“simple”匹配方法,选择长度最大的词,用在上文的 例子中即选择“一个劲儿的”;对“complex”匹配方法,选择“词组长度最大的”那个词组,然后选择这个词组的第一个词,作为切分出的第一个词,上文 的例子中即“研究生_命_起源”中的“研究生”,或者“研究_生命_起源”中的“研究”。

2.Largest average word length(最大平均词语长度)。经过规则1过滤后,如果剩余的词组超过1个,那就选择平均词语长度最大的那个(平均词长=词组总字数/词语数量)。比如“生活水平”,可能得到如下词组:

生_活水_平 (4/3=1.33)

生活_水_平 (4/3=1.33)

生活_水平 (4/2=2)

根据此规则,就可以确定选择“生活_水平”这个词组

3.Smallest variance of word lengths(词语长度的最小变化率),由于词语长度的变化率可以由标准差(http://baike.baidu.com/view/78339.htm)反映,所以此处直接套用标准差公式即可。比如

研究_生命_起源 (标准差=sqrt(((2-2)^2+(2-2)^2+(2-2^2))/3)=0)

研究生_命_起源 (标准差=sqrt(((2-3)^2+(2-1)^2+(2-2)^2)/3)=0.8165)

于是选择“研究_生命_起源”这个词组。

4.Largest sum of degree of morphemic freedom of one-character words,其中degree of morphemic freedom可以用一个数学公式表达:log(frequency),即词频的自然对数(这里log表示数学中的ln)。这个规则的意思是“计算词组中的所有单字词词频的自然对数,然后将得到的值相加,取总和最大的词组”。比如:

设施_和服_务

设施_和_服务

这两个词组中分别有“务”和“和”这两个单字词,假设“务”作为单字词时候的频率是5,“和”作为单字词时候的频率是10,对5和10取自然对数,然后取最大值者,所以取“和”字所在的词组,即“设施_和_服务”。

也许会问为什么要对“词频”取自然对数呢?可以这样理解,词组中单字词词频总和可能一样,但是实际的效果并不同,比如

A_BBB_C (单字词词频,A:3, C:7)

DD_E_F (单字词词频,E:5,F:5)

表示两个词组,A、C、E、F表示不同的单字词,如果不取自然对数,单纯就词频来计算,那么这两个词组是一样的(3+7=5+5),但实际上不同的词频范围所表示的效果也不同,所以这里取自然对数,以表区分(ln(3)+ln(7) < ln(5)+ln(5), 3.0445<3.2189)。

这个四个过滤规则中,如果使用simple的匹配方法,只能使用第一个规则过滤,如果使用complex的匹配方法,则四个规则都可以使用。实际使用中,一般都是使用complex的匹配方法+四个规则过滤。(simple的匹配方法实质上就是正向最大匹配,实际中很少只用这一个方法)

看到这里也许对MMSEG的分词方法有了一个大致的了解,正如文章开头所述,它是一个“直观”的分词方法。它把一个句子“尽可能长(这里的长,是指所切分的词尽可能的长)”“尽可能均匀”的区切分,稍微想象一下,便感觉与中文的语法习惯比较相符。如果对分词精度要求不是特别高,MMSEG是一个简单、可行、快速的方法。

在具体实现一个分词程序的时候,大概有以下几点需要考虑:

1.“方法”决定“速度”。在基于词典的分词算法中,词典的结构对速度的影响是比较大的(词典的结构一般决定了匹配的方法和速度)。一般的构造词典的方法有很多,比如“首字索引+整词二分”,将所有词语的首字用某一Hash算法索引,然后将词体部分排序,使用二分查找。这样的方法可行,但不是最快的。对于这样的词典匹配,trie结构一般是首选。trie也有一些变种和实现方法,对于大量静态数据的匹配(比如词典,一旦创建,便很少去修改里面的内容,故称之为“静态”),一般采用“双数组trie树结构(Double array trie tree)”,其相关资料网上有很多,可以Google或者Baidu。这里提几个可供参考的类库:

Darts,   http://chasen.org/~taku/software/darts/ , C++

Darts-clone, http://code.google.com/p/darts-clone/ , C++, 某些方面比Darts好一些

2.MMSEG的分词效果与词典关系较大(这里是说词典里有哪些词语,以及词频的精确度),尤其是词典中单字词的频率。可以根据使用领域,专门定制词典(比如计算机类词库,生活信息类词库,旅游类词库等),尽可能的细分词典,这样得到的分词效果会好很多。同时也可以通过词典达到一些特殊目的(地址分词等)。关于词库,可以参考“搜狗”的细胞词库(http://pinyin.sogou.com/dict/)以及其提供的语料库(可以根据其划分好的语料库,统计某一方面的词频,http://www.sogou.com/labs/resources.html)。

3.中文分词的处理,与编码关系很大(GBK, GB2312, BIG5, UTF-8),一般是以UTF-8为主,减少编码的复杂性。

4.MMSEG算法中取得所有的“chunk”是比较复杂的部分,根据不同的词典结构会有不同的方法。如果使用“双数组trie树”结构,会简单一些,可以用“递归”实现,也可以用“三层for循环实现”。出于性能考虑,一般是使用for循环。

这里是一个基于MMSEG算法的PHP中文分词扩展 http://code.google.com/p/xsplit/ 并加入了一些常用函数

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。如发现有害或侵权内容,请点击这里 或 拨打24小时举报电话:4000070609 与我们联系。

    猜你喜欢

    0条评论

    发表

    类似文章 更多
    喜欢该文的人也喜欢 更多