自然语言处理NPL-最大概率分词算法.docx

《自然语言处理NPL-最大概率分词算法.docx》由会员分享，可在线阅读，更多相关《自然语言处理NPL-最大概率分词算法.docx（13页珍藏版）》请在优知文库上搜索。

1、N1.P基于最大概率的汉语切分Ytinrete要求：基于最大概率的汉语切分目标：采用最大概率法进行汉语切分。其中：n-gram用bigmm.平济方法至少用1.ap1.acc平滑.输入：接收一个文本，文本名称为：COrPUS_foresixi输出：切分结果文本.其中：切分表示：用一个字节的空格”分隔,如：我们在学习.姆个标点符号都总算一个切分单元。输出文件名为；学号ixiBigram参数训练诏料：corpus_1.brjrain.txt注：请严格按此格式输出,以便得到正研评冽结果切分性能评价:什切分结果评测F100zF=2PR(P+R)特别注怠:代码缶同问题本次作业取后得分会保合考虑：切分性能、

2、代码、文档等几个方面.第三次作业上交的截止时间I2014年1月7I1.24:001.关于最大概率分词根本思想是：一个待切分的汉字串UJ能包含多种分词结果，将其中概率用大的作为该字中的分词结果.根据：由于谱吉的规律性,句子中前面出现的词对后面可能出现的诃有很强的预示作用。公式I：其中W表示词，S去示待切分字符串，?WS)=笔产”(W)P(W)=P(vv1,vv2,.,1)P(vv1.)*P(vv2)*.*P(vv.)例如：S：有意见分歧然蓝在语料库中的出现次数n户语料库中的总词数NP(W1.)=P(Yi)XP(JS见)XP(分歧)=1.8*10-9P(W2)=P(有意)XK见XP(分歧)=1*1

3、0-11P(WI)P(W2)所以选择WI历史信息过长，计算存在困魔P(Wi1.W1.W2*1)为了便于计律,通常考虑的历史不能太长，一般只考虑的面n1个词构成的历史.即：P(Wikyin+1-wi1.)n-gramn较大时：提供了更多的语境信息,语境更具区别性。但是，。数个数多、计算代价大、训练语料需要多、参数估计不可谥”n较小时：语境信息少，不具区别性.但是，参数个数少、计算代价小、训练语料，无需太多、参数估计可搪。JI目要求使用bigram,即考虑前一个词，即考虑左邻词.左邻词假设对字申从左到右进行扫描，可以得到w1.,w2.wi1.wi,等假设干候选词，如果的的尾字跟Wi的首字邻接，就称

4、Wi-I为Wi的左邻词,比方上面例中,候选词“有”就是候选词“意见”的左邻诃,“意见”和“见”都是“分歧”的左匏诃.字部最左边的词没有左邻词.量正确左邻词如果某个候选词Wi有假设干个左邻词Wj,Wk.等等，其中累计概率必大的候选词称为Wi的最正确左邻词.比方候选词“意见”只有一个左领词“有”.因此，“有”同时也就是“意见”的最正确左邻词：快选诃“分歧”有两个左邻词“意见”和“见”，其中“意见”的累计概率大于“见”累计概率，因此“意见”是“分歧”的最正确左邻词。假设某n-gram在训练语料中没有出现,那么该n-gram的概率必定是0,解决的方法是Ir大训练语料的规模。但是无论怎样扩大训练语料，都

5、不可能保证所有的词在训练语料中均出现，由于训练样本缺乏而导致所估计的分布不可犯的问题,称为数据稀疏问题。在N1.P领域中，数据林疏何趣永远存在,不太可能有一个足修大的训练语料,因为谙言中的大局部词都M干低侦诃.斛决触平相财把在训练样本中出现过的事件的概率适当收小.把破小得到的概率密度分配给训练评科中没有出现过的事件.这个过程有时也称为disc。Unting（战值）.目前已经提出了很多数据平滑技术，如：Add-one平滑AddYC1.ta平滑Witten-Be1.1.平滑GtKx1.-Turing平JttChurch-Ga1.c平滑Jc1.inck-Mcrccr平滑Katz平滑这里我使用IaP1

6、.aCe平滑ddone平常（I.ap1.aces1.aw）规定任何个n-gram在训练语料至少出现一次（即规定没有出现过的n-gram在训练语料中出现了一次）。没有出现过的n-gram的概率不再是0.2.算法描述I）对一个待分词的字串S,按照从左到右的顺序取出全部候选词W1.w2j,Wi-IWi,-Wn；#inc1.*dc#inc1.udc#incIdc#inc1.ude#inc1.udeusingnamespaces(d;constchar*(ruin_1.ex(=corpU1.fbrJnIin.tx1.:训练文件constchardic-tcxt=Pic.tXf检出诃典文件mapdiczi

7、!衣map:iteratordiejt:/madic_in_iext/(estintnain()IFI1.E*f_in：Cin=1.bpen(1.rain_(ex1.*r*):ofstream匚OUMdiCdoub1.erae=O;iniCQUnt=O:charch;stringword;ch=ecc(Un);whi1.e(EOF!=chIChM词的一历剖(word.appc11d(1.ch;if(.w=word)word.c1.car();Idsc”单词结束jf(,=word0=word.sizd)word.c1.car();ch=fgec(Ci11);cn1.inue:dic-i1.=di

8、c.find(word):if(dic.it!=d()找到dicjt-sccond=disccond+1;word.c1.ead):Ie1.se新单词count;dic.insert(air(word,I);wn1.c1.car():ch=fgctc(fjn):Uif(n=chW吸收换行ch=fgec(Cin);Coutcountendkdic_it=dic.bcgin():whi1.c(dicjt!=d()I1.outfirsisccond)/counUf_outratccnd1.;dicj(+;f_outc1.osc();fc1.ose(Cin);了测试用ifstrcamfi1.c(dic

9、-tcxt);intcountjcxt;fi1.ecount_(ext;siringwon1._1.ext:doub1.eratc_tcxt:forinti=0;iratejex;di_in_(ext.inser1.(pair(word_1.ext.ra1.c_tex1.):fi1.e.c1.ose。；*/returnO;3.dg1.-fc,i.cpp读入词典die.tx1.和带切分文本Iargex输出分词结果201I366znc1.udcWinc1.udc*inc1.udeinc1.dcWinc1.udcWinc1.dc#inc1.udeusingnamespacestd:constchar

10、*earge=argeJKTW输入文件constchars*oukpu1.=2011211366.1.x火输出文件constchardicjcxt=Pictx1.W输入词典文件constinimax_won1.=20W假设一个词展长包括IO个汉字doub1.eIap1.accW1.aPbCC平滑mapdie词典map:iteratordieJt:typedefsrctWOn1.PN单词池内元素Iintnum:标记in(p_bcgin;起始也imp_endW结束位置doub1.ewordajaate:单词本身概率doub1.ep1.usjatu”单词累进柢率intbest;“最正确左邻词stri

11、ngthis_woM：词本身|word_pre:forttni=0;iword_poo1.sizeO：i+)if(max=(word_poo1.at(i).p_end”/是结尾诃(end_woixi_temp.push_kick(i);imbe$1.em1.wOfd=0;初始化fortinti=1.:iIif(woixJ_poo1.aend_word_(emp.a1.(i),p1.us_i,ate(woni_poo1.ai(end_w(bcsi_cnd_word=i;Iintp)sition=cnd_wordtcmp.at(bcst_cnd_wwd);voctorp1.c(c;Whi1.e(O

12、!=(WOn1.Px)1.aupoSmOn),p_begin)往回找Iwond_comp1.ctc.push_back(won1._poo1.at(position).this_won1.):position=(word,poo1.at(position),bcst;word_comp1.etc.pu*h_back(w。Tx1.POOIpo疝ion)=kiM用空格分开拼成成品1comp1.ee=word-con)1.ee.a(i);if(0!=i)comp1.ete+=*u;returncomp!ctci1.u1.int11uin()dicjni();FI1.E*fjn:ofstrcamf_out(out_put);U11=fpcn(targcc,T);charch1=0,ch2=0;siringwn1.scn1.ance.s_comp1.e1.e;ch1.=fgetc(U11);if(EOF=dd)cou1.,fi1.eidempIwond.appci(1.,ch1.);wond.append(I.d)2);if(”=word)一个句子(s_comp1.ecc.c1.car();s_comp1.e(e=zdg1._fenci(sentance);1.ComPIC1.C+=Q：加上J1.out