国内外新闻动态,ASO干货,行业资讯。 德普优化,出海必备ASO数据分析平台! 投稿请发送至邮箱:2902675294@qq.com

中文分词算法研究-mmseg

资讯快闻 蓝天白云 1495℃ 0评论

0

中文不像英文那样,天然被空格分开,计算机在理解中文文本是,往往需要对文本进行分词处理。中文分词是自然语言处理、搜索引擎索引的基础,中文分词算法有时也是一些公司的核心技术。

如何进行中文分词?为提升分词的性能、保证效果可控,一般现在工业界会以基于词典的算法来作为基础分词算法,在特定情况下引入一些其它的方法来解决歧义问题。

先来看两种最简单最容易理解的方法,最大正向匹配切词和最大逆向匹配切词。假设词典中有三个词AB、CD、DE,对于“ABCDE”这个句子,最大正向匹配切词结果为:AB/CD/E,最大逆向匹配切词结果为:AB/C/DE。这两种算法分别从正向和反向找词典中最长匹配的词,然后切开,借助于trie树这种数据结构,算法的整体算法复杂度为O(n),n为待切分的句子的长度,复杂度与词典规模无关。看似简单的算法却能比较有效地解决中文分词问题。

据SunM.S. 和 Benjamin K.T.(1995)的研究表明,中文中90.0%左右的句子,正向最大匹配法和逆向最大匹配法完全重合且正确,只有大概9.0%的句子两种切分方法得到的结果不一样,但其中必有一个是正确的(歧义检测成功),只有不到1.0%的句子,或者正向最大匹配法和逆向最大匹配法的切分虽重合却是错的,或者正向最大匹配法和逆向最大匹配法切分不同但两个都不对(歧义检测失败)。根据这项研究结果,使用正向匹配或者逆向匹配可以达到大约至少90%的准确率!一般来说逆向匹配准确率会略高于正向。

分词过程中歧义产生的根源可归纳为以下三类:
1. 由自然语言的二义性所引起的歧义,称为第一类歧义。如:“兵乓球拍卖完了”    (比较难搞定)
2. 由机器自动分词产生的特有歧义,称为第二类歧义。
又细分为两种:组合型歧义与交集型歧义。
组合型歧义就是对于字串AB,可以切分为AB,又可以切分为A/B;   他|从|马|上|下来
交集型歧义就是ABC,可以切分为AB/C,又可以切分为A/BC。       美容和服装市场
这其中交集型歧义占了绝大多数,据统计达94%,因此处理好交集型歧义在汉语分词中有着非常重要的地位。
3. 由于分词词典的大小引起的歧义,称为第三类歧义(未登录词)。如:“王小二是一个农民”用机器切分被分为“王/小/二/是/一个/农民”
统计表明第一类歧义字段只占歧义字段总数的5%左右,剩下来的就都是第二类歧义字段和第三类歧义字段。故自动分词阶段对歧义的研究主要集中在对第二类、第三类歧义字段的研究。

有了以上前人的经验总结,不难发现,如果对分词的准确率要求不算太高,只要有一个比较好的词典,再加上trie树这种数据结构,就可以实现一个基于最大正向匹配的分词算法了。

下面介绍一种中文分词算法mmseg

介绍之前先讲两个概念:trie树、全切分

1. trie树(字典数),用边表示转移条件,节点表示状态,如下所示,表示这样一个词典集:in,inn,int,tea,ten,to 。其中边是字母,节点为蓝色表示到达一个词。中文同样道理,只不过边可能包含汉字。借助trie树这种数据结构,只用扫一遍字符串,就可以找出所有词典中的词。

trietree

2. 全切分:从头到尾依次遍历句子中的每一个字,找出以该字起始的所有的词,包括单字。利用trie树这种数据结构可以实现全切分算法。

假设词典为:中华人民共和国,中华人民,中华,华人,人民共和国,人民,共和国,共和

对“中华人民共和国”的全切分结果为:
1、[中华人民共和国, 中华人民, 中华, 中]
2、[华人, 华]
3、[人民共和国, 人民, 人]
4、[民]
5、[共和国, 共和, 共]
6、[和]
7、[国]

mmseg中文分词算法:
每次最多往后取三个词组成一个chunk,找出所以可能的chunk,然后用四条规则来过滤:
  • 规则1:取最大匹配的chunk (Rule 1: Maximum matching)
  • 规则2:取平均词长最大的chunk (Rule 2: Largest average word length)
  • 规则3:取词长标准差最小的chunk (Rule 3: Smallest variance of word lengths)
  • 规则4:取单字词自由语素度之和最大的chunk (Rule 4: Largest sum of degree of morphemic freedom of one-character words): 即各单字词词频的对数之和

举例:研究生命起源

编号 chunk 长度
0 研_究_生 3
1 研_究_生命 4
2 研究_生_命 4
3 研究_生命_起 5
4 研究_生命_起源 6
5 研究生_命_起 5
6 研究生_命_起源 6

利用1规则:取最长chunk,保留4、6两个chunk

利用2规则:4、6平均词长均为2,还是得到4、6两个chunk

利用3规则:4标准差为0,小于6的标准差: ((3-2)^2+(1-2)^2+(2-2)^2)^0.5=2^0.5

得到唯一结果chunk4,然后取第一个词“研究”作为切分结果,然后继续对剩下的部分“生命起源”继续用上述方法切分。

每次切分的过程也可以理解为在一棵高度为3的树上,根据mmseg制定的规则,找到一条可能是最优的路径。

第一条规则和第二条规则可以近似理解成是最大正向和最大逆向匹配过程。

 

有了以上知识,利用全切分,就可以写出一个基本的mmseg分词算法了,而且mmseg算法本身非常灵活,可以结合自身的需求来修改规则,应付特殊情况。

至于为什么mmseg这4条规则比较有效,可以参考这篇论文:

A Word Identification System for Mandarin Chinese Text Based on Two Variants of the Maximum Matching Algorithm

 

 

转载请注明:德普微新文 » 中文分词算法研究-mmseg

喜欢 (1)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址