版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、NLP基于最大概率的汉语切分Ytinrete要求:基于最大概率的汉语切分目标:采用最大概率法进行汉语切分。 其中:n-gram用bigram,平滑方法至少用Laplace平滑。输入:接收一个文本,文本名称为:corpus_for_test.txt输出:切分结果文本,其中:切分表示:用一个字节的空格“ ”分隔,如:我们 在 学习 。 每个标点符号都单算一个切分单元。输出文件名为:学号.txtBigram参数训练语料:corpus_for_train.txt注:请严格按此格式输出,以便得到正确评测结果切分性能评价:分切分结果评测F*100, F=2P*R/(P+R)特别注意:代码雷同问题本次作业最
2、后得分会综合考虑:切分性能、代码、文档等几个方面。第三次作业上交的截止时间:2014 年1月7日24:00 1.关于最大概率分词基本思想是:一个待切分的汉字串可能包含多种分词结果,将其中概率最大的作为该字串的分词结果。根据:由于语言的规律性,句子中前面出现的词对后面可能出现的词有很强的预示作用。公式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历史信息过长,计算存在困
3、难p(wi|w1w2wi-1)为了便于计算,通常考虑的历史不能太长,一般只考虑前面n-1个词构成的历史。即: p(wi|wi-n+1wi-1)n-gramn 较大时: 提供了更多的语境信息,语境更具区别性。但是,参数个数多、计算代价大、训练语料需要多、参数估计不可靠。n 较小时: 语境信息少,不具区别性。但是,参数个数少、计算代价小、训练语料,无需太多、参数估计可靠。题目要求使用bigram,即考虑前一个词,即考虑左邻词。左邻词假设对字串从左到右进行扫描,可以得到w1 ,w2 ,wi-1 wi,等若干候选词,如果wi-1 的尾字跟wi 的首字邻接,就称wi-1 为wi 的左邻词。比如上面例中,
4、候选词“有”就是候选词“意见”的左邻词,“意见”和“见”都是“分歧”的左邻词。字串最左边的词没有左邻词。最佳左邻词如果某个候选词wi 有若干个左邻词wj , wk ,等等,其中累计概率最大的候选词称为wi 的最佳左邻词。比如候选词“意见”只有一个左邻词“有”,因此,“有”同时也就是“意见”的最佳左邻词;候选词“分歧”有两个左邻词“意见”和“见”,其中“意见”的累计概率大于“见”累计概率,因此“意见”是“分歧”的最佳左邻词。数据稀疏问若某n-gram在训练语料中没有出现,则该n-gram的概率必定是0。解决的办法是扩大训练语料的规模。但是无论怎样扩大训练语料,都不可能保证所有的词在训练语料中均出
5、现。由于训练样本不足而导致所估计的分布不可靠的问题,称为数据稀疏问题。在NLP领域中,数据稀疏问题永远存在,不太可能有一个足够大的训练语料,因为语言中的大部分词都属于低频词。解决办法: 平滑技术 把在训练样本中出现过的事件的概率适当减小。 把减小得到的概率密度分配给训练语料中没有出现过的事件。 这个过程有时也称为discounting(减值)。目前已经提出了很多数据平滑技术,如: Add-one 平滑 Add-delta 平滑 Witten-Bell平滑 Good-Turing平滑 Church-Gale平滑 Jelinek-Mercer平滑 Katz平滑这里我使用laplace平滑Add-o
6、ne 平滑(Laplaces law)规定任何一个n-gram在训练语料至少出现一次(即规定没有出现过的n-gram在训练语料中出现了一次)。没有出现过的n-gram的概率不再是0。2.算法描述1)对一个待分词的字串S,按照从左到右的顺序取出全部候选词w1 ,w2 ,wi-1 wi, wn;2) 到词典中查出每个候选词的概率值P(wi),当候选词没有出现时,由laplace平滑设其概率为1/(字典数+1),记录每个候选词的全部左邻词;3) 按照公式1计算每个候选词的累计概率,同时比较得到每个候选词的最佳左邻词;4) 如果当前wn是字串S的尾词,且累计概率P(wn)最大, wn就是S的终点词。5
7、) 从wn开始,按照从右到左的顺序,依次将每个词的最佳左邻词输出,即为S的分词结果。3. 程序设计整个程序我分为两个阶段,字典生成阶段和分词阶段。(make_dic.cpp)字典生成:目标:输入为训练语料(corpus_for_train.txt),输出为字典(dic.txt),字典内容为单词和单词出现在字典中的频率,首行为词典总词数。实现步骤:首先读入训练,通过空格和换行符作为判定,分出单个单词。若单词没有在字典中出现,则将其加入字典,单词自身频数加一,单词总数加一;若单词在字典中出现,则单词自身频数加一。将数据存入map中,然后再遍历map,创建一个输出流,输出为字典文件,数据为具体单词和
8、他的出现概率(自身频数/单词总数)。(zdgl_fenci.cpp)分词:目标:输入为字典和待切分语料(利用kill_space先将老师预先存好的待切分语料的空格和换行删去,成为为切分语料target.txt),输出为切分好的语料(.txt)。实现步骤:首先在主函数中,循环取出待切分语料的每个句子,将句子传给分词子程序,分词子程序处理后返回分好的句子,将句子输出到文件,再取下一句,依次循环,直到处理完为止。分词子程序,处理过程分为三步:1. 将待切分的句子切成备选的切分词,并放在“单词池”中,切分标准参考一个假定的单词最大长度,程序里面我设置成20,也就是单词最长10个汉字(可以根据词典来决定
9、),具体切分我考虑了两种,不同之处体现在对取到的单词(从一个汉字到10个汉字遍历地取),若不出现在词典中(出现在词典中的肯定会列入),第一种做法是只保留单个汉字形成的单词,另一种做法是保留全部的可能性。若采取第一种则效率会有很大的提高,但理论上会降低准确性,第二种虽然能够考虑到所有的情况,但是数据往往是前一种的几十倍,而且对于句子中很多单词都有在词典时,分词结果几乎和前一种相同,如果句子中的所有词都能在词典中时,分词结果就一样了(laplace平滑使得未出现的概率是最低的,乘积也会最低,所以不会选择未出现的词),但会多出几十倍的运算。两种的代码我都写出来了,考虑实际,我觉得第一种比较妥当,第二
10、种我注释起来。2. 对“单词池”操作,通过循环的遍历,直到计算出所有的最佳左邻词。3. 在“单词池”中找出所有的句尾词,找到概率最大的,再通过左邻词,往回找,直到找到句头词,将这些词用空格分开,返回。4. 程序源码:1.kill_space.cpp将待切分文本corpus_for_test.txt变成不含空格和换行的待切分文本target.txt#include#include#include #include/*Name: 删除空格 Description: 删除空格 */using namespace std;int main()FILE *f_in, *f_out;/输入输出文件 cha
11、r ch;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);return 0;2. make_dic.cpp读入训练预料corpus_for_train.txt输出词典文件 dic.txt#include#include#include#include#includeusing namespace std;const char *train_text = corpus_for_
12、train.txt;/训练文件 const char *dic_text = dic.txt;/输出词典文件 map dic;/词典表map :iterator dic_it;/map dic_in_text;/test int main()FILE *f_in;f_in=fopen(train_text, r);ofstream f_out(dic_text);double rate=0;int count=0;char ch;string word;ch=fgetc(f_in);while(EOF!=ch)if( !=ch&n!=ch)/词的一部分 word.append(1, ch);i
13、f(。=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(pair(word,1); word.clear();ch=fgetc(f_in);/if(n=ch)/吸收换行/ch=fgetc(f_in);f_outcountendl;dic_it
14、=dic.begin();while(dic_it!=dic.end()f_outfirstsecond)/count;f_outratecount_text;string word_text;double rate_text;for(int i=0; iword_text;filerate_text;dic_in_text.insert(pair(word_text,rate_text); file.close();*/return 0;3. zdgl_fenci.cpp读入词典dic.txt和带切分文本target.txt输出分词结果.txt#include#include#include
15、#include#include#include#includeusing namespace std;const char *target = target.txt;/输入文件const char *out_put= .txt;/输出文件 const char *dic_text = dic.txt;/输入词典文件 const int max_word=20;/假设一个词最长包括10个汉字double laplace ;/laplace平滑map dic;/词典map :iterator dic_it; typedef struct word_pre/单词池内元素int num;/标记int
16、 p_begin;/起始位置int p_end;/结束位置double word_rate;/单词本身概率double plus_rate;/单词累进概率int best;/最佳左邻词string this_word;/词本身word_pre;void dic_init_test(void)/测试用int count_text=;laplace = (double)1/(count_text+1);dic.insert(pair(有,0.018); dic.insert(pair(有意,0.0005); dic.insert(pair(意见,0.001); dic.insert(pair(见,
17、0.0002); dic.insert(pair(分歧,0.0001); void dic_init(void)/初始化词典ifstream file(dic_text);int count_text;filecount_text;laplace = (double)1/(count_text+1);string word_text;double rate_text;for(int i=0; iword_text;filerate_text;dic.insert(pair(word_text,rate_text); file.close();string zdgl_fenci(string s
18、entance)/最大概率分词,输入为不带“。”的句子,输出为分好的句子if(sentance.size()=2)return sentance;/单个字直接返回int min=0, max=sentance.size()-1;/单词位置标记/第一步建立单词池vectorword_pool;/单词池int word_pre_num=0;/stackword_link;string temp_word;/第一种方法,对于未出现词,只保存单个字for(int i=0; i=max; i+=2)temp_word.clear();for(int j=i; j=max&jsecond;elsew_pr
19、e.word_rate=laplace;if(0=i)/句头词w_pre.plus_rate=w_pre.word_rate;w_pre.best=0;elsew_pre.best=-1;w_pre.plus_rate=(double) -1;w_pre.p_begin=i;w_pre.p_end=j+1;w_pre.this_word=temp_word;word_pool.push_back(w_pre);/入池/第二种方法,记录所有可能情况/*/严格全部入池for(int i=0; i=max; i+=2)temp_word.clear();for(int j=i; j=max&jsec
20、ond;elsew_pre.word_rate=laplace;if(0=i)w_pre.plus_rate=w_pre.word_rate;w_pre.best=0;elsew_pre.best=-1;w_pre.plus_rate=double(-1);w_pre.p_begin=i;w_pre.p_end=j+1;w_pre.this_word=temp_word;word_pool.push_back(w_pre);/入池*/第二步计算最佳左邻词bool fail=true;/标记while(fail)fail=false;for(int i=0; iword_pool.size();
21、 i+)/遍历整个单词池if(-1=(word_pool.at(i).best)/没有算出左邻词int p_begin_temp=(word_pool.at(i).p_begin;vectorbest_word_temp;/计算最佳左邻词用for(int j=0; jword_pool.size(); j+)/遍历整个单词池if(p_begin_temp=(word_pool.at(j).p_end+1)/再考虑范围内if(-1=(word_pool.at(j).best)/考虑的左邻词本身数据不全fail=true;/标记未完成best_word_temp.clear();break;/跳出
22、循环else/best_word_temp.push_back(j);/记录if(0!=best_word_temp.size()/所有备选项资料完备int max_p=0;/best_word_temp序号for(int k=1; k(word_pool.at(best_word_temp.at(max_p).plus_rate)max_p=k;/记录左邻词和概率(word_pool.at(i).best=best_word_temp.at(max_p);(word_pool.at(i).plus_rate=(word_pool.at(i).word_rate)*(word_pool.at(
23、best_word_temp.at(max_p).plus_rate);/第三步,选出最佳句尾词,并通过最佳左邻词,返回直到句头词。vectorend_word_temp;for(int i =0; iword_pool.size(); i+)if(max=(word_pool.at(i).p_end)/是结尾词end_word_temp.push_back(i);int best_end_word=0;/初始化for(int i=1; i(word_pool.at(end_word_temp.at(best_end_word).plus_rate)best_end_word=i;int po
24、sition=end_word_temp.at(best_end_word);vectorword_complete;while(0!=(word_pool.at(position).p_begin)/往回找word_complete.push_back(word_pool.at(position).this_word);position=(word_pool.at(position).best;word_complete.push_back(word_pool.at(position).this_word);/最后一个/分词完成,每个词都放在word_complete里面 string co
25、mplete;for(int i=word_complete.size()-1; i=0; i-)/用空格分开,拼成成品 complete+=word_complete.at(i);if(0!=i)complete+= ;return complete;/返回 int main()/dic_init_test();/测试用dic_init();FILE *f_in;ofstream f_out(out_put);f_in = fopen(target, r);char ch1=0, ch2=0;string word, sentance, s_complete;ch1=fgetc(f_in);
26、if(EOF=ch1)coutfile id empty;ch2=fgetc(f_in);while(EOF!=ch1&EOF!=ch2)word.append(1, ch1);word.append(1, ch2);if(。=word)/一个句子s_complete.clear();s_complete=zdgl_fenci(sentance);s_complete+= 。 ;/加上“。”f_out0)/防止漏掉最后一句话s_complete.clear();s_complete=zdgl_fenci(sentance);s_complete+= 。 ;/加上“。”f_out0)/防止漏掉最
27、后一句话s_complete.clear();s_complete=zdgl_fenci(sentance);s_complete+= 。 ;/加上“。”f_outs_complete;/输出break;/*测试s_complete=zdgl_fenci(有意见分歧);s_complete+= 。 ;/加上“。”f_outs_complete;/输出*/fclose(f_in);f_out.close();return 0;5.实验总结:由于我的编程能力比较差,所以这个实验对我来说是个极大的挑战,最开始我甚至认为我绝对不能完成这项工作了,但是慢慢来一点一点的写,遇到问题上网查资料,实在不行换一
28、种方法,一点一点的调试,最终还是能写出来了。具体设计实现分次的时候,我完全没有头绪,想过用矩阵,但矩阵在确认最佳左邻词的时候不知道如何,遍历用链表,但是不知道切分点一致时不同的左邻词怎么连上去。网上查到了别人用有向图的做法(见附录),当时对我来说是极具诱惑力的,但是特别注意里面有一项代码雷同问题,我能查得到的别人也一定查得到吧,我这么想着,所以就放弃了这个念头,还是自己想吧,最后想出了用vector容器并通过遍历来解决,真是不容易。最后是大半夜写完的,程序跑出来我自己都要哭出来了,太不容易了。然后看看结果,第一句话和分词模板没有去掉空格前完全一样,又一次被感动了,看起来算圆满完成了。附录:网上
29、别人做的用有向图最大概率分词/ word.cpp : Defines the entry point for the console application./#include stdafx.h/ mympseg.cpp : 定义控制台应用程序的入口点。#include #include #include #include using namespace std;const int NODENUM=100;/最大节点数map mapWord2Prob;const int MaxWordLength=8;/词的最大长度const int MinWordLength=2;/词的最小长度float
30、probNODENUM;/每个节点的最大累计概率int prevNodeNODENUM;/每个节点的最优前趋节点const string strDelimiter= ;/分词分割符void LoadDict()mapWord2Prob有=0.018;mapWord2Prob有意=0.0005;mapWord2Prob意见=0.001;mapWord2Prob见=0.0002;mapWord2Prob分歧=0.0001;/词作为边struct edgeNodestring termText;/词 int start;/词的开始位置 int end;/词的结束位置 float prob;/词在语料
31、库中出现的频率或者概率 ;/分割位置作为点struct vexNodeint nSegNo; /分割节点编号list linkedlist; /与之相连的链表head;/存储节点信息vexNode adjlistNODENUM;/建立邻接表存储void InitialGraph()int i=0;for(i=0;iNODENUM;i+)adjlisti.nSegNo=i;/插入一条边void InsertEdge(edgeNode & newEdgeNode)int v1=newEdgeNode.end;adjlistv1.linkedlist.push_front(newEdgeNode);
32、/形成切分词图void CreateWordSegGraph(string s)short i=0;short j=0;short len=0;short restlen=0;short n=s.length();float freq=0;string w;for(j=0;jn;j+=2)for(len=2;len=MaxWordLength;len+=2)restlen=n-j;if (len=restlen) / 如果剩余词长度不够长,跳出循环w=s.substr(j,len);elsebreak;if (mapWord2Prob.find(w) != mapWord2Prob.end()
33、freq=mapWord2Probw;elsefreq=100;if(freq != 100)edgeNode stCandidateWord;stCandidateWord.termText=w;stCandidateWord.start=j/MinWordLength;stCandidateWord.end=(j+len)/MinWordLength;stCandidateWb = freq;cout插入一条边 word w freq stCandidateWb start stCandidateWord.start end stCandidateWord.endendl;InsertEdge(stCan
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024-2030年中国射频连接器行业发展分析及投资前景预测研究报告
- 2024-2030年中国宠物智能玩具行业消费需求与营销趋势预测报告
- 2024-2030年中国安全装置行业市场现状供需分析及市场深度研究发展前景及规划战略投资分析研究报告
- 2024-2030年中国存量房改造行业前景动态与发展趋势研究分析报告
- 2024-2030年中国女身模特行业市场运营模式及未来发展动向预测报告
- 2024-2030年中国太阳能热水器安项目可行性研究报告
- 2024-2030年中国大型相机行业市场发展趋势与前景展望战略分析报告
- 2024-2030年中国复方电解质葡萄糖注射液-M3B行业当前经济形势及投资建议研究报告
- 清远市清新区太平镇乡村公益性岗位人员招聘考试试题及答案
- 2022年晋中左权县事业单位招聘考试试题及答案
- MOOC 船舶电力拖动系统-大连海事大学 中国大学慕课答案
- 《阿Q正传》《边城》比较阅读课件15张-统编版高中语文选择性必修下册
- 台灯底座注塑模具设计
- 工业产品质量安全月风险评估与管控
- Unit1RelationshipsLesson1Teachers教学设计高二上学期英语北师大版选择性
- 性商课程培训课件
- 高中消防安全教育
- 打造鹰雁团队课件
- 如何识别质量风险并预防
- 铁路防雷及接地工程技术规范(TB 10180-2016)
- 基于单片机的老人防丢系统设计
评论
0/150
提交评论