自然語(yǔ)言處理NPL-最大概率分詞算法

1、精選優(yōu)質(zhì)文檔-傾情為你奉上NLP基于最大概率的漢語(yǔ)切分Ytinrete要求：基于最大概率的漢語(yǔ)切分目標(biāo)：采用最大概率法進(jìn)行漢語(yǔ)切分。 其中：n-gram用bigram，平滑方法至少用Laplace平滑。輸入：接收一個(gè)文本，文本名稱為：corpus_for_test.txt輸出：切分結(jié)果文本，其中：切分表示：用一個(gè)字節(jié)的空格“ ”分隔，如：我們 在 學(xué)習(xí) 。 每個(gè)標(biāo)點(diǎn)符號(hào)都單算一個(gè)切分單元。輸出文件名為：學(xué)號(hào).txtBigram參數(shù)訓(xùn)練語(yǔ)料：corpus_for_train.txt注：請(qǐng)嚴(yán)格按此格式輸出，以便得到正確評(píng)測(cè)結(jié)果切分性能評(píng)價(jià)：分切分結(jié)果評(píng)測(cè)F*100, F=2P*R/(P+R)特別注

2、意:代碼雷同問(wèn)題本次作業(yè)最后得分會(huì)綜合考慮：切分性能、代碼、文檔等幾個(gè)方面。第三次作業(yè)上交的截止時(shí)間：2014 年1月7日24:00 1.關(guān)于最大概率分詞基本思想是：一個(gè)待切分的漢字串可能包含多種分詞結(jié)果，將其中概率最大的作為該字串的分詞結(jié)果。根據(jù)：由于語(yǔ)言的規(guī)律性，句子中前面出現(xiàn)的詞對(duì)后面可能出現(xiàn)的詞有很強(qiáng)的預(yù)示作用。公式1：其中 w表示詞， s表示待切分字符串。公式2：例如：S：有意見(jiàn)分歧W1: 有/ 意見(jiàn)/ 分歧/W2: 有意/ 見(jiàn)/ 分歧/P(W1)=P(有)×P(意見(jiàn))×P(分歧) 1.8*10-9P(W2)=P(有意)×P(見(jiàn))×P(分歧)

3、1*10-11P(W1)> P(W2)所以選擇 W1歷史信息過(guò)長(zhǎng)，計(jì)算存在困難p(wi|w1w2wi-1)為了便于計(jì)算，通常考慮的歷史不能太長(zhǎng)，一般只考慮前面n-1個(gè)詞構(gòu)成的歷史。即： p(wi|wi-n+1wi-1)n-gramn 較大時(shí)：􀂄 提供了更多的語(yǔ)境信息，語(yǔ)境更具區(qū)別性。但是，參數(shù)個(gè)數(shù)多、計(jì)算代價(jià)大、訓(xùn)練語(yǔ)料需要多、參數(shù)估計(jì)不可靠。n 較小時(shí)：􀂄 語(yǔ)境信息少，不具區(qū)別性。但是，參數(shù)個(gè)數(shù)少、計(jì)算代價(jià)小、訓(xùn)練語(yǔ)料，無(wú)需太多、參數(shù)估計(jì)可靠。題目要求使用bigram，即考慮前一個(gè)詞，即考慮左鄰詞。左鄰詞假設(shè)對(duì)字串從左到右進(jìn)行掃描，可以得到w1 ,w

4、2 ,wi-1 wi,等若干候選詞，如果wi-1 的尾字跟wi 的首字鄰接，就稱wi-1 為wi 的左鄰詞。比如上面例中，候選詞“有”就是候選詞“意見(jiàn)”的左鄰詞，“意見(jiàn)”和“見(jiàn)”都是“分歧”的左鄰詞。字串最左邊的詞沒(méi)有左鄰詞。最佳左鄰詞如果某個(gè)候選詞wi 有若干個(gè)左鄰詞wj ， wk ,等等，其中累計(jì)概率最大的候選詞稱為wi 的最佳左鄰詞。比如候選詞“意見(jiàn)”只有一個(gè)左鄰詞“有”，因此，“有”同時(shí)也就是“意見(jiàn)”的最佳左鄰詞；候選詞“分歧”有兩個(gè)左鄰詞“意見(jiàn)”和“見(jiàn)”，其中“意見(jiàn)”的累計(jì)概率大于“見(jiàn)”累計(jì)概率，因此“意見(jiàn)”是“分歧”的最佳左鄰詞。數(shù)據(jù)稀疏問(wèn)若某n-gram在訓(xùn)練語(yǔ)料中沒(méi)有出現(xiàn),則該

5、n-gram的概率必定是0。解決的辦法是擴(kuò)大訓(xùn)練語(yǔ)料的規(guī)模。但是無(wú)論怎樣擴(kuò)大訓(xùn)練語(yǔ)料，都不可能保證所有的詞在訓(xùn)練語(yǔ)料中均出現(xiàn)。由于訓(xùn)練樣本不足而導(dǎo)致所估計(jì)的分布不可靠的問(wèn)題，稱為數(shù)據(jù)稀疏問(wèn)題。在NLP領(lǐng)域中，數(shù)據(jù)稀疏問(wèn)題永遠(yuǎn)存在，不太可能有一個(gè)足夠大的訓(xùn)練語(yǔ)料，因?yàn)檎Z(yǔ)言中的大部分詞都屬于低頻詞。解決辦法: 平滑技術(shù)􀂄 把在訓(xùn)練樣本中出現(xiàn)過(guò)的事件的概率適當(dāng)減小。􀂄 把減小得到的概率密度分配給訓(xùn)練語(yǔ)料中沒(méi)有出現(xiàn)過(guò)的事件。􀂄 這個(gè)過(guò)程有時(shí)也稱為discounting(減值)。目前已經(jīng)提出了很多數(shù)據(jù)平滑技術(shù)，如：􀂄 Add-one

6、 平滑􀂄 Add-delta 平滑􀂄 Witten-Bell平滑􀂄 Good-Turing平滑􀂄 Church-Gale平滑􀂄 Jelinek-Mercer平滑􀂄 Katz平滑這里我使用laplace平滑Add-one 平滑(Laplaces law)規(guī)定任何一個(gè)n-gram在訓(xùn)練語(yǔ)料至少出現(xiàn)一次（即規(guī)定沒(méi)有出現(xiàn)過(guò)的n-gram在訓(xùn)練語(yǔ)料中出現(xiàn)了一次）。沒(méi)有出現(xiàn)過(guò)的n-gram的概率不再是0。2.算法描述1)對(duì)一個(gè)待分詞的字串S，按照從左到右的順序取出全部候選詞w1 ,w2 ,wi-1

7、wi, wn；2) 到詞典中查出每個(gè)候選詞的概率值P(wi)，當(dāng)候選詞沒(méi)有出現(xiàn)時(shí)，由laplace平滑設(shè)其概率為1/(字典數(shù)+1)，記錄每個(gè)候選詞的全部左鄰詞；3) 按照公式1計(jì)算每個(gè)候選詞的累計(jì)概率，同時(shí)比較得到每個(gè)候選詞的最佳左鄰詞；4) 如果當(dāng)前wn是字串S的尾詞，且累計(jì)概率P(wn)最大， wn就是S的終點(diǎn)詞。5) 從wn開(kāi)始，按照從右到左的順序，依次將每個(gè)詞的最佳左鄰詞輸出，即為S的分詞結(jié)果。3. 程序設(shè)計(jì)整個(gè)程序我分為兩個(gè)階段，字典生成階段和分詞階段。(make_dic.cpp)字典生成：目標(biāo)：輸入為訓(xùn)練語(yǔ)料(corpus_for_train.txt)，輸出為字典(dic.txt)

8、，字典內(nèi)容為單詞和單詞出現(xiàn)在字典中的頻率，首行為詞典總詞數(shù)。實(shí)現(xiàn)步驟：首先讀入訓(xùn)練，通過(guò)空格和換行符作為判定，分出單個(gè)單詞。若單詞沒(méi)有在字典中出現(xiàn)，則將其加入字典，單詞自身頻數(shù)加一，單詞總數(shù)加一；若單詞在字典中出現(xiàn)，則單詞自身頻數(shù)加一。將數(shù)據(jù)存入map中，然后再遍歷map，創(chuàng)建一個(gè)輸出流，輸出為字典文件，數(shù)據(jù)為具體單詞和他的出現(xiàn)概率（自身頻數(shù)/單詞總數(shù)）。(zdgl_fenci.cpp)分詞：目標(biāo)：輸入為字典和待切分語(yǔ)料（利用kill_space先將老師預(yù)先存好的待切分語(yǔ)料的空格和換行刪去，成為為切分語(yǔ)料target.txt），輸出為切分好的語(yǔ)料（.txt）。實(shí)現(xiàn)步驟：首先在主函數(shù)中，循環(huán)取出

9、待切分語(yǔ)料的每個(gè)句子，將句子傳給分詞子程序，分詞子程序處理后返回分好的句子，將句子輸出到文件，再取下一句，依次循環(huán)，直到處理完為止。分詞子程序，處理過(guò)程分為三步：1. 將待切分的句子切成備選的切分詞，并放在“單詞池”中，切分標(biāo)準(zhǔn)參考一個(gè)假定的單詞最大長(zhǎng)度，程序里面我設(shè)置成20，也就是單詞最長(zhǎng)10個(gè)漢字（可以根據(jù)詞典來(lái)決定），具體切分我考慮了兩種，不同之處體現(xiàn)在對(duì)取到的單詞（從一個(gè)漢字到10個(gè)漢字遍歷地?。?，若不出現(xiàn)在詞典中（出現(xiàn)在詞典中的肯定會(huì)列入），第一種做法是只保留單個(gè)漢字形成的單詞，另一種做法是保留全部的可能性。若采取第一種則效率會(huì)有很大的提高，但理論上會(huì)降低準(zhǔn)確性，第二種雖然能夠考慮到

10、所有的情況，但是數(shù)據(jù)往往是前一種的幾十倍，而且對(duì)于句子中很多單詞都有在詞典時(shí)，分詞結(jié)果幾乎和前一種相同，如果句子中的所有詞都能在詞典中時(shí)，分詞結(jié)果就一樣了（laplace平滑使得未出現(xiàn)的概率是最低的，乘積也會(huì)最低，所以不會(huì)選擇未出現(xiàn)的詞），但會(huì)多出幾十倍的運(yùn)算。兩種的代碼我都寫(xiě)出來(lái)了，考慮實(shí)際，我覺(jué)得第一種比較妥當(dāng)，第二種我注釋起來(lái)。2. 對(duì)“單詞池”操作，通過(guò)循環(huán)的遍歷，直到計(jì)算出所有的最佳左鄰詞。3. 在“單詞池”中找出所有的句尾詞，找到概率最大的，再通過(guò)左鄰詞，往回找，直到找到句頭詞，將這些詞用空格分開(kāi)，返回。4. 程序源碼：1.kill_space.cpp將待切分文本corpus_fo

11、r_test.txt變成不含空格和換行的待切分文本target.txt#include<iostream>#include<fstream>#include<map> #include<string>/*Name: 刪除空格 Description: 刪除空格 */using namespace std;int main()FILE *f_in, *f_out;/輸入輸出文件 char ch;f_in=fopen("corpus_for_test.txt", "r");f_out=fopen("t

12、arget.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讀入訓(xùn)練預(yù)料corpus_for_train.txt輸出詞典文件 dic.txt#include<iostream>#include<stdio.h>#include<fstream>#include<map>#include<s

13、tring>using namespace std;const char *train_text = "corpus_for_train.txt"/訓(xùn)練文件 const char *dic_text = "dic.txt"/輸出詞典文件 map <string, int> dic;/詞典表map <string, int>:iterator dic_it;/map<string, double> dic_in_text;/test int main()FILE *f_in;f_in=fopen(train_tex

14、t, "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);if("。"=word)word.clear();else/單詞結(jié)束 if(" "=word|0=word.size()word.clear();ch=fgetc(f_in);cont

15、inue;dic_it=dic.find(word);if(dic_it!=dic.end()/找到 dic_it->second=dic_it->second+1;word.clear();else/新單詞count+;dic.insert(pair<string,int>(word,1); word.clear();ch=fgetc(f_in);/if('n'=ch)/吸收換行/ch=fgetc(f_in);f_out<<count<<endl;dic_it=dic.begin();while(dic_it!=dic.end(

16、)f_out<<dic_it->first<<endl;rate=(double)(dic_it->second)/count;f_out<<rate<<endl;dic_it+;f_out.close();fclose(f_in);/*測(cè)試用 ifstream file(dic_text);int count_text;file>>count_text;string word_text;double rate_text;for(int i=0; i<count_text; i+)file>>word_t

17、ext;file>>rate_text;dic_in_text.insert(pair<string,double>(word_text,rate_text); file.close();*/return 0;3. zdgl_fenci.cpp讀入詞典dic.txt和帶切分文本target.txt輸出分詞結(jié)果.txt#include<iostream>#include<stdio.h>#include<fstream>#include<map>#include<string>#include<vector

18、>#include<stack>using namespace std;const char *target = "target.txt"/輸入文件const char *out_put= ".txt"/輸出文件 const char *dic_text = "dic.txt"/輸入詞典文件 const int max_word=20;/假設(shè)一個(gè)詞最長(zhǎng)包括10個(gè)漢字double laplace ;/laplace平滑map<string, double> dic;/詞典map <string, do

19、uble>:iterator dic_it; typedef struct word_pre/單詞池內(nèi)元素int num;/標(biāo)記int p_begin;/起始位置int p_end;/結(jié)束位置double word_rate;/單詞本身概率double plus_rate;/單詞累進(jìn)概率int best;/最佳左鄰詞string this_word;/詞本身word_pre;void dic_init_test(void)/測(cè)試用int count_text=;laplace = (double)1/(count_text+1);dic.insert(pair<string,dou

20、ble>("有",0.018); dic.insert(pair<string,double>("有意",0.0005); dic.insert(pair<string,double>("意見(jiàn)",0.001); dic.insert(pair<string,double>("見(jiàn)",0.0002); dic.insert(pair<string,double>("分歧",0.0001); void dic_init(void)/初始化詞典ifs

21、tream file(dic_text);int count_text;file>>count_text;laplace = (double)1/(count_text+1);string word_text;double rate_text;for(int i=0; i<count_text; i+)file>>word_text;file>>rate_text;dic.insert(pair<string,double>(word_text,rate_text); file.close();string zdgl_fenci(strin

22、g sentance)/最大概率分詞，輸入為不帶“?！钡木渥?，輸出為分好的句子if(sentance.size()<=2)return sentance;/單個(gè)字直接返回int min=0, max=sentance.size()-1;/單詞位置標(biāo)記/第一步建立單詞池vector<word_pre>word_pool;/單詞池int word_pre_num=0;/stack<int>word_link;string temp_word;/第一種方法，對(duì)于未出現(xiàn)詞，只保存單個(gè)字for(int i=0; i<=max; i+=2)temp_word.clear

23、();for(int j=i; j<=max&&j<max_word+i; j+=2)temp_word.append(1, sentance.at(j);temp_word.append(1, sentance.at(j+1);dic_it=dic.find(temp_word);if(dic_it!=dic.end()|j=i)/有記錄，或是第一個(gè)詞word_pre w_pre;word_pre_num+;w_pre.num=word_pre_num;if(dic_it!=dic.end()w_pre.word_rate=dic_it->second;el

24、sew_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);/入池/第二種方法，記錄所有可能情況/*/嚴(yán)格全部入池for(int i=0; i<=max; i+=2)temp_word.clear();for(int j=i;

25、j<=max&&j<max_word+i; j+=2)temp_word.append(1, sentance.at(j);temp_word.append(1, sentance.at(j+1);/入池word_pre_num+;word_pre w_pre;w_pre.num=word_pre_num;dic_it=dic.find(temp_word);if(dic_it!=dic.end()w_pre.word_rate=dic_it->second;elsew_pre.word_rate=laplace;if(0=i)w_pre.plus_rate=

26、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);/入池*/第二步計(jì)算最佳左鄰詞bool fail=true;/標(biāo)記while(fail)fail=false;for(int i=0; i<word_pool.size(); i+)/遍歷整個(gè)單詞池if(-1=(word_pool.at(i).best)/沒(méi)有算出左鄰詞int

27、 p_begin_temp=(word_pool.at(i).p_begin;vector<int>best_word_temp;/計(jì)算最佳左鄰詞用for(int j=0; j<word_pool.size(); j+)/遍歷整個(gè)單詞池if(p_begin_temp=(word_pool.at(j).p_end+1)/再考慮范圍內(nèi)if(-1=(word_pool.at(j).best)/考慮的左鄰詞本身數(shù)據(jù)不全fail=true;/標(biāo)記未完成best_word_temp.clear();break;/跳出循環(huán)else/best_word_temp.push_back(j);/

28、記錄if(0!=best_word_temp.size()/所有備選項(xiàng)資料完備int max_p=0;/best_word_temp序號(hào)for(int k=1; k<best_word_temp.size(); k+)/遍歷，找到概率最大的if(word_pool.at(best_word_temp.at(k).plus_rate>(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(

29、i).plus_rate=(word_pool.at(i).word_rate)*(word_pool.at(best_word_temp.at(max_p).plus_rate);/第三步，選出最佳句尾詞，并通過(guò)最佳左鄰詞，返回直到句頭詞。vector<int>end_word_temp;for(int i =0; i<word_pool.size(); i+)if(max=(word_pool.at(i).p_end)/是結(jié)尾詞end_word_temp.push_back(i);int best_end_word=0;/初始化for(int i=1; i<end_

30、word_temp.size(); i+)if(word_pool.at(end_word_temp.at(i).plus_rate>(word_pool.at(end_word_temp.at(best_end_word).plus_rate)best_end_word=i;int position=end_word_temp.at(best_end_word);vector<string>word_complete;while(0!=(word_pool.at(position).p_begin)/往回找word_complete.push_back(word_pool.

31、at(position).this_word);position=(word_pool.at(position).best;word_complete.push_back(word_pool.at(position).this_word);/最后一個(gè)/分詞完成，每個(gè)詞都放在word_complete里面 string complete;for(int i=word_complete.size()-1; i>=0; i-)/用空格分開(kāi)，拼成成品 complete+=word_complete.at(i);if(0!=i)complete+=" "return compl

32、ete;/返回 int main()/dic_init_test();/測(cè)試用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);if(EOF=ch1)cout<<"file id empty"ch2=fgetc(f_in);while(EOF!=ch1&&EOF!=ch2)word.append(1,

33、 ch1);word.append(1, ch2);if("。"=word)/一個(gè)句子s_complete.clear();s_complete=zdgl_fenci(sentance);s_complete+=" 。 "/加上“?！眆_out<<s_complete;/輸出sentance.clear();/還原else/不是一個(gè)句子sentance+=word;word.clear();/還原ch1=fgetc(f_in);if(EOF=ch1)if(sentance.size()>0)/防止漏掉最后一句話s_complete.cl

34、ear();s_complete=zdgl_fenci(sentance);s_complete+=" 。 "/加上“。”f_out<<s_complete;/輸出break;ch2=fgetc(f_in);if(EOF=ch2)if(sentance.size()>0)/防止漏掉最后一句話s_complete.clear();s_complete=zdgl_fenci(sentance);s_complete+=" 。 "/加上“?！眆_out<<s_complete;/輸出break;/*測(cè)試s_complete=zdg

35、l_fenci("有意見(jiàn)分歧");s_complete+=" 。 "/加上“?！眆_out<<s_complete;/輸出*/fclose(f_in);f_out.close();return 0;5.實(shí)驗(yàn)總結(jié)：由于我的編程能力比較差，所以這個(gè)實(shí)驗(yàn)對(duì)我來(lái)說(shuō)是個(gè)極大的挑戰(zhàn)，最開(kāi)始我甚至認(rèn)為我絕對(duì)不能完成這項(xiàng)工作了，但是慢慢來(lái)一點(diǎn)一點(diǎn)的寫(xiě)，遇到問(wèn)題上網(wǎng)查資料，實(shí)在不行換一種方法，一點(diǎn)一點(diǎn)的調(diào)試，最終還是能寫(xiě)出來(lái)了。具體設(shè)計(jì)實(shí)現(xiàn)分次的時(shí)候，我完全沒(méi)有頭緒，想過(guò)用矩陣，但矩陣在確認(rèn)最佳左鄰詞的時(shí)候不知道如何，遍歷用鏈表，但是不知道切分點(diǎn)一致時(shí)不同的左

36、鄰詞怎么連上去。網(wǎng)上查到了別人用有向圖的做法(見(jiàn)附錄)，當(dāng)時(shí)對(duì)我來(lái)說(shuō)是極具誘惑力的，但是特別注意里面有一項(xiàng)代碼雷同問(wèn)題，我能查得到的別人也一定查得到吧，我這么想著，所以就放棄了這個(gè)念頭，還是自己想吧，最后想出了用vector容器并通過(guò)遍歷來(lái)解決，真是不容易。最后是大半夜寫(xiě)完的，程序跑出來(lái)我自己都要哭出來(lái)了，太不容易了。然后看看結(jié)果，第一句話和分詞模板沒(méi)有去掉空格前完全一樣，又一次被感動(dòng)了，看起來(lái)算圓滿完成了。附錄：網(wǎng)上別人做的用有向圖最大概率分詞/ word.cpp : Defines the entry point for the console application./#include

37、"stdafx.h"/ mympseg.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。#include <iostream>#include <string>#include <list>#include <map>using namespace std;const int NODENUM=100;/最大節(jié)點(diǎn)數(shù)map <string,float> mapWord2Prob;const int MaxWordLength=8;/詞的最大長(zhǎng)度const int MinWordLength=2;/詞的最小長(zhǎng)度f(wàn)loat pro

38、bNODENUM;/每個(gè)節(jié)點(diǎn)的最大累計(jì)概率int prevNodeNODENUM;/每個(gè)節(jié)點(diǎn)的最優(yōu)前趨節(jié)點(diǎn)const string strDelimiter=" "/分詞分割符void LoadDict()mapWord2Prob"有"=0.018;mapWord2Prob"有意"=0.0005;mapWord2Prob"意見(jiàn)"=0.001;mapWord2Prob"見(jiàn)"=0.0002;mapWord2Prob"分歧"=0.0001;/詞作為邊struct edgeNodes

39、tring termText;/詞 int start;/詞的開(kāi)始位置 int end;/詞的結(jié)束位置 float prob;/詞在語(yǔ)料庫(kù)中出現(xiàn)的頻率或者概率 ;/分割位置作為點(diǎn)struct vexNodeint nSegNo; /分割節(jié)點(diǎn)編號(hào)list <edgeNode> linkedlist; /與之相連的鏈表head;/存儲(chǔ)節(jié)點(diǎn)信息vexNode adjlistNODENUM;/建立鄰接表存儲(chǔ)void InitialGraph()int i=0;for(i=0;i<NODENUM;i+)adjlisti.nSegNo=i;/插入一條邊void InsertEdge(ed

40、geNode & newEdgeNode)int v1=newEdgeNode.end;adjlistv1.linkedlist.push_front(newEdgeNode);/形成切分詞圖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;j<n;j+=2)for(len=2;len<=MaxWordLength;len+=2)restlen=n-j;if (len

41、<=restlen) / 如果剩余詞長(zhǎng)度不夠長(zhǎng)，跳出循環(huán)w=s.substr(j,len);elsebreak;if (mapWord2Prob.find(w) != mapWord2Prob.end()freq=mapWord2Probw;elsefreq=100;if(freq != 100)edgeNode stCandidateWord;stCandidateWord.termText=w;stCandidateWord.start=j/MinWordLength;stCandidateWord.end=(j+len)/MinWordLength;stCandidateWord.

42、prob = freq;cout<<"插入一條邊 word "<<w<<" freq "<<stCandidateWb<<" start "<<stCandidateWord.start<<" end "<<stCandidateWord.end<<endl;InsertEdge(stCandidateWord);/尋找i的最佳前趨詞void getPrev(int i)vexNode oVexNode=adjlisti;edgeNode oEdgeNode;list <edgeNode>:iterator itList;/得到前驅(qū)詞的集合 float maxProb = 0; int maxNode = -1; /根據(jù)前驅(qū)詞集合挑選最佳前趨節(jié)點(diǎn) for(itList=oVexNode.linkedlist.begin(); itList!=oVexNode.linkedlist.end();itList+ ) float nodeProb =