加载中…
个人资料
yfx416
yfx416
  • 博客等级:
  • 博客积分:0
  • 博客访问:103,682
  • 关注人气:75
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

中文分词与隐马尔科夫模型之一(机械分词)

(2011-10-02 23:50:52)
标签:

中文分词

隐马尔科夫模型

分类: 数据挖掘

这篇博客主要讲讲中文分词算法。中文分词在文献检索系统中是一个非常重要的功能,它将一个完整的句子分拆成几个词语,这几个词语就构成了这个句子的特征向量。举个例子,比如这么一句话:我爱北京天安门。分词就是要把这个句子正确得拆分成:我 | 爱 | 北京 | 天安门。

具体怎么拆分呢?很自然的想法就是字典匹配。这需要根据语料库构造一个庞大的字典D,这个字典存放着所有可能的词语。每次从词典中查找和待匹配串前缀最长匹配的词,如果找到匹配词,则把这个词作为切分词,待匹配串减去该词;如果词典中没有词与其匹配,则按单字切分。以上面的例子来看,先看’我‘可能的分词,字典中没有包含以’我‘字为前缀的词语,那么’我‘就是一个分词。接下来从’爱‘字开始,看字典中有没有包含以’爱‘为前缀的词语,假设字典中没有,那么’爱‘就是一个分词。再看’北‘,字典中有以’北‘开始的词,继续扩展,有以’北京‘开始的词么,假使有,那么继续,看有以’北京天‘开始的词语么,没有,那么’北京‘就是一个分词,就这么一直继续下去直到句子完结。

索引树的构造

这个算法很简单,关键问题就是如何构造一个高效的索引词典,能够快速查找出包含某些特定前缀的的最长词语。针对索引的问题,很自然的想法就是构造一颗树,利用树来索引。的确是这样的,这种树称之为Trie树,也可以称之为字典树。下面就来具体看看这棵树是如何构成的。

假设下面一个词典

大 大学 大运会 大学生 大人 活动 生活 中 中心 心

这些词语的第一个字归纳起来有这么几个:大,活,生,中,心。这些词语按照第一个字来分,可以分成这么几个组:

大:大,大学,大运会,大学生,大人

中:中,中心

活:活动

心:心

生:生活

于是我们想到了,根据每个词语的第一个字我们可以构造一个字典索引,这样就可以把字典分成一些组。这就形成第一级的索引。索引的构造方法就是利用二叉查找树,比如AVL树,红黑树。具体的构造方法不记得了的同学赶紧回去翻翻本科《数据结构》教材。经过这一步,我们就会得到下面这样一颗首字索引树:

13E5F9A0B09A4A8DAF7CDDD97CCE3395803DC448

有了第一级的首字索引,我们接下来针对上面的每个首字索引分组构造第二级索引。我们来看‘大’这个组:

大:大,大学,大运会,大学生,大人

根据第二个字,这个分组又可以分成下面这样一些子组:

大-null:大

大-学:大学,大学生

大-运:大运会

大-人:大人

针对第二个字,我们又可以构成一个二叉树索引如下:

DCBC1A45BD6D48EC04084805F0016BF4E24A78C8

这棵树添加到已有的树中去,就得到下面这样一颗树,构成了‘大’字的二级索引

0D03E6927017113AA0931F0640B3FD416625D8A2

再继续前面的前面的思路,我们就可以继续得到相应的三级索引,四级索引。。。,直到最后我们可以得到下面这样一颗最终的Trie树

8914C535E66012664D47CE823FCB5A8D3B91A87A

针对这颗树做几点说明:

1.蓝色表示它的第一级索引树,红色表示表示它的第二级索引子树,绿色表示第三极索引子树

2.从第一级索引子树到最后一级索引子树的路径就构成了分词 [注意:‘活’和‘生’有一条线相连,图画的有点问题,也懒得重画了]

构造算法

有了上面的具体例子,构造算法就呼之欲出了。构造算法关键是一个单词插入过程,下面给出简单伪码

4F197BC300BCEDD17ADAE706D66EA3C42D81B52F

检索算法

字串检索算法如下也很简单,就是按照字串中每个字出现的顺序,依次检索各级子树,如果各级子树都存在,那么就证明该字串所代表的单词存在,可以确立为一个分词。伪码如下:

6CBE4260DF3768B58EE8D4DF54BBCFD0D947D17E

这就是最大前向匹配分词算法,也可以称之为机械分词。据说百度就是基于这种分词方法(小道消息,也许是空穴来风)。这种算法需要在内存中构造一颗字典索引树,其实开销是有点大的。只不过由于现代计算机内存都比较大,都足以在内存中驻留这样一棵树,因此分词算法往往不需要考虑分布式并行的情况。一般情况下,中文语料库构造的字典索引树大概在百兆级别。

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有