面向中文全文索引的中文分词策略

点赞:31235 浏览:144772 近期更新时间:2024-01-24 作者:网友分享原创网站原创

摘 要:中文分词是中文信息化处理的基础环节.在中文全文索引中,中文分词更起着举足轻重的作用.该文首先比较了常见的中文分词算法,最后选用了综合性能较优的分词算法―基于词频统计的匹配分词,引入全文索引的开源项目Lucene中.通过与传统的机械分词对比,发现使用基于词频统计的匹配分词的全文索引,不但大大节省索引空间,而且显著地提高了检索的质量.

关 键 词:中文全文索引;中文分词;Lucene

中图分类号:TP391文献标识码:A文章编号:1009-3044(2012)03-0722-05

ChineseFull-textIndexfortheChineseWordSegmentationStrategy

XIChao-qiong

(GuangdongFoodandDrugSchool,Guangzhou510663,China)

Abstract:ChineseSegmentationisthebasicstepofChineseinformationprocessing.ItplaysanimportantroleespeciallyintheChinesefulltextindexing.ThispaperfirstmakesparisonbetweenalgorithmsofChinesesegmentation,andthenchoosesthemostsuitableone,whichisbasedonthestatisticalmodelofwordfrequency,toapplytotheopensourcefulltextindexingprojectLucene.ByparisonwiththetraditionalChinesesegmentationmethod,wefindthatthenewfulltextindexing,whichappliednewChinesesegmentationmethod,notonlyseshugeamountofspaceofindexing,butalsoimprovesthequalityofsearchingsignificantly.

Keywords:ChineseFullTextIndexing,Chinesesegmentation,Lucene

1概述

相对于以字母为基本语言单位的拉丁语系而言,东亚语言(以中、日、韩CJK语言为代表)是以具有独立意义的单字作为最小的语言组织单位.两种语系都以最小语言组织单位通过相互排列和组合不断产生新的单词.但是东亚语言最大的特点,就是单词与单词之间没有明显分隔标记[1].试想检测如英文文本把所有单词之间的空格都去掉,然后让计算机进行信息化处理,那么这一过程的首要一步就是把连续的单词串进行切分识别.同样对于天然没有明显标记作为词的分界的东亚语言来说,在对其进行信息化处理时,分词成为首要而且必不可少的步骤[2].

以汉语为例,中文分词具有广阔的应用前景.在文本校对、汉字的简体/繁体转换、自然语言理解、文本分类和机器翻译等中文信息处理系统都以分词作为其最基本的模块.本论文排版所使用MSWORD所提供的文本自动校对功能、简繁体转换功能和自动取词功能等,便是以分词作为系统的一个基本模块[3].校对系统运用分词模块对文本进行分词,然后运用词语之间搭配的合理性来识别可能的错误;简繁体转换功能,不但从字一级把如“学习”转成“”,而且还进行相应的习惯用词变换,如“硬件”转成“硬”,而后一级的用词转换是离不开分词模块;自动取词功能,让用户左键双击中文汉字时,其所组成的中文词语则被高亮选中,用户可以对选中的词语作进一步的编辑.这一功能同样是运用分词系统来实现的.

2中文分词算法

正如引言所述,传统上的中文分词算法分为三类:基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法.

第一类,基于字符串匹配的分词方法.

这种方法的原理,是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配,若在词典中找到某个字符串,则匹配成功(识别出一个词)[1].按照扫描方向的不同,串匹配分词方法可以分为正向匹配和逆向匹配;按照不同长度优先匹配的情况,可以分为最大匹配和最小匹配.一般来说,由于中文单字成词的特点,最大匹配的效果远远高于最小匹配.据统计分析,逆向匹配的正确率高于正向匹配[5].

这种机械的划分的优点,就是实现简单.前期工作只要具备一个充分大的词条条目的机器词典;后期工作就是选择一个兼顾效率与准确率的分词策略――逆向最大匹配.当然,它的缺点也是显然易见的,对于歧义问题不能很好地处理.中文分词所遇见的歧义问题主要分为两大类[5]:(1)交集型歧义字段,据统计,这种歧义字段占全部歧义字段的85%以上[6].所以这也是分词系统所要重点解决的问题.在字段ABC中,这里,A,B,C分别代表有一个或多个汉字组成的字串.A,AB,BC,C分别都是词表中的词,则称该字段为交集型歧义字段.如:“研究生#命起源”,“研究#生命起源”两种切分结果.(2)组合型歧义在字段ABC中,A,B,AB分别都是词表中的词,则称该字段为交集型歧义字段.如“:学生#会#参加#献血”,“学生会#参加#献血”.

无论哪一种歧义,由于基于字符串匹配的分词没有利用上下文语境,只单纯从词的匹配角度进行机械的划分,因此其处理歧义的能力是相当弱,总体来说他的准确率在三大类中是较低的一种.

第二类,基于理解的分词方法.

从常识角度看,理解上下文的语义是分词正确且有效的途径.基于理解的分词方法其基本思想就是在分词的同时进行句法、语义分析,利用句法信息和语义信息来处理歧义现象.然而正如前文所言,理解与分词有时是互为前提的,没有正确的分词难有正确的理解,没有正确的理解也不可能有正确的分词.这便陷入先有鸡还是先有蛋的逻辑矛盾[6].

在当今自然语言处理(NaturalLanguageProcessing)还有待发展的今天,这种分词方法还处于理论研究阶段,离真正实用还有一段好长的距离.

第三类,基于统计的分词方法.

基于字符串匹配的分词方法没有很好地利用句子中上下文所提供的语言背景知识.而基于理解的分词的立足点是要充分利用语义信息,但实现却相当困难.在这两者之间,人们找到一个平衡点―从统计角度处理语言背景所提供知识.

基于统计的分词方法,所统计的对象是多元的.最常见的是基于字与字之间的结合频率[7]来决定是否成词.这种方法的原理是在上下文中,如果相邻的字之间出现次数越多,那么它们是单词的概率就越高.用形式化的语言来描述是:

设字串C等于{C1C2C3C5},

检测定划分成为两个词(即两个字串切分)S1等于{C1C2},S2等于{C3C5}

定义Prob(C)、Prob(S1)和Prob(S2),分别为C、S1和S2出现的概率.

则两切分之间的相互信息(MutualInformation)

检测定两个不同的阈值γ1<γ2时,当MI(S1,S2)大于γ2时,我们相信S1与S2两者关系相当紧密,这样的切分是不适合的.当MI(S1,S2)小于γ1时,表示S1与S2两者关系独立,字串C可能含有两个或以上的词.当MI(S1,S2)介于γ1与γ2之间时,S1与S2两者是弱关联,这时需要重新估计划分的位置.

基于统计的分词的好处就是事先不需要大词条的词典,只需对字、词的频率进行统计.比起第一类的算法,它能有效地识别歧义和未登录词.但它也有局限性,首先算法的执行比第一类的算法需要相当大的运算量,其次对于常用的高频非词组性的习惯用语不能正确切分,如“我的”、“之类”等.

事实上,在实际应用的分词系统上,并不是单纯采用某类的算法,而是扬长避短综合地运用.下文所使用的基于词频统计的匹配分词算法,便是将第一与三类算法作综合,在执行效率与歧义处理之间取得较好的平衡点.

3基于词频统计的匹配中文分词

在进行全文索引时,利用中文分词技术,把中文文本切分成一个个长度较小的中文序列,接着把分词产生的中文序列及其位置等相关信息,生成倒排索引表(InvertedIndexTable)[8].倒排索引表的逻辑结构就像每一本书后的索引表一样,以关 键 词(即分词产生的中文序列)为索引表的关键字,页码(即中文序列的相关信息)为其查找内容.在进行查找时,同样要利用中文分词技术分析用户输入的内容,然后按照分析结果直接在倒排索引表查找相关内容.不论是前期的索引工作抑或是后期的搜索工作,中文分词的作用都是举足轻重的.尤其是前期索引的分词的好坏,直接影响后期搜索的准确率和召回率的高低.

无论是一元切分还是二元切分,它们都没有有效利用文本中的语义信息.单纯的机械切分虽然带来100%的召回率,但对于海量的信息,用户所关注的不是返回的检索的多寡,而是检索的质量.尤其是应用于互联网的搜索引擎,一个关键字至少可以带来几十万的查询结果,这时检索的准确率将优先于召回率作为首要考虑因素.而要提高检索的准确率,必然要引入此前所讲三大类的传统分词算法.

接下来的部分,我们将引入现今一个较成功的分词算法基于词频统计的匹配分词到全文索引项目Lucene中.前半部分将详述分词的原理,后半部分将描述移值至Lucene的相关细节.

3.1基于词频统计的匹配分词原理

利用已有的词典对字串进行完全匹配的粗分,生成含有所有可能的切分方案,然后构造一个反映所有切分方案的有向无环图.最后通过Dijkstra的最短路径算法求出概率最大的切分方案.

3.2模型求解步骤

模型定义:

字串C等于{C1C2C3等Cn},Ci为字串的第i个单字,字串C长度为n,n>等于1.模型目标:

生成切分可能性最大的分词串S等于{S1S2S3等Sm},其中Si为分词串第i个词.模型求解步骤:

1)粗分字串,产生所有可能的分词串方案,并构造相应的有向无环图

首先构造初步的有向无环图G,其中该图的结点个数|V|等于n+1.每一个结点Vi代表字串中的单字Ci(i<=n),而Vn+1为终结符.连结Vi与Vi+1(i<=n),边Ei代表单字Ci以独立的单字作为一种可能的划分.例如“瑞星以技术和怎么写作”,生成图1的初步有向无环图.

图1

接着,对图中的Vi(1<=i<=n),通过词典搜索以Vi开头的词,然后与以Vi开始的字串进行匹配.若Vi至Vj的字串匹配成功,则添加一条有向边,代表单词(ViVi+1等Vj).接上例,生成如图2的有向无环图.

图2

2)利用Dijkstra的最短路径算法,选择最优划分

用数学语言精确地描述我们的模型目标,对于字串C等于{C1C2C3等Cn},切分成分词串S等于{S1S2S3等Sm},使到条件概率Prob(S|C)达到最大值.

其中Prob(S|C)等于Prob(S,C)÷Prob(C)等于Prob(S)×Prob(C|S)÷Prob(C)

我们知道,Prob(C)是一个定值;而对于某一个分词串S,其对应的字串C是一定的,所以Prob(C|S)恒为1.因此,要使Prob(S|C)取得最大值,必先令Prob(S)达最大值.检测定对于分词串S,Si与Si+1(1<=i<=n)是相互独立的.

则Prob(S)等于Prob(S1,S2,S3...Sm)等于∏

按照如下规则给有向无环图的边赋于权值:

(1)若Si为数字串或英文串,赋权值0至边.

(2)若Si为汉字串(串长为n),赋权值-logki+100至边.(加100的目的是使权值为非负)最后,利用Dijkstra的最短路径算法求最优划分方案.

4基于词频统计匹配分词策略应用于全文索引项目Lucene

4.1Lucene简介

Lucene是一个开放源代码的Ja全文索引引擎工具包.比起商业的笨重和昂贵的全文索引工具,它可以按照需要进行扩展和剪裁,方便的嵌入到各种应用中实现针对应用的全文索引/检索功能.Lucene起初是由著名搜索引擎Excite的架构师DougCutting在SourceFe作为开源项目.到2002年,Lucene1.2版正式作为ApacheSoftwareFoundation的子项目.

面向中文全文索引的中文分词策略参考属性评定
有关论文范文主题研究: 关于分词的论文范文资料 大学生适用: 自考论文、学术论文
相关参考文献下载数量: 17 写作解决问题: 写作参考
毕业论文开题报告: 标准论文格式、论文选题 职称论文适用: 论文发表、职称评初级
所属大学生专业类别: 写作参考 论文题目推荐度: 经典题目

由于Lucene的卓越的架构所带来良好的扩展性,吸引了开源社区对其不断功能扩展,尤其是分词部分,迄今已经从原来单纯的英语切分,扩展到俄、德等多种语言.随着其功能续步完善,Lucene有越来越多应用案例.比如,Web论坛系统Jive的检索部分和开放开发平台Eclipse的帮助索引部分都嵌入Lucene作为其后台的全文索引.

4.2中文分词实现

本次实现所使用的带词频的词典来自于中科院的ICTCLAS分词系统[2],其格式说明参考至网上“计算所汉语词法分析系统ICTCLAS字典格式解析(字典格式说明)”[10],特次致谢.

由于Lucene各模块之间的关系是松耦合,因此对其扩展改动所涉及的面相当少.本次加入中文分词实现只涉及Lucene的.apache.lucene.analysis中与分析相关的package.

实现架构规划,如图3.

1).rickyzhang.lucene.省略

功能说明:包含一元切分、二元切分和基于词频统计匹配切分的Analyzer和Tokenzier实现.主要类图说明图4.

图4

说明:AbstractChineseAnalyzer所含的Chinese_STOP_WORDS包含高频的汉语虚词,如“但是”“因为”等,其目的是过滤(Filter)这些高频词条.

2).rickyzhang.lucene.util

功能说明:包含求最短路径的有向无环图的类SegmentGraph,词典类Dictionary,对文本进行初次切分Token的SimpleTokenizer和对外最终接口SentenceSegment.

图5

3).rickyzhang.lucene.test

功能说明:包含测试中使用的索引工具Indexer和检索工具Searcher.

5与二元切分和一元切分作比较

本次评测内容分为索引和检索两部分.所索引的对象内容范围广泛,包括:现代小说,人物传记,学术论文,哲学简史和文言文经典.此次共索引49个文件,总大小为6.12MB.5.1索引评测

对比数据如表1:

说明:测试机器AMDDuron1.6GHz,内存512MB

1)从索引速度看,基于词频统计匹配切分比一元切分和二元切分差一个数量级.

其原因可以从算法复杂度中推出,一元切分和二元切分的计算复杂度是O(N),而基于词频统计匹配切分是O(N2)(主要是在计算最短路径上Dijkstra算法上)

2)从索引所占空间看,二元切分所占的空间约为一元切分和基于词频统计匹配切分的两倍.

正如此前分析,由于二元切分所分出来的词条是以物理位置作为划分界限,比起基于词频统计匹配切分所分出的具语义的单词,它们重复的几率相对较低,故二元切分占索引空间相当大.而一元切分之所以是最省空间的,其原因就是常用高频汉字大概只有三千个左右,因此在所有切分中,其倒排索引表所含的表项是最少.

5.2检索评测

传统上检索评测分为三部分:召回率、准确率和检索时间.

召回率是指检索出的相关内容和索引中所有的相关内容的比率.

准确率是检索出的相关内容和检索出的内容的比率.

定义所述的“相关内容”是一个相对概念,这与检索者的主观意向有密切的关联.

然而对于何一个检索系统来讲,召回率和准确率是不可能两全其美:召回率高时,准确率低;反之,准确率高时,召回率低.

本次,评测以抽查的方式列举了10个不同的关键字作为检索对象,分别用三种不同的切分方法所生成的索引进行检索.(由于Lucene检索时使用的是相同算法,而且关键字长度较短,用不同切分方法对关键字进行分析所花费时间可忽略,故检索时间不作为评测部分.)对比数据如表2:

表2检索评测对比数据说明:测试机器AMDDuron1.6GHz,内存512MB

1)以语义作为切分的检索的准确率高

很明显“理解越深,越准确”,单纯的机械切分严重割裂了文本的语义.比如,以“华人”作为关键字,一元切分和二元切分都把含有“中华人民共和国”的文本作为检索结果.

2)切分的准确性真接影响召回率

由于基于词频统计匹配切分对于未登录词的切分相对较弱,因此对于某些地名、人名等专有名词的检索效果远差于一元和二元切分.这是造成基于词频统计匹配切分的召回率低于机械切分的主要原因.

6结论

中文分词技术对全文索引起着举足轻重的影响.不论是前期索引的时空效率,抑或是后期检索的质量,都与中文分词工作有密不可分的关系.通过本次探索,应用基于词频统计匹配切分的全文索引的质量明显优于应用传统的一元和二元切分技术的全文索引.前者不但节省索引空间,而且带来更高的检索质量.

然而基于词频统计匹配切分还有提高的空间.鉴于大部分的检索关键字为专有名词,而基于词频统计匹配切分的全文索引在这方面略差于传统的机械切分,因此在后续工作有必要对专有名词如人名、地名等进行专门优化切分,以此提高其检索的召回率.