算法課程設(shè)計中文分詞程序設(shè)計與實(shí)現(xiàn)

1、遼 寧 科 技 大 學(xué)課程設(shè)計說明書設(shè)計題目： 中文分詞程序設(shè)計與實(shí)現(xiàn) 學(xué)院、系： 裝備制造學(xué)院 專業(yè)班級： 計算機(jī)09（1）班 學(xué)生姓名： 高 祥 指導(dǎo)教師： 遲呈英 成 績： 2012年 3 月 2 日目 錄一 需求分析隨著國內(nèi)互聯(lián)網(wǎng)的迅猛發(fā)展，網(wǎng)絡(luò)信息量急劇膨脹，如果完全由人工來整理如此繁多的信息，那是難以想象的工作量，同時也不現(xiàn)實(shí)的，如何有效、快速、準(zhǔn)確的從大量的信息中找到我們所需要的信息，是擺在我們面前的一個重要和迫切的任務(wù)，為了解決這個難題，人們采用了中文分詞技術(shù)，通過分詞技術(shù)，就可以使得對海量信患的整理更準(zhǔn)確更合理，使得檢索結(jié)果更準(zhǔn)確，效率也會大幅度地提高。所謂中文分詞，就是把一

2、個漢語句子按照其中詞的含義進(jìn)行切分。隨羞人們更深入熬研究，中文信息處理技術(shù)得到了廣泛應(yīng)用，并對中文分詞技術(shù)的要求也越來越高。中文分詞技術(shù)已經(jīng)引起多方的關(guān)注，并成為中文信息處理的一個前沿課題l卜21。目前在自然語言處理技術(shù)中，中文處理技術(shù)遠(yuǎn)遠(yuǎn)落后于西文處理技術(shù)，許多西文的處理方法中文不能直接采用，就是因?yàn)橹形谋仨氝M(jìn)行分詞處理。中文分詞是其它中文信息處理的基礎(chǔ)，搜索弓|擎只是中文分詞的一個應(yīng)用，其它應(yīng)用比如機(jī)器翻譯(mt)、語音合成、自動分類、自動摘要、自動校對、中文文獻(xiàn)瘁全文檢索等翻，都需要焉到分詞。分詞準(zhǔn)確性對搜索弓|擎來說十分重要，但如果分詞速度太慢，即使準(zhǔn)確性再高，對于搜索引擎來說也是不可

3、用的，因?yàn)樗阉鞴璴擎需要處理數(shù)以億詩的網(wǎng)頁，如果分詞耗用的時間過長，會嚴(yán)重影響搜索引擎內(nèi)容更新的速度。因此對于搜索引擎來說，分詞的準(zhǔn)確性和速度，二者都需要達(dá)到很高的要求，中文分詞技術(shù)要想更好的服務(wù)予更多的產(chǎn)品，需要更多的專業(yè)隊伍投入到研究中來，因此，中文分詞的研究還是一個相當(dāng)長的探索過程。目前中文分詞得到了很多現(xiàn)實(shí)的應(yīng)用，主要體現(xiàn)在在信息檢索、同音字和多音字方面的識別、文本校對、簡體繁體的囪動轉(zhuǎn)換、自動標(biāo)引、自動文撬、視器翻譯、語言文字研究、搜索弓|擎研究、自然語言理解和中文信息處哈爾濱二程大學(xué)碩七學(xué)位論文理等方面m，也是中文智能計算技術(shù)發(fā)展的前提和基礎(chǔ)。隨著對中文分詞技術(shù)關(guān)注度的不斷提高，大

4、量的學(xué)者都加入到了這一研究領(lǐng)域，使中文分詞取得了豐碩的研究成果。近10年來，語言學(xué)界、人工智能領(lǐng)域和情報檢索界的學(xué)者們，在中文分詞與自動標(biāo)引的研究與實(shí)踐上進(jìn)行了大量的研究，找到了許多解決中文分詞的方法，目前關(guān)于中文分詞研究方法主要有三個方面，即基于字符串匹配的分詞方法、基于統(tǒng)計的分詞方法和基于理解的分詞方法。中文分詞的研究，主要是從詞層面進(jìn)行的研究，這一問題很早就受到了廣泛的關(guān)注。目前，各種分詞系統(tǒng)也不斷建立，分詞系統(tǒng)在運(yùn)行速度、準(zhǔn)確度等方面已經(jīng)具有了研究應(yīng)用的價值，但是在句子中詞該如何被界定，仍然是一個比較困難的問題，同時，在不同的應(yīng)用領(lǐng)域由于應(yīng)用需求的不同，需要達(dá)到的分詞效果有很大區(qū)別。詞

5、的確切概念難以標(biāo)準(zhǔn)化，詞的應(yīng)用領(lǐng)域不同，使得分詞規(guī)范難以統(tǒng)一，需要達(dá)到的分詞效果也有很大區(qū)別。在這一長期的研究和實(shí)踐過程中，分詞規(guī)范、歧義字段處理和未登錄詞識別成為困擾我們的主要技術(shù)難題，隨著計算機(jī)技術(shù)和漢語語言研究的發(fā)展，中文分詞技術(shù)將會有更大的突破。二 設(shè)計主要分為兩大模塊：一個建立一棵樹，一個是查詢。建樹有三個層次，第一層一維數(shù)組，第二層是數(shù)組，用于二分查找使用，第三層是二叉樹。查詢分為直接查詢第一層的一維數(shù)組，第二層用二分查找（第二層漢子相同的平均概率是26，一般第二字成詞切相同），第三層直接順序查找，以及查找句子中的數(shù)字和漢子標(biāo)點(diǎn)。 輸出：（1）建樹 包括：以此字開頭的詞語有幾個；在

6、一維數(shù)組中的中位置；結(jié)束 （2）查詢 包括輸出每個詞的首字。然后輸出分詞后的結(jié)果。輸入語句開始截取第一個字len2否len4否是第二層二分查找第三層 直接順序查找打印詞語結(jié)束三 編碼與調(diào)試因?yàn)樽址容^所需的時間同字符串的長度成正比，對于較長的詞條，這種現(xiàn)象尤為突出。為了消除這種冗余操作，我們提出將詞典的詞尾部分以自動機(jī)的形式來組織。為此，我們將組成單詞的每個字以一種鏈表節(jié)點(diǎn)的形式存儲，其抽象數(shù)據(jù)結(jié)構(gòu)的定義如下：struct node3 string s; bool isword; node3 *l,*r; node3(string s = ,bool isword = 0, node3 *l

7、 = 0, node3 *r = 0): s(s),isword(isword),l(l),r(r);struct node2 string s; bool isword; node3 *child; node2(string s =,bool isword = 0, node3* child =0): s(s),isword(isword),child(child);struct node string s; vectorv;vectordic;int binarysearch(int x, string sec)/二分查找第二個字 int l = 0,r = dicx.v.size() -

8、 1; while (l 1; if (dicx.vmid.s = sec) return mid; else if (dicx.vmid.s s = cc) return p; else p = p-l; return 0;四 結(jié)果分析截取每一個詞的第一個字講一段話拆分成詞的形式逐詞遍歷法將詞典中的所有詞按由長到短的順序在文章中逐字搜索,直至文章結(jié)束。也就是說,不管文章有多短,詞典有多大,都要將詞典遍歷一遍。這種方法效率比較低，大一點(diǎn)的系統(tǒng)一般都不使用。最大正向匹配法()通常簡稱為法。其基本思想為：假定分詞詞典中的最長詞有i個漢字字符，則用被處理文檔的當(dāng)前字串中的前i個字作為匹配字段，查找字

9、典。若字典中存在這樣的一個i字詞，則匹配成功，匹配字段被作為一個詞切分出來。如果詞典中找不到這樣的一個i字詞，則匹配失敗，將匹配字段中的最后一個字去掉，對剩下的字串重新進(jìn)行匹配處理如此進(jìn)行下去，直到匹配成功，即切分出一個詞或剩余字串的長度為零為止。這樣就完成了一輪匹配，然后取下一個i字字串進(jìn)行匹配處理，直到文檔被掃描完為止。當(dāng)然，最大匹配算法是一種基于分詞詞典的機(jī)械分詞法，不能根據(jù)文檔上下文的語義特征來切分詞語，對詞典的依賴性較大，所以在實(shí)際使用時，難免會造成一些分詞錯誤，為了提高系統(tǒng)分詞的準(zhǔn)確度，可以采用正向最大匹配法和逆向最大匹配法相結(jié)合的分詞方案（即雙向匹配法，見（四）。）全切分要求獲得

10、輸入序列的所有可接受的切分形式，而部分切分只取得一種或幾種可接受的切分形式，由于部分切分忽略了可能的其他切分形式，所以建立在部分切分基礎(chǔ)上的分詞方法不管采取何種歧義糾正策略，都可能會遺漏正確的切分，造成分詞錯誤或失敗。而建立在全切分基礎(chǔ)上的分詞方法，由于全切分取得了所有可能的切分形式，因而從根本上避免了可能切分形式的遺漏，克服了部分切分方法的缺陷。全切分算法能取得所有可能的切分形式，它的句子覆蓋率和分詞覆蓋率均為100%，但全切分分詞并沒有在文本處理中廣泛地采用，原因有以下幾點(diǎn)：1)全切分算法只是能獲得正確分詞的前提，因?yàn)槿蟹植痪哂衅缌x檢測功能，最終分詞結(jié)果的正確性和完全性依賴于獨(dú)立的歧義處

11、理方法，如果評測有誤，也會造成錯誤的結(jié)果。2)全切分的切分結(jié)果個數(shù)隨句子長度的增長呈指數(shù)增長，一方面將導(dǎo)致龐大的無用數(shù)據(jù)充斥于存儲數(shù)據(jù)庫；另一方面當(dāng)句長達(dá)到一定長度后，由于切分形式過多,造成分詞效率嚴(yán)重下降。并行分詞方法：這種分詞方法借助于一個含有分詞詞庫的管道進(jìn)行,比較匹配過程是分步進(jìn)行的,每一步可以對進(jìn)入管道中的詞同時與詞庫中相應(yīng)的詞進(jìn)行比較,由于同時有多個詞進(jìn)行比較匹配,因而分詞速度可以大幅度提高。這種方法涉及到多級內(nèi)碼理論和管道的詞典數(shù)據(jù)結(jié)構(gòu)。（詳細(xì)算法可以參考吳勝遠(yuǎn)的并行分詞方法的研究。）五 參考文獻(xiàn)1 國家技術(shù)監(jiān)督局信息處理用現(xiàn)代漢語分詞規(guī)范，中華人民共和國國家標(biāo)準(zhǔn)gbt13715

12、92中國標(biāo)準(zhǔn)出版社，19932 碩士學(xué)位論文.中文自動分詞系統(tǒng)的研究與實(shí)現(xiàn). 周程遠(yuǎn) 200911013碩士學(xué)位論文 .基于條件隨機(jī)場的中文分詞研究與應(yīng)用, 顏軍 200904014 網(wǎng)絡(luò)文章中文分詞入門之最大匹配法 發(fā)表于 2009年01月12號 由 52nlp 5一種基于自動機(jī)的分詞方法.鞍山科技大學(xué).計算機(jī)學(xué)院,東北大學(xué).信息學(xué)院 遲呈英，戰(zhàn)學(xué)剛, 姚天順6種中文分詞算法優(yōu)劣比較，http：wwwhtmldatacn?p=248六 總結(jié)分詞是中文自然語言處理的基礎(chǔ)，在現(xiàn)實(shí)中已經(jīng)得到廣泛應(yīng)用。比如，google的chrome瀏覽器就內(nèi)置了中文分詞功能。如上圖，我們可以注意到，在chrome

13、中雙擊無鏈接文本時，chrome選中的不是一個字，也不是一句話，而是一個詞。當(dāng)然，中文分詞在數(shù)據(jù)挖掘等方面的應(yīng)用就更加明顯了。掌握自然語言處理的基本知識，已經(jīng)成為it行業(yè)對計算機(jī)專業(yè)學(xué)生的基本要求。雖然我曾經(jīng)系統(tǒng)學(xué)習(xí)過算法數(shù)據(jù)結(jié)構(gòu)等基礎(chǔ)課程，但編寫程序時仍然遇到了很多問題，僅在漢字編碼的問題上就糾纏了很久。幸而在很多細(xì)致的文檔論文的幫助下，使我對分詞程序有了更深的了解。也懂得了算法也需要團(tuán)結(jié)合作才能效率更高。加深了我對各種算法的了解，增強(qiáng)了我的功底。自然語言處理是一個正在快速發(fā)展的學(xué)科，但愿我有朝一日能在這個領(lǐng)域大顯身手。七 附錄（程序源代碼）#include #include #includ

14、e #include using namespace std;const int start1 = 0xb0,start2 = 0xa1, end1 = 0xf8,end2 = 0xff;const int maxwordlen = 48;ifstream fin(segdict.txt);ofstream out(out1.txt);/- 建樹部分-struct node3 string s; bool isword; node3 *l,*r; node3(string s = ,bool isword = 0, node3 *l = 0, node3 *r = 0): s(s),iswor

15、d(isword),l(l),r(r);struct node2 string s; bool isword; node3 *child; node2(string s =,bool isword = 0, node3* child =0): s(s),isword(isword),child(child);struct node string s; vectorv;vectordic;const range =(end1 - start1)*(end2 - start2);/一維數(shù)組范圍int arrayrange;/一維數(shù)組代替哈希表void begin() /初始化 for (int i

16、 = 0; i l != 0) last = last-l; if (last-s != t) last-l = new node3(t,(len = 2),0, 0); last = last-l; if (len 2) buildtree(s.substr(2,maxwordlen),last-r);void dictionary() /構(gòu)造整個結(jié)構(gòu) begin(); string s; int n,k = 0; while(fin s) node n; n.s = s.substr(0,2); int m1 = (unsigned char)s0 - start1)*(unsigned

17、char)s1 - start2)+(unsigned char)s0 - start1; arraym1 = k+; out s arraym1 n; out n endl; for (int i = 0; i s; out s 0 & n.vsize-1.s != t) n.v.push_back(node2(t, (len = 4),0); size = n.v.size(); if (len 4) buildtree(s.substr(4,maxwordlen),n.vsize-1.child); dic.push_back(n); out end array endl endl;/-

18、查詢部分-vectordest;int binarysearch(int x, string sec)/二分查找第二個字 int l = 0,r = dicx.v.size() - 1; while (l 1; if (dicx.vmid.s = sec) return mid; else if (dicx.vmid.s s = cc) return p; else p = p-l; return 0;unsigned chartoint(char c) return unsigned(unsigned char)c) ;bool iscc(char c) unsigned val= char

19、toint(c); return val = start1 & val end1;bool isec(char c) unsigned val= chartoint(c); return val 0x80;void findnum(string src, vector&dest, int &starpos,int &endpos) int strlen = src.length(); while (endpos starpos) dest.push_back(src.substr(starpos,endpos-starpos); starpos = endpos; void segment(s

20、tring src, vector&dest) int strlen = src.length(); int startpos = 0, endpos; while (startpos = strlen) return ; unsigned seglen = 2; string headcc = src.substr(startpos, 2); cout headcc endl = 0); string seccc = src.substr(startpos + 2,2); if (seccc.length() 0 & iscc(seccc0) int b2 = binarysearch(headindex,seccc); if (b2=0) if (dicheadindex.vb2.isword) seglen += 2; endpos = startpos + 4; node3 *p =