加载中…

CCC.

正文 字体大小:

基于两字词簇的汉语快速自动分词算法

(2006-11-08 16:21:42)
分类: 中文分词
 

(郭祥昊 钟义信)/((北京邮电大学人工智能实验室,北京 100876))  (杨 丽)/((北方交通大学,北京 100044))

 摘要  本文提出了一种快速汉语自动分词算法。其主要思想是利用汉语中两字词占75%的统计规律,提出了两字词根和两字词簇的概念。算法把三音节以上的词用两字词簇来压缩处理,也就是把长词的扫描范围限定在词汇量很小的词簇内,从而不仅提高了分词速度,而且彻底解决了传统最大匹配分词算法中最大匹配词长的设定问题。另外,本文还提出了用两字词簇快速检测交叉歧义的算法。本文的分词算法简洁、速度快、易于实现。
 关键词  自然语言处理 分词算法 切分歧义

A Fast Algorithm for Chinese Words Automatic Segment Based
on Two-letters-word-family Structure

Guo Xianghao and Zhong Yixin
(AI Lab,Beijing University of Post and Telecommunication,Beijing 100876)
Yang Li
(CECE Center,Northern Jiaotong University,Beijing 100044)

 Abstract  A fast algorithm for Chinese words automatic segment is put forward in this paper.A structure calledtwo-letters-word-familywhich is the collection of all the Chinese words that share the same beginning two letters is introduced.The key idea of the algorithm is to compress the words which consist of more than three Chinese letters into two-letters-word-family and handle together using length changing maximum matching algorithm.In addition to this,a new method to detect segmenting ambiguousness is also introduced.
 Keywords  natural language processing,Chinese words automatic segmenting,segmenting ambiguousness.

1 问题的提出

  自动分词是汉语自然语言处理的第一步。目前,汉语自然语言处理的应用系统处理对象越来越多的是大规模语料(如Internet信息搜索引擎,各种全文检索系统等),因此分词的速度和分词算法的易实现性变得相当关键。在多种分词算法中,正向最大匹配分词算法(Maximum Matching,简称MM算法)简洁、易于实现,在实际工程中应用最为广泛。但是,它是长词优先的机械匹配算法,存在着以下不足:①速度慢。设分词词典的词条数为N,最大匹配词长为M,在词典的词条没有进行排序和索引的极端情形下,为了识别出一个两字词须平均进行(M-2)N+N/2次扫描匹配。当词条数目N比较大的时候,速度慢得难以忍受。②难以设定最大匹配词长M。M较大时,该算法的时间复杂度明显提高(见表1)。为提高速度而降低M又将使算法不能识别汉字数目大于M的词,导致切分精度降低。M取多大才合适,学术界一直有争论[1],也是实际应用中难以处理的问题之一。③最大匹配分词方法不能发现交叉切分歧义。解决这个问题的一般方法是再进行一次逆向最大匹配(Reverse Maximum Matching)分词,两者结合起来发现交叉歧义。但是这样做,算法的时间复杂度至少是MM算法的两倍。

表1 分词实验结果

  两字词根法 正向MM法 逆向MM法
词典词条数 32210 42449 42449
实际词汇数 42449 42449 42449
速   度

(秒) 

1.27(无歧义校正)

2.55(有歧义校正)

13.76 (M=6)
18.21 (M=7)
13.24 (M=6)
17.67 (M=7)
正 确 率 95.2%(无歧义校正)
99.0%(有歧义校正)
95.2% (M=7) 97.6% (M=7)
  注:1)实验语料来自《人民日报》,共5484字。实验是在奔腾166微机上进行的。
2)歧义校正算法参考了文献[7]的思想,具体算法略。
    现在已经出现了一些最大匹配分词算法的改进算法[2—4]试图解决这些问题,但是完美地解决上述所有问题的算法尚未出现,并且一些改进算法比较复杂,失去了最大匹配分词算法简单清晰、易于工程实现的优点。

2 两字词根与词簇

  本文提出了一种分词算法,它是MM算法的一种改进。该算法除了保留了MM算法的简洁和易于工程实现的优点之外,还显著地提高了分词速度,彻底消除了设置M的难题,并可用它快速发现交叉歧义现象。
  汉语的词频统计表明[1,5],在汉语中,两字词大约占75%左右。一些分词算法注意到了这个统计规律,试图利用它来提高分词的速度和效果。如张普,张光汉[6]提出的算法是单字词和多字词优先,其余的一律以两字词处理。姚天顺[5]提出了2—3—1优先分词规则,优先处理两字词。我们的算法也利用了词频统计结果,不仅优先处理两字词,而且把三音节以上的长词归化到二字词簇里处理,从而将传统的MM算法全局最大匹配化为局部变长最大匹配。这种改进显著地提高了分词速度。这里,先提出两字词根和词簇的概念:
  设A为汉语中所有多音节词的集合。
  在A中引入一种关系“~”:X~Y当且仅当X与Y的头两个汉字相同。例如,“研究”~“研究生”~“研究员”。
  这种关系显然有以下性质:
  (1) 对于任意的X∈A,有X~X;
  (2) 对于任意的X,Y∈A,若X~Y,则Y~X;
  (3) 对于任意的X,Y,Z∈A,若X~Y,Y~Z,则X~Z。
  即上述关系是A元素之间的一种等价关系。因此,可以利用它来把A进行分类。
  设集合T={<x,y>|x,y为汉字},称T为两字词根集。
  对于任意t∈T,令
  Dt={X:X∈A,X的头两个汉字为t}
  可以证明,对于任意取定的头两个汉字为t的X∈A,
  Dt={Y:Y∈A,Y~X}
  因而,若令A/D={Dt:t∈T}
  则A/D是由所有等价类构成的集合。
  我们称t为多音节词的两字词根,简称词根,称集合Dt为以t为词根的词簇。
  例如,词根t为“研究”时,词簇Dt={研究,研究员,研究生,研究室,研究所,研究生会,研究生院,……}
  当|Dt|=n时,Dt总可以写成n维向量的形式:Dt=(d1,d2,…,dn),di表示Dt中的第i个词,i=1,2,…,n。当|Dt|≥1时,可以把它里面的元素进行某种排序,如按词的长度升序排序。
  设|di|为di的词长(以汉字数目计)。定义Cml为词簇内最长的词汇长度,即:
Cml=max(|di|),di∈Dt,1≤i≤n。
  注意:词簇的词根t不一定是一个汉语词,在这种情况下,它不会出现在Dt中。
  我们的分词算法所依据的分词词典是由一个通用汉语词典经处理后产生,由单音节词和两字词簇两部分构成。由通用词典生成两字词簇的算法比较简单,此略。
  两字词簇的词条形式如下:
  t|Dt|CmL T1 T2…Tn (n≥0)
  其中,t为词根,Ti(0≤i≤n)是di去掉词根t后所剩的汉字。在|Dt|为1时,词条不存在Ti
  以下是两个词条的例子:
    研究74  员 生 室 所 生会 生院
    解决12
  分词词典是一个文本文件,其词条形式如上。将它读入内存后,建立起如下数据结构:

354-1.gif (9202 bytes)

图1 词簇的内存映像

  可见,该分词词典有一条主链表,其结点为词簇结点headi,每个词簇结点headi又分别引出一子条链表。词簇结点主要有词根、词簇的最大词长等信息,子链表的结点Ti即为Dt的元素。

  词簇结点headi的结构如下:
  struct two_word_head{
char head[3]  //词根
int cl;      //词簇的词条个数
int cml;     //词簇内最大词长
Tail * tail;   //指向Tn指针
two_word_head * next; //指向下一词簇结点的指针
  };
    Tail结构表征di,i=1,2,…,n。
  struct Tail{
    char * ch;    //词内容
    Tail * next;   //下一di
  }

3 算法描述与分析

3.1 分词算法
  分词时,从句子流中读入两个汉字,扫描词簇结点链表,把这两个汉字与词根进行匹配,称为主扫描。如果匹配成功,则根据词簇结点的信息,再顺序从句子中读入(cml-2)个汉字,在词簇内进行变长最大匹配,称为从扫描。算法描述如下:
  设句子S=a1a2…apap+1…an,设当前分词指针p指向汉字ap
  (1)把apap+1读入进行考察。
  (2)执行主扫描。搜索分词词典,如果找到以apap+1为词根的词簇结点,转(4)。
  (3)否则,ap为单音节词,转(6)。
  (4)如果词簇结点中Cml=2,则为两字词,转(6)。
  (5)执行从扫描,具体过程如下:
    令K=Cml
    do
    如果字串<ap+2 ap+3…ap+k-1>在词簇内,即<ap ap+1…ap+k-1>是一汉语多音节词,转到(6)    K=K-1
  until K=2
  (6)把新分出的词W加上分隔符,顺序放入缓冲区,等待歧义处理。
  (7)令p=(p+词W的长度),转(1)。
3.2 算法效率分析
  从上面的算法描述中可以看出,对于两字词,一次主扫描就能够切分出来;对于由三个汉字或多于三个汉字组成的长词,算法用主扫描首先把它定位到词簇,再用从扫描具体找出该词。从扫描的实质就是最大匹配算法,但参加匹配的词个数很少(是词簇中的词个数,最少的为1个,最多的才30多),其扫描时间与主扫描的时间(扫描结点多达3万余)相比可以忽略。也就是说,无论是两字词还是长词,切分扫描时间是基本相等的,这与传统的最大匹配算法完全不同,这也是我们提出的算法速度快的原因。下面我们估算两种算法速度的对比。
  先作以下假设和简化:
  (1) 通用分词词典的词条个数为N,两字词占3/4,长词的最大长度(以汉字个数记)为M,长词平均长度为L,为提高分词精度,最大匹配系数选为M。
  (2) 两字词根分词词典由通用分词词典生成,主链表的结点数目根据我们的生成算法结果约为(3/4)*N(见表1)。
  (3) 两个词典都没有进行排序和索引,词条在词典中的出现位置是随机的。
  对于最大匹配分词算法:
  (1)切分出一个两字词要进行的匹配次数(数学期望值,下同):(M-2)N+N/2
  (2)切分出一个长词要进行的匹配次数:(M-L)N+N/2
  考虑两字词大约占3/4,所以切分出一个词的平均匹配次数为:
  356-1.gif (2472 bytes)
  对于两字词根分词算法:
  (1)切分出一个两字词要进行的匹配次数:3/4*N/2
  (2)切分出一个长词要进行的匹配次数:3/4*N/2
  故:
    356-2.gif (2774 bytes)

两种算法的平均匹配次数相比:
   356-3.gif (2212 bytes)
  一般情形下,最大匹配分词算法中,M取6或7才能有较好的切分精度[1],上式表明,我们提出的分词算法相当可观地提高了速度,表1的分词对比实验也证实了这一点。
3.3 歧义的发现和处理
  自动分词问题中,存在着覆盖歧义和交叉歧义两种歧义现象。歧义切分的校正机制是提高切分精度和建造实用切分系统的关键。为了进行歧义切分的校正,首先要能发现歧义切分。实验表明,交叉歧义占切分歧义的大多数。本文采用词簇词根匹配方式来快速检测交叉歧义的存在。
  假定通过上述分词算法,句子流S被切分出m个词:
  S=W1W2…Wm
  其中Wi=ai1 ai2…ain
  定理一:如果S的切分中不存在交叉歧义,则任意相邻的两个词WiWi+1(0≤i≤m-1)中,Wi的最后一个字a与Wi+1的第一个字b组成的字串ab一定不是词簇的词根。
  理由很简单,因为如果ab是词簇的词根,则从Wi起,还可形成如下合理的切分方式:…W1iWab…,其中W1i为Wi去掉字a后的剩余部分,Wab为以ab为词根的多音节词。因此,这里出现切分歧义。
  利用定理一,可以判定交叉歧义是否存在。算法如下:
  while i≤(m-1) do
  begin
    ①取得Wi的最后一个字a与Wi+1的第一个字b,组成的字串ab;
    ②扫描词簇结点链表,把这两个汉字与词根进行匹配;
    ③如果匹配成功,则发现交叉歧义,进行歧义处理;
    ④否则,i=i+1。
  end
  上面的交叉歧义检测方法算法简洁,比正、逆向匹配相结合检测歧义的方法要快得多。
  为验证本文的分词算法,我们设计了一个分词系统,它可进行MM、RMM和二字词簇分词。分词的实验语料是《人民日报》的新闻文稿(陌生的人名和地名已经预先放入分词词典),实验结果见表1。两种分词方法的时间比与我们的理论推导基本相符,但是还存在一点差异,其原因在于我们的理论推导进行了一些简化,而且具体的程序实现方法也会带来一些误差。

4 结  语

  本文提出的分词算法有以下优点:
  (1)利用词频统计结果,占所有词汇75%左右的两字词只需通过主扫描就可切分出来,提高了分词速度。
  (2)把长词的匹配限制在其二字词簇内部进行,也就是把传统MM分词方法的全局长词优先匹配改进为局部变长长词匹配,各词簇的最大词长各不相同,不存在一个全局的最大词长M。这样,不仅提高了处理速度,而且使MM分词方法的M设置难题彻底消失。
  (3)分词词典的生成和维护都简单方便。我们的分词词典是一个文本文件,用户可以用一般文本编辑器对它进行修改。
  (4)系统在分词过程中总会发现新词。但即使向我们的分词词典增加大量新词,也基本上不会影响分词速度,因为有很大部分新词会添加到已存在的词簇里去,主链表上结点数目增加并不大。
  我们的实际应用表明,该算法既能满足分词速度要求,又易于实现。

参考文献

[1] 刘开瑛、郭炳炎:《自然语言处理》,北京,科学出版社,1991
[2] 苏新宁:汉语词切分标引算法的改进,《情报学报》,1996,15(6),426—430
[3] 骆正清、陈增武、胡正序:一种改进的MM分词方法的算法设计,《中文信息学报》,1996,11(3)
[4] 张民、李生等:基于知识评价的快速汉语自动分词系统,《情报学报》,1994,15(2),95—105
[5] 姚天顺、张桂平、吴映明:基于规则的汉语自动分词系统,《中文信息学报》,1990,4(1)
[6] 张普、张光汉:现代汉语“有穷多层列举”自动分词方法的讨论,《语言和计算机》,1987,(3),112—124
[7] 王晓龙、王开铸、李仲荣:最小分词问题及其解法,《科学通报》,1989,34

收稿日期:1998年1月12日
  作者简介:郭祥昊,1970年生,博士研究生,主要研究领域为人工智能、自然语言处理。钟义信,1940年生,教授,博士生导师,主要研究领域为信息科学理论、通信理论、人工智能与人工神经网络。杨丽,1971年生,硕士研究生,研究方向为智能电子系统。

(责任编辑 孙月湘)

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

       

    验证码: 请点击后输入验证码 收听验证码

    发评论

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

      

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

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

    新浪公司 版权所有