您好,欢迎访问三七文档
当前位置:首页 > 行业资料 > 冶金工业 > 自然语言处理NPL-最大概率分词算法
NLP基于最大概率的汉语切分Ytinrete要求:基于最大概率的汉语切分目标:采用最大概率法进行汉语切分。其中:n-gram用bigram,平滑方法至少用Laplace平滑。输入:接收一个文本,文本名称为:corpus_for_test.txt输出:切分结果文本,其中:切分表示:用一个字节的空格“”分隔,如:我们在学习。每个标点符号都单算一个切分单元。输出文件名为:学号.txtBigram参数训练语料:corpus_for_train.txt注:请严格按此格式输出,以便得到正确评测结果切分性能评价:分切分结果评测F*100,F=2P*R/(P+R)特别注意:代码雷同问题本次作业最后得分会综合考虑:切分性能、代码、文档等几个方面。第三次作业上交的截止时间:2014年1月7日24:001.关于最大概率分词基本思想是:一个待切分的汉字串可能包含多种分词结果,将其中概率最大的作为该字串的分词结果。根据:由于语言的规律性,句子中前面出现的词对后面可能出现的词有很强的预示作用。公式1:其中w表示词,s表示待切分字符串。公式2:例如:S:有意见分歧W1:有/意见/分歧/W2:有意/见/分歧/P(W1)=P(有)×P(意见)×P(分歧)=1.8*10-9P(W2)=P(有意)×P(见)×P(分歧)=1*10-11P(W1)P(W2)所以选择W1历史信息过长,计算存在困难p(wi|w1w2…wi-1)为了便于计算,通常考虑的历史不能太长,一般只考虑前面n-1个词构成的历史。即:p(wi|wi-n+1…wi-1)1212(|)*()(|)()()()(,,...,)()*()*...*()iiPSWPWPWSPWPSPWPn()iiwPw在语料库中的出现次数语料库中的总词数Nn-gramn较大时:�提供了更多的语境信息,语境更具区别性。但是,参数个数多、计算代价大、训练语料需要多、参数估计不可靠。n较小时:�语境信息少,不具区别性。但是,参数个数少、计算代价小、训练语料,无需太多、参数估计可靠。题目要求使用bigram,即考虑前一个词,即考虑左邻词。左邻词假设对字串从左到右进行扫描,可以得到w1,w2,…,wi-1wi,…等若干候选词,如果wi-1的尾字跟wi的首字邻接,就称wi-1为wi的左邻词。比如上面例中,候选词“有”就是候选词“意见”的左邻词,“意见”和“见”都是“分歧”的左邻词。字串最左边的词没有左邻词。最佳左邻词如果某个候选词wi有若干个左邻词wj,wk,…等等,其中累计概率最大的候选词称为wi的最佳左邻词。比如候选词“意见”只有一个左邻词“有”,因此,“有”同时也就是“意见”的最佳左邻词;候选词“分歧”有两个左邻词“意见”和“见”,其中“意见”的累计概率大于“见”累计概率,因此“意见”是“分歧”的最佳左邻词。数据稀疏问若某n-gram在训练语料中没有出现,则该n-gram的概率必定是0。解决的办法是扩大训练语料的规模。但是无论怎样扩大训练语料,都不可能保证所有的词在训练语料中均出现。由于训练样本不足而导致所估计的分布不可靠的问题,称为数据稀疏问题。在NLP领域中,数据稀疏问题永远存在,不太可能有一个足够大的训练语料,因为语言中的大部分词都属于低频词。解决办法:平滑技术�把在训练样本中出现过的事件的概率适当减小。�把减小得到的概率密度分配给训练语料中没有出现过的事件。�这个过程有时也称为discounting(减值)。目前已经提出了很多数据平滑技术,如:�Add-one平滑�Add-delta平滑�Witten-Bell平滑�Good-Turing平滑�Church-Gale平滑�Jelinek-Mercer平滑�Katz平滑这里我使用laplace平滑Add-one平滑(Laplace’slaw)规定任何一个n-gram在训练语料至少出现一次(即规定没有出现过的n-gram在训练语料中出现了一次)。没有出现过的n-gram的概率不再是0。2.算法描述1)对一个待分词的字串S,按照从左到右的顺序取出全部候选词w1,w2,…,wi-1wi,…wn;2)到词典中查出每个候选词的概率值P(wi),当候选词没有出现时,由laplace平滑设其概率为1/(字典数+1),记录每个候选词的全部左邻词;3)按照公式1计算每个候选词的累计概率,同时比较得到每个候选词的最佳左邻词;4)如果当前wn是字串S的尾词,且累计概率P’(wn)最大,wn就是S的终点词。5)从wn开始,按照从右到左的顺序,依次将每个词的最佳左邻词输出,即为S的分词结果。3.程序设计整个程序我分为两个阶段,字典生成阶段和分词阶段。(make_dic.cpp)字典生成:目标:输入为训练语料(corpus_for_train.txt),输出为字典(dic.txt),字典内容为单词和单词出现在字典中的频率,首行为词典总词数。实现步骤:首先读入训练,通过空格和换行符作为判定,分出单个单词。若单词没有在字典中出现,则将其加入字典,单词自身频数加一,单词总数加一;若单词在字典中出现,则单词自身频数加一。将数据存入map中,然后再遍历map,创建一个输出流,输出为字典文件,数据为具体单词和他的出现概率(自身频数/单词总数)。(zdgl_fenci.cpp)分词:目标:输入为字典和待切分语料(利用kill_space先将老师预先存好的待切分语料的空格和换行删去,成为为切分语料target.txt),输出为切分好的语料(2011211366.txt)。实现步骤:首先在主函数中,循环取出待切分语料的每个句子,将句子传给分词子程序,分词子程序处理后返回分好的句子,将句子输出到文件,再取下一句,依次循环,直到处理完为止。分词子程序,处理过程分为三步:1.将待切分的句子切成备选的切分词,并放在“单词池”中,切分标准参考一个假定的单词最大长度,程序里面我设置成20,也就是单词最长10个汉字(可以根据词典来决定),具体切分我考虑了两种,不同之处体现在对取到的单词(从一个汉字到10个汉字遍历地取),若不出现在词典中(出现在词典中的肯定会列入),第一种做法是只保留单个汉字形成的单词,另一种做法是保留全部的可能性。若采取第一种则效率会有很大的提高,但理论上会降低准确性,第二种虽然能够考虑到所有的情况,但是数据往往是前一种的几十倍,而且对于句子中很多单词都有在词典时,分词结果几乎和前一种相同,如果句子中的所有词都能在词典中时,分词结果就一样了(laplace平滑使得未出现的概率是最低的,乘积也会最低,所以不会选择未出现的词),但会多出几十倍的运算。两种的代码我都写出来了,考虑实际,我觉得第一种比较妥当,第二种我注释起来。2.对“单词池”操作,通过循环的遍历,直到计算出所有的最佳左邻词。3.在“单词池”中找出所有的句尾词,找到概率最大的,再通过左邻词,往回找,直到找到句头词,将这些词用空格分开,返回。4.程序源码:1.kill_space.cpp将待切分文本corpus_for_test.txt变成不含空格和换行的待切分文本target.txt#includeiostream#includefstream#includemap#includestring/*Name:删除空格Description:删除空格*/usingnamespacestd;intmain(){FILE*f_in,*f_out;//输入输出文件charch;f_in=fopen(corpus_for_test.txt,r);f_out=fopen(target.txt,w);ch=getc(f_in);while(EOF!=ch){if(''!=ch&&'\n'!=ch)putc(ch,f_out);ch=getc(f_in);}return0;}2.make_dic.cpp读入训练预料corpus_for_train.txt输出词典文件dic.txt#includeiostream#includestdio.h#includefstream#includemap#includestringusingnamespacestd;constchar*train_text=corpus_for_train.txt;//训练文件constchar*dic_text=dic.txt;//输出词典文件mapstring,intdic;//词典表mapstring,int::iteratordic_it;//mapstring,doubledic_in_text;//testintmain(){FILE*f_in;f_in=fopen(train_text,r);ofstreamf_out(dic_text);doublerate=0;intcount=0;charch;stringword;ch=fgetc(f_in);while(EOF!=ch){if(''!=ch&&'\n'!=ch)//词的一部分{word.append(1,ch);if(。==word)word.clear();}else//单词结束{if(==word||0==word.size()){word.clear();ch=fgetc(f_in);continue;}dic_it=dic.find(word);if(dic_it!=dic.end()){//找到dic_it-second=dic_it-second+1;word.clear();}else{//新单词count++;dic.insert(pairstring,int(word,1));word.clear();}}ch=fgetc(f_in);//if('\n'==ch)//吸收换行//ch=fgetc(f_in);}f_outcountendl;dic_it=dic.begin();while(dic_it!=dic.end()){f_outdic_it-firstendl;rate=(double)(dic_it-second)/count;f_outrateendl;dic_it++;}f_out.close();fclose(f_in);/*测试用ifstreamfile(dic_text);intcount_text;filecount_text;stringword_text;doublerate_text;for(inti=0;icount_text;i++){fileword_text;filerate_text;dic_in_text.insert(pairstring,double(word_text,rate_text));}file.close();*/return0;}3.zdgl_fenci.cpp读入词典dic.txt和带切分文本target.txt输出分词结果2011211366.txt#includeiostream#includestdio.h#includefstream#includemap#includestring#includevector#includestackusingnamespacestd;constchar*target=target.txt;//输入文件constchar*out_put=2011211366.txt;//输出文件constchar*dic_text=dic.txt;//输入词典文件constintmax_word=20;//假设一个词最长包括10个汉字doublelaplace;//laplace平滑mapstring,doubledic;//词典mapstring,double::iteratordic_it;typedefstructword_pre//单词池内元素{intnum;//标记intp_begin;//起始位置intp_end;//结束位置double
本文标题:自然语言处理NPL-最大概率分词算法
链接地址:https://www.777doc.com/doc-4777632 .html