自然语言理解工程报告

中文分词工程报告课程：自然语言理解姓名：学号：班级：日期：2013/11/14一，研究背景（一）研究背景：由于中文只有字、句和段能通过明显的分界符来简单划界，唯独词没有一个形式上的分界符，虽然英文也同样存在短语的划分问题，不过在词这一层上，中文比之英文要复杂的多、困难的多。中文分词技术产生的因为是中文在基本文法上有其特殊性，具体表现在：1．中文词语之间没有分隔，而现代汉语中双字或多字词居多，一个字不等同于一个词。2．在中文里，“词”和“词组”边界模糊。现代汉语的基本表达单元虽然为“词”，且以双字或者多字词居多，但由于人们认识水平的不同，对词和短语的边界很难去区分。3.中文分词的方法其实不局限于中文应用，也被应用到英文处理，如手写识别，单词之间的空格就很清楚，中文分词方法可以帮助判别英文单词的边界。（二）主要研究方法①基于字位的中文分词研究方法②基于数据驱动的中文分词研究方法③基于中文文本分词的中文分词研究方法④基于优化最大匹配的中文分词研究方法⑤基于无词库的中文分词研究方法（三）主要存在问题中文是一种十分复杂的语言，让计算机理解中文语言更是困难。在中文分词过程中，有两大难题一直没有完全突破。1.歧义识别：歧义是指同样的一句话，可能有两种或者更多的切分方法。主要的歧义有两种：交集型歧义和组合型歧义。交集型歧义相对组合型歧义来说是还算比较容易处理，组合型歧义就必需根据整个句子来判断了。如果交集型歧义和组合型歧义计算机都能解决的话，在歧义中还有一个难题，是真歧义。真歧义意思是给出一句话，由人去判断也不知道哪个应该是词，哪个应该不是词。2.新词识别：新词指那些在分词词典中没有收录，但又确实能称为词的那些词。最典型的是人名，除了人名以外，还有机构名、地名、产品名、商标名、简称、省略语等都是很难处理的问题，而且这些又正好是人们经常使用的词，因此对于搜索引擎来说，分词系统中的新词识别十分重要。新词识别准确率已经成为评价一个分词系统好坏的重要标志之一。（四）现有解决方案现有的分词算法可分为三大类：基于字符串匹配的分词方法、基于理解的分词法和基于统计的分词法。按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。1.字符匹配：这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。2.理解法：这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控部分。3.统计法：从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。（五）应用中文分词是其他中文信息处理的基础，搜索引擎只是中文分词的一个应用。其他的比如MT、自动分类、自动摘要、自动校对等等，都需要用到分词。因为中文需要分词，可能会影响一些研究，但同时也为一些企业带来机会。分词准确性对搜索引擎来说十分重要，但如果分词速度太慢，即使准确性再高，对于搜索引擎来说也是不可用的，因为搜索引擎需要处理数以亿计的网页，如果分词耗用的时间过长，会严重影响搜索引擎内容更新的速度。因此对于搜索引擎来说，分词的准确性和速度，二者都需要达到很高的要求。二，模型方法（一）基本原则合并原则：1、语义上无法由组合成分直接相加而得到的字串应该合并为一个分词单位。2、语类无法由组合成分直接得到的字串应该合并为一个分词单位。3、附着性语(词)素和前后词合并为一个分词单位。4、使用频率高或共现率高的字串尽量合并为一个分词单位。5、双音节加单音节的偏正式名词尽量合并为一个分词单位。6、双音节结构的偏正式动词应尽量合并为一个分词单位切分原则：1、有明显分隔符标记的应该切分之。2、内部结构复杂、合并起来过于冗长的词尽量切分（二）汉语自动分词基本算法1.最大匹配法(MM)①正向最大匹配算法(FMM)逆向最大匹配算法(BMM)双向最大匹配算法(MM)FMM算法描述：(1)令i=0，当前指针pi指向输入字串的初始位置，执行下面的操作：(2)计算当前指针pi到字串末端的字数（即未被切分字串的长度）n，如果n=1，转(4)，结束算法。否则，令m=词典中最长单词的字数，如果nm,令m=n；(3)从当前pi起取m个汉字作为词wi，判断：(a)如果wi确实是词典中的词，则在wi后添加一个切分标志，转(c)；(b)如果wi不是词典中的词且wi的长度大于1，将wi从右端去掉一个字，转(a)步；否则（wi的长度等于1），则在wi后添加一个切分标志（单字），执行(c)步；(c)根据wi的长度修改指针pi的位置，如果pi指向字串末端，转(4)，否则，i=i+1，返回(2)；(4)输出切分结果，结束分词程序。2.最短路径法基本思想：设待切分字串S=c1c2…cn，其中ci(i=1,2,…,n)为单个的字，n为串的长度，n1。建立一个节点数为n+1的切分有向无环图G，各节点编号依次为V0，V1，V2，…，Vn。算法描述：(1)相邻节点vk-1,vk之间建立有向边vk-1,vk，边对应的词默认为ck(k=1,2,…,n)。(2)如果w=cici+1…cj(0ijn)是一个词，则节点vi-1,vj之间建立有向边vi-1,vj，边对应的词为w。(3)重复步骤(2)，直到没有新路径(词序列)产生。(4)从产生的所有路径中，选择路径最短的(词数最少的)作为最终分词结果。3.基于语言模型的分词方法方法描述：设对于待切分的句子S，W=w1w2……wk(1kn)是一种可能的切分。4.基于HMM的分词方法基本思想：把输入字串(句子)S作为HMM的输入；切分后的单词串Sw为状态的输出，即观察序列5.由字构词(基于字标注)的分词方法基本思想：将分词过程看作是字的分类问题。该方法认为，每个字在构造一个特定的词语时都占据着一个确定的构词位置(即词位)。假定每个字只有4个词位：词首(B)、词中(M)、词尾(E)和单独成词(S)，那么，每个字归属一特定的词位。6.生成式方法与区分式方法的结合大部分基于词的分词方法采用的是生成式模型而基于字的分词方法采用区分式模型(Discriminativemodel)：本次实验主要采用FMM三，系统设计（一）系统的详细设计：宋词语料的处理：1.对宋词语料进行分词处理是该系统的第一步，分词处理的目的是初步形成分词语料以及了解如何进行中文分词。2.宋词语料大，首先我们需要对其进行抽样调查，经调查发现其中除了全角字符外，还有一些半角字符以及不能识别字符等，为此我们需要对这些问题进行处理。3.采用识别国标码来进行分析，第一步：取出半角字符，以ch80h为标准，对于所有满足此条件的字符进行跳过处理。4.识别汉字标点符号，经初步分析可知，汉字的最小国标码为B000h，所以可以采用对小于该国标码的汉字进行相应处理，从而识别出一个、两个、三个词组。5.处理单个字符：由于每个汉字是以全角字符的形式存储的，因而需要用charch[2]来存储，在读入时，先判别高字符是否大于80h，若大于则读入下一个字符，否则跳过该全角字符（注意，以处理过半角字符，继续读入一个字符）对于满足条件的字符，则存储。同时进行查表来判断该字是否已经出现过，出现过则次数加一，然后清空ch[2]，继续循环处理。对所有语料处理完后，再对存储的初步结果进行排序处理。6.处理两个字：由于处理两个字时需要考虑到标点符号的影响，当当前字符为汉字，下一个字符为标点时，则不能作为一个词。中间缓存采用ch[4]来存储，先读入高字节，若为标点，采用5来处理；若为汉字，用ch[0,1]来存储，继续读入下一个字符，若为汉字，则读入形成一个词，查表累计次数；若不是汉字，即符号，则跳过该符号。然后对ch[4]清空，继续循环读入，处理完所有语料再排序处理。7.处理三个汉字，同6，只是用ch[6]进行缓存，以后两个字为判断标志。对人民日报语料处理：1.分析语料可以发现词语是以全角字符开头，以”/”或者”{”为结束标志；词语之间以空格分开；对于”/”或者”{”后面的注释部分可以不处理。2.由于词语的长度不固定，为此在处理过程中采取的缓存空间应该较大，以确保能够处理长度足够大的词组。3.处理过程中，采用循环输入，先识别出一个词的开始，以大于80h为判别依据，不断检测下一个字符的高字节（确保当前汉字读写完毕），若遇到结束否，则该词读入完毕，存储该词，同时对于后面的注释部分采用跳过处理。4.由于标点符号在处理过程中不可以忽略，因而需要对标点进行相应处理，采用的识别机制是大于80h5.由于分词过程中，需要选取最大阈值，所还应该统计最长字符串的长度，以备切分时所用，为了简化系统，在此采用默认最大长度为一个定值。不断循环处理语料，知道语料的结束，对应的语料字典也生成完毕。切分语料：1.切分语料的依据是FMM算法，并利用分隔符（此处为标点符号）来进行辅助切分。2.FMM算法的具体实施过程已在模型方法中说明，此处可略去；标点符号辅助切分，对应于人民日报语料中的标点符号。3.对于待切分语料，需要进行中间处理，因为语料字典只能识别出全角字符以及其识别的字词有限，为此需要对待切分语料进行两部处理：①去除其中的半角字符。②添加未登录字到语料字典中，由于语料有限，无法准确判断一个词，所以在此简化处理识别位登陆字。4.以处理好的中间语料作为输入，利用FMM算法对其切分。由于语料有限，在处理阈值是可以采用简化处理，给予一个固定的阈值，这样实现起来也较为简单。5.不断的循环输入，检测是否结束，当中间语料读入完毕，相应的切分结果也统计完毕。（二）系统流程：1.宋词语料：2.人民日报语料：3.切分流程：（三）训练模型及测试：由于语料大小有限，在切分的过程中会出现一系列的问题：比如有一些字无法切分，半角字符处理有问题，标点符号未登陆……1.若是没有登陆标点符号，那么在切分的时候，很容易把标点符号的前后两个字组成一个词，很显然这是不符合常理的。2.有一些系统未登录词，比如说先前已“/”作为词结束标志的时候，字典中对于“落”的存储为“落{luo}”这样在遇到“落”字的时候，便无法进行处理，后来采用了两种方法以应对该问题：1）添加一“{”作为结束标志；2）添加未登录字的识别过程。3.半角字符会影响到系统的切分，由于半角字符不属于中文词语，一概采用去除处理。4.切分时分别采用散文语料，新闻语料，小说语料来进行，通过观察切分结果，我发现对新闻语料切分后的找回率最高。分析原因可知，各种问题的语法构成不同，以及一些未登录词没有采用相应的添加处理。（四）评估：1.由于语料有限，以及处理过程的简化，最终的召回率不是太高，有以下几个原因：①由于FMM算法在且分时，最大召回率为95%；②词典中的词语有限，存在未登录词；③算法的简化，阈值采用自己默认的数来决定；④国标码中的汉字数量有限，有一些字未能识别。2.处理宋词语料的过程中，刚开始采用的是分三步来识别（先识别一个字；再识别两个字；最后识别三个字）发现效率比较低，因而采用嵌套处理，同时采用了goto语句，方便跳转。3.由于语料较大，同时考虑到对于存储的每一个词包含两个信息（该词是什么以及该词对应的次数）为此想到了可以采用stl中的mapstring,int来进行存储，在排序过程中采用优先队列可以方便排序，从而避免使用结构体处理过程中的繁琐。4.采用优先队列排序时，采用默认方式由高到低进行，排序过程中由于是以int（及对应的次数作为排序依据）所以需调整为mapint,string。采用此方法处理时时间复杂度、空间复杂度较低。5.由于采用的是国标码而非扩展国标码，因而存在语料中的字无法识别，统计结果与实际结果存在偏差；对于标点符号的的处理默认其范围在8000h——B000h