《自然语言处理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_o
13、ut(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.out0M防止混拣最后句话s_comp1.e(e.c1.ear();s-comp1.ete=zd
14、g1.enci(sen(aje);s_comp1.ctc+=w”;/加上“JCouts-comp1.ctc1(h出Ibreak;Ich2=fgcc(fjn);if(E0F=ch2)if(scmanceSiZeOM)M防止漏抻最后一句话s-comp1.ctc.c1.car();s-comp1.e(c-zdg1.fcnci(scntancc);s.con1.e(e+=。加上“Jf_outs_comp1.ete;/ft5出Ibrcak;户测试s_comp1.c1.e=zdg1.fenci(有意见分歧”)：s_comp1.ctc+=加上J匚OIHVsomp1.ctcW输出*/fc1.osc(fjn):
15、Cout.c1.osc();HHUE0：5.实验总结：由于我的编程能力比拟差，所以这个实验对我来说是个极大的挑战，又开始我甚至认为我绝而不能完成这项工作上但是慢慢来一点一点的写,退到问题上网查资料,实在不行换一种方法，一点一点的调试,股终还是能写出来了.具体设计实现分次的时候，我完全没有头绪，想过用矩阵，但矩阵在确认最正确左邻词的时候不知道如何.遍历用鞋表.但足不知道切分点一致时不同的左邻词怎么连上去.河上查到了别人用有向图的的法（见附录），当时对我来说是极具诱窸力的.但是特别注意里面有项代码雷同向SS，我能衽得到的别人也一定杳得到吧，我这么想希，所以就放弃了这个金头，还是自己想吧，Ift后想
16、出了用YeCUM容器并通过泗历来解决，真是不容历，最后是大半夜号完的，程序跑出来我自己都要哭出来了,太不容易了。然后看看结果，第一句话和分诃模板没有去掉空格前完全一样,又一次被感动了，看起来算圆满完成了.nt*.网上别人供的用育向BB大票率分询/wo!xi.cpp:Definestheentrypointfortheconso1.eapp1.ication./,inc1.udeStdafxJTI1.mymseg.c:定义控制台应用程序的入口点，#inc1.udeWinc1.udcWinc1.udc#inc1.udeusingnanpaccs1.d:constintNoDENUM=100W最大节
17、点数mapmapWrd2Prob:constintMaxWgth=8:4同的最大长度constiniMinWordng1.h=2;词的最小长度f1.oatpbNODENUM每个节戊的地大累iI概率intPrevNix1.eINoDENUMH/母个节点的最优前船节点conststringStrDdim1.tCr=，分诃分割符void1.OadDiC1()ImapVord2P11)b(,=0.018;mapWord2Px)b*H).(KM)5:mapWord2Pmb意见E).0()I;mapWor1.2Pb%=0.(K)02:mapWord2Pmb分歧=0.0001:)“词作为边S1.ruc1.C
18、dgeNcKiestringterm1.x1.;词intSu1.rt:“诃的开始位置Mend以诃的结束位置f1.oaprob;词在语料库中出现的频率或者概率)：”分割位置作为点structvexNodeIintnScgNo:分割W点编号IiMIinkcd1.ist;与之相连的小底head；存储节点信息vexNodeIidjIisHNODENUMI;建立邻接表存储voidInitiaIGraphOIinii=0;for(i=0;iNODENUM;i+)(adj1.isii.nSegNo=i;”插入一条边voidInsertEdgc(edgeN1.c&newEdgeNode)IintvIncwEd
19、gcNd;adj1.isv1.1.inked1.ist.push,front(newEdgeNode);)形成切分词图voidCreateWorISegG11ph(sirings)Ishorti=0;shortj=();shortIen=O;shortres1.1.en=O:shortn=gth():f1.oatfrcq=O;stringw;for(j=0tbr(=2Jcn=MaxVHghJcn=2)res1.1.en=nj;if(/如果朝氽词长度不好长.跳出给环(W=S-SubsirtjJen);)e1.se(break;Jif(nWord2Prob.find(w)-mapWord2Prob
20、.end()(frcq=mapWo111.2Prbw);)e1.se(frcq=100;)if(freq!=100)(cdgcNodcStCandidatcWord:stCa11diHcWo111.(crmTcxt=w;sCa1.ida(eWoJ,sta11=jMinWord1.ength:s(Candida1.eWn1.e1.=(j+),MinWord1.eng1.h:stCandidatcWord.prob=frcq:co1.插入一条边wordwfreqesCandidaieWord.protxstartMstCandida1.cWord.s1.artends1.CandidatcWord
21、.endend1.:InscrtEdge(StCandidateWord);I”寻找i的G正确前的词voidgctPrcv(inti)vexNode0VexN0de=adj1.istij;cdgeNkOEdgCNOdc:1.ist:iteratori1.1.is1.:得到前驱词的集合f1.oatnwxProb=O;inimaxNode=-I;根据前现词集合挑选G正确前电节点forth1.iSI=OVCXN(XIC.Iinkcd1.iNbcginO;it1.ist!-oVcxNd()i(1.is()(f1.oatnodePrb=Probm1.is1.starU-i1.1.is1.prbT候选节点
22、概率CmnVv”搜索结点,i*其前趋累计概率MnodePmbM开始位置statmaxPb)(候选节点概率最大的开始节点就是最正确的趋节点maxN(k=it1.ist-start;maxProb=nodeProb;IIprobi-maxPmbH节点概I率p!evNodei)=InaKNOde;域正确前照节点CoUIV”节点”的最正确前界节点”maxNdcvbki=prcvN(1.ci)(COU正确路径结点Vviend1.;strSeg=strScqKMicc.substr(n1.cft4MinWgth.(nRight-n1.cft)4MnWgth)+strDc1.imitcr+strScg;Ir
23、ernstrSeg;intmain(intargc,charargv)/i11JinaiiKintargc._TCHARtargv11)1.oadDiC1.();Ini1.iaIGraphO;for(inti=0:iNODENUM:i+)pbi=0;pnevNode(i=0:Istring“rScqucnc”有意见分岐;构建邻接表表示的切分词图，(有向图)Crca1.eWordSegGraph(s1.rScquence):Co1.I”寻找域正确前曲,e1.1.;For(inti=1n=strSeqgth()MinVgthJ+)getPrev(i)：Icoutw”最正确切分路径end1.:COU1.v”分词结果BcstScg(MrScqucncc)m:returnO;
