中文分词关键技术研究(硕士学位论文)

holy_527

贡献于2012-02-09

字数:0 关键词: 搜索引擎

南京理工大学 硕士学位论文 中文分词关键技术研究 姓名:曹卫峰 申请学位级别:硕士 专业:计算机应用技术 指导教师:刘凤玉 20090601 硕上论文中文分词关键技术研究摘要中文分词就是将中文连续的字序列按照一定的规则重新组合成词序列的过程。其作为中文信息处理的基础,己经被广泛应用于相关领域。因此,对中文分词的研究具有重要的理论和现实意义。本文将重点研究中文分词的词典机制、歧义消除、切分算法等技术。鉴于语言的统计规律性,本文的中文分词算法使用词典和统计相结合的方法。在核心词典的组织方面,考虑到词典查找的时间效率、存储的空间效率、汉语词组的统计规律等特点,我们使用双字Hash索引分词词典机制,仅对词组的前两个字符依次建立Hash索引,构成深度为2的Trie树,词组的剩余字串则按序组成词典正文。歧义消除和未登录词识别是中文分词的两大技术难点,本文重点研究交叉型歧义的检测和消除。本文提出一种新的方法来检测交叉型歧义产生的位置,即将所有候选词条表示成二元切分词图,若原子字符的上方和右方同时不为空,则此处存在交叉型歧义。对于交叉型歧义的消除,则使用双字耦合度和t一测试差相结合的方法来判断是否切分。最后,把所有候选词条以及它们之间的相邻共现概率表示成带权有向无环图,来计算图中始末结点间的最短路径来达到最优分词。实验表明,该中文分词算法在CPU2.0GHz,内存256MB的环境下,切分速度达到35000字/秒,分词准确率达到97.2%,召回率达到93.7%。算法的性能能够满足大部分上层应用的要求。关键词:中文分词,哈希索引,概率统计,最短路径算法 AbstractChineseWordSegmentation(CWS)isaprocessofturningaseriesofChinesecharactersintoaseriesofChinesewordswithsomerules.AsthefundamentalcomponentofChineseinformationprocessing,CWSiswildlyusedincorrelativeareas.Accordingly,researchonCWShasimportanttheoreticandrealisticmeaning.Inthisthesis,wemainlyresearchonthetechonogiesofdictinory,ambiguityresolution,andsegmentationalgorithmetc.AccordingtothestatisticalcharactersofChinesewords,thealgorithminthisthesisisbasedondictionaryandstatistics.Whenweorganizethecoredictionary,weconsidertheefficientoftimeandspace,andthestatisticalcharactersofChinesewords,SOweusethemethodoffirsttwocharactersHashtable,toformaTrie.treewhichdepthis2,whiletherestcharactersofthewordsalestoredbyorder.AmbiguityresolutionandunknownwordidentificationarethetwodifficultiesinCWS,inthisthesis,wefocusonresolveoverlappingambiguity,andwepresentanewwaytofindtheoverlappingambiguoussegmentationposition:weorganizeallthecandidatewordsasa2一dimensionsegmentationgraph,andiftherealewordsbothatthetopandtherightofanatomcharacter,itmeansthatthereisanoverlappingambiguityatthisposition.Thenweusethemethodofdoublecharactercouplinganddifferenceoft-testtodecidetheposition.Atlast,weconvertallthecandidatewordsandtheirdistancesintoadirectionmapwithlengthandwithoutcircle,togetthebestCWSresultbycomputingtheshortestpathbetweenthestartnodeandendnodeofthemap.OurexperimentismadeonaPCequippedwithPentium4CPUat2.0G.Hz,256M—ByteofRAM.Astheexperimentresultsshowthatthespeedofthisalgorithmcanreach35000character/s,theprecisionrateCanreach97.2%,andtherecallrateCanreach93.7%.TheperformanceofthealgorithmCanmeetthedemandofmostapplicationsystems.Keyword:ChineseWordSegmentation,HashIndex,ProbabilityandStatistics,ShortestPathAlgorithm 声明本学位论文是我在导师的指导下取得的研究成果,尽我所知,在本学位论文中,除了加以标注和致谢的部分外,不包含其他人已经发表或公布过的研究成果,也不包含我为获得任何教育机构的学位或学历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文中作了明确的说明。研究生躲啤扣7年簖肋日学位论文使用授权声明南京理工大学有权保存本学位论文的电子和纸质文档,可以借阅或上网公布本学位论文的部分或全部内容,可以向有关部门或机构送交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密论文,按保密的有关规定和程序处理。研究生签名:叩年《月沙日 硕_上论文中文分词关键技术研究1引言在自然语言处理中,词是最小的能够独立活动的有意义的语言成分【Il。我们知道,在英文文本中,单词之间是以空格作为自然分界符的。中文和英文比起来,有其自身的特点,就是中文以字为基本书写单位,句子和段落通过分界符来划界,但是词语之间没有一个形式上分界符。也就是说,从形式上看,中文没有“词"这个单位。因此,进行中文的自然语言处理通常都是先将中文文本中的字序列切分为合理的词序列,然后再在此基础上进行其它分析处理。将中文连续的字序列按照一定的规则重新组合成词序列的过程,就叫做中文分词。1.1研究背景“没有中文分词,其他一切深入的中文信息处理都无从谈起。"一位专家这样说。作为中文信息处理基础的中文分词技术,己经被广泛应用于中文信息领域的信息检索、自动摘要、中文校对、汉字的智能输入、汉字简繁体转换、机器翻译、语音合成等技术中。自20世纪80年代初,中文信息处理领域提出自动分词以来,相关方面的众多专家学者、科研院所、商业机构为之付出了不懈的努力,取得了一些重要的进展和一些实用性的成果,提出了许多中文分词方法,有些成熟的技术已经应用于产品当中。但这些分词方法或多或少都存在着不足之处,比如对于检索系统,由于近年来信息的多元化、复杂化,对信息处理技术的研究、发展、应用提出了新的挑战,跨越了单纯文本的检索,例如问答系统必须对关键字进行语义分析与处理。这就要求信息处理技术必须跟上信息发展的速度,在速度与性能方面具备更高的指标。要让计算机能够自动地处理信息就必须借助分词技术让计算机理解自然语言。然而在当前的技术水平下,中文分词算法要想获得更好的切分精度,通常都需要借助大量的语言资源,相应地又要求耗费更大比例的时间和空间去处理这些语言资源。因此一般切分精度比较高的算法,切分的速度都比较慢;而一些切分速度快的算法,因为抛弃了一些繁琐的语言处理,所以切分精度都不高。从当前一些主要的分词算法来看,切分精度虽然有差别,但差别不是特别大,好的算法切分精度能够达到95%以上,普通算法的切分精度也能达到80%以上;而切分速度相对而言差别则比较大。对于当前的一些实际应用,l:l,女HWeb搜索引擎来说,时间效率是非常重要的,那些较高切分精度的分词算法,因为速度太慢不仅无法满足Web搜索引擎的应用需求,有时甚至也无法满足其它自然语言处理研究的需求。目前的许多实际应用产品,为了保证速度而牺牲部分准确度,因而采取了一些比较简单的切分算法。 I引言硕上论文限于当前的技术水平,中文切分要做到百分之百的正确是不大可能的。而且中文的特点之一就是词没有确定的规范与标准,这也导致了上层不同的应用对分词有不同的标准要求,有些应用把不属于同一个词组的字符联想出现,有些应用却把属于同一个词组的字符分割开了。比如对于以词为单位的键盘输入系统,为了提高输入速度,一些互现频率高的相互邻接的几个字通常作为一个输入单位,如:“也就”、“这是”、“每一"等等。而对于检索系统来说,则倾向于分词单位较小化,比如把“中文分词算法"切成“中文\分词\算法",使得无论用“中文分词算法”、“中文分词"还是用“分词"、“分词算法”进行检索,都能得到结果。目前研究中文分词技术的大多是科研院校等,清华大学、北京大学、中国科学院、微软中国研究院等等都有自己的研究队伍,此外,海量科技是专业研究中文分词的商业公司。但科研院校集中于研究通用的分词算法,以提高分词准确率为目的,评测机构关于分词也是以通用的分词精度为准绳,且又允许参评系统的输出结果具有一定的“柔性”12】,大部分不能很快产品化,而一个专业公司的力量毕竟有限。鉴于中文分词在分词标准和分词算法本身上存在的困难,本文将在前人的研究基础上,对中文分词中的词典机制、歧义消除、算法实现等关键技术进行研究,并且实现一种实用的中文分词算法。1.2中文分词的发展概况及现状自20世纪80年代初,中文信息处理领域提出自动分词以来,取得了一些重要的进展和成果,提出了许多中文分词方法,实现了许多中文分词系统,其中典型的分词系统【3】有如下几个。北京航空航天大学的CDWS是我国第一个实用性的自动分词系统,在实现CDWS过程中,相关研究者在自动分词的理论上作了深入细致的探讨,首次论证了汉语自动分词的可行性,初步建立了一个描述书面汉语的计算模型,对自动分词的有关概念和术语都给出了明确的定义,并且把歧义切分字段也首次作了分类,具有很大的理论意义。清华大学也先后研制开发了SEG、SEGTAG分词系统。复旦大学的分词系统对一般的人名识别效率很高。哈尔滨工业大学的分词系统是一种典型的运用统计的方法进行纯分词的分词系统。还有杭州大学改进的MM分词系统和北京大学计算语言学研究所研制的系统。中科院汉语词法分析系统是目前较为满意的系统,在973评测中获得了第一名,该分词系统的主要是思想是先通过CHMM(层叠形马尔可夫模型)进行分词,通过分层,既增加了分词的准确性,又保证了分词的效率,但是该系统为提高分词的召回率和准确率,在未登录词识别、重新切分等方面进行了相当多的语言处理,花费了太多时间,以致切分速度不是很快。另外还有MicrosoftResearch汉语句法分析器中的自动分词系统。2 硕十论文中文分词关键技术研究1.3中文分词简介根据定义,中文分词就是将一段中文的字序列切分成词序列的过程。例如“我是一个学生"的切分结果为“我\是\一个\学生”。然而虽然现在中文分词领域已经有了相当多的技术积累,但是中文分词问题仍然未能得到完美的解决。就像上面的例子中“我是一个学生"的英文表达为“IRITIastudent”。计算机可以简单地通过空格知道“student"是一个单词,但是计算机却不能很容易地明白此处“学’’和“生”两个字合起来才构成一个词。中文分词不仅在分词算法的实现上存在难点,而且中文分词本身存在着规范标准问题。1.3.1分词规范(1)“词"是否有清晰的定义?在每本汉语语法教科书中,我们都可以找到对“词’’的这样一条定义:语言中有意义的能单说或用来造句的最小单位。这个定义相当抽象,从计算的层面上讲,这种模棱两可的定义是不可计算的,即不可操作的。而产生如此定义涉及多个方面【4j:①核心词典问题:在进行分词时需要有一个核心(通用的、与领域无关的)词典,即普通词典,凡在该词典中存在的词,在分词时就应该切分出来。但是应该将哪些词组收入到核心词典中去,虽然已经提出各种收词的条件,但是对每个词组按照这些条件的进行判断却难以操作,因此目前还没有合理的可操作的理论和标准。②词的变形结构问题:汉语中的动词和形容词有些可以产生变形结构,例如“打牌”、“开心"、“看见"、“相信”可能变形为“打打牌”、“开开心"、“看没看见"、“相不相信”等。在对变形结构进行切分时,如果切分出“打打\牌”、“开开\心’’就不怎么合理,“看\没\看见"还说得过去,但“相\不\相信"就说不过去了。在进行中文分词时,对这些变形结构的切分缺少可操作的、合理的规范。③词缀的问题:例如语素“者”在现代汉语中单独使用是没有意义的,因此“作者”、“成功者”、“开发者”内部不能切开。依据这个标准,“开发中国第一个操作系统软件者"、“作出了巨大个人财产和精神牺牲者”、“克服许多困难而最终获得成功者”内部也不能切开,这样复杂的结构在本质上就与词的定义相矛盾。又如职务名称“外交部长",语义上理解为“外交部之长”,切成“外交\部长”、“外交部\长"、“外交\部\长"或不予切分,都会有人提出异议。④非词语素问题:现代的书面汉语并非纯粹的“现代汉语”,其中夹杂着不少文言成分,如“为民除害”、”以逸待劳”、”帮困济穷”等等。探寻白话文中夹杂文言成分的规律,是中文信息处理需要解决的一大问题。经过信息界和语言学界的共同努力,在1993年作为国家标准公布的《信息处理3 l引言硕士论文用现代汉语分词规范》中,文本中的词语被称为“分词单位",以区别语言学中更严格的“词”概念。该标准按词类分别给出了各类分词单位的定义,然而又把“结合紧密”、“使用稳定”也视为分词单位的界定准则,但是像“结合紧密”和“使用稳定”这样的判断是相当主观的。一些评测机构也是按照分词规范的思路来对参加测试的结果进行评测的,在这些评测比赛中,允许参评系统的输出结果有一定的“柔性"【2】,即分词结果尽管同组织方给出的标准答案不一样,但结果如果仍符合“紧密"和“稳定’’的规范条款,就认为切分是正确的。这种评测方法的不足之处在于从一定程度上引入了评测者的主观判断。因此,这样的规范与标准,无论在分词系统的实现上还是评测上都造成了极大的困惑。一句话,这种评测标准缺少对什么是词的可计算定义。(2)词频对领域有一定的敏感性。即使一些统计信息是从精心挑选的“平衡语料库"中计算而来,将之应用于不同领域也会产生偏移,从而导致切分过程中切分的精度下降。而且不同目标的应用对词的切分规范的要求又有所不同,理论上讲汉语自动分词规范,作为规范,那么必须支持各种不同目标的应用,但不同目标的应用对词的要求是不同的,甚至是有矛盾的。①以词为单位的键盘输入系统,为了提高输入速度,一些互现频率高的相互邻接的几个字也常常作为输入的单位,比如:“每一"、“再不”、“这就”、“也就"等。②检索系统,检索系统的词典注重术语和专名,并且一些检索系统倾向于分词单位较小化。比如,在构造倒排文档及创建索引时把“分布式计算"切成“分布式\计算",使得无论用“分布式计算"还是用“分布式"检索,都能查到。上述的两个实例,前者把不是词的几个字放在了一起组成了“词",而后者把是词的却切分开了。事实上,许多中文信息处理系统,都是根据自己服务目的制定适合自己需要的分词系统。因此分词系统的通用性、适应性普遍不足,其分词结果很难采用统一的通用的分词标准来评价。1.3.2中文分词的难点事实表明,并非有了成熟的分词算法,我们就能够轻松地解决中文分词过程中存在的问题。因为中文是一种十分复杂的语言,而让计算机去理解中文语言就更加困难了。比如文言文,普通人去理解就有极大的困难,更不用谈让计算机去处理所面临的困难了。即使从现代词的意义上对中文文本进行切分,也面临两大难题:歧义识别、新词识别。1.3.2.1歧义识别中文分词过程面临的歧义主要有两种情况:组合型歧义和交叉型歧义。所谓组合型歧义,是指某个词组其中的一部分也是一个完整的有意义的词,即对于字串4 硕十论文中文分词关键技术研究“AB”,如果“AB”组合起来是一个词,并且其子串“A"、“B”单独切分开各自也成为有意义的词,则称“AB”存在组合歧义。例如在“中华人民共和国”中,其子串“中华”、“人民"、和“共和国”都各自成词,但是它们组合起来也构成一个词。而交叉型歧义就是指两个相邻的词之间有重叠的部分,比如对于字串“ABC",如果其子串“AB”、“BC"分别为两个不同的有意义的词,那么对“ABC”进行切分,既可以切分成“AB\C",也可以切分成“A\BC",则称“ABC"存在交叉型歧义。例如“保证金融安全",而“保证"、“保证金"和“金融”在词典中都有存在。对于组合型歧义,可以使用最大正向匹配算法解决,但对于交叉型歧义,则不能解决问题,研究表明,歧义的产生主要后者,它约占整个分词歧义的85蚶5J以上。所以,处理好交叉型歧义字段在很大程度上能保证一定的分词精度。另外还存在一种歧义是真歧义。真歧义是指给出一句话,即使由人去判断也不知道应该如何切分。例如“乒乓球拍卖完了”这句话,我们可以切分成“乒乓球拍\卖\完\了"、也可切分成“乒乓球\拍卖\完\了”。如果没有相关的上下文语境,那么将无法知道“拍卖”在这里是否应该作为一个词组切分在一起。1.3.2.2新词识别新词,又称为未登录词。语言在不断的发展和变化过程中导致新词不断出现,同时词的衍生现象也非常普遍,所以任何词典都不可能囊括所有的词。新词中最典型的是人名,人名很容易与常规词形成交叉型歧义。例如在句子“赵飞虎昨天去南京了”这句话中,人们可以很容易地理解此处“赵飞虎”是作为人名的一个词组;但是在句子“赵飞虎背熊腰”中,“赵飞虎”就不能算作一个词了。新词中除了人名以外,还有机构名、地名、产品名、商标名、简称、省略语等,这些词人们经常使用但让计算机能够正确处理却很困难。在相关的运用到中文分词的信息处理应用中,分词算法能否对新词进行有效识别对上层应用来说十分重要,目前新词识别的准确率已经成为一个评价分词系统好坏的重要指标。1.4本文的研究内容本文的主要目标是通过对目前中文分词关键技术的研究,设计并初步实现一个实用的中文分词系统。主要研究内容与工作有以下几点:(1)分析了当前中文分词的研究现状,介绍了几个典型的分词系统,介绍中文分词的规范,难点等。(2)研究了三类基本的分词算法:基于字符串匹配的分词方法,基于统计的分词方法,基于知识理解的分词方法。并以正向最大匹配算法为例,简单介绍了其实现原理与过程。并指出必须根据上层具体应用使用相应的实现方法。(3)鉴于大部分上层应用对中文分词的速度要求很高,分词过程中需要频繁地与气 硕十论文词典进行查找与匹配。根据语言的统计规律,本文使用了基于双字Hash索引的分词词典机制,并设计实现了其数据结构。(4)在歧义切分方面,本文重点就交叉型歧义的位置检测和歧义消除进行了研究分析。并且提出了一种新的方法来检测交叉型歧义产生的位置,即将所有候选词条表示成二元切分词图,若原子字符的上方和右方同时不为空,则此处存在交叉型歧义。而对于交叉型歧义的消除,则使用双字耦合度和t-澳JJ试差相结合的方法来判断是否切分。(5)以最短路径算法为思想,设计并初步实现了一个中文自动分词系统。1.5本文的结构安排第一章引言。首先介绍了本文的研究意义;然后对中文分词的发展概况及现状进行了说明;接着阐述了中文自动分词基本概念、分词规范以及难点;最后介绍了本文的主要工作和论文的结构安排。第二章中文分词算法。首先介绍了常用的中文分词算法,包括基于字符串匹配的分词方法,基于统计的分词方法,基于知识理解的分词方法;接着为了说明不同上层应用对中文分词算法的不同要求,并以检索系统中中文分词算法的使用进行举例说明;最后给出了中文分词的评测标准。第三章基于双字Hash索引的分词词典。本章首先介绍了目前中文分词技术中常用的词典机制及相应算法,并结合实例,给出词组在词典中查找匹配的过程。然后介绍我们的分词算法中使用的核心词典的机制及实现方法。第四章歧义消除。本章重点讨论如何消除交叉型歧义,文章首先介绍了常用的检测方法,并提出一种根据二元切分词图中所有候选词条的排列的规律,检测交叉型歧义产生位置的新方法;最后介绍耦合度和t一测试差相结合的方法消除交叉型歧义的实现原理与方法。第五章算法的实现与实验。本文采用基于词典和统计相结合的方法,根据算法的流程,介绍了重点步骤的实现原理与方法,最后进行实验与分析。第六章总结和展望。对本文所做的工作进行了总结,并对将来进一步的研究工作进行了展望。6 硕士论文中文分词关键技术研究2中文分词算法在第一章中已经简单介绍了中文分词的概念、及技术难题等。本章将首先介绍目前常用的一些分词算法,并以正向最大匹配分词法为例,介绍算实现原理与方法;接着为了说明不同上层应用对中文分词算法的不同要求,并以检索系统中中文分词算法的使用进行举例说明;最后给出中文分词的评测指标。2.1中文分词算法介绍自从1983年,北京航空航天大学实现了我国第一个实用性的自动分词系统CDWS到现在,国内外的研究者在中文分词领域进行了广泛的研究,提出了许多有效的算法。这些算法大致可分为以下几类:基于字符串匹配的分词方法、基于统计的分词方法、基于知识理解的分词方法。2.1.1基于字符串匹配的分词方法基于字符串匹配的方法又叫做机械分词法,这种方法要事先准备一个“充分大的"词典,然后将待切分的句子按照一定的扫描规则与词典中的词条进行匹配,如果匹配成功,则将这个词切分出来,否则进行其他相关处理。按照扫描方向的不同分为正向匹配和逆向匹配;按照不同长度优先分配的情况,分为最大匹配和最小匹配;按照与词性标注过程是否相结合,又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的基于字符串匹配的方法有如下四种。(1)正向最大匹配分词法之所以称为最大匹配,就是要求每一句的切分结果中词组的总数最少。比如在“我们是中华人民共和国的公民”这句话中,我们可以清楚地判断,如果在字典中进行匹配,只要匹配成功就切分出来,那么这句话可能被切分成“我们\是\中华\人民\共和国\的\公民”,该结果中一共包含7个词。但是,为了实现最大匹配,我们将把“中华人民共和国”作为一个整体的词进行处理。因此就要求将上面这句话切分为“我们\是\中华人民共和国\的\公民",一共是5个词,根据最大匹配的原则,我们选择第二种分词结果。J下向最大匹配法又分为增字匹配法与减字匹配法【6】。增字匹配法需要一种特殊结构的词典,这种方法能够达到非常高的分词效率,在此只介绍减字匹配法。减字匹配法的流程如图2.1所示,首先将句子读入,然后将句子在词典中进行查找匹配,如果没有匹配成功则在句子末尾减去一个字,再在词典中进行查找匹配,重复上述过程,直到匹配上词典上的某个词组或只剩下一个字符,接着将句子剩余的部分重复上述流程,直到将句子全部分解成原子或词典中存在的词组。7 2中文分例算法硕七论文图2.1减字分词法过程图2.1是减字法的分词过程,为了说明该方法是如何分词的,我们利用减字法进行正向最大匹配分词,以“我们是中华人民共和国的公民”为例。如果事先知道词典的最长词长,那么将减少很多步骤,从而提高分词速度。此处假设词典中最长词长为7。那么实例的整个匹配过程如下所示:表2.1实例的匹配步骤步骤操作的句子操作分词结果l我们是中华人民共和国的公民只取7个字2我们是中华人民词典匹配失败3我们是中华人词典匹配失败我们词典匹配成功我们是中华人民共和减词并取前7个字是中华人民共和词典匹配失败我们是词典匹配成功我tfJ\是 硕士论文中文分词关键技术研究中华人民共和国减词并取前7个字中华人民共和国词典匹配成功我们\是\中华人民共和国NULL减词我'lfJ\是\中华人民共和国\的\公民(2)逆向最大匹配分词法逆向最大匹配分词的扫描方向与正向最大匹配分词相反,是从句子的结尾开始扫描,直至句首。统计结果表明,单纯使用正向最大匹配的错误率为1/169,单纯使用逆向最大匹配的错误率为1/24517。,显然逆向最大匹配分词法在切分的准确率上比正向最大匹配分词法有较大的提高。比如待切分字串为“瑞星以技术和服务开拓网络安全市场",那么正向最大匹配的结果为“瑞\星\以\技术\和服\务\开拓\网络\安全\市场”,逆向最大匹配的结果为“瑞\星\以\技术\和\服务\开拓\网络\安全\市场’’,而前者是错误的,后者才是正确的结果。当然,这也只是个特例,一定会有正向最大匹配比逆向最大匹配更准确的情况。关于正向最大匹配算法和逆向最大匹配算法相应的词典组织结构,我们做如下设想:设置正向最大匹配的词典中的词是正序的,而逆向最大匹配的词是逆序的,比如前者词典中的一个词为“见义勇为",则后者词典中为“为勇义见"。这样可以省略处理待匹配字符串顺序的工作,从而节约时间。(3)最少切分分词法(使每一句中切出的词组数目最小)(4)双向匹配法(将正向最大匹配法与逆向最大匹配法组合)最大匹配法分词存在如下缺陷:首先,词典词长限制,词长过短,长词就会被切错;词长过长,查找匹配效率就会比较低。其次,掩盖分词歧义,不能发现交叉型歧义。最后,最大的匹配并不一定是想要的分词结果。但这种方法的优点在于实现简单,而且切分速度快。2.1.2基于统计的分词方法从概率的角度出发,单个字出现在词组中的联合概率是比较大的,因此当相邻的字越经常出现,则越有可能是一个词组。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度16j。因此可以对语料中相邻共现的各个字的组合的频度进行统计,计算它们的相关度,计算两个汉字A、B的相邻共现的概率。可以对语料中相邻共现的各个字的组合的频率进行统计,例女I:IN个字的语料库中字A出现的次数为』、,。次,字B出现的次数为Ⅳ。次,那么字A独立概率为尸(么)=N。/Ⅳ,字B独立概率为尸(B)=NB/Ⅳ,假设A、B是完全独立出现,那么“AB”在一起出现的次数应该大约为P(A)母P(B)聿N=(NA牛%)/N次,如果实际出现的次数为Ⅳ彳丹次,那么我们定义一9 2中文分词算法硕一L论文个相关度Cab:Cab=些娄堕些:罂姿塑忑;:丝星一坐趟(2.1)AB纯随机联合出现次数(以木N占/N)M乖虬一7如果Cab超过规定的一个阈值,即相邻字出现的联合概率远大于单字出现的概率之积,则相邻的字串“AB”有可能属于同一个词组。这种方法首先切分与词典能匹配成功的所有可能的词,即找出所有候选词条,然后运用统计语言模型和决策算法得出最优的切分结果。由于纯粹从统计的角度出发,因此在统计意义上某些经常出现在一起的字并不能构成完整的词语,例如“上的"、“下的”、“这一"等在文本中会大量的互邻同现,但他们却分属于不同的词;并且统计语言模型和决策算法在很大程度上决定了解决歧义的方法,需要大量的标注语料,并且分词速度也因搜索空问的增大而有所减慢。基于统计的分词方法所应用的主要的统计量或统计模型有:互信息、N元文法统计模型、隐马尔科夫模型和最大熵模型等。这些统计模型主要是利用词与词之间的联合出现概率作为分词判断的信息。2.1.3基于知识理解的分词方法该方法主要基于句法、语法分析,并结合语义分析。通过对上下文内容所提供信息的分析对词进行定界,它通常包括三个部分:分词子系统、句法语义子系统、总控部分【8】。在总控部分的协调下,分词子系统可以获得有关词、句子等的句法和语义信息,用来对分词歧义进行判断。这类方法试图让机器具有人类的理解能力,需要使用大量的语言知识和信息。由于汉语的复杂性,难以将各种语言信息组织成机器可直接读取的形式,因此目前基于知识理解的分词系统还处在试验阶段。分词算法是中文自动分词的核心,一个好的分词算法对于中文处理系统的综合性能起着举足轻重的作用。但对于任何一个成熟的系统来说,不可能单独依靠某一种算法来实现,都需要综合不同的算法。据了解,海量科技的分词算法就采用“复方分词法”,所谓复方,相当于用中药中的复方概念,即用不同的药才综合起来去医治疾病。以目前流行的Web搜索引擎来说,会综合考虑种算法来处理问题。2.2根据具体应用使用合适的分词算法现在很多的中文分词算法都是通用的分词算法,然而对于某一具体的应用系统,并不是单纯使用某种分词算法就能解决问题,我们可以根据具体应用的所需满足条件使用不同的方法。在此以中文信息检索中所用到的分词算法为例进行说明。(1)混合分词对于实际应用的检索系统来讲,当不清楚选择哪种分词算法更好的话,不妨试着合并使用多种方法,而混合分词就是一种简单易实现的方法,也是大型检索系统常10 硕上论文中文分词关键技术研究用的一种方法,使用混合分词方法能够涵盖更多的词汇[61。混合分词的原理就是“先用专业词典进行一遍分词,再用普通词典进行一遍分词”,我们将用一个实例对为何要进行两次分词进行说明。例如,对“搜索引擎知识”这句话进行分词,如果我们的词典中含有“搜索引擎’’这个词,那么这句话的切分结果就是“搜索引擎\知识"。如果词典中没有“搜索引擎”这个词,而只含有“搜索”,“引擎’’,“知识"这三个词,那么这句话的切分结果就是“搜索\引擎\知识”。因此我们可以得到这样一个结论,对同一文本进行切分,如果使用的词典不同,会导致不同的分词结果。显然,如果用第一种方法分词,当一个用户想要查找包含“搜索”这个关键字的相关资源时,他就不会搜索到结果。同理,假设检索系统不对用户输入的词进行切分,如果用第二种方法分词,当一个用户想要查找包含“搜索引擎”这个关键字的相关资源时,同样也找不到结果。所以,只进行一遍分词必然有一定得局限性,如果采用两遍、甚至多遍分词,便会解决上述问题。对于上面这个例子,我们采取组织两个词典的措施:一个为专业词典,一个为普通词典。其中,专业词典放置一些比较专业的词组,比如名人人名、专有名词、地点名、机构名等,普通词典就是我们常用的词组。那么我们可以将“搜索引擎”放入专业词典,将“搜索"、“引擎’’放入普通词典。先用专业词典进行一遍分词,再用普通词典进行一遍分词,最后将结果合并到一起,那么结果如“搜索引擎\搜索\引擎\知识”。这样既满足了查询“搜索引擎”的要求,又满足了查询“搜索”的要求。据了解【9J,百度的分词采取了至少两个词典,一个是普通词典,一个是专用词典(人名等)。而且是专用词典先切分,然后将剩余的片断交由普通词典来切分。一般专业的搜索引擎对分词速度要求要达到1M/s以上,因此为了提高处理速度,百度的普通词典切分采用双向最大匹配算法,这种分词算法舍弃了一定得精度来达到极快的切分速度。因为对于搜索引擎来说,在查询切分和文档切分时采用相同的分词算法,如果有一些文档切分是分词是错误,在查询切分时也产生相同的切分错误。那么即使两次切分阶段错误,但最后相同错误却使匹配成功,使得仍然可以正确检索到结果。关于更详细的中文检索系统与分词算法的关系可以参考文献[6】。(2)基于字的切分法不论词典包含的词组有多么的齐全,总是要比新词的出现慢一步,所以有些词在落后一步的词典中是分不出来的,尤其在互联网中,新词的数量更是每天都在增长。那么如何对那些分不出来的词进行处理呢?可以采用多元切分的混合分词的方法。一元分词和二元分词是比较流行的非词典式分词方法。一元分词就是将“ABCDE"切分成“A\B\C\D\E”,这个例子中,就是将一个词拆成一个个独立的字,这称之为一元分词。同样,二元分词就是将“ABCDE’’切分成“AB\BC\CD\DE”,在这个例子中,就是将一个词拆成两两相连的词。在实际应用中,对分不出来的新词 2中文分词算法硕I:论文我们也可以不分词,比如将“ABCDE’’切分成“ABCDE”,这样,我们就较好的保持了新词的完整性。那么,在实际的应用中,我们就可以把三种分词方法全部利用上,以求达到最好的效果。如下一个词条“ABCDEFGHIJ”,假设这个词条首先通过词典分割成“ABCDE\FGH\IJ”。假设FGH与IJ是出现在词典中的字条,ABCDE是分不出来的词,那么对ABCDE进行三遍混合分词,最终结果便为“A\B\CkD\E认B\BC\CDkDEkABCDE\FGH\IJ’’。例如在下面一个例子中“木子美"属于新词,在词典中并不存在,那么我们按照混合分词的方法来对“木子美对记者说”进行分词就该分为“木\子\美\对\记者\说\木子\子美\木子美”。因此当我们查询“木子美”或“木子”的时候也能给出正确的结果。2.3中文分词的评测标准对中文分词来说,召回率(Recall)和准确率(Precision)是最基本的两个评测指标。切分召回率=正确切分的词数覆幂雨磊恧甄’切分准确率=正确切分的词语数瓦飘丽丽丽。(2.2)例如,待切字串“他说的确实在理”的一个分词结果为:“他\说\的确\实在\理”,假设评测给出的答案为“他\说\的\确实\在\理’’。那么切分召回率是:3/6=50%,切分准确率是:3/5=60%。本章小结本章首先详细介绍了中文分词常用的三种算法:基于字符串匹配的分词方法,基于统计的分词方法,和基于知识理解的分词方法;接着为了说明不同上层应用对中文分词算法的不同要求,以检索系统中中文分词算法的使用进行举例说明;最后给出中文分词的评测指标。12 硕上论文中文分词关键技术研究3基于双字Hash索引的分词词典中文分词主要关心两项指标:切分速度和切分精度。由于在分词过程中,需要频繁地在词典中进行信息查找匹配,因此要求设计出高效的数据结构来组织词典,以提高查找匹配的速度,这样才能满足上层应用的性能要求。3.1常用词典算法介绍使用索引来组织数量庞大的文件是一种高效的方法。目前在各种中文处理系统中常用于组织词典的索引方法主要有两种:一种是Hash索引、一种是Tile索引树。3.1.1基本概念国标GB2312汉字编码表共收录了6763个汉字,为了对齐,里边加上有5个空白编码,所以实际上共有6768个汉字。根据汉字机内码编码规律,汉字在编码表中的偏移量计算公式如下㈣:offset=(cl一0xB0)木94+(c2—0xAl)(3.1)其中,offset代表某汉字在编码表中的位置,c1、c2代表汉字的内部码。因此每一个汉字都有自己唯一的偏移量。对词典中相同首字的词语的进行Hash表的索引,则词典中都有唯一的一项地址,表示以此字开头的词语的集合。3.1.1.1Hash索引Hash函数是一个映像,其将关键字的集合映射到某个地址的集合。用Hash表的方法构造词典就是将关键字与表项的存储位置建立一个对应的函数关系。以首字Hash词典机制的原理为例,据汉字机内码的编码规律可知,我们就可以通过一对一映射的Hash函数实现词首字的快速查找。根据Hash函数的定义可知,Hash函数一般都无法避免冲突,所以通常还要有相应的冲突处理方法,因此对于词组中的剩余字串最快的只能通过二分查找来进行查找。我们的思想是基于Hash索引的词典机制就是构造一种Hash函数来计算词语的Hash值,将Hash值相同的词组放入一个通常称之为“桶"的集合内。匹配时先计算待查词的Hash值,得到首字的存储位置,然后再进入相应的Hash桶内再进行二分查找。3.1.1.2Trie树键树【ll】又称数字查找树。它是一棵度>=2的树,树中的每个结点中不是包含一个或几个关键字,而是只含有组成关键字的符号。例如,若关键字是数值,则结点中只包含一个数位;若关键字是英文单词,则结点中只包含一个英文字母。键树中每个结点的最大度d和关键字的“基”有关,若关键字是英文单词,则d=27,若关键字是13 3基于双宁Hash索引的分词访J典硕{j论文数值,则d=11。键树的深度h则取决于关键字中字符或数位的个数。若以树的多重链表表示键树,则树的每个结点中应含有d个指针域,此时的键树称为Trie树。若从键树的某个结点开始到叶子结点的路径上,每个结点中都只有一个孩子,即为单支树,则可将该路径上的所有结点压缩成一个“叶子”,且在该叶子结点中存放关键字值及指向该元素的指针域。在分支结点中不设置数据域,每个分支结点所表示的字符均由其双亲结点的指针所指向的位置决定。在Tile树中的查找操作过程如下:从根结点出发,沿着与给定值相应的指针逐层向下直到叶子结点,若叶子结点中的关键字与给定值相等,则查找成功;若分支结点中与给定值相应的指针为空,或叶子结点中的关键字与给定值不相等,则查找失败。图3.1是一个字母类型的Trie索引树,比如查找单词“have”,则首先在第一级索引中查找字母“h",接着按照第一级索引中“h”对应的指针找到对应的第二级索引,再在其中查找字母“a",⋯⋯,依次查找下去,最后找到叶子结点中的关键字“have”,与给定值相等,说明查找成功。又比如查找单词“hza'’,同样首先在第一级索引中查找字母“h”,接着按照第一级索引中“h”对应的指针找到对应的第二级索引,在其中找到字母“Z",此时的指针为空,查找失败。$a⋯h⋯3.1.2几种词典结构14图3.1一个字母类型的Tile索引树结构 硕士论文中文分词关键技术研究文献【12]提出了三种典型的的分词词典机制:基于整词二分的分词词典机制、基于Trie索引树的分词词典机制、和基于逐字二分的分词词典机制,下面对它们进行简单的介绍。3.1.2.1基于整词二分的分词词典机制如图3.2所示,这种机制下的分词词典包括三个部分:首字Hash表、词索引表、词典正文。词典正文是以词为单位的有序表,词索引表是指向词典正文中每个词的指针表。通过首字Hash表的哈希定位和词索引表很容易确定指定词在词典正文中的可能位置范围,进而在词典正文(“桶”)中通过整词二分进行定位,匹配过程是一个全词匹配的过程。以查找S==“你小子大白天还在睡觉"中从“大"字开始的最长词(及所有词)为例,根据图3.2的词典结构,实例的匹配步骤如下:(1)取从“大’’字开头最长可能的字串WordMax,WordMax=“大白天还在睡觉”;(2)用整词二分法在词典中查找候选词WordMax,查找失败;(3)去掉Word—Max最后一个字,重复步骤(2),查找失败;(4)重复步骤(3);(5)经过5次尝试,Word.Max最终消减到“大白天”,此时查找成功,于是返回WordMax=“大白天"。泞字tlash袭入U项个数第~项指针i通索·jl袭弼娥lj二殳指针蠲典正文图3.2基于整词二分的分词词典机制从上述的匹配步骤可以看出,此过程类似于J下向的最大匹配。即先匹配最长词,若成功则返回;否则在待匹配字串的末尾减去一个字符,接着继续匹配,直至结束本轮匹配。3.1.2.2基于Trie索引树的分词词典机制基于Trie索引树的分词词典机制,如图3.3所示。这种分词词典包括两个部分:首字Hash表、Trie索引树结点。Tile索引树的优点是在对被切分字串的一次扫描过程中,不需要预先知道待查词组的长度,沿着树链逐字匹配即可;缺点是它的构造和 3基于双‘≯Hash索,j【的分词词典硕士论文维护比较复杂,而且都是单词树枝(一条树枝仅代表一个词组),由于词典在进行中文分词时会事先读入内存,因此这种空间浪费了一定的空间。下面举一个实例进行说明,以查找S==“你小子大白天还在睡觉"中从“大”字开始的最长词(及所有词)为例,按照图3.3的词典结构,其匹配步骤如下:(1)首先通过首字散列表得到以“大”字开头的词的Trie索引树结点,假设为Tl;(2)由于结点Tl中包含关键字“NULL’’(表示空字符),因此“大’’字是一个词。在结点Tl中用二分法查找关键字“白”,其指针指向的目标结点假设为T2。(3)结点T2中包含关键字“NULL”,因此“大白"也是一个词。在结点T2中继续用二分法查找关键字“天",此时“天’’的目标结点已是叶子结点,所以“大白天"也是一个词,查询结束。最后得到“大白天’’为最长词。污宇ltash袭入U项个数第一项指譬1.苁键宇予树天小予树指针瓣‘≯豹。l’rio索rjl树夫絮爱+蠡图3.3基于Trie索引树的分词词典机制从上图可以看出,为了节省空间,此处的Trie索引树并非如图3.1所示,把所有汉字索引都列出来,而只是列出了词组存在的部分,故上述步骤(2)采取二分查找的方法来进行查找。而在图3.1中是可以直接根据指针去查找是否在该位置是否存在词,虽然图3.1的方法速度更快,但严重浪费了空间。3.1.2.3基于逐字二分的分词词典机制16 硕十论文中文分词关键技术研究这种词典机制是前两种机制的一种改进方案。逐字二分与整词二分的词典结构完全一样,只是查询过程有所区别。逐字二分吸收了Tile索引树的查询优势,即采用“逐字匹配”,而不是整词二分的“全词匹配",这在一定程度上提高了匹配的效率。但由于仍采用整词二分的词典结构,因此逐字二分查询效率的提高存在局限性。以查找S==“你小子大白天还在睡觉”中从“大”字开始的最长词(及所有词)为例,按照图3.4的词典结构,实例的匹配步骤如下:(1)通过首字Hash表找到以“大’’字开头的词在词索引表中的范围Rl,并且可知其中的头一项“大"为一个单字词;(2)通过二分法在范围Rl内查找第二个字为“白”的词,可得到“大白”开头的词在词索引表中的范围R2,并且其中的头一项“大白"为一个二字词;(3)通过二分法在范围R2内查找第三个字为“天”的词,可知以“大白天”开头的词在词索引表的范围R3,并且其中的头一项“大白天”为一个三字词;(4)通过二分法在范围R3内查找第四个字为“在”的词,此范围为空,查询结束。最后得到“大白天”为最长词。根据代数知识可知,R3∈R2∈R.。翁字索弓l袈硼索0l袭人图3.4例子在基于逐字二分的分词词典机制中的查询过程3.2双字Hash索引分词词典3.2.1词典的实现原理啊夫人粢天},1人f{菜人n话人l,{裂久妇火久},j灭说梦话大鲮17 3基于双’≯Hash索引的分词访J典硕十论文陈桂林、王永成等于2000年在《计算机研究与发展》--t:U上的《一种改进的快速分词算法))t13】一文,提出一种在对现有词典进行重构的基础上提高分词速度的算法。这种分词的基础是建立一种支持首字Hash和标准的二分查找,且不限词条长度的词典。以后发展的基于Hash的词典机制,都是以文献[13】为基础的。整词二分和Trie索引树是分词词典机制的两个极端。前者的数据结构简单、占用空间小,构建及维护也简单易行,但由于采用全词匹配的查询过程,效率低下;后者的数据结构复杂、空间浪费较为严重,树的构造和维护也较为繁琐,但它采用的查询过程是“逐字匹配”,所以查询效率较高。而逐字二分分词词典机制虽然采用了较为匹配方法的更为高效,但并没有改进整词二分的数据结构,使得匹配过程并不是完全意义上的逐字匹配,这就导致查询效率并没有得到最大限度的提高。根据文献[14】中的显示的数据,在该文使用到的一个包含43570条词组的词典中,单字词组有2606条,双字词组有33527条,两者共计36133条,占整个词条数目的82.93%,并且两者使用频率更是达到96.35%之多。相反,多字词语不仅所占比例较小,而且它们的使用频度也较低。表3.1词条分布及出现统计词条字数1234567词条数2606335273693362283363所占。目分5.9876.958.488.3l0.19O.080.01比(%)出现频率56.739.652.211.190.1440.0830.023(%)文献[15】、【16】分别提出了基于双字和基于四字的Hash机制,为了最大限度的提高匹配的时间效率并兼顾空间利用率,并且鉴于上述词条的分别及出现的统计特点,我们的重点研究基于双字Hash索引分词词典机制,该方法吸纳了整词二分及Tile索引树二者的优点,仅对词语的前两个字顺次建立Hash索引,构成深度为2的Tile子树,词的剩余字串则按序组成类似于整词二分词典机制所使用的词典正文,这样就构造了如图3.5所示的词典结构。18 硕士论文中义分词关键技术研究嚣字Itash袭11嫠霉l为las谰h爱指针P1次7爱指针一次字Itash寝楚☆为溯剩余‘≯串指镑藿客芰篙串w慰岔为谰一话图3.5双字Hash索引分词词典结构由图3.5可知,双字Hash索引分词词典结构由三部分组成:(1)首字Hash索引。首字Hash索引的每个单元包括三项内容:①关键字(2字节):词组的第一个汉字字符A;②是否为词(1位):标示单个字符A是否为词;③次字Hash索引指针(4字节):指向以汉字A起始的所有词语的第二个汉字的索引。(2)次字Hash索引。次字Hash索引的每个单元也包括三项内容:①关键字(2字节):词组的第二个汉字字符B;②是否为词(1位):标示字串AB是否为词;③剩余字串组指针(4字节):指向以字串AB起始的所有词语的剩余字串有序数组。(3)剩余字串组。剩余字串组是以字串AB起始的所有词语剩余字串的有序数组,每个单元包括两项内容:①剩余字串(不定长2*n字节):除去词的前两个汉字字符(A、B)后的剩余部分;②是否为词(n.1位):标示从第一个汉字A至对应位置的子串是否也构成一个词。如图中所示,“大白天"是“大白天说梦话"的起始子串,因为“天"对应的标示为“T”,所以“大白天”也是一个词,而“说’’字对应的标示为“F”,所以“大白天说"不是一个词。因为最后一个字符肯定会是某个词的一部分,所以它不需标识(此处以#号表示结束符号)。以上描述的双字Hash索引分词词典结构(正向)很适合正向最大匹配分词方法,而且不用预知待查询词的长度,在从汉字串S的第i个汉字开始分词时,首先逐字匹配S【i】、S[i+l】(此步类似于Trie索引树的查询方式),然后再在S【i】、Sli+11所指向的剩余字串组中逐字缩小范围查询(此步类似于“逐字二分’’的查询方式),这样就能仅通过一遍扫描而达到最大匹配的目的。19 3基于双:≯Hash索引的分词词典硕十论文现举例如下:查询S==“你小子又在大白天说梦话了。”中从“大’’字开始的最长词。(1)首先在首字Hash索引(11)中通过Hash定位得到以“大”字开头的索引项Pl;(2)因为Pl中的“是否为词"属性值为“T",所以“大”是一个词。再由Pl的“指针"得到以“大”字开头的所有词的次字Hash索引12。(3)在12中通过Hash定位得到“白”字的索引项P2。因P2中“是否为词"属性为“T”,所以“大白"也是一个词。再由P2中的“指针”得到以“大白’’开头的所有词的剩余字串组。(4)在W中查找第一个字为“天”的词,得到范围Wl;Wl中仅包含一个字串“天说梦话”,“天"字对应的“是否为词’’标示值为“T”,所以“大白天”是一个词;(5)在W中逐字搜索后续的字“说”、“梦”、“话”并缩小范围,最终得到语句S中从“大”字开始的最长词为“大白天说梦话"。3.2.2词典的数据结构词典在系统中的数据结构如图3.6所示。由于汉字的编码规则,由于每个首字不同,直接构成一级索引,词典共包括6768个数据块。对于每一个相同的首字,再对次字进行Hash索引,即为基于双字的Hash索引,构成二级索引。对于次字以后剩下的词则排列成有序的正文词典。(1)词典类的几个结构体structwordltem{imnWordLen;char木sWord;intnHandle;intnFrequency;>;structindexTable{intnwordCount_l;intnwordCount_2;wordltempWordltemHead;);structwordChain{wordltemdata;wordChain母next;); 硕上论文中文分词关键技术研究上面三个结构体分别用来表示词组,索引表,和分词过程中的链表。(2)词典类的几个重要函数函数boolLoad(char*sFileName)。对词典进行加载,构成深度为2的Trie树,后面所有的查找,都是针对这个索引表进行的。函数boolgetFrequency(char奉sWbrd,intnHandle)。获得输入词条及相应的handle的频率值。函数boolgetMaxMatch(char宰sW-ord,char宰sWordRet,intnpHandleRet)。多次调用,主要是获取所有候选词条及其相应的handle值。函数boolgetHandle(char木sWord,intnpFrequency)。用来查找给定词条的相关信息。(3)词典的组织结构图676B十教据块图3.6词典的结构图2l 3基于双字Hash索0f的分词词典硕士论文3.2.3实验与分析为了更好的说明上文提到的四种词典机制的效率,现在对各种方法进行性能对比,由于没有足够的资源支持,因此本文引用文献【15】的数据进行说明。选取该文进行了三种不同类型的测试:(1)对词典中所有词依次查询~次;(2)对词典中所有词依次查询,查询次数与词频成正比;(3)任取一段文本(大小1.16M),用正向最大匹配法切分该文本;关于实验的空间、时间的结果如下表所示。表3.2各词典机制的实验对比结果词典机制词典空间(字节)实验(1)(ms)实验(2)(ms)实验(3)(ms)整词二分1,207,22219095214.401逐字二分1,207,22214042l2,824Trie索引树2,583,74013138l1-832双字Hash索引1,435,336110330l,793从上面的实验结果可知,从空间方面看,逐字二分与整词二分的词典结构不变,因此词典的大小相同,Tile索引树的词典结构复杂,所占用的空间也最多,双字Hash索引结构的词典所占空间比逐字二分与整词二分稍多,但只有Trie索引的占用空间的55.5%。从时间方面看,双字Hash索引相对于Tile索引树,时间性能的提高有限,但以实验(3)为例说明,双字Hash索引的词典机制对于逐字二分与整词二分来说,运行速度分别提高T(2.824.1.793)/1.793=57.5%和(14.401.1.793)/1.793=7.03倍。本章小结整词二分法因为要进行整词匹配比较,所以速度相对比较慢。逐字二分法是在整词二分基础上的改进,词典整体结构不变,但是在二分查找匹配的时候吸取了Trie树的特点,每次只比较单个汉字,逐字地进行查找。双字Hash的提出是利用中文词语大多数是二字词的统计特点,而且在文档中,通常多字词出现的频率也比双字和单字词要低。词典机制采用前两字逐个Hash索引、剩余字串有序排列的结构,查询过程采用逐字匹配的方法,在不提升已有典型词典机制维护复杂度的情况下,提高了中文分词的速度,是一种较简洁、高效的词典组织机制。 硕上论文中文分词关键技术研究4歧义消除中文分词中的歧义包括组合型歧义和交叉型歧义,本章重点研究如何发现和消除交叉型歧义。首先介绍了交叉型歧义的概念;接着介绍交叉型歧义发现的常用方法,并提出一种新的发现方法;然后介绍如何采用双字耦合度和t.测试差相结合来消除交叉型歧义;最后给出本章小结。4.1歧义介绍汉语文本中含有许多歧义切分字段,典型的歧义有交叉型歧义和组合型歧义。只有向分词系统提供进一步的语法、语义知识才有可能作出正确的决策,排除歧义常常使用词频、词长、词间关系等信息。比如在“真J下在"这段字串中,“真"作为单字词的频率大大低于“在”作为单字词的频率,即“在”常常单独使用而“真"作为单字词使用的可能性较小,所以应切分成“真正\在"。有时切分歧义发生在一小段文字中,但为了排除歧义,需要看上下文信息。如“学生会"既可能是一个名词,指一种学生组织,也可能是“学生\会",其中“会”为“可能”或“能够”的意思。在“学生会主席"中只能是前者,在“学生会去图书馆"中只能是后者,但在“学生会组织义演活动"中歧义仍然排除不了,这种真歧义的判断需要查看更多的语境信息。研究表明,交叉型歧义约占整个分词歧义的85%【5】以上。处理好交叉型歧义字段在很大程度上能保证一定的分词精度,因此本文重点研究交叉型歧义的发现与消除。为方便描述,我们称词典包含的句子中所存在的组合方案为候选词条。例如句子S==“他说的确实在理"共有10个候选词条:他,说,的,的确,确,确实,实,实在,在,在理。其中,会引起交叉歧义的词条为“的确”、“确实"、“实在’’、“在理’’,这些词条都和别的词条存在交叉现象。例如,“的确"和“确实",“实在"和“在理”。其他的词条不存在交叉现象。4.2交叉型歧义的发现现在比较常用的交叉型歧义发现方法有:双向扫描法和逐词扫描法。(1)双向扫描法:对同一字段分别采用正向最大匹配和逆向最大匹配方法进行切分,如果两种方法所得结果不同,则认为存在歧义。例如S==“瑞星以技术和服务开拓网络安全市场”,正向最大匹配结果为“瑞\星\以\技术\和服\务\开拓\网络\安全\市场”;逆向最大匹配结果为“瑞\星\以\技术\和\服务\开拓\网络\安全\市场”。两者在“和服务’’处切分结果不同,故此处存在交叉型歧义。通过分析可知,采用这种方法可以检查出大多数的交叉型歧义字段;而采用逐词扫描法可以识别全部的交叉23 4歧义消除硕}:论文型歧义字段。(2)逐词扫描法:其基本过程大致如下:①从待分字串的起点取出不超过词典中最长词长的字串作为匹配字段:②在词典中查找该江配字段;③如果未找到该匹配字段,则去除匹配字段的最后一个汉字,将得到的新字串作为新的匹配字段,并转到步骤②。这个过程类似于减字正向最大匹配过程;④如果找到该匹配字段,则切分出一个词,设该词为CiCi+1⋯Ci。同时与之前最近的切分词cpCp+l⋯Cq做比较;⑤如果i<=q,则二者存在交集型歧义,根据作出交叉型歧义字段的标记,并转到⑧;⑥如果二者是组合型歧义,由于i0,则p(x,Y)>p(x)木P(Y),即X,Y是正相关的,并且随着I(x,J,)值的增大,相关程度也随之增大,如果I(x,Y)大于一个给定的阈值,这时可以认为xy是一个词;(2)若I(x,Y)≈O,则p(x,Y)≈p(x)木p(y),此时X,Y之间的结合关系不明确;(3)若I(x,Y)O时,字Y有与后继字z相连的趋势,(2)tx.:(y)20时,不反映任何趋势:(3)‘.:(J,)0,‘.:(y)<0,此时必有At(x:Y)>0。这表示X,Y之间相互吸引,那么在切分时就倾向于相连(即把xy当作属于同一个词处理)。因为统计量At(x:Y)=tw,,(x)一‘,:(y)是正值与负值之差,增大了距离,所以趋势比单独使用乙,,(x)或,,,(),)更显得突出。(2)若0。,(x)<0,‘。:(y)>0,此时必有At(x:Y)<0。这表示X,Y之间相互排斥,在切分时倾向于断开。(3)若乙,,(石)>0,‘,:(y)>0。表示y吸引X,同时W吸引Y,此时就产生了“竞争”:当At(x:),)>O,倾向于相连;当At(x:y)<0,倾向于断开。(4)若0.,(x)<0,‘,:(y)<0。表示x吸引Y,同时V吸引X,此时也产生了“竞争”:当At(x:),)>0,倾向于相连;当At(x:y)<0,倾向于断开。t测试差和双字耦合度这两个统计量都是用来计算字问位置连或者断的概率,不过双字耦合度是互邻的两个字符结合力的绝对度量,与上下文无关;而t测试差不但表示互邻的两个字符结合力的相对度量,还要考虑处理字对的前后各一个字符的影响关系。计算t测试差可以弥补双字耦合度的不足之处,比如图4.2中的例子,如果用t-沏lJ试差来计算的话,得到的计算值分别为:△,(对,比)=13.51,At(比,方)=一27.41,△,(方,法)=69.82,根据计算值可以得到的切分结果是“对Lk\方法”。但是在单独使用t一测试差来计算的时候,有时发生判断错误,比如如下实例:叼昂 硕十论文中文分词关键技术研究案发现场图4.3“案发现场”的歧义路径不意图如果使用t-钡lJ试差计算,那么各个计算值为:缸(案,发)一35.41,At(发,现)=55.07,At(现,场):54。根据这些计算值可以得到最后切分结果为“案\发现\场”。相反,双字耦合度的计算值为:Couple(案,发)=0.21,Couple(发,现)=0.99,Couple(现,场)=1.0,根据这些计算值可以得到最后切分结果为“案发\现场”。根据以上分析,我们尝试将这双字耦合度和t测试差这两个统计量结合起来,希望使用各自的优点,同时相互使用能够弥补各自的不足之处。4.3.2双字耦合度和t_测试差相结合的方法对任意相邻的有序字对xy,Couple(x:Y)反映了X,Y之间的静态结合能力,At(x:Y)则动态考虑了wxyz四个字的耦合影响。综上所述,双字耦合度和t-i贝1]试差各有特点,且具一定程度的互补性,把它们结合起来,可以形成更加合理的判断根据。由于计算Couple(x:Y),At(x:Y)时均离不开X,Y额联合出现次数——,.(z,Y),所以本质上这是一个关于汉字的一阶Markov模型,亦即关于汉字的二元语法模型。4.3.2.1N一元统计模型N一元文法统计模型【"1的基本思想是:一个词组的出现与其上下文环境中出现的词组序列紧密相关,第11个词组的出现只与前面n.1组个词相关,而与其他任何词组都不相关。假设WlW2⋯W。是长度为n的字串,则词Wi出现的似然度用方程表示为:尸(肜)=尸(彬%⋯呢)=尸(%)尸(%I彬)P(%l彬%)⋯P(形I%%⋯形一。)(4.9)=Ⅱ尸(彬I彬%⋯形一,)从公式4.9可知,要计算得到词组wi的出现概率,必须要知道在Wi之前所有词组的出现概率。即使这是可计算与操作的,但这种方法也是相当的繁琐。但是如果任意一个词组Wi的出现概率只与它前面相邻的一个词组有关,那么问题的解决就可以得到极大的简化。这时的文法模型叫做二元模型,也叫一阶Markov链,即:尸(∥)≈尸(彬)P(%I彬)尸(%I%)⋯尸(%J睨一,)一⋯.,⋯,、(4.10)=17.尸(形I形一。)29 4歧义消除硕一{:论文一般说来,N元文法模型就是假设当前词组的出现概率只与在它前面出现的紧邻的N.1个词组有关。这些概率参数值都可以通过大规模语料库的统计计算得来。比如当N=2时,统计二元概率的计算公式就为:唧㈣≈鬻㈣式(4.11)中count(⋯)表示一个特定词序列在整个语料库中出现的累计次数。4.3.2.2算法流程我们现在讲解交叉型歧义的消除过程。假设一个具有交叉型歧义的字串S为:al⋯aib]⋯bmCl⋯Cn(i>0,m>0,n>O),存在以下两种切分方案:SEGl:al⋯aibl⋯bmIc1.”cn1....................一USEG2:a1.。。aiIL.jbl⋯bmCl⋯CnI....................Jw11plw12w21p2w22图4.4实例的两种切分方案其中w11,w12,w21,w22均为实际存在的词组,pl,p2为可能的断点,分别对应bmCl与aibl之间的位置。对于词频法,容易做出以下判断:如果p(wl1)术p(w12)>p(w21)宰p(w22),则肯定SEGl,否则肯定SEG2。我们不妨换一个角度进行思考。歧义字串S有两个可能的断点pl和p2,即位置bmcl和aibl(在切分时,必定选择两个断点中的一个进行切分,但不会同时都进行切分),前者对应SEGl,后者对应SEG2。那么最终哪一个断点成立,可以认为是字串al⋯aibl⋯bmCl⋯c。(而不再是词w11,w12,w21,w22)共同作用的结果。因此,我们的注意力自然转移到Couple(bin:q),At(bin:q),Couple(a,:包),At(at:岛)上。由于在绝大多数情况下,有m<=2,i+n<=4,故这四个统计值的作用域基本覆盖了整个字串S。换而言之,可以认为交叉型歧义字串S的排歧是将上述四个统计值作为参数的函数,那么可以进行计算各歧义位置的CDT(CoupleandDifferenceofT—test)值,来判断选择如何切分。CDT(S)=F(Couple(bm:q),At(b.:q),Couple(a,:b1),At(a,:61))(4.12)文献[19]提出了一种将互信息和t一测试差相结合的方法。本文也采用同样的线性迭加法,只是我们将互信息替换为双字耦合。因为双字耦合度和t一测试差的取值范围相差较大,前者取值范围为O一1,后者取值范围为.834.5—753.4,这些统计值都是根据大规模浯料库的训练所得。所以在进行线性迭加之前先要进行归一化处理。30 硕上论文中文分词关键技术研究Co印彪‘(x,y):—Couple(x,—y)-1.tco,,p(4.13)oc岬△f+(x,J,):—At(x,y—)-儿(4.14)6Ⅺ公式中的段却和%印是双字耦合度的均值和均方差,地和吒是t一测试差的均值和均方差,这四个值都是根据大规模语料库的训练统计得到的。然后通过下式将二者叠加起来:CDT(x,y)=Couple’(x,J,)+五乖At’(x,Y)(4.15)在式(4.15)中,五的值经过实验比较,发现取五=O.07时测试得到的切分准确率最高。在确定相关统计量的计算方法以后,可以概括得知本文的交叉型歧义的消除算法步骤如下:(1)在二元切分词图中,找出句子中所有的交叉型歧义的位置。(2)计算各交叉型歧义位置的CDT值。(3)按CDT计算值的大d,Jll页序依次判断歧义位置的切分与否。值越大,结合强度越高,两者越可能结合为一个词组。并且,两个歧义位置在其中一个歧义位置确定之后,与该位置相关的其它歧义位置就不必再进行判断,可以直接选择是切分还是连接了。从上文分析可知,支持本算法的一个重要资源就是任意两个相邻词组的互邻同现概率矩阵,由于矩阵中的零单元会导致计算除法是分母为零的运算失败,因此需要进行数据平滑处理:令‘是实际统计所得的次数,‘+是经平滑调整后的次数,则:ri":掣(4.16)N+s、。其中N为进行大规模训练师语料库中的总字数,那么N=y,:,S为汉字集合的个数。平滑后满足:91∑‘‘/Ⅳ一1,即∑p—l(4.17)公式4.17的证明如下: 4岐义洧障颐+论文∑F/N=1‘/_Ⅳ+iIN++‘/_v:生±翌:丝+选±兰2:翌+!尘±12:盟(Ⅳ+印‘N(Ⅳ+s)+N(Ⅳ+s)+.Ⅳ:g±垒±=±生2:坐!苎:生(Ⅳ+研+ⅣN’N+s’N(_Ⅳ+S)+N一14.3.3实验与分析现在取十段包含交叉型歧义的文本,使用本文的方法,对其进行切分,运行结果如下所示。厂“9’’‘’+’‘”“。”5”46。8”。11”8’“4。”’457“。‘’485“88。?图4.5实例的运行结果图将实例存在的歧义,以及本文的切分结果列张表如下所示。 硕上论文中文分词关键技术研究表4.1测试实例待切文本两种切分本文切分结果技术和服务技术\和\服务技术\和服\务技术\和\服务今天下午今天\下午今{天FI午今天\下午国家规定国家\规定国\家规\定国家\规定等同志等\同志等同\志等\同志情不白禁地情不白禁\地情\不\自\禁地情不自禁\地加强调杏研究加强\调奄研究加\强调\查\研究加强\调查\研究以及其他以及\其他以\及其\他以及\其他提高产品质量提高\产品\质量提\高产\品质\量提高\产品\质量不合理不\合理不合\理不\合理市场经济体制市场经济\体制市场\经济体制市场经济\体制从表中的对比可以看出,除了对文本“加强调查研究"的切分存在瑕疵,该瑕疵也不属于没有消除交叉型歧义的范畴。除此以外,本文使用的方法可以有效消除切分字段中的交叉型歧义。本章小结由于本文使用统计与词典相结合的方法,在此过程中会找出所有候选词条,此过程能有效消除大部分的组合型歧义,因此本章重点介绍了交叉型歧义的检测与消除。首先根据二元切分词图中候选词条的排列规律,检测出交叉型歧义产生的位置;然后计算各歧义位置的双字耦合度和t一测试差的线性叠加值CDT,根据CDT的大小判断是否切分。实验结果表明,该歧义消除方法,能有效处理大部分的交叉型歧义字段,准确率要比使用互信息和t一测试差相结合的方法更高。 5算法的实现实验硕f:论文5算法的实现与实验本章分为两个部分,第一部分介绍分词算法的流程,包括理论基础及方法实现;第二部分进行实验,并进行分析;最后对本章进行小结。图5.1分词算法流程框架从图5.1可以看出,我们首先将待切分文本进行原子切分,切分成单个原子;其次找出所有候选词条,生成二元切分词图;然后在二元图词典中找出相邻词组之间的边长,把二元切分词图表示成带权有向无环图;最后求解图中始末结点间最短路径,该路径即为切分结果。下面简单介绍各个步骤及相关操作。5.1算法的实现下面将对算法流程中的原子切分、如何找出所有候选词条和最短路求解三个部分进行重点介绍。5.1.1原子切分在进行原子切分之前,首先要进行断旬处理。所谓断句,就是根据分隔符、换行符等语句的分隔标志,把待切字串分隔成多个稍微简单一点的短句,再进行分词处理,最后再把各个分词结果组合起来,形成最终的分词结果。分成短句之后,即可进行原子切分。所谓原子,是指该短句中不可分割的最小语素单位,例如:一个汉字、短句前后的开始结束标识字段、全角标点符号、连在一起的数字字母单字节字符等。举例说明,例如在字串“2009年三星S-208型号的手机价格是l元钱"中,2009,S-208、l都是一个原子,其它的每一个汉字也是一个原 硕士论文中文分词关键技术研究子。经过原子切分后,源字符串成了一个个独立的最小语素单位。我们以待切字串S==“他说的确实在理"为例,将其切分成原子序列的结果为:“他,说,的,确,实,在,理’’。5.1.2候选词条原子切分之后的工作就是把原子之间所有可能的组合,即所有候选词条都找出来。可以用两个循环实现:第一个循环遍历整个原子序列;第二个循环是当找到一个原子后,不断把后面相邻的原子和该原子组合到一起,访问核心词典看它能否构成一个有意义有词组,直至词典中不存在该组合。一个原子序列:S(n)(O<=n=1为字串的长度。进行如下操作:(1)对应每个汉字字符,根据其所表示的汉字字符在字符序列中的位置,建立一个结点数为m+l的有向无环图G,各结点编号分别为:Vo,V1,V2⋯Vm。(2)从每个结点i开始,循环一遍。若W==CiCi+I⋯Ci是一个词,把W加入到切分列表中,即在G中添加边;记录该词组所有的信息,包括标出边的权值Lpj;跳出此次匹配,进入下一个循环。词的集合组成一个全序关系。clC2c-lCic^lCmLIL2Lw图5.2切分的带权有向无环图实例S==“他说的确实在理”构成的有向无环图如下所示。的实lLm图5.3实例的切分有向无环图5.1.3最短路径算法本算法的最短路径思想来自于K一最短路径算法,K一最短路径就是前K条最短路径。此算法己大量使用于计算机网络路由【201、交通管理【2¨及统计分词㈤等应用中。在本中文分词算法中使用一种优化的Dijkstra算法【lll'1231来求最短路径。Dijkstra算法求解的是有向图中起点到其他所有结点的最短路径【9l,而在切分带权有向图的应用中,与其有二个本质区别:首先有向边的源点编号均小于终点编号,即所有的有向边方向一致:其次,我们求的是带权有向无环图始末结点之间的最短路径,而且在算法实现时为了提高切分速度,只求解始术两个结点之问的第一条最短路径。但是找出最36 硕士论文中文分词关键技术研究短路径,在初始时刻并不知道路径的经过结点,还是要记录几种情况,最后对各条路径的长度进行排序,选择出其中的最短的一条路径,因此下文将介绍K一最短路径的算法的基本思想及实现。5⋯131基本思想所NK-最短路径,其实就是最短路径和最长路径的折中,就是找出从起点到达终点所经过的路径,保留前K条最优路径。其求解过程为:将待切分字串进行原子切分,找出原子之间所有可能的候选词条后,构造切分的有向无环图。每个候选词条对应有向图中的一个结点,相邻词条对应图中的一条有向边,并赋予相应的边长(权值)。然后针对该切分带权有向无环图,在起点到终点的所有路径中,求出长度值按严格升序的依次为第1,第2,⋯,第i,⋯,第K条路径集合作为相应切分结果集。5.1.3.2模型描述设S==ClC2⋯C。为待切字串,其中Ci(i=l,2,⋯n)为单个的汉字字符(即原予),n>=1为字串的长度。对应每个汉字字符,建立一个节点,所有节点组成一个集合。对该集合进行如下操作:(1)对应每个汉字字符,根据其所表示的汉字字符在字符序列中的位置,建立一个结点数为n+l的带权有向无环图G,并对各个结点分别进行编号为:Vo,Vl,V2⋯Vm。(2)从每个结点i开始,循环一遍。若W=Cifi十l⋯ci是一个词,把W加入到切分列表中,即在G中添加边;记录该词组所有的信息,比如标出边的权值Lk;然后继续匹配W’==fiGi+i⋯CjCj+l是否为词,若为词,则在G中继续添加边、记录信息,然后再在末尾添加一个原子,再进行匹配,如此往复;若不为词则跳出此次循环,i++,进入下一个循环。词的集合组成一个全序关系,如下所示。C1C2Ci.ICiCj+lCmLlL2/—、\飞‰/)、、.—/1LmLw图5.4切分带权有向无环图5.1.3.3K一路径求解5.1.3.3.1链表——有向无环图的表示所谓稀疏矩阵【ll】,即若在矩阵ANN中有S个非零元素,令万=t/(N*N),称万为矩阵的稀疏因子,通常认为万<=0.05是称为稀疏矩阵。对于非稀疏矩阵往往使用N*N的数组来表示N个结点之间的连接关系。而对于稀疏矩阵来说,N*N的数组无疑会37 5算法的实现实验硕十论文浪费大量的空间,于是采取压缩存储,只存储稀疏矩阵中的非零元,记录邻接两点的边的方式来记录稀疏矩阵。因此本文使用一个有序的链表,用来表示稀疏矩阵的邻接表,链表中的结点与稀疏矩阵中的非零元一一对应。为了表达得更明白些,我们不妨看下面这张图:图5.5按Index值升序排列的有序链表图5.5显示的是一个按照Index值进行了升序排序的链表,当插入新结点时必须确保Index值的有序性。只是本文所用到链表的排序规则不是Index,而是row和col两个参数,如下图所示:ll2I3lI2222:l图5.6col优先排序的有序链表从图5.6可以看出,这个有序链表的排序规则是先按col值升序排序,若col值相同的按照row值升序排序。当然排序规则是可以改变的,同样也可以先按row值排序,再按col值排序,此处不再赘述。以S==“他说的确实在理”为例。其候选词条的邻接表如下所示: 硕上论文中文分词关键技术研究gow:OI‰晴:ll托啊:2I女滞:3I‘ow:3Col:I———_◆Col:2———_◆踟I:3———_Col:4——_踟j:5sllord-掰i臀#蟛ist[ord:他,,dlord:髓sWord:的.,cliord·∞确上kow:4l艇埔:4I≈晡:5Roq:5黼:6CoI:5—————’Col:6———_‰I:6—————’份I:7——●CoI:1sWord:确s|ord:确蛮sword:凌sword:凌在sword:露上TR∞:6Kow'-7Row:8CoI:8————一’Col:8—————■Col:9渤rd:在理silord:理sWord:宋鞠糸图5.7实例的链表存储结构5.1.3.3.2链表的二维图表表示如果根据图5.7所示的链表中row和col的坐标信息将链表元素放到一个二维表中的话,我们就得到了一张如下的二维图:l23456T日9始椭他说的的确确确实实实在在在理理末燃图5.8实例的二维表不图5.8的二维表显示初次切分后的候选词条中所有词组,第一个字相同的在同一行,最后一个字相同的在同-N,原来的原子在对称轴上。并且行和列有一个非常有意思的关系:列值col::n的所有词组需要和行值ro、V==n的所有词组计算两者的距离。例如“的确’’这个词,它的c01::5,而row=:5的词有两个,分别为“实”和“实在"。所以和“的确”需要计算距离的词有两个:“实"、“实在”。5.1.3.3.3相邻词条之间的边长390l2345B78 5算法的实现实验硕士论文求解K一最短路径,首先要找出相邻词条之间的出现频率,相邻词条之间的频率是一个统计值,可以到二元图词典中进行查找得到。然后使用公式进行平滑计算距离,伪代码如下。pCur=GetHeadO;//首先获得指向链表的头结点while(plCur!=NULL)//循环直到链尾sWord);//找到下一个以pCur.>col开头的词条GetElement(pCur一>col,-l,pCur,&pNextWords);while(pNextWords&&pNextWords-->row--=pCur·->c01){//先连接词条,再查找同现频率,比如的确@实在strcpy(sTwoWords,pCur一>sWord);//sTwoWords=的确strcat(sTwoWords,WORD_SEGMENTER);//sTwoWords=的确@strcat(sTwoWords,pNextWords->sWord);//sTwoWords=的确@实在//在词典中查找相邻词条的频率nTwoWordsFreq=GetFrequency(sTwoWords);//平滑处理的计算dTemp2(double)1/MAX_FREQUENCE;dValue2-log(dSmoothingPara木(1+dCurFreqency)/(MAX_FREQUENCE+80000)+(1一dSmoothingPara)奉((1-dTemp)木nTwoWordsFreq/(1+dCurFreqency)+dTemp));pNextWords=pNextWords一>next;//指向下一个词)pCur=pCur->next;)因此,如果将图5.8中所有相关的行与列元素之间的关系(边长)找到,通过二元分词图表示出了每个词组之间的边长。二元切分词图中每一个元素表示稀疏图的一条边,它的行值代表边的起点(前驱),它的列值代表边的终点(后继)。以S==“他说的确实在理"为例,在添加了边长信息之后所形成的二元分词图如下图所示。 硕十论文中文分词关键技术研究023SBT日口1011l23t55T8g10ll12384始黼B世2lT他@说4lB9D3说@的说@的确59859T的@确的卸甬实13.261326的确@实的确@实在13291329确@实确@实在127312T3确实日在确实@在理13161318实@在实@在理13.09实在@理T.49在日理14.45在理@末槲束3.4T理@末抖束图5.9初次分词后添加边长后的二元分词图表的二维表示形式在求解K一最短路径前,我们将图5.9换一个角度观察,其可以等价为一张带权有向无环图,如下图所示:图5.10实例的带权有向图表示41 5算法的实现实验硕十论文从图5.10可以看出“的@确实”的距离为5.97,而“的确@实"间的距离为13.26,这说明“的@确实”组合的可能性要大一些。但这只不过是一面之词,究竟如何组词还需要放到上下文的语境中进行通盘考虑,以达到整体最优。按照Dijkstra算法的表示方法把二元分词图表转化成图5.10的表示形式,就能比较清楚地看出,求解的过程实际就是找到从起点Vo到终点V12的前K条最短路径。这样一来,求最优分词方案就成了求整体最短路径。5.1.3.3.4统计方法的缺陷由于是统计资料,语料库中的统计值对切分结果是有一定影响的。以S==“他说的确实在理”为例,求2一最短路径,结果如下:路径(1):O一>卜>2->3->6->9->11->12->13;始##始\他\说\的\确实\在\理\末##末。路径(2):O一>卜>2->3->6->10->12->13;始##始\他\说\的\确实\在理\末##末。可以计算出路径(1)的长度为39.85,路径(2)的长度为43.34。虽然在求解卜最短路径的过程中,切分结果以路径(1)为最优路径,因为路径(1)的长度小于路径(2)的长度,但根据语感知识,实际上路径(2)的切分结果更为准确。造成这一结果的原因是二元图词典中的边长的属性值是一个统计值,存在误差。5.1.3.3.5最短路径求解以S==“他说的确实在理",求解3一最短路径为例。根据上文所介绍的步骤,我们首先进行原子切分;其次根据核心词典,找出待切字段中包含的所有候选词条;然后添加边长构造待切字段的切分的带权有向无环图。为了简化计算模型,本文将此带权有向无环图的有向边的边长设置为1,即假定所有候选词条都是对等的【19】。然后在从起点到终点的所有路径中,求解出最短路径。每个结点维护一张表,用来记录前K个最短路径,并记录相应路径上当前结点的相关信息。如果同一长度对应多条路径,那么结点的表必须把所有路径信息全部记录下来,最后通过回朔即可求出前K条最短路径。实例S==“他说的确实在理"的3一最短路径的求解过程如下图所示:42 硕J:论文中文分词关键技术研究的确实在Table(4)路徭长废前驱编号l3(2,1)24(3,1),●I(2,1)l·r’,,,。’I.一.一一·一一.一·.一·.·-·..一】一..·..一一一.一·-一一.-一..1-一.一一.一_11table{5)Table(6)Table(7)il●路行长度前驱编号14(4,1)25(4,2)(5,1)36(5,2)图5.1l实例的有向无环图及Table(Vi)的内容路徭长度淞编罟l5(5,1)(6,1)26(5,2)(6,2)37(6,3)每个结点的K一最短路径长度都由它的所有前驱的K一最短路径长度加1构成,由于实例中K=3,即取长度最短的前3条路径,把其他路径排除。各个结点的前3一最短路径如下:结点1:路径l“他”(前驱Vo);结点2:路径1“他\说”(前驱Vl,及Vl的路径1);结点3:路径1“他\说\的"(前驱V2,及V2路径1);结点4:路径1“他\说\的确’’(前驱V2,及V2的路径1)、路径2“他\说\的\确”(前驱V3,及V3的路径1);结点5:路径l“他\说\的确\实"(前驱V3,及V3的路径1)和“他\说\的\确实”(前驱V4,及V4的路径1)、路径2“他\说\的\确\实”(前驱V4,及V4的路径2);图5.12中结点Vi的表Table(i)中各属性代表的含义说明如下:43审囱 5算法的实现实验硕十论文路径编号:从起点到结点Vi的各条路径,长度相同的路径其编号相同,所以同一编号的路径可能有多条,同一个fj{『驱在表中也可能出现多次,只是每次词结点的路径编号又各异;长度:对应路径的长度,即路径所经过的各条边的边长之和,表按路径长度的升序排列;前驱:前驱中包含两个参数,第一个参数表示结点Vi的该条路径的前驱结点,由于前驱结点可能含有多条路径,所以第二个参数表示此前驱结点经过它自己的何条路径来到达此结点,形成新的路径的。例如Table(7)的第一行元素值(1,5,(5,1)))和(1,5,(6,1))。在(1,5,(5,1))中:1表示结点V,的第一条路径,5说明其路径长度为5,(5,1)表示此路径的前驱为结点V5,V5的先前路径为Table(5)中的第一条路径,如上图5.3中的虚线框处所示。上图中的虚线是回朔出的第一条路径,此处由于Table(5)中(3,1)在(4,1)前面,故图中选择了(3,1)路线。当回朔到fj{f驱为(0,0)时,表示本次结束。图中对应的分词结果是“他\说\的\确实\在理"。5.2实验和分析本系统的实验都是在CPU2.0G,内存256MB的硬件环境下进行测试的,根据测试结果,统计计算出切分准确率、切分召回率、切分速度。其中召回率和准确率的计算公式参考本文的章节——“2.3中文分词的评测标准”,对于切分速度,本文使用单位字符/秒。经过小范围的测试,该算法的切分召回率达到97.2%,切分准确率达到93.7%,切分速度达到约35000字/秒。现在举两个例子进行说明,给出了实验的运行结果,并对结果进行分析。(1)实例1是切分S==“他说的确实在理”的3一最短路径,切分运行结果如下: 顶±论立中文分词关键技术研究酽Fm口i豳弛m∞M#ⅡⅡ‘IlI。r一匡蚕i二国营&·处理用时l『——一时隧;徽i8漂羹愁汴图512实例的3一最短踌径切分结果测试给出实例的3一最短路径,结果是按照路径长度的升序排列。由上文可知其中的路径(1)的长度为39.85,路径(2)的长度为4334。虽然切分结果显示路径(1)为最优路径,因为路径(1)的长度小于路径(2)的长度,但根据语感知识,实际上路径(2)的切分结果更为准确。造成这一结果的原因是二元圉词典中的词组之间的边长是一个统计值,不可避免存在误差。(2)实例2是选择网络中《教育部要求全国学校实施晨检应对流感疫情》一文进行测试,为了节省运行时间和空间,只选取第一条最短路径,即令K_1。原文内容如下:中新网5月15日电中国内地己确诊2例输入性甲型HINI流感病例,教育部13前发出通知,要求各级教育部门和各级各类学校进一步落实甲型H1N1流感防控措施,全面实施晨检,保障师生的身体健康安全,确保中考、高考工作顺利进行。通知要求各地各校要高度重视,加强领导。要高度重视甲型H1N1流感防控工作,按照“高度重视、积极应对、联防联控、依法科学处置”的防控原则,在当地党委、政府统一领导和卫生部门的具体指导下.切实加强学校防控甲型HlNl流感工作领导,进一步完善本地本校甲型HINl流感防控工作预案,特别是中考、高考期间的防控应对措施。要切实按照教育部、卫生部通知要求.确保各项防控措施落实到位。45 5算法的宴现实验预±论文通知指出,要进一步加强宣传教育。要进一步加大甲型HINI流感可防、可控、可治的宣传力度,要把甲型HINI流感防控知识作为当前一个时期学校宣传教育重点,通过形式多样、形象生动的宣传形式普及科学防控知识,特别是还没有开展相关教育的,要立即面向全体师生宣传甲型HINI流感防控知识,进行正确舆论引导。要教育并督促学生保持良好个人卫生习惯。通知指出,要加强与当地卫生部门联系。要密切与卫生部门的联系,及时了解本地甲型HINI流感防控信息和防控要求,并按照要求及时调整防控措麓,形成各级各部门系统联动,群肪群控的有效应对的工作格局。通知强调,要加强疫情监测。要全面实旄晨检,对缺勤的师生员工逐一进行登记,并查明缺勤的原因,发现流感样疫情要在2小时内报告当地疾控机构和教育部门。加强对寄宿制学校特别是农村寄宿制中小学校防控工作的指导,制定并落实防拉措施和工作制度。对患有流感样症状的师生要劝其及时就医,并遵照医嘱进行医学观察。切分的运行结果为;酋十!¨口葚囵《羹鬻瀚憨壤麓黧辫鳖戮搿嬲籍穗瓣《麟黼黧嚣嚣辫黼蕤烈黼溉酾黼糍雅萤黔‘!十、#、月、5月、15日、卑、十目、内≈!马、砘钳2蜊、搏^、性、■、2、HlNl、渐、■倒、.、弼矾日■、x&、^瀚麟黼黼麟蠢9口t、#旌、。、l、口女、搜目、戢青、部、、、Ⅲ±$、j目、i$、.、n*、§日、∞、#、m#、#女垤I垃、.、圈5.13网络文本的切分结果中\新\网\5月\15日\电\中国\内地\已\确诊\2\例\输入\性\甲\型\HINI\流感\病例\,\教育部、日前\发出\通知\,\要求\各级\教育\部门\和\各级\各类\学校\进一步\落实\甲\型\H1NI\流感\防\控\措施\,\全面\实施\晨、检、,\保障\师生\46 硕士论文中文分词关键技术研究的\身体\健康\安全\,\确保\中考\、\高考\工作\J|顷利\进行\。\通知\要求\各地\各\校\要\高度\重视\,\all强\领导\。\要\高度\重视\甲\型\H1Nl\流感\防\控\工作\,\按照\”\高度\重视\、\积极\应\对\、\联防\联控\、\依法\科学\处置\”\的\防\控\原则\,\在\当地\党委\、\政府\统一\领导\和\卫生\部门\的\具体\指导\下\,\切实\all强\学校\防\控\甲\型\H1Nl\流感\工作\领导\,\进一步\完善\本地\本校\甲\型\HlNl\流感\防\控\工作\预案\,\特别\是\中考\、\高考\期间\的\防\控\应\对\措施\。\要\切实\按照\教育\部\、\卫生部\通知\要求\,\确保\各项\防\控\措施\落实\到位\。\通知\指出\,\要\进一步\all强\宣传\教育\。\要\进一步\Dn大\甲\型\H1Nl\流感\可\防\、\可\控\、\可\治\的\宣传\力度\,\要\把\甲\型\H1N1\流感\防\控\知识\作为\当前\一个\时期\学校\宣传\教育\重点\,\通过\形式\多样\、\形象\生动\的\宣传\形式\普及\科学\防\控\知识\,\特别\是\还\没有\开展\相关\教育\的\,\要\立即\面向\全体\师生\宣传\甲\型\H1Nl\流感\防\控\知识\,\进行\正确\舆论\引导\。\要\教育\并\督促\学生\保持\良好\个人\卫生\习惯\。\。.通知\指出\,\要\Dn强\与\当地\卫生\部门\联系\。\要\密切\与\卫生\部门\的\联系\,\及时\了解\本地\甲\型\H1N1\流感\防\控\信息\和\防\控\要求\,\并\按照\要求\及时\调整\防\控\措施\,\形成\各级\各\部门\系统\联动\,\群\防\群\控\的\有效\应\对\的\工作\格局\。\通知\强调\,\要\Dn强\疫情\监测\。\要\全面\实施\晨\检\,\对\缺勤\的\师生员工\逐一\进行\登记\,\并\查明\缺勤\的\原因\,\发现\流感\样\疫情\要\在\2小时\内\报告\当地\疾\控\机构\和\教育\部门\。\Dn强\对\寄宿\制\学校\特别\是\农村\寄宿\制\中小学校\防\控\工作\的\指导\,\制定\并\落实\防\控\措施\和\工作\制度\。\对\患\有\流感\样\症状\的\师生\要\劝\其\及时\就医\,\并\遵照\医嘱\进行\医学\观察\。\我们在进行评测时,允许输出结果具有一定的柔性【21,例如,“2”是一个数词,“例”是一个单位量词,那么也认为“2\例”的切分结果是正确的,虽然“2例”合在一起表示一个数量词更加确切些。经过统计,实例2的测试结果为:答案中的总词数为345,切分出的词语总数为379,正确切分的词数为334。计算出切分召回率96.8%,切分准确率88.1%。对上文701个字符的切分用时20ms,切分速度达到35000字/秒。对实例2的切分,未登录词“甲型H1N1流感”出现对切分准确率影响很大,如果我们只统计一次“甲型H1N1流感”,那么切分准确率将提高到94.1%。由于本算法使用的核心词典所包含词组有限,而且算法也没有进行专业词典的切分,因此该分词算法对不同领域的敏感性较强。比如自然科学、经济、艺术及其他47 5算法的实现实验硕一L论文特定领域包含较多专有名词,那么本算法对这些文本的切分召回率和准确率就没有普通文本高。因此,对上面文本中的“中新网”、“甲型H1N1流感"等专有名词的切分是错误的。不像地名的数目有限且不易变化,人名具有一定的规律性,其他专有名词的数量庞大,而且几乎每天网络中都会出现很多新的专有名词,这也是不同的上层应用会首先使用不同的专业词典进行粗分、然后再用核心词典进行切分的原因。本章小结本算法是使用词典与统计相结合的方法进行中文分词,首先在核心词典中进行机械查找,找出所有候选词条;再从二元图词典中找出候选词条中相邻词组的边长;最后将所有候选词条及其相关信息转换成带权有向无环图,计算图中始末结点间的最短路径来达到最优分词。 硕士论文中文分词关键技术研究6总结与展望6.1本文总结(1)本文的分词系统使用词典与统计相结合的方法。词典采用前两字逐个Hash索引、剩余字串有序排列的结构,查询过程首先进行Hash查找,然后进行二分查找,在不提升已有典型词典机制维护复杂度的情况下,提高了中文分词的速度,是一种较简洁、高效的词典组织机制。(2)在歧义消除方面,本文提出了一种交叉型歧义发现方法:根据二元切分词图的排列规律,若原子的上方和右侧都存在词组,则此处存在交叉型歧义。然后计算歧义位置的CDT值,来判断是如何切分,从而消除歧义。实验表明,我们实现的分词算法是简单有效的,运行时间和运行性能两个方面都能满足一般上层应用的要求。6.2未来工作本文采用到的相邻词组间的边长、分词算法中使用到的几个阈值和参数都涉及到各种概率统计信息,都是根据一般的语料库和已知实验的结果来确定的,经验性比较强。我们希望在接下来的工作中,能利用机器学习的方法进行一些参数选择的实验,争取得到更加合理的参数值,使准确率和召回率有进一步的提高。另外,我们的分词算法还没有解决消除组合型歧义、识别未登录词等问题。本文认为未登录词中的地名、常用人名(比如伟人名)以及其他专有名词可以采用统计的方法,即使用一个专业词典。但更一般的人名识别,使用规则的方法应该更加合理。如果上层应用为语法分析系统,那么分词算法应该具有词性标注的功能。虽然只需要在分词词典中添加一个词性的属性,那么在查找每个词组时,就很容易同时找到这个词的词性。但是有些词组在不同的语境中词性是不同的,要准确标出词性还需要进一步的研究与工作。49 致谢硕士论文致谢时光飞逝,两年研究生的学习和生活即将画上一个句号。在这里我首先要深深地感谢我的指导老师刘凤玉教授,在这两年来的学习和生活中,刘老师给予我细致的关怀和悉心的指导,刘老师为人之友善、知识之渊博、治学之严谨,使我受益匪浅,并为我努力学习的榜样。这两年来,我在学习和科研上所获得的每一点进步和成果无不包含着她的心血。借此机会,我向刘老师表达我最深切的感谢和最诚挚的敬意。此外,还有张宏老师和严悍老师在学习上给我无私帮助和认真指导,在此,我深深表达我的感谢和敬意。我还要感谢几年来在一起朝夕相处的同学,感谢他们所给予我热情帮助和快乐友谊。特别是任雨同学和李陟师兄在平时学习和毕业设计的过程中给予我的帮助和支持,使我顺利完成毕业论文。在此我还要特别感谢我的家人和朋友,是他们的无私的支持和鼓励,使我在两年的学习和生活罩能够专心致志,不为学费而烦恼,顺利完成学业。最后,我衷心祝福他们在未来的日子里健康、快乐。 硕上论文中文分词关键技术研究参考文献朱德熙.语法讲义.北京:商务印书馆,1982黄昌宁,赵海.中文分词十年回顾.中文信息学报.2007,2l(3):8~19http://www.caopeng.org/bbs/thread-11140一l—1.htmlhttp://www.hackvip.corn/wen/sort0227/sort0276/Hackvip_33078.html陈小荷.现代汉语自动分析.北京:北京语言文化大学出版社,1999卢亮,张博文.搜索引擎原理、实践与应用.第1版.北京:电子工业出版社,2007http://www.hackvip.corn/wen/sort0227/sort0276/Hackvip_330783.htmlhttp://www.hackvip.com/wen/sort0227/sort0276/Hackvip_330784.htmlhttp://www.chinawiss.com/docs/docs/13/1193.htmlhap:Hi.ca.yahoo.com/skyerhit/blog/p_8/严蔚敏,吴伟明.数据结构(C语言版).北京:清华大学出版社,2004孙茂松,左正平,黄昌宁.汉语自动分词词典机制的实验研究.中文信息学报.2000,14(1):1~6陈桂林,王永成,韩客松,王刚.一种改进的快速分词算法.计算机研究与发展.2000,37(4):418-424李振星,徐泽平,唐卫清,唐荣锡.全二分最大匹配快速分词算法.计算机工程与应用.2002,38(111:106~109李庆虎,陈玉健,孙家广.一种中文分词词典新机制——双字哈希机制.中文信息学报.2003,17(4):13~18张培颖,李村舍.一种中文分词词典新机制——四字哈希机制.微型电脑应用.2006,22(10):35-36,55朱小娟,陈特放.词频统计中文分词技术的研究.仪器仪表用户.2007,14(3):78-79王思力,王斌.基于双字耦合度的中文分词交叉歧义处理方法.中文信息学报.2006,2l(5):14-17,30孙茂松,黄昌宁,郭嘉彦,陆方,沈达阳.利用汉字二元语法关系解决汉语自动分词中的交集型歧义.计算机研究与发展.1997,34(5):332~339杨云,徐佳,李千目,刘凤玉.基于Dijkstra策略的QoS路由多目标算法.小型微型计算机系统.2004,25(09):1660.1664潘福全,陆健,王丰元,项乔君.考虑禁行路线路网的最优路径求解.交通与计算机.2006,243):5-81J1J1J1J1J1J1J1●-1j1J1J1jU刁习卅卵q刀列叨m¨眨BM”M"体侈加扒rILr●Lr●Lr●Lr●Lr●Lr●Lr●Lr●Lr●Lr●Lr●Lr●Lr●Lr●Lr●Lr●Lr●Lr●Ln●0I=L 参考文献硕士论文【22】张华平,刘群.基于N一最短路径方法的中文粗分模型.中文信息学报.2002,16(5):1-7【23]候识忠.数据结构算法:VisualC++6.0程序集.第l版.北京:水利水电出版社,2005【24】贺敏,龚才春,张华平,程学旗.一种基于大规模语料的新词识别方法.计算机工程与应用.2007,43(21):157~159[25】http://blog.minidx.com/2008/0I/04/352.html【26】翟伟斌,周振柳,蒋卓明,许榕生.汉语分词词典设计.计算机工程与应用.2007,43(1):1~2,26[27】张科.多次Hash快速分词算法.计算机工程与设计.2007,7(28):1716~1718【28】高文利,李德华.分词索引树的构建.语言研究.2007,27(4):103~105[29】郑家恒,张剑锋,谭红叶.中文分词中歧义切分处理策略.山西大学学报.2007,30(2):163-167【30】罗智勇,宋柔.现代汉语通用分词系统中歧义切分的实用技术.计算机研究与发展.2006,43(6):1122-1128【3l】孙茂松,邹嘉彦.高频最大交集型歧义切分字段在汉语自动分词中的作用.中文信息学报.1999,13(1):27~37[32】瞿凤文,赫枫龄,左万利.字典与统计相结合的中文分词方法.小型微型计算机系统.2006,27(9):1766~1771【33】郑德权,于凤,王开涛,赵铁军.基于汉语二字应成词的歧义字段切分方法.计算机工程与应用.2002,39(1):17~18,26【34】刘群,张华平,俞鸿魁,程学旗.基于层叠隐马模型的汉语词法分析.计算机研究与发展.2004,41(8):1421~1429【35】王思力,张华平,王斌.双数组Tile树算法优化及其应用研究.中文信息学报.2006,20(5):24-30[36】http://www.hackvip.com/wen/sort0227/sort0276/Hackvip_33078.html[37】罗桂琼,费洪晓,戴弋.基于反序词典的中文分词技术研究.计算机技术与发展.2008,18(1):80-8352 中文分词关键技术研究 作者: 曹卫峰 学位授予单位: 南京理工大学 相似文献(10条) 1.会议论文 嘎日迪 起步奋斗的二十年庆祝中国中文信息学会民族语言文字信息专业委员会成立20周年暨第十届民 族语言文字信息处理研讨会召开 本文主要介绍了我们民族语言文字信息专业委员会成立时的背景、过程;全国少数民族语言文字信息处理学术讨论会的基本情况;少数民族语言文字 信息处理专业委员会成立后给中央政府的有关部门提出的建议以及专业委员会挂靠单位的变动等内容. 2.期刊论文 朱靖波.姚天顺 中文信息自动抽取 -东北大学学报(自然科学版)1998,19(1) 论述了信息抽取与信息检索的区别,信息抽取与深入的自然语言处理的区别,中文信息目动抽取的目的、任务和基本模型;然后介绍了一些国外的IE系 统;讨论了关于中文信息自动抽取的一些问题和正在开展的中文信息抽取研究工作. 3.会议论文 徐谈林.任大任.李学金 中文信息的AP语言处理法 1985 该文提出中文信息的AP处理方法,着力于实现一个计算机中文信息系统,用以对汉字进行分类与处理,实现用计算机直接来对汉字的情报进行收集 、整理、分类和传输。中文信息的文字传递主要是依靠汉字作为信息的媒体。该文还列出AP语言中文信息处理系统简图,并对汉字分类处理的实现加以 说明。(刘佳摘) 4.学位论文 丘志文 基于认知机理的汉字智能造字之汉字基元研究 2008 现有的中文信息处理系统都采用字库,基于字库的中文处理平台虽然为我国的中文信息化做出了不可磨灭的贡献,但由于其不是造字而是选字的特点 而带有许多不足:不能建立长期稳定的信息化标准、不能很好地传承汉字文化、不符合汉字认知机理、与汉字教育脱节、信息熵高等。本文在对汉字的 认知机理进行分析研究的基础上,将汉字文化和认知科学的成果相结合,对汉字智能造字的基础-汉字基元进行了深入的研究和探讨。主要研究内容和结果 如下: (1)在对汉字字库相关中文信息处理流程进行深入分析和述评的基础上,在认知心理学原型理论的指导下,深入研究了人对汉字的认知机理,并将这种 认知机理应用于计算机,在计算机进行汉字智能造字的实现原理方面进行了理论分析和实验研究。 (2)本文着重研究作为造字基石的汉字基元。深入分析了与汉字基元相关的研究,得出汉字部首和汉字部件可作为汉字基元的主要来源但不能直接采 用的结论。在此基础上,兼顾传承文化、方便使用和方便计算机处理的原则,提出了汉字基元的提取流程。 (3)依据上述流程开展大量的实验研究,探索了以工程实验方法研究文化问题的途径。本文选取GB18030收录的27484个汉字作为实验样本集,以独体字 和《辞海》的250个部首作为初始基元进行大量的实验研究,通过实验和分析,提取获得了877个汉字基元。 (4)利用计算机技术设计开发了汉字基元计算机研究平台。研究平台对相关信息进行查询以便研究分析;对汉字基元进行字频统计,表明提取得到的 汉字基元集符合汉字的认知规律且能够完全覆盖27484个汉字;对汉字基元字形信息的分类统计可为汉字基元映射知识提供前期研究的实验数据;对汉字 编码的识别解析为智能造字的输入提供了可能的解决途径。 5.会议论文 赵珀璋 中文信息处理系统的输入 1985 文章首先介绍了中文信息处理系统的一个模型。然后讨论了几种输入系统类型,并详细论述了通用汉字输入编码思想。最后阐述了中文信息的自然 输入方式—文字识别和语音识别。(本刊录) 6.会议论文 曲声波.周征 试论中文信息信息字词兼容处理技术 1991 7.期刊论文 《中文信息学报》征稿简则 -中文信息学报2009,23(5) 一、<中文信息学报>主要刊臀中文信息的基础理论、应用技术、中文信息处理系统及设备、中文信息的自动输入和人工编码输入、汉字字形信息、 自然语言处理、计算语言学及民族语言文字信息处理及网上信息处理等方面的研究论文、技术报告、综述、通讯、简报、国内外学术活动等. 8.会议论文 盛玉麒 古今汉语信息处理平台研究之一《汉语大字典高点阵(96×96)宋体字模库》研制报告 1996 9.学位论文 罗丽俊 中文信息处理中若干技术的研究与实现 2008 随着Intenet迅猛发展,各种资源不断增多。为了快速、高效的查找信息,信息处理以成为当前重要的研究领域。 针对信息处理涉及的内容,本文对中文信息处理中的若干关键技术进行了研究,主要研究内容和贡献如下: 实现了一种基于句法词典的句法分析方法。通过把文法规则映射为特征词,把句法分析转换为利用特征词生成句法判定树,使概率方法和规则方法 有效的结合在一起。在封闭的测试中,该方法获得了89.40%的查全率,87.13%的查准率。 提出了一种利用样本距离,改进K-means聚类的方法,有效地避免了初始点的选择所带来的误差,以及噪声和孤立点的影响。 介绍了一种把多种语料库存入字典结构,以及使用此字典结构的方法;对特征词,使用多层hash存储,结合最大向前匹配,实现了快速分词算法 ,1G内存下,分词速度到2M/S;在实现基于隐马尔可夫模型的词性标注同时,结合平滑算法,标注正确率达到86%,排歧正确率达到82%;在实现基于 KNN分类算法中,使用CHI统计方法选取属于该类的特征词,同时把该类的文档加载到其后,解决了信息冗余问题:通过利用句子的特性,计算句子在文 本中的权重,简单实现了基于统计的机械自动文摘;通过采用向量空间模型,对输入语句进行同义词扩展,对文档采用倒排结构存储,实现了一个简单 的信息检索。 10.会议论文 中国科学院软件研究所 多语言信息处理平台 2006 2003年,在国家"863"软件重大专项<民族语言版本Linux操作系统和办公套件研发>和中科院知识创新工程西部行动计划项目<基于Linux的跨平台藏文 信息处理系统>的资助下,中科院软件研究所联合西藏自治区藏语委办、西北民族大学、新疆大学和内蒙古科立公司等单位,在国产Linux操作系统和办公 套件的基础上,按照标准化、规范化和开放性的少数民族语言处理模型的要求,研发通用的支持蒙、藏、维等少数民族语言的基本系统平台和满足电子政 务、办公应用要求的办公套件,包括文字处理、幻灯片演示、电子表格、电子邮件等组件.本文介绍一、民族语言版本Linux操作系统和办公套件, 二、 跨语言信息检索系统和辅助机器翻译系统。 本文链接:http://d.g.wanfangdata.com.cn/Thesis_Y1541188.aspx 授权使用:武汉大学(whdx),授权号:cedfa30b-c16e-4ec7-af6c-9e3300e92f1b 下载时间:2010年11月19日

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 18 金币 [ 分享文档获得金币 ] 2 人已下载

下载文档

相关文档