中文分词算法研究

中文分词算法研究（精选7篇）

中文分词算法研究 篇1

随着搜索引擎技术的广泛应用,全文检索技术和中文分词技术也逐步受到广泛的研究和应用。然而到目前为止,还没有完全成熟实用的中文分词系统面世,这成为严重制约中文信息处理发展的瓶颈之一。本文致力于研究中文分词算法,通过实验对分词模块的分词效果做出比较,对分词算法、词典对分词质量的影响做出客观的判断和评估,从而为中文分词的进一步发展提供了基础和方向。

1 分词技术综述

1.1 全文检索技术

所谓全文检索是指计算机索引程序通过扫描文章中的每一个词,对每一个词建立一个索引,指明该词在文章中出现的次数和位置,当用户查询时,检索程序就根据事先建立的索引进行查找,并将查找的结果反馈给用户的检索方式。在中文文档中根据是否采用分词技术,索引项可以是字、词或词组,由此可分为基于字的全文索引和基于词的全文索引。

基于字的全文索引是指对于文章中的每一个字都建立索引,检索时将词分解为字的组合。对于各种不同的语言而言,字有不同的含义,比如英文中字与词实际上是合一的,而中文中字和词有很大分别。此方法查全率较高, 但查准率较低。有时会出现令人啼笑皆非的检索结果,如检索货币单位“马克”时,会把 “马克思”检索出来。

基于词的全文索引是指对文章中的词,即语义单位建立索引,检索时按词检索,并且可以处理同义项等。英文等西方文字由于按照空白切分词,因此实现上与按字处理类似,添加同义处理也很容易。中文文字则需要切分字词,以达到按词索引的目的。对中文文档进行切词, 提高分词的准确性, 抽取关键词作为索引项, 实现按词索引可以大大提高检索的准确率。

1.2 中文分词技术

中文分词与英文分词有很大的不同,对英文而言,一个单词就是一个词,而汉语是以字为基本的书写单位,词语之间没有明显的区分标记,需要人为切分。

目前国内外对于中文分词的主要研究成果分为以下几种:正向最大匹配法、反向最大匹配方法、分词与词性标注一体化方法、最佳匹配法、专家系统方法、最少分词词频选择方法、神经网络方法等[1]。

纵观众多研究成果,可以看出当前中文分词还存在一下两个基本的问题需要解决[2]:

(1)歧义问题。汉语中存在大量的歧义现象,对几个字分词可能有好多种结果。简单的分词往往会歪曲查询的真正含义。

(2)未登录词识别问题。理想的系统应该能对未登录词进行记录和识别,并通过不断整理,增强未登录词识别的能力。

2 分词算法研究

下面各节,对当前研究的分词算法进行了分析,并设计了分词原型选择实验,对当前流行分词模块进行测评和比较。

2.1 中文分词基本原理

中文分词的基本处理是针对输入文字串进行分词、过滤处理,输出中文单词、英文单词和数字串等一系列分割好的字符串。中文分词模块的输入输出如图1所示。

2.1.1 ICTCLAS模块

ICTCLAS(Institute of Computing Technology, Chinese Lexical Analysis System)是由中国科学院计算技术研究所研究的基于多层隐马尔可夫模型HMM的汉语词法分析系统。HMM是一个双重随机过程,两个组成部分:①马尔可夫链:描述状态的转移,用转移概率描述;②一般随机过程:描述状态与观察序列间的关系,用观察值概率描述[4]。

基于HMM的分析系统的功能有:中文分词;词性标注;未登录词识别。

该模块包含的词典是通过统计方法建立的,对其进行了封装,以.dct格式存储。

2.1.2 最大正向匹配算法模块

最大正向匹配算法是项目中常用的分词解决方案。最大正向匹配算法模块采用机械式匹配算法的原理,通过建立词典并进行正向最大匹配,对中文进行分词。尽管最大匹配法分词是常用的解决的方案,但是无疑它存在很多明显的缺陷,这些缺陷也限制了最大匹配法在大型搜索系统中的使用频率。最大匹配法的问题有以下几点:

2.1.2.1 长度限制

由于最大匹配法必须首先设定一个匹配词长的初始值,这个长度限制是最大匹配法在效率与词长之间的一种妥协。

(1) 词长过短,长词就会被切错。例如当词长被设成5时,也就意味着它只能分出长度为5以下的词,例如当这个词为“中华人民共和国”长度为7的词时,我们只能取出其中的5个字去词典里匹配,例如“中华人民共”,显然词典里是不可能有这样的词存在的。因此我们无法下确的划分出“中华人民共和国”这样的词长大于5的词。

(2) 词长过长,效率就比较低。效率是分词算法、甚至是整个算法理论体系的关键。算法书里所有的高深的查询或排序算法都是从效率出发的,否则任何办法都可以解决分词效率低的问题。必须要在词长与效率之间进行妥协,既要求分词尽量准确,又要求词长不能太长。

2.1.2.2 掩盖分词歧义

中文是如此复杂的语言,机械的电脑是很难理解这么复杂的语言,因此它必然会带来歧义性,两个简单的例子:

(1)“有意见分歧”(正向最大匹配和逆向最大匹配结果不同)。

有意/ 见/ 分歧/,有/ 意见/ 分歧/

(2)“结合成分子时”(正向最大匹配和逆向最大匹配结果相同)。

结合/成分/子时/

由于词的歧义性使我们在使用最大匹配法分词会产生错误的结果,而且使用正向分词与逆向分词往往会产生截然不同的结果。尽管使用回溯法或计算计算词的使用频率,可以使出现歧义的可能性减少,这样的结果仍然是不可避免的。

2.2 分词模型比较实验

2.2.1 分词系统的评价准则

分词系统的最主要的工作是进行分词。对于分词而言,不仅要求所研制的软件在分词的正确率和速度方面满足一定的要求,而且要像开发大型传统软件那样,在各个阶段不断的进行评价,其目的主要是检查它的准确性和实用性,分词的评价主要有以下几个方面:

(1)分词正确率。书面汉语的文本可以看成是字符序列,分词的正确率直接影响更高一级的处理。

(2)切分速度。切分速度是指单位时间内所处理的汉字个数。在分词正确率基本满足要求的情况下,切分速度是另一个很重要的指标,特别对于算法不单一,使用了辅助手段,诸如联想,基于规则的,神经网络,专家系统等方法更应该注意这一点。通常中文信息处理的文本数量是相当大的,因此必须考虑方法是否能使系统总开销合理。

(3)功能完备性。自动分词方法除了完成分词功能外,还应具备词库增删、修改等功能。

(4)易扩充性和可维护性。这是提供数据存储和计算功能扩充要求的软件属性,包括词库的存储结构,输入/输出形式的变化等方面的扩展和完善。这项指标与系统清晰性、模块性、简单性、结构性、完备性以及自描述性等软件质量准则有直接的联系,随着开发版本的升级,需要不断提高与改进,使之适应中文信息处理的各种应用。

(5)可移植性。 可移植性是指方法能从一个计算机系统或环境转移到另一个系统或环境的容易程度。 一个好的分词方法不应该只能在一个环境下运行,而应该稍作修改便可在另一种环境下运行,使它更便于推广[5]。

本着以上几点原则,设计了分词模块测评实验。

2.2.2 实验参数

通常,我们用查全率、查准率来衡量信息检索系统的检索效率。查全率( recall ratio) 指系统在实施某检索作业时,检出相关文献的能力。查准率(precision ratio) 指系统在实施某一检索作业时,拒绝不相关文献的能力,是衡量信息检索系统精确度的尺度[6]。一般来说,查全率越高,精度越低,反之精度越高,查准率越低。由F1参数来综合查全率和查准率的结果进行比较。当然还有快速查找大量文本文件的速度和能力,例如:对单一项的查询、多个项的查询、短语查询、通配符等功能。但与分词模块直接相关的参数主要是查全率、查准率、F1参数和分词速度[7]。本实验中,也使用查全率、查准率、F1参数、分词速度几个参数来评价系统性能。公式如下:

查全率undefined

undefined

分词速度undefined

2.2.3 测试集

在实验中,选择测试集来自北京大学的《人民日报》1998年上半年的纯文本语料。共包含3,148篇文章1,673,069字。

2.3.4 实验步骤

(1)收集一个题材和体裁分布平衡的测试文本集(生语料)。

测试集的规模一般在50万至100万字次左右。

(2)编制一个分词评测软件。

软件的输入是两个文本:

①被测系统对测试集实施自动分词的输出结果。

②标准文本。

评测软件对这两个文本进行逐词对比和统计计算,然后分别输出被测系统的评测结果:查全率、查准率、F1参数、分词时间、分词速度。

2.2.5 测试算法

测试步骤如下,见图2:

(1)读取生语料,读取熟语料,进入2;

(2)是否存在下一个文件?是,进入3;否,进入12;

(3)滤掉标点,把句子分隔开,存在数组中,进入4;

(4)加载分词模块,进入5;

(5)对处理后的生语料进行分词,并记录开始时间,进入6;

(6)记录结束时间,进入7;

(7)将分词结果和熟语料对应输出,进入8;

(8)判断是否存在下一个句子,是,进入9;否,进入10;

(9)判断是否存在下一个词,是,进入11;否,进入8;

(10)计算相关参数,并进入2;

(11)在熟语料的对应句子中进行匹配,判断是否成功?是,accurate++,进入9;否,进入9;

(12)计算相关参数;

2.2.6 测试结果及分析

对测试结果进行整合得到:ICTCLAS耗时60.110s,分词速度为60.47KB/s;最大正向匹配算法进行分词,耗时25.763s,分词速度为141.09KB/s。

测评综合结果如表1所示。

对结果进行分析,可以看出最大正向匹配算法在速度上明显优于中科院ICTCLAS分词模块,但在查准率、查全率和F1参数上逊于中科院ICTCLAS分词模块。正确性比较见图3。

分析原因有以下两点:

(1)算法匹配方式:

最大正向匹配算法一般选择最长的词语进行匹配,而语料库中的熟语料并未按照最长词语进行划分。这是导致分词结果与熟语料存在一些不匹配的另一个原因。但这并不代表该算法正确率不高,而只是与语料库不完全匹配。这一点可以由人工从分词的结果中看出来。

(2)词典的质量:

最大正向匹配算法模块选用的通用词典在质量上可能与ICTCLASC存在差别。在机械式匹配算法中,词典的质量严重影响着分词的质量。所以,词典的质量可能是导致模块几个参数值下降的一个原因。因此,有必要进一步提高词典的质量。

综合分词结果来看,得到以下结论:

ICTCLAS模块在查准率、查全率、F1参数占有优势。但是,其词典存储形式不开源,不支持词典编辑,并且无法建立专业词典,功能完备性、易扩充性和可维护性上具有缺陷。在测试中发现,其稳定性不高,参数传递不精准可能会导致分词系统的分词结果出现乱码。

最大正向匹配算法在查准率、查全率等参数上测试结果逊于ICTCLAS。但其正向最大匹配算法的速度和精度上基本能够满足系统的要求。并且能够通过词典质量的进一步改进,使得分词效果得到改善。它在功能完备性、易扩充性和可维护性上优于ICTCLAS,更适用于在系统开发中的应用。

3 结束语

论文研究了当前搜索引擎技术中采用的分词技术,设计了分词模块的选择试验,比较了ICTCLAS和最大正向匹配算法模块这两种技术的优缺点。

由于是对中文自动分词技术的初步应用,所以工作还存在一些不足。比如:分词算法还存在切分歧义,切分处理技术还不能适应汉语丰富的构词变化等问题。

摘要：当前搜索引擎技术被广泛的应用,这使得全文检索技术和中文分词技术的研究逐渐深入。本论文致力于研究中文分词算法,通过实验对分词原理做出比较,对分词算法、词典对分词质量的影响做出判断和评估,并设计了分词原型比较实验,比较测评了当前流行的中文分词方式:中科院分词模块和最大正向匹配法模块。

关键词：全文检索,中文分词,查准率,查全率,F1参数

参考文献

[1]马玉春,宋涛瀚.web中中文文本分词技术研究.计算机应用,2004,24(4):134~136

[2]易丽萍,叶水生,吴喜兰.一种改进的汉语分词算法.计算机与现代化,2007,2:13~15

[3]Chien Lee-Feng.PA T-tree-based adaptive keyphrase extraction for intelligent Chinese information retrieval.Information Pro-cessing and Management,1999,35:501~521

[4]顾铮,顾平.信息抽取技术在中医研究中的应用.医学信息学,2007,20:27~29

[5]何淑芳.基于BBS文本信息的中文自动分词系统的研究.青岛:中国海洋大学,2006.

[6]张自然,金燕.知识检索与信息检索的检索效率比较.情报科学,2005,4:590~592

[7]曹桂宏,何丕廉,吴光远,聂颂.中文分词对中文信息检索系统性能的影响.计算机工程与应用,2003,19:78~79

中文分词算法研究 篇2

信息化的发展和网络的普及,使得人们对信息处理的方式也发生了变革。要让计算机能够自动地处理信息就必须借助分词技术让计算机理解自然语言。在自然语言信息处理中,中文与英文存在着巨大的不同。在英文中,空格作为自然分隔符去分辨单词,而在中文中,字、句、段能够以明显的分隔符来分辨,可是对于词是没有这样的分隔符的。然而词是中文里最小的能够独立存在的有意义的成分,所以对于中文来说,将词确定下来是理解自然语言的第一步。特别是现如今中文搜索引擎技术的飞速发展,使得中文分词技术显得越发的重要。目前使用最广泛的方法是基于词典的分词方法,这种方法核心是词典的匹配算法。本文就是基于Lucene平台的加入设计改进的MMSEG算法的中文分词技术方法。

1 基于Lucene的中文分词

作为开源组织Apache Jakarta的成员项目,Lucene是一个用Java语言实现的成熟的、自由的、开源的软件项目,是一个高性能的、可扩展的信息检索工具集,可以方便快捷地融入到应用程序中,以增加索引和搜索功能[2,3,4]。

文本分词技术在Lucene中起着及其重要的作用,因为要对需要索引和检索的文档进行分词处理,Lucene的核心包和扩展包对中文分词采取类似英文的机械式切分方法,这些方法由于完全不考虑中文独特的语法和语义,所以很难保证用户在中文环境下对全文检索的需求。因此,在Lucene的架构上,选择了加入MMSEG算法,以此来设计并实现了可以适用于日常应用的中文词典分词模块,其中设计的中文歧义消除模块能够有效地屏蔽大部分的机器歧义字符串,从中提取出正确的词汇。

2 中文分词技术

对于计算机来说,中文自动分词就是清楚,合理地将中文的词与词相分割开,达到明确文字所要表达的意思,当前汉语信息处理的主要任务已从“字处理”转移到“词处理”。因此,词的切分问题是首先需要解决的,除此之外汉语中的歧义也是自动分词过程中不可避免的现象。在自动分词过程中具有两种或两种以上切分形式的字段称为歧义字段,只有歧义字段才会产生错误切分。因此想要提高中文分词的速度和准确率,选择一个能快速准确切分词和消除歧义现象的算法是极其重要的。

根据是否利用机器可读词典和统计信息可将汉语自动分词方法分为三大类:(1)基于词典的方法;(2)基于统计的方法;(3)混合方法[5]。在这其中应用范围最广,最流行的当属基于词典的方法。这种算法是在切分时用待切分的字符串去匹配词典中的字条,如果匹配成功则切分成一个词。目前最常用的基于词典的字符串匹配方法,主要包括最大匹配、全切分和最短路径法。

3 中文分词算法

3.1 FFM算法

最大匹配算法是基于字符串匹配的分词方法,按照一定的策略将待处理的字符串与足够大的机器词典中的词条进行匹配,若在词典中找到某个字符串,则匹配成功,切出该词,否则进行其他相关处理。按照扫描方向的不同,字符串匹配可以分为正向匹配和逆向匹配;按照长度不同优先匹配的情况,可以分为最大匹配和最小匹配。在此主要介绍最大匹配算法。最大匹配算法能够保证将词典中存在的最长复合词切分出来,之所以称为最大匹配,就是要求每一个句子的切分结果中词的总数最少。最大匹配算法原理简单且易于实现,能保证最长复合词从词典中切分出来[6,7]。

这里提到的有两种最大匹配法:(1)简单最大匹配算法;(2)复杂最大匹配算法。

简单最大匹配法算法的基本思想:(1)取待切分汉语句的m个字符作为匹配字段,其中m为机器可读词典中最长词条的汉字个数;(2)查找机器可读词典并进行匹配若能匹配则将这个匹配字段作为一个词切分出来,若不能匹配则将这个匹配字段的最后一个字去掉,剩下的字符串作为新的匹配字段进行再次匹配,重复以上过程直到切分出所有词为止。

最大匹配算法的要求就是,每一句的切分结果中词的总数最少,即取出与最长词条相符合的词。例如在“中国人民大学大学生”中,在词典中匹配,这句话可能被切分为“中国/人民/大学/大学生”。而按照最大匹配算法,则是“中国人民大学/大学生”。可是,随之带来的是忽略了词条中的子词,“中国/人民/大学/大学生”。同时产生的歧义无法消除,如由于自然语言的二义,例如“棒球拍卖完了”,既能切分为“棒球/拍卖/完了”,也可以切分为“棒球拍/卖/完了”。另外由于机器自动分词产生的歧义,如“他只会诊断一般的疾病”,切分为“他/只会/诊断/一般/的/疾病”,也可以切分为“他/只/会诊/断/一般/的/疾病”。

复杂最大匹配算法的基本思想:从字句的开头开始分词,如果存在有歧义的分词(例如,_C1_是一个单词,但是_C1C2_也是一个单词),就继续搜寻以_C1_或者_C1C2_开头的三词块。例如以下存在的可能的三词块:

其中第三个词块的长度是最长的,则在第三个词块中的第一个单词_C1C2_就被认为是正确的分词。在此基础上继续重复这个过程从汉字C3开始,一直到字句的最后一个词被识别。

3.2 改进的FMM算法,即MMSEG算法

MMSEG算法实现了前面所说的最大匹配算法的简单和复杂形式。更进一步实现了三个消除歧义方法,也就是为了消除之前算法所无法消除的歧义。

规则1:组合长度最大

适用于简单最大匹配法以及复杂最大匹配法,即,取最大长度的单词。例如:

“同济大学物理科学馆”,存在如下组合:

同济大学__物理__科学馆

同济大学__物理__科学__

同济大学__物__理科__

同济__大学物理__科学馆

同济__大学__物理__

应用此规则可以切分出合理的组合,选择组合长度最大的词块,然后选择这个词块的第一个词,作为切分出的第一个词,上文例子中“同济大学__物理__科学馆”中的“上海大学”,或者“同济__大学物理__科学馆”中的“上海”。

规则2:平均词语长度最大

在应用复杂最大匹配算法时,如果经过规则后任然存在超过1个最大长度的三词块,例如:

“竞技场”,存在如下组合:

竞技场__(3/1=3)

竞技__场__(3/2=1.5)

竞__技__场(3/3=1)

由于组合长度均为3,规则1无法处理。利用规则2,即选择最大平均词语长度的词块(平均词长=词组总字数/词语数量)。根据此规则,选择平均词语长度为3的“竞技场”。

规则3:词语长度的变化率最小

当出现例如这样的词汇“研究生命起源”,其组合如下:

研究生__命__起源sqrt(((3-2)2+(1-2)2+(2-2)2))/3)=0.8165

研究__生命__起源sqrt(((2-2)2+(2-2)2+(2-2)2))/3)=0

规则1无法过滤,因为组合长度均为6,经过规则2也无法过滤,因为平均词语长度均为6/3=2。此时,利用规则3(词语长度变化率)来切分,也就是标准差公式。

标准差,在概率统计中最常使用作为统计分布程度上的测量。标准差定义是总体各单位标准值与其平均数离差平方的算术平均数的平方根。它反映组内个体间的离散程度。

根据此条规则,由标准差公式算出的结果得出,选择第二条词块。

规则4:单字词词频自然对数累加计算

例如“设施和服务”,存在如下的组合:

设施__和__服务

设施__和服__务

设__施__和__服务

设__施__和服__务

经过规则1后,剩下两个词块无法过滤:

设施__和__服务

设施__和服__务

而经过规则2和规则3的计算后,所得结果依然相同,此时利用规则4(单字词词频自然对数累加计算),比较单个字词的使用频率,选择更常见的那个。同时,这里选择自然对数计算而不是直接累加,是因为即使词频一样,实际的效果也是不同的。例如,两个词块中都存在2个单字词,其词频分别为3和7,另一种情况为5和5,直接的累加结果均为10,这样就无法区分。而对其取自然对数再相加,得到结果为(ln5+ln5)>(ln3+ln7)。

4 中文分词模块的设计与实现

4.1 词典和数据结构

本文测试词典源自于网络上开源的词典,包含约2万个以上的词条,一定程度上保证了测试的完整性和准确性。存储词典的数据结构为Hash Map,其时间复杂度为O(1)。

测试词典的词条长度的分布如图1所示。

由于词条长度大于7的比例过小,为了分词的准确性,特此省略7字长度以上的词条。

4.2 分词模块系统框架

分词模块系统框架如图2所示。

4.2.1 分词预处理

首先预处理阶段,利用显式(空格,分段符等)和隐式的切分标记(标点符号、数字、ASCII字符以及出现频率高、构词能力差的单字词、数词+单字常用量词模式)将待分析的文本切分成短的汉字串。

4.2.2 分词流程

分词的基本流程如图3所示,其中切分的过程包括对FFM和MMSEG算法的选择。在词条切分之后进行歧义的过滤,此时就需要MMSEG算法中的4条规则的作用。

5 实验结果

测试的文章段落来自“人民日报”的网络版中一篇文章,测试的分词结果是自动分词的结果。

路遥生前有言:“写作就是燃烧自己。”为创作《平凡的世界》,他花4年时间阅读了100多部长篇小说及各类书籍,翻阅了10年间全国主要报纸,多次重返陕北故乡。创作期间,他把自己“关”起来如牛马般劳作。得知作品获茅盾文学奖时他说:很高兴,但当初只想着写,能不能获奖确实没想过。幸福在于创造的过程,而不是那个结果。凡做一件事,便把这件事看作自家生命,专注于创作过程,路遥深入“不闻掌声”之境。

分词的结果如图4所示。

根据多次实验结果的分析和测算,对比公布的现在较流行的分词算法所得结果,对比结果如表1所示。

6 结束语

随着互联网的快速发展,网络上每天会产生难以计数的信息,面对这种信息爆炸,人们要想在其中寻找合适的信息是极其困难的。由此而生的全文搜索引擎发挥着巨大的作用,而其是以匹配英文语言出现的。对于汉语的搜索检索仍然是研究的重要课题,引起了广泛的关注和研究热情,但因为概念较新,目前已发表的关于中文分词技术的文献还不多。

本文采用的基于正向最大匹配算法(FFM)结合MMSEG算法的中文分词技术通过Lucene搜索引擎架构实现的中文分词器,比其原本的中文分词模块工作效率更高,分词效果更好。因此在针对汉语的搜索方面,提出了一个更好的解决方向。同时,本系统也存在许多不足的地方,比如分词速度不够快;分词词典不够完善;对于未登陆词条的处理还不够;以及欠缺对专有名词的处理。今后,还将在自动更新词典,完善词典中数据结构方面进行完善,使匹配词条时能更快,更有效率。

参考文献

[1]Chen K J,Liu S H.Word identification for Mandarin Chinese sentences[C].Proceedings of the Fifteenth International Conference on Computational Linguistics,Nantes:COLING-92,1992.

[2]王志嘉,薛质.一种基于Lucene的中文分词的设计与测试[J].信息技术,2010(12):50-54.

[3]周敬才,胡华平,岳虹.基于Lucene全文检索系统的设计与实现[J].计算机工程与科学,2015(2):252-256.

[4]朱岸青,黄杰.基于Lucene的全文检索系统模型的研究和开发[J].暨南大学学报:自然科学与医学版,2009,30(5):504-508.

[5]龙树全,赵正文,唐华.中文分词算法概述[J].电脑知识与技术,2009,5(10):2605-2607.

[6]张春霞,郝天永.汉语自动分词的研究现状与困难[J].系统仿真学报,2005,17(1):138-143.

中文分词算法研究 篇3

分词算法的研究是中文信息处理的基础工作,也是中文文本特征抽取的前提。所谓分词就是把字与字连在一起的汉语句子分成若干个相互独立、完整、正确的单词[1]。目前常用的分词方法[1,2]归纳起来主要有两类:一类是理解式分词法,即利用汉语的语法知识、语义知识和心理学知识进行分词,此类方法需要建立分词数据库、知识库和推理机;另一类是机械式分词法,此类方法一般以分词词典为依据,通过将文档中的汉字串与词表中的词逐一匹配来完成词的切分。

分词方法的性能可以从准确性、高效性、通用性和适用性等几个方面来衡量。但考虑到分词算法的应用领域大多对实时性和准确性两方面有很高的要求,因此,实现较简单的机械式分词法中的正向最大匹配法仍然是应用最为广泛的一种方法。下面就通过对该方法的分析,提出了一种可以提高分词效率的改进的正向最大匹配方法。

1 正向最大匹配算法

基于分词词典的正向最大匹配法[1,3](Forward Maximum Matching,FMM)的目的是通过正向扫描待分析的汉字串,将其与词典中“最大”的词条进行匹配,将符合匹配条件的最长的词语分离出来。其算法流程如图1所示。

2 改进的FMM算法

在分析了FMM算法的分词流程之后,这里提出一种改进的FMM算法,此算法保留了传统FMM算法实现简单的特点,同时利用了词频统计[4]结果,在优先处理两字词后,将长于两字的长词放到两字词根的后缀集合中进行处理,从而将传统FMM算法的全局最大匹配模式转化为局部变长最大匹配模式[5,6]。经分析,这种改进显著提高了分词速度。

2.1 分词词典构造

分词词典是由一个通用汉语词典经处理后产生的,由单音节词和两字词根后缀两部分构成。两字词根后缀词条的形式如下:

t+N+maxLength+postfix1+postfix2+…+postfixN

其中t为两字词根,N为以t为词根的两字后缀词的数目,maxLength为两字词根后缀集合中最常词条的长度,postfix1,postfix2等表示各个后缀,按照字数升序排列。

分词词典是一个文本文件,按照如上的词条形式,将其读入内存,建立链表形式的数据结构。链表中的结点为两字词根,每个结点包括两字词根、两字词根后缀集合的最长词条长度等信息。

2.2 算法描述

分词时,从汉字串中读入两个汉字,扫描词根结点链表,把这两个汉字与词根进行匹配,称为词根扫描。如果匹配成功,则根据词根结点的信息,再顺序从汉字串中读入maxLength-2个汉字,并在两字词根后缀结点内进行最大匹配,称为后缀扫描。具体算法描述如下:

算法:改进的正向最大匹配法

输入:分词词典和汉字字串S=C1C2…CiCi+1 …CN,且分词指针Pi指向CI

输出:词集合

Step1:将CiCi+1读入。

Step2:执行词根扫描。搜索分词词典,如果找到以CICI+1词根的词根结点,转到step4。

Step3:如果没有找到以CICI+1为词根的词根结点,则Ci为单音节词,转到step6。

Step4:如果词根结点中maxLength=2,则为两字词,转到step6。

Step5:执行后缀扫描。令k=maxLength,当k大于2时,反复执行如下操作:如果字串Ci+2Ci+3…Ci+k-1在 词根后缀结点集合内,则CiCi+1…Ci+k-1是一个汉语多音节词,转到step6,k值减1。

Step6:把新分出的词W加上分隔符,顺序放入缓冲区。

Step7:令Pi=(Pi+词W的长度),转Step1继续读取字串后面的字符,直至遇到标点符号。

3 算法效率的对比分析

时间复杂度是衡量和分析算法优劣的一个非常重要的标准。在其它条件相同的情况下,如果时间复杂度较低,则说明该种分词方法的性能越好,分词速度越快。计算分词方法的时间复杂度时,一般选择匹配次数作为基本衡量单位,即平均每切分一个词所需要的匹配次数[2]。根据文献[2]给出的词频统计数据和时间复杂度的计算方法,下面对改进的FMM算法和传统FMM算法的时间复杂度进行分析比较。

为了简化计算,先作如下假设:

① 通用分词词典的词条个数为N,两字词占3/4,长词的最大长度(以汉字个数计算)为M,长词平均长度为L,为了提高分词精度,最大匹配系数为M。

② 两字词根分词词典由通用分词词典生成,主链表的结点数目为3/4×N。

③ 两个词典没有排序和索引,词条在词典中出现的位置是随机的。

根据假设,下面估算两种算法成功匹配一个词需要进行比较的平均次数。

对于传统的FMM算法:

① 切分一个两字词要进行的平均匹配次数C1=(M-2)×N+N/2。

② 切分一个长词要进行的平均匹配次数C2=(M-L)×N+N/2。

对于改进的FMM算法,由于采用了两字词根分词的方法,因此可以得到:

① 切分出一个两字词要进行的平均匹配次数C1=3/4×N/2。

② 切分出一个长词要进行的平均匹配次数C2=3/4×N/2。

考虑到两字词大约占词典词条数量的3/4,所以可以得到切分出一个词的平均匹配次数的计算公式:

C=3/4×C1+1/4×C2 (1)

如果取最大匹配系数M为17,长词平均长度为4[2],按照公式(1)计算得到两种分词算法的平均匹配次数分别为15N和3N/8。

由此可以看出,改进的FMM算法成功匹配一个词所需要进行比较的平均次数要小于传统FMM算法比较的平均次数,即其时间复杂度优于传统FMM算法。

4 结束语

本文在传统分词算法的基础上提出的改进分词方法由于采用了词频统计结果,不仅保留了传统算法实现简单的特点,同时也进一步提高了分词速度,可以很好满足中文信息处理对分词的要求。

参考文献

[1]刘源,谭强,等.信息处理用现代汉语分词规范及自动分词方法[M].北京:清华大学出版社,1994.

[2]揭春雨,刘源,等.论汉语自动分词方法[J].中文信息学报,1989,3(1):1-8.

[3]苏新宁.信息检索理论与技术[M].北京:科学技术文献出版社,2004.

[4]骆正清,陈增武,胡上序.一种改进的MM分词方法的算法设计[J].中文信息学报,1996,10(3):30-36.

[5]郭辉,苏中义,王文,等.一种改进的MM分词算法[J].微型电脑应用,2002(1).

中文分词算法研究 篇4

关键词：中文分词,最大匹配算法,校园网

信息社会的飞速发展，促使高校教学向多元化、信息化方向发展，通过校园网平台是信息沟通的一种重要方式，要想高效快速的查找信息，中文分词是必不可少的基础技术。中文却通过字与字之间的组合来进行意思的表达，也就是字组成词，而在中文句子的描述中，字与字、词与词没有隔断的现象，词与词没有明显的界限，这就影响了关键字的获取和匹配，完全凭着阅读人对句法、语义的感觉进行区分。目前，对中文分词最常见的算法是正反向最大匹配算法，但这种算法容易产生歧义等问题，本文提出一种改进型正反向最大匹配中文分词算法在校园网信息提取中的应用。

1 中文分词及其难点

分词也被称为切词，是将连续的中文汉字序列通过一定的规范重新组合成分词序列。例如：在英文中要想表达“我是一名教师”—“I am a teacher.”计算机可以快速地通过空格完成对词的切分，也可以立刻找到“教师”对应的单词“teacher”。但是在中文“我是一名教师”的描述中，要想让计算机进行“教师”的理解则需要大费周折，因为计算机不能立刻理解中文汉字“教”和“师”组合在一起表示“教师”。必须进行正确的切词“我是一名教师”，才能让计算机进行下面的操作。中文分词是中文信息处理的基础，所以良好的中文分词对众多相关学科领域的发展有很大的推动作用。

1.1 歧义识别

组合型歧义是指组成某个词的一部分任然是一个词，例如“人民大会堂”是一个词，同时“人民”和“大会堂”也是词；交集型歧义是指一句话中某个字与前后都可以组成单词，例如“这种面包装很好”，既可以分为“这种面包装很好”，也可以分为“这种面包装很好”，真歧义是一句话有不同解释，即便是我们也很难找到正确的意思，例如“北京人多”，既可以理解为“北京人多”，也可以理解为“北京人多”。真歧义必须结合上下文意思进行理解，而在中文分词中主要是对交集型歧义的处理。

1.2 新词识别

中文词语中包含大量的人名、地名、机构名、商标名等，这些词语方便了人们的日常使用，计算机识别这些名词确实非常困难。

2 最大匹配算法及其改进

2.1 传统双向最大匹配算法

最大匹配算法分为正向和逆向两种，最大正向匹配是考查机器字典中的最大词所含字数I，在待切分的语料库中从左至右切出字长为i的字符串，将切分出来的字符串与机器字典进行匹配，成功则作为一个词被切分出来，若是匹配不成功则去掉最右边的一个字，将剩下的i-1个字符串与机器字典匹配，依次循环直到匹配出字符串中所有词。算法可以描述为：

第一步：i=0，当前指针P，指向输入字符串的初始位置；

第二步：计算指针P到输入字符串末端的最大长度，设为m;

如果m=1转向第三步；否则n=词典最长词的字数；

如果m<n，则n=m;

第三步：对当前指针P取n个汉字作为一个待定词t，进行判断：

(1）如果t出现在词典中，则切词成功，在t后添加切分符号，再次转入第三步；

(2）如果t不在词典中且长度大于1，则去除最右端一个字符转向第三步中的（1）；若去除最右端一个字符后长度为1，则作为一个单字词加到词典，再转向第三步；

(3）根据当前字符串的长度，修改指针P,

如果指向字符串末端，则转向第四步；

否则i=i+1，返回I.

第四步：输入分词结果。

最大匹配法是遵循“长词优先”原则对语料库进行分词，虽然能够保证最大的词语长度，得到较少的切分次数。但是现有的最大匹配法都只是在局部范围内进行最大匹配，即每次最大匹配都是在最先i个或是最后i个字符的范围进行匹配，这样并没有充分体现“长词优先”的原则[6-7]。例如：

例句1：“当中华人民共和国成立的时候”

例句2：“当他看到小孩子时”。

用正向最大匹配法进行切分，例句1的切分结果是“当中华人民共和国成立的时候”，显然是错误的，例句2切分结果“当他看到小孩子时”则正确。

2.2 双向结合最大匹配算法的改进

考查上面的例子注意到，正向最大匹配算法虽然对大多数情况适用，但是对分词过程中产生的歧义不能消除。进一步分析，分词初始阶段读入语料库的过程相当于是将语料库装入队列，队列的大小可以看作是分词过程中的最大词长。在进行词典匹配，匹配成功相当于从队列中输出；否则对待切分字符串删除最后一个字符，类似于出栈操作。所以，结合队列和栈之间的关系，该进了正向最大匹配算法，过程如下：

第一步：栈1、2清空，栈1中存放长度最大为i的带切分字符串；当读入的带切分字符串为0时结束操作。

第二步：栈1存放的字符串与词典匹配，匹配成功，转入第三步；否则将字符串中的最后一个字符进行出栈操作，回到第二步。

第三步：栈1中如果剩下最后1个字符，则最为单字词直接输出，并转向第一步，若剩下字符个数大于1，则继续执行第四步。

第四步：将栈1中最后一个字输出，得到总字数为（i-1）的字符串，将这（i-1）个字符串作为待匹配字符串压入栈2.

第五步：将栈2中的字符串再次与词典进行匹配，如果不成功，意味着栈1中的词不存在交集型歧义，是一个独立的词语，可以将栈1的字符串输出得到一个切分成功的词，并转向第一步；如果匹配成功，则意味着栈1与栈2中的有交集型歧义，转向第六步；

第六步：按照“长词优先”原则，对比栈1和栈2的词长，选择最终的切分结果，对余下的语料执行第一步；若词长相等，基于语料库得到两个可能的词的成词概率，选择概率最大的一组作为切分结果，剩下语料转为第一步。

对于例1，将“当中华人民共和”压入栈1，与词典匹配出“当中”，将“中”压入栈2，再压入“华人民共和国”，栈2匹配成功，根据“长词优先”，“中华人民共和国”被分出，前面的分词结果就是“当中华人民共和国”，可以很好的避免交集型歧义的产生。同时结合逆向最大匹配法可以很好的提高中文分词的效果。

3 实验结果分析

本文选择高等教育出版社出版的小学6年级语文课文10篇（不包括诗词歌赋文言文）计6 114字，从网站上选择短篇小说15篇计71 420字、网上时事政治新闻稿件20篇计31 420字作为实验语料。对比正向最大匹配算法、逆向最大匹配算法、双向最大匹配和本文算法，可以看出，本文提出实际使用效果要高于其他两种如表1。

参考文献

中文分词算法概述 篇5

自然语言处理是人工智能的一个重要分支。中文分词是中文自然语言处理的一项基础性工作,也是中文信息处理的一个重要问题。随着搜索引擎技术的广泛应用,全文检索技术和中文分词技术也逐步受到广泛的研究和应用,然而到目前为止,还没有完全成熟实用的中文分词系统面世,这成为严重制约中文信息处理发展的瓶颈之一。本文致力于研究中文分词算法,通过分词算法对分词的质量做出客观的判断和评估,从而为中文分词的进一步发展提供基础和方向。

2 中文分词技术综述

2.1 全文检索技术

所谓全文检索是指计算机索引程序通过扫描文章中的每一个词,对每一个词建立一个索引,指明该词在文章中出现的次数和位置,当用户查询时,检索程序就根据事先建立的索引进行查找,并将查找的结果反馈给用户的检索方式。在中文文档中根据是否采用分词技术,索引项可以是字、词或词组,由此可分为基于字的全文索引和基于词的全文索引。

基于字的全文索引是指对于文章中的每一个字都建立索引,检索时将词分解为字的组合。对于各种不同的语言而言,字有不同的含义,比如英文中字与词实际上是合一的,而中文中字和词有很大分别。此方法查全率较高,但查准率较低。有时会出现令人啼笑皆非的检索结果,如检索货币单位“马克”时,会把“马克思”检索出来。

基于词的全文索引是指对文章中的词,即语义单位建立索引,检索时按词检索,并且可以处理同义项等。英文等西方文字由于按照空白切分词,因此实现上与按字处理类似,添加同义处理也很容易。中文文字则需要切分字词,以达到按词索引的目的。对中文文档进行切词,提高分词的准确性,抽取关键词作为索引项,实现按词索引可以大大提高检索的准确率。

2.2 中文分词技术

中文分词与英文分词有很大的不同,对英文而言,一个单词就是一个词,而汉语是以字为基本的书写单位,词语之间没有明显的区分标记,需要人为切分。中文分词系统是利用计算机对中文文本进行词语自动识别的系统,对其研究已经取得了很多成果,出现了众多的算法。根据其特点,可以将现有的分词算法分为四大类:基于字符串匹配的分词方法、基于理解的分词方法、基于统计的分词方法和基于语义的分词方法等。

3 中文分词方法

中文分词方法的基本原理是针对输入文字串进行分词、过滤处理,输出中文单词、英文单词和数字串等一系列分割好的字符串。中文分词模块的输入输出如图1所示。

3.1 基于字符串匹配的分词方法

这种方法又叫作机械分词方法、基于字典的分词方法,它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行匹配。若在词典中找到某个字符串,则匹配成功(识别出一个词)。该方法有三个要素,即分词词典、文本扫描顺序和匹配原则。文本的扫描顺序有正向扫描、逆向扫描和双向扫描。匹配原则主要有最大匹配、最小匹配、逐词匹配和最佳匹配。

1)最大匹配法(MM)。基本思想是:假设自动分词词典中的最长词条所含汉字的个数为i,则取被处理材料当前字符串序列中的前i个字符作为匹配字段,查找分词词典,若词典中有这样一个i字词,则匹配成功,匹配字段作为一个词被切分出来;若词典中找不到这样的一个i字词,则匹配失败,匹配字段去掉最后一个汉字,剩下的字符作为新的匹配字段,再进行匹配,如此进行下去,直到匹配成功为止。统计结果表明,该方法的错误率为1/169。

2)逆向最大匹配法(RMM)。该方法的分词过程与MM法相同,不同的是从句子(或文章)末尾开始处理,每次匹配不成功时去掉的是前面的一个汉字。统计结果表明,该方法的错误率为1/245。

3)逐词遍历法。把词典中的词按照由长到短递减的顺序逐字搜索整个待处理的材料,一直到把全部的词切分出来为止。不论分词词典多大,被处理的材料多么小,都得把这个分词词典匹配一遍。

4)设立切分标志法。切分标志有自然和非自然之分。自然切分标志是指文章中出现的非文字符号,如标点符号等;非自然标志是利用词缀和不构成词的词(包括单音词、复音节词以及象声词等)。设立切分标志法首先收集众多的切分标志,分词时先找出切分标志,把句子切分为一些较短的字段,再用MM、RMM或其它的方法进行细加工。这种方法并非真正意义上的分词方法,只是自动分词的一种前处理方式而已,它要额外消耗时间扫描切分标志,增加存储空间存放那些非自然切分标志。

5)最佳匹配法(OM)。此法分为正向的最佳匹配法和逆向的最佳匹配法,其出发点是:在词典中按词频的大小顺序排列词条,以求缩短对分词词典的检索时间,达到最佳效果,从而降低分词的时间复杂度,加快分词速度。实质上,这种方法也不是一种纯粹意义上的分词方法,它只是一种对分词词典的组织方式。OM法的分词词典每条词的前面必须有指明长度的数据项,所以其空间复杂度有所增加,对提高分词精度没有影响,分词处理的时间复杂度有所降低。

由上面的算法,不难看出基于字符串匹配的分词方法的优缺点:

优点:简单,易于实现。

缺点:1)匹配速度慢;2)存在交集型和组合型歧义切分问题;3)词本身没有一个标准的定义,没有统一标准的词集;4)不同词典产生的歧义也不同;5)缺乏自学习的智能性。

3.2 基于理解的分词方法

该方法又称基于人工智能的分词方法,其基本思想就是在分词的同时进行句法、语义分析,利用句法信息和语义信息来处理歧义现象。它通常包括三个部分:分词子系统、句法语义子系统和总控部分。在总控部分的协调下,分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断,即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。目前基于理解的分词方法主要有专家系统分词法和神经网络分词法等。由于汉语语言知识的笼统、复杂性,难以将各种语言信息组织成机器可直接读取的形式,因此目前基于理解的分词系统还处在试验阶段。

1)专家系统分词法。从专家系统角度把分词的知识(包括常识性分词知识与消除歧义切分的启发性知识即歧义切分规则)从实现分词过程的推理机中独立出来,使知识库的维护与推理机的实现互不干扰,从而使知识库易于维护和管理。它还具有发现交集歧义字段和多义组合歧义字段的能力和一定的自学习功能。

2)神经网络分词法。该方法是模拟人脑并行,分布处理和建立数值计算模型工作的。它将分词知识所分散隐式的方法存入神经网络内部,通过自学习和训练修改内部权值,以达到正确的分词结果,最后给出神经网络自动分词结果。

3)神经网络专家系统集成式分词法。该方法首先启动神经网络进行分词,当神经网络对新出现的词不能给出准确切分时,激活专家系统进行分析判断,依据知识库进行推理,得出初步分析,并启动学习机制对神经网络进行训练。该方法可以较充分发挥神经网络与专家系统二者优势,进一步提高分词效率。

3.3 基于统计的分词方法

该方法的主要思想:词是稳定的组合,因此在上下文中,相邻的字同时出现的次数越多,就越有可能构成一个词。因此字与字相邻出现的概率或频率能较好反映成词的可信度。可以对训练文本中相邻出现的各个字的组合的频度进行统计,计算它们之间的互现信息。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时,便可以认为此字组可能构成了一个词。该方法又称为无字典分词。

该方法所应用的主要的统计模型有:N元文法模型、隐Markov模型和最大熵模型等。在实际应用中一般是将其与基于词典的分词方法结合起来,既发挥匹配分词切分速度快、效率高的特点,又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。

3.4 基于语义的分词方法

语义分词法引入了语义分析,对自然语言自身的语言信息进行更多的处理,如扩充转移网络法、知识分词语义分析法、邻接约束法、综合匹配法、后缀分词法、特征词库法、矩阵约束法、语法分析法等。

1)扩充转移网络法。该方法以有限状态机概念为基础。有限状态机只能识别正则语言,对有限状态机作的第一次扩充使其具有递归能力,形成递归转移网络(RTN)。在RTN中,弧线上的标志不仅可以是终极符(语言中的单词)或非终极符(词类),还可以调用另外的子网络名字分非终极符(如字或字串的成词条件)。这样,计算机在运行某个子网络时,就可以调用另外的子网络,还可以递归调用。词法扩充转移网络的使用,使分词处理和语言理解的句法处理阶段交互成为可能,并且有效地解决了汉语分词的歧义。

2)矩阵约束法。其基本思想是:先建立一个语法约束矩阵和一个语义约束矩阵,其中元素分别表明具有某词性的词和具有另一词性的词相邻是否符合语法规则,属于某语义类的词和属于另一词义类的词相邻是否符合逻辑,机器在切分时以之约束分词结果。

4 中文分词算法中的难点

4.1 歧义问题

歧义切分字段处理一个汉语句子是以连续字串的形式书写的。由于可能存在歧义,分词并不是一个简单的从输入串中发现合法词的过程。一个句子经常对应几个合法词序列,因此,汉语分词中的一个重要问题就是在所有这些可能的序列中选出一个正确的结果。歧义切分是自动分词中不可避免的现象,是自动分词中一个比较棘手的问题。对歧义切分字段的处理能力,严重影响到汉语自动分词系统的精度。实践表明,只用机械匹配进行分词,其精度不可能高,虽然有时也能满足一些标准不高的需要,但不能满足中文信息处理高标准的要求。

4.2 未登录词识别问题

未登录词辨别未登录词包括中外人名、中国地名、机构组织名、事件名、货币名、缩略语、派生词、各种专业术语以及在不断发展和约定俗成的一些新词语。是种类繁多,形态组合各异,规模宏大的一个领域。对这些词语的自动辨识,是一件非常困难的事。

5 自动分词的评价准则

自动分词系统的最主要的工作是进行分词。对于分词而言,不仅要求所研制的软件在分词的正确率和速度方面满足一定的要求,而且要象开发大型传统软件那样,在各个阶段不断地进行评价,其目的主要是检查它的准确性和实用性,分词的评价主要有以下几个方面:

5.1 分词正确率

书面汉语的文本可以看成是字符序列,分词的正确率直接影响更高一级的处理。现有的分词系统切分错误主要集中在歧义字段和专有名词(如人名、地名、机构名和未登录词等)。为了获得分词系统切分正确率,应该进行整体测试,歧义测试和专业词测试。因此,自动分词系统的切分正确率的基本公式为:

其中,S1,S2,S3。分别为总体测试、歧义测试和专业词测试的正确率;

Bi(i=1,2,3)为三种测试加的权值。

5.2 切分速度

切分速度是指单位时间内所处理的汉字个数。在分词正确率基本满足要求的情况下,切分速度是另一个很重要的指标,特别对于算法不单一,使用辅助手段,诸如联想,基于规则,神经网络,专家系统等方法更应注意这一点。通常中文信息处理的文本数量是相当大的,因此必须考虑方法是否能使系统总开销合理。在人机交互方式下处理歧义问题的策略和人机接口的设计,有时会严重地影响切分速度,这也是应考虑的因素。

5.3 功能完备性

自动分词方法除了完成分词功能外,还应具备词库增删、修改、查询和批处理等功能。

5.4 易扩充性和可维护性

这是提供数据存储和计算功能扩充要求的软件属性,包括词库的存储结构,输入/输出形式的变化等方面的扩展和完善。这项指标与系统清晰性、模块性、简单性、结构性、完备性以及自描述性等软件质量准则有直接的联系,对于研究实验性质的软件是非常重要的,因为这类软件需要不断提高与改进,使之适应中文信息处理的各种应用。

5.5 可移植性

可移植性是指方法能从一个计算机系统或环境转移到另一个系统或环境的容易程度。一个好的分词方法不应该只能在一个环境下运行,而应该稍作修改便可在另一种环境下运行,使它更便于推广。

6 结论

由于中文的独特性,目前还没有完美的中文分词算法。中文分词算法的进一步完善应该在已经取得的成绩的基础上,综合运用多种方法,并引入新的模型和方法,通过不断探索,使中文分词算法越来越完善。

摘要：当前搜索引擎技术被广泛地应用,这使得全文检索技术和中文分词技术的研究逐渐深入。中文分词是中文信息的关键技术之一,其质量高低直接影响中文信息处理效率。文章致力于研究中文分词算法,对多种中文分词算法、自动分词系统的理论模型进行了详细的阐述和讨论,为中文分词的进一步发展提供基础和方向。

关键词：中文分词,全文检索,算法,搜索引擎,歧义切分

参考文献

[1]马玉春,宋涛瀚.web中中文文本分词技术研究[J].计算机应用,2004,24(4):134-136.

[2]曹桂宏,何丕廉,吴光远,等.中文分词对中文信息检索系统性能的影响[J].计算机工程与应用,2003(19):78-79.

[3]刘开瑛.中文文本自动分词和标注[M].北京:北京商务印书馆,2000.

一种基于词典的中文分词改进算法 篇6

随着信息技术的迅速发展,人们接触和处理的信息量不断增多,如何在种类繁多、数量巨大的资料中快速查找自己所需要的信息显得尤为重要。自动化检索工具的出现对于人们快速获取信息起到了重要作用,这些工具的核心是关键词,而中文分词技术则是中文关键词提取的基础和保证。可以说,中文分词是对中文信息进行处理的最基本环节,是信息提取、信息检索、机器翻译、语言识别、自然语言理解等中文信息处理领域的基础研究课题。

1 基于词典的中文分词

1.1 中文分词问题描述

中文分词就是借助计算机自动为中文进行断句,让计算机能够正确理解中文所要表达的意思。而基于词典的中文分词,就是针对输入的中文句子,通过分词算法,与专业词库进行比对,将输入的中文句子分成单个的字或者多字组成的词。

1.2 中文分词难点分析

中文分词的研究虽然取得了很大成就,但由于中文是连续的文字,存在中文歧义[1],并影响最终的切分效果。未登录词识别问题和歧义识别问题[2]是中文分词领域的两个关键问题。

(1)未登录词的识别问题。由于中文分词本身所具有的复杂性,分词系统不可能将所有中文词语的词典都加载进去,因此待切分语句中必然会存在词典中没有收录的词,即未登录词。未登录词包含人名、地名等,它的存在严重影响了中文分词的准确率与效率。

(2)歧义识别。中文歧义是指同样一个中文句子,可能会得到两种以上的切分结果。中文歧义一般分为交集型歧义(OAS)、覆盖型歧义(CAS)和真歧义3种:(1) 交集型歧义(OAS)。设A,B,C分别代表一个或多个连续的汉字,假如连续的中文字串ABC中,AB,BC分别成词,则称其为交集型歧义;(2)覆盖型歧义(CAS)。交集型歧义相对组合型歧义来说比较容易处理,组合型歧义就必须根据整个句子来判断。设A,B各为一个或多个连续的汉字,若A,B分别成词,则称其为覆盖型歧义;(3)真歧义。对于一句话,要得到正确的分词结果,必须根据上下文的其它句子进行判断。

1.3 基于词典的分词算法机制

基于词典的分词系统的分词效率很大一部分取决于词典选择,所以词典能否快速高效的存储和查找数据是关键。目前最常用的词典机制[3]有基于tire索引树的词典和基于整词二分法的词典机制。

基于tire索引树的词典机制是由首字散列表和tire索引树节点两个部分组成。优点是不需预知待查询词的长度,沿着树枝进行逐字匹配。缺点是构造和维护比较复杂,并且一个树枝仅代表一个词,浪费了一定空间。

基于整词二分法的词典机制[4]是由首字散列表、词索引表和词典正文组成。其中,首字散列表根据所有词典首字确定一个映射,通过该首字可直接确定入口的数组指针和长度,词典正文则是以词为单位的有序表。这种词典机制占用空间小且易于维护,但由于采用全词匹配的查询过程导致效率较低。

1.4 基于词典的主要分词算法

基于词典的分词算法主要有最大正向匹配算法MM和最大逆向匹配算法DMM两种,对这两种算法的研究是本文进行算法改进的基础。

(1)最大正向匹配算法MM。最大正向匹配算法的基本思想是从左向右开始切分句子,尽可能寻找最长的中文词语进行匹配。用数学语言描述为:假设有一个中文句子ABCD,A∈W,AB∈W而ABC∉W,其中W为中文词典,通过与中文词典对比,切分为使AB成词,而不是使A和B独立成词。

(2)最大逆向匹配算法RMM。最大逆向匹配方法与正向最大匹配比较相似,但最大逆向匹配算法是从句子的末尾向前进行分割,如果失败就减掉最前面的字。用数学语言描述为:假设有一个中文句子ABCD,D∈W,CD∈W而BCD∉W,其中W为中文词典,那么就使CD切分成词,而不是C和D单独成词。

(3)优缺点分析。正向最大匹配法的切分速度对中文词典的存储方式要求较高。显然,当选择的中文存储词典数据结构效率高时,切分速度较快。正向最大匹配法对切分歧义的排除效果较差。以“上海大学城书店”为例,正确切分结果应为“上海/大学城/书店”,用正向最大匹配法切分结果却为“上海大学/城/书店”。而使用逆向最大匹配法时,可得到正确的切分结果。因此某些时候,逆向最大匹配算法对切分歧义的排除效果相对较高。正向最大匹配算法的主要弊端是最大词长的值固定不变,即分词之前,总是先对最大词长赋一个固定的初始值,容易导致两个问题:词长过短,长词就会被切错;词长过长,在切分时就会浪费一部分时间用于查词典,导致效率降低。

2 词典机制与分词算法改进

2.1 改进后的词典结构设计

基于对以上词典结构的分析,通过对中国汉字编码体系[5]和中文分词特点的研究,采用了一种新的词典机制。利用HashTable的开散列法,将同一首字下相同长度的词语以有序列表的形式存储在一起,从而方便在词典中快速查找词。存储结构如图1所示。

这种存储结构的优点:(1)将同一首字下的相同长度的词语以有序列表的形式存储在一起,与基于tire树的存储方式相比,大大缩小了存储空间;(2)利用区位码的方式可有效确定出唯一首字,通过首字和长度大大缩减了查找范围,提高了查找速度;(3)以有序列表的形式进行存储,实现了词典的扩展,满足了分词过程的需求。

2.2 中文分词算法改进

通过对两种经典分词算法的分析,作出如下改进:

(1)根据词典动态确定最大词长。通过对《现代汉语》词典词条的统计,发现在12 022个词条中大部分词为两个字、3个字和4 个字,而5 个、6 个、7 个字组成的词较少,8个及以上组成的词更少[6]。通过经典的最大匹配算法顺序进行查找往往比较浪费时间,所以本文改算法根据词典中的词条动态确定所要切分的最大词长的长度,从而消除由于经典算法中最大词长不变,最大词长过短所带来的长词被切分错误或者最大词长过长所带来的耗时长、效率低的问题。

(2)返回最佳分词结果。据统计,单纯使用最大正向匹配的分词结果错误率为1/169,单纯使用最大逆向匹配的分词结果错误率为1/245,所以本文结合最大正向和最大逆向匹配的优点,解决本文前述的正向最大匹配法对切分歧义的排除效果较差的缺点,将两种分词结果进行比对,若分词结果相同则任意返回;如若不同,则返回逆向匹配算法的分词结果,最终提高分词的精确度。

3 分词系统的设计

综上所述,设计实现一个新的分词系统,对歧义识别问题和未登录词的识别问题进行一定程度改进。该分词系统通过一个简单的UI图形界面形式进行呈现,通过实现用户自主添加用户词典这一功能有效改善未登录词的识别问题,通过获取两种算法的最优分词结果,一定程度上消除部分歧义问题。

3.1 系统流程图设计

本文分词系统的整体流程图和所包含的功能如图2所示。

3.2 具体实现思路

3.2.1 词典存储和搜索过程实现

为使词典在存储过程中实现同一首字下相同长度词语的集中放置,从而缩小词语在词典中的搜索范围,提高查找速度。本文利用HashTable的开散列方法进行词典构建,搜索过程中通过待切分字符串的首字和长度确定相同首字下相同长度的链表位置,从而进行逐一匹配。

3.2.2 预处理过程实现

在对输入的字符串进行分词时,输入的字符串大多会出现含有除中文字符以外的字符。这就需要程序能够自动对加载进来的字符串进行预先处理,从而为下一步分词作好准备。消除多余的空格,根据分词算法程序的具体要求,作好对标点符号以及特殊字符的处理,对字符与数字、数字与汉字、字符与汉字间进行适当标记。

3.2.3 主要分词算法过程实现

通过本文提出的最大匹配算法改进方法,从动态确定最大词长和返回最佳分词结果两个方面入手实现分词算法。

(1)最大正向匹配算法实现。针对最大正向匹配算法中最大词长固定的弊端,对经典的算法进行部分改进,让程序根据词典中的词条动态获取最大词长。改进后的最大正向匹配算法基本流程如下:

Step1:获取经过预处理的待切分字符串;

Step2:获得词典中最大词长的长度;

Step3:将最大词长长度与所要切分的字符串长度进行比较。若字符串长度小于最大词长长度,则字符串的长度为最大词长,否则以最大长度自左至右截取字符串进行切分;

Step4:在词典对应长度的词中查找。首先判断待切分的字符串长度,若长度为1,判断是否为数字或者字母,若是则原样输出;反之,判断是否为空格,若是则替换为切分标识符,再判断是否为标点,若是则剔除,若否则输出原字符串后加切分标识符。若待切分字符串长度不为1,若在词典中匹配成功,则在字符串后输出标识符并转6),否则转5);

Step5:删除字符串最后一个字,生成新的待切分字符串并转4);

Step6:判断待切分字符串长度是否为0,若不为0则转3),反之分词完成。

(2)最大逆向匹配算法实现。最大逆向匹配算法基本流程如下:

Step1:获取经过预处理的待切分字符串;

Step2:获取词典中最大词长的长度;

Step3:将最大词长长度与所要切分的字符串长度进行比较。若字符串长度小于最大词长的长度,则字符串的长度为最大词长,否则以最大长度自右至左截取字符串进行切分;

Step4:在词典对应长度的词中查找。首先判断待切分的字符串长度,若长度为1,判断是否为数字或者字母,若是则原样输出;反之,判断是否为空格,若是则替换为切分标识符;再判断是否为标点,若是则剔除,若否则输出原字符串后加切分标识符。若待切分字符串长度不为1,若在词典中匹配成功则在字符串后输出标识符并转6),否则转5);

Step5:删除字符串的第一个字,生成新的待切分字符串并转4);

Step6:判断待切分字符串长度是否为0,若不为0则转3),反之分词完成。

(3)双向匹配算法实现。双向匹配算法的基本思想是将正向最大匹配和逆向最大匹配结合起来,对两者的分词结构进行分析比较,返回准确性较高的字符串,算法流程如下:

Step1:获取待切分的字符串;

Step2:利用正向最大匹配和逆向最大匹配算法进行分词,然后对分词结果进行比较,如果分词结果相同则返回字符串,算法结束,否则转3);

Step3:比较分词数目,返回分词数目少的分词结果。如果分词数目相同,则返回逆向最大匹配的分词结果,算法结束。

4 结语

本文对基于词典的分词过程以及常见的词典结构和分词算法进行分析和研究,并设计出一个新的词典结构,对经典的分词算法进行改进,通过词典加载功能改善未登录词的识别问题,通过双向匹配算法获取最优分词结果改善歧义识别问题。由于中文分词的复杂性,本文设计的系统能针对歧义识别问题的本质提出相应的对策,如对于“日韩美德四国”中的“美德”应正确切分为“美”/“德”才能保证信息处理正确,这类覆盖性歧义无法处理。在后续工作中,期望找出能够改善歧义识别问题的方法。

摘要：深入探讨基于词典的分词过程、常见词典结构以及分词算法。在分析现有系统的基础上,设计一个新的词典结构,对经典的分词算法进行改进,通过词典加载功能改善未登录词的识别问题,通过双向匹配算法获取最优分词结果,改善歧义识别问题。

关键词：中文分词,双向匹配算法,词典机制

参考文献

[1]张春霞,郝天永.汉语自动分词的研究现状与困难[J].信息技术,2005,17(1):138-147.

[2]孙铁利,刘延吉.中文分词技术的研究现状与困难[J].信息技术,2009,7(3):187-192.

[3]谭骏珊,吴惠雄.一种改进的整词二分法的中文分词词典设计[J].信息技术,2009,14(1):1-6.

[4]刘湘赣.语言分析算法在互联网信息检索中的应用[J].软件导刊,2015,14(9):66-68.

[5]姚兴山.基于哈希算法的中文分词算法的改进[J].图书情报工作,2008(6):60-62.

中文分词算法研究 篇7

自动分词技术就是将连续的字所构成的句子切分成不同的具有一定意义的词的技术,它是中文信息处理的关键技术。影响分词技术发展的瓶颈是切分歧义,切分歧义可分为交集型切分歧义和组合型切分歧义,简称交集型歧义和组合型歧义。

组合型歧义词在不同的语境下有不同的切分方式,例如:

(1) 你要考虑你自己的/将来/;市长/将/来/我们学校考察工作。

(2) 他/才能/有资格获得冠军;人/才/能/推动科技进步。

(3) 国家的/中长期/计划是指导国家战略发展的计划;这是国际共产主义运动/中/长期/没有解决的一个重大理论问题。

“将来”、“才能”、“中长期”在上述三个句子的前半句从合切分,后半句则从分。

“何时从分,何时从合”就是组合型歧义消解要解决的问题。目前虽然存在许多消解方法,但几乎所有的组合型切分歧义消解方法都将歧义词的上下文环境信息作为切入点,用上下文环境信息作为参数构建模型,再用一定标注好的语料作为训练样本,从而获得歧义消解技术。如文献[2]从上下文信息中获取词性搭配规则,用SVM模型进行消歧;文献[3]从语境信息的窗口大小、位置和频次等角度考察歧义词的上下文语境,用对数似然比建立计算模型,进行歧义消解;文献[4]以条件随机场CRF为计算模型,利用歧义字段的上下文的词和词性建立特征模板, 进行歧义消解;文献[5]使用语境信息中对数似然比的最大值和语境信息中合、分两种情况下各自的对数似然比之和取值大者进行消歧;文献[6]利用相对词频作为语境的计算模型进行歧义消解。文献[7]以最大信息熵作为计算模型计算歧义字段上下文信息,进行消歧。

我们从歧义字段不同切分方式所得的结果入手,比如歧义字段“中长期”可切分为“中”、“长期”和“中长期”两种不同的结果,在全文范围内,考察结果词与其前后搭配所构成的词是否合理或为字典中的词,分别计算从合、从分切分的支持度,依据支持度因子进行组合性歧义消解。随后的章节中将介绍相关知识,然后构造组合型歧义的消解算法,最后是实验验证和小结。

1 相关概念

定义1 设S=c1、c2、c3、c4,其中S为字符串。ci,i=1,2,3,4为字符, 把连续的字符串切分成不同的词的技术称为分词技术,如S可切分为:词c1c2和词c3c4,由于不同切分造成词意的差异称为切分歧义。

定义2 给定任意汉字串***AB***, W为词表,若 AB∈W、A∈W、B∈W、在真实文本中可切分为:/AB /,或切分为:/A / B /,则称AB为组合型歧义词。

定义3 假设事务数据库D={d1,d2,…,dm},事务dk={t1,t2,…tn,…tp,},tn(n=1,2,…,p)称为事务项(item)。令T={t2,t2,…,tm}是D中全体项目的集合,则有如下几个基本概念:

项集:对于全体项目集T而言,T的任何子集X称为D中的项目集(itemsets),简称为项集$X‚\left|X\right|=k$,即项集X中的项目个数,称为项集X的长度,包含k个项的项集称为k-项集。

设X⊂I,Y⊂I,X∩Y=Ø,则

项集支持度为:

$support(X)=\frac{count(X)}{|D|}$

$support(X,Y)=\frac{count(X{\displaystyle \cup Y})}{support(X)+support(Y)}$

其中,support(X)是项集X的支持度,support(X,Y)是X∪Y的支持度,$\left|D\right|$是事务数据库D的总事务数。

2 组合型歧异消解

2.1 基本定义

定义4 共现频繁词集 设A、B为文本信息库T中的词,若给定最少阈值α有:

$support(A,B)=\frac{support(A{\displaystyle \cup B})}{support(A)+support(B)}\ge \alpha$

则称A、B为共现频繁词集。

定义5 设句子S=w1…wi-1wiwi+1…wn,wi为组合型歧义字段,从合时切分为/wi/,从分则可表示为/wi1/wi2/。

如果support(wi,wi+1)≥α,则称wi,wi+1为从合右共现频繁词集。

如果support(wi-1,wi)≥α,则称wi-1,wi为从合左共现频繁词集。

如果support(wi2,wi+1)≥α,则称wi2,wi+1为从分右共现频繁词集。

如果support(wi-1,wi1)≥α,则称wi-1,wi1为从分左共现频繁词集。

定义6 对于组合型歧义字段wi,则从分或从合时的支持因子为:

support(合)=support(wi,wi+1)+support(wi-1,wi) (1)

support(分)=support(wi-1,wi1)+support(wi2,wi+1) (2)

如果support(合)≥support(分)则支持从合,否则从分。

2.2 设计原理

组合型字段的合与分制约于歧义字段所在句子的前后语境,不同切分方式所得结果词在全文中的总体分布情况以及结果词与前后搭配所构成的词在全文中的分布情况,很大程度上可以判定歧义字段的分与合。所以我们首先将歧义字段按照从合、从分两种方式切分,获取所有可能切分结果;然后计算各切分结果与其前缀或后缀是否构成字典中的词的支持度。综合考虑各种支持度,构造从分、从合判别因子,进行组合型歧义消解。

如“国家的/中长期/计划是指导国家战略发展的计划;这是国际共产主义运动/中/长期/没有解决的一个重大理论问题”中,可能的切分结果词为“中长期”和“中”、“长期”,结果词与前后搭配可得“国家的中长期”、“中长期计划”、“国家的中”、“长期计划”、“运动中长期”、“中长期没有”、“运动中”、“长期没有”等词串,其中“国家的中”和“运动中长期”不能构成词,其支持度为零,所有结果词的支持度为:

support(国家的中长期)=1、support(中长期计划)=1、support(国家的中)=0、support(长期计划)=1

support(运动中长期)=0、support(中长期没有)=1、support(运动中)=1、support(长期没有)=1

则对于“国家的中长期计划是指导国家战略发展的计划”依据式(1)、式(2)有:

support(合)≥support(分) 支持从合

对于“这是国际共产主义运动中长期没有解决的一个重大理论问题”依据式(1)、式(2)有:

support(合)≤support(分) 支持从分

2.3 算法实现

组合型歧义消解算法伪代码表示如下:

输入 包含歧义字段wi的文本T,组合型歧义字段wi;

输出wi的正确切分方式。

过程:

3 实验验证

3.1 样例说明

我们考察下面例句中的歧义字段“将来”、“才能”、“中长期”:

1) 你要考虑你自己的将来;市长将来我们学校考察工作。

2) 他才能有资格获得冠军;人才能推动科技进步。

3) 国家的中长期计划是指导国家战略发展的计划;这是国际共产主义运动中长期没有解决的一个重大理论问题。

首先将三个例句在北大计算机语言研究所的分词测试平台上[8]测试,结果如图1所示。

然后再在猎兔分词平台[9]测试结果如图2所示。

从两个测试平台来看,三例句中的组合型歧义字段“将来”、“才能”、“中长期”都未能准确消除。因为三句子中的后半句都错误的采取从合切分。

依据我们设计的算法人工计算各结果词的支持度如表1所示。

从表中可以看出:三例句中的歧义字段“将来”、“才能”、“中长期”前半句支持从合,后半句支持从分,符合切分预期。

3.2 实验模拟与评估

为方便演示我们所设计的算法,我们选取8个组合型歧义字段,从语料库中下载包含歧义字段的一定数量的语料,利用分词字典与人工相结合的方式鉴别前后搭配所成词的合理性及其切分的正确与否。实验结果如表2所示。

结论:我们的方法具有较高的可信度。从实验结果来看,利用分词字典,从共现支持度的角度消除组合型歧义字段是可行的。

4 结 语

本文讨论了基于关联规则的组合型歧义的消解策略,方法的最大特点是从可能的切分方式所得结果词与前后搭配所构成的新词的支持度出发,构造从分或从合切分支持度因子,对组合型歧义字段进行消岐。通过样例人工计算和模拟实验验证,该方法可行并具有较高的应用价值。

摘要：自动分词技术的瓶颈是切分歧义,切分歧义可分为交集型切分歧义和组合型切分歧义。以组合型歧义字段所在句子为研究对象,考察歧义字段不同切分方式所得结果与其前后搭配所得词在全文中的支持度,构造从合或从分切分支持度度量因子,依据该因子消除组合型歧义。通过样例说明和实验验证该方法可行并优于现有技术。

关键词：中文信息处理,组合型歧义,共现支持度,歧义消解,支持度因子

参考文献

[1]孙茂松,黄昌宁,邹嘉彦.利用汉字二元语法关系解决汉语自动分词中的交集型歧义[J].计算机研究与发展,1997,34(5):332-339.

[2]刘禹孜,何中市.一种基于SVM和规则消除组合型歧义的算法[J].重庆大学学报:自然科学版,2005(10):50-53.

[3]肖云,孙茂松,邹嘉彦.利用上下文信息解决汉语自动分词中的组合型歧义[J].计算机工程与应用,2001(19):87-90.

[4]丁德鑫,曲维光,徐涛,等.基于CRF模型的组合型歧义消解研究[J].南京师范大学学报:工程技术版,2008,8(4):73-77.

[5]冯素琴,陈惠明.基于语境信息的汉语组合型歧义消歧方法[J].中文信息学报,2007,21(6):13-17.

[6]曲维光,吉根林,穗志方,等.基于语境信息的组合型分词歧义消解方法[J].计算机工程,2006,32(17):74-77.

[7]秦颖,王小捷,张素香.汉语分词中组合歧义字段的研究[J].中文信息学报,2007,21(1):3-8.

[8]http://www.icl.pku.edu.cn/.