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

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：13 大?。?9.50KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩12頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　課程設(shè)計說明書　　設(shè)計題目：中文分詞程序設(shè)計與實(shí)現(xiàn) 　　學(xué)院、系：裝備制造學(xué)院 　　專業(yè)班級：計算機(jī)09（1）班 　　學(xué)生姓名：

2、 　　指導(dǎo)教師： 　　成績： 　　2012年 3 月 2 日　　目錄

3、;　　需求分析　　隨著國內(nèi)互聯(lián)網(wǎng)的迅猛發(fā)展，網(wǎng)絡(luò)信息量急劇膨脹，如果完全由人工來整理如此繁多的信息，那是難以想象的工作量，同時也不現(xiàn)實(shí)的，如何有效、快速、準(zhǔn)確的從大量的信息中找到我們所需要的信息，是擺在我們面前的一個重要和迫切的任務(wù)，為了解決這個難題，人們采用了中文分詞技術(shù)，通過分詞技術(shù)，就可以使得對海量信患的整理更準(zhǔn)確更合理，使得檢索結(jié)果更準(zhǔn)確，效率也會大幅度地提高。所謂中

4、文分詞，就是把一個漢語句子按照其中詞的含義進(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)、

5、語音合成、自動分類、自動摘要、自動校對、中文文獻(xiàn)瘁全文檢索等翻，都需要焉到分詞。分詞準(zhǔn)確性對搜索弓|擎來說十分重要，但如果分詞速度太慢，即使準(zhǔn)確性再高，對于搜索引擎來說也是不可用的，因?yàn)樗阉鞴璴擎需要　　目前中文分詞得到了很多現(xiàn)實(shí)的應(yīng)用，主要體現(xiàn)在在信息檢索、同音字和多音字方面的識別、文本校對、簡體繁體的囪動轉(zhuǎn)換、自動標(biāo)引、自動文撬、視器翻譯、語言文字研究、搜索弓|擎研究、自然語言理解和中文信息

6、處哈爾濱]二程大學(xué)碩七學(xué)位論文理等方面M，也是中文智能計算技術(shù)發(fā)展的前提和基礎(chǔ)。隨著對中文分詞技術(shù)關(guān)注度的不斷提高，大量的學(xué)者都加入到了這一研究領(lǐng)域，使中文分詞取得了豐碩的研究成果。近10年來，語言學(xué)界、人工智能領(lǐng)域和情報檢索界的學(xué)者們，在中文分詞與自動標(biāo)引的研究與實(shí)踐上進(jìn)行了大量的研究，找到了許多解決中文分詞的方法，目前關(guān)于中文分詞研究方法主要有三個方面，即基于字符串匹配的分詞方法、基于統(tǒng)計的分詞方法和基于理解的分詞方法。中文分詞的研

7、究，主要是從詞層面進(jìn)行的研究，這一問題很早就受到了廣泛的關(guān)注。目前，各種分詞系統(tǒng)也不斷建立，分詞系統(tǒng)在運(yùn)行速度、準(zhǔn)確度等方面已經(jīng)具有了研究應(yīng)用的價值，但是在句子中詞該如何被界定，仍然是一個比較困難的問題，同時，在不同的應(yīng)用領(lǐng)域由于應(yīng)用需求的不同，需要達(dá)到的分詞效果有很大區(qū)別。詞的確切概念難以標(biāo)準(zhǔn)化，詞的應(yīng)用領(lǐng)域不同，使得分詞規(guī)范難以統(tǒng)一，需要達(dá)到的分詞效果也有很大　　設(shè)計<

8、;/b>　　主要分為兩大模塊：　　一個建立一棵樹，一個是查詢。建樹有三個層次，第一層一維數(shù)組，第二層是數(shù)組，用于二分查找使用，第三層是二叉樹。查詢分為直接查詢第一層的一維數(shù)組，第二層用二分查找（第二層漢子相同的平均概率是26，一般第二字成詞切相同），第三層直接順序查找，以及查找句子中的數(shù)字和漢子標(biāo)點(diǎn)。</

9、p>　　輸出：（1）建樹包括：以此字開頭的詞語有幾個；在一維數(shù)組中的中位置；結(jié)束　?。?）查詢包括輸出每個詞的首字。然后輸出分詞后的結(jié)果。　　編碼與調(diào)試　　因?yàn)樽址容^所需的時間同字符串的長度成正比，對于較長的詞條，這種現(xiàn)象尤為突出。為了消除

10、這種冗余操作，我們提出將詞典的詞尾部分以自動機(jī)的形式來組織。為此，我們將組成單詞的每個字以一種鏈表節(jié)點(diǎn)的形式存儲，其抽象數(shù)據(jù)結(jié)構(gòu)的定義如下：　　struct Node3　　{　　string S;

11、　　bool IsWord;　　Node3 *L,*R;　　Node3(string s = "",bool isWord = 0, Node3 *l = 0, Node3 *r = 0):　　S(s),IsWord(isWord),L(l),R(r){}<p&g

12、t;　　};　　struct Node2　　{　　string S;　　bool IsWord;　　Node3 *C

13、hild;　　Node2(string s ="",bool isWord = 0, Node3* child =0):　　S(s),IsWord(isWord),Child(child){}　　};　　struc

14、t Node　　{　　string S;　　vector<Node2>v;　　};　　vector<

15、;Node>Dic;　　int BinarySearch(int x, string Sec)//二分查找第二個字　　{　　int L = 0,R = Dic[x].v.size() - 1;　　while (L <= R

16、)　　{　　int mid = (L + R) >> 1;　　if (Dic[x].v[mid].S == Sec)　　return mid;　　else if (Dic[x].

17、v[mid].S < Sec)　　L = mid + 1;　　else R = mid - 1;　　}　　return -1;　　}</p&

18、gt;　　Node3* RemainSearch(Node3*p, string cc) //順序查找剩下的字　　{　　while (p != 0)　　{　　if (p-

19、>S == cc)　　return p;　　else　　p = p->L;　　}&l

20、t;p>　　return 0;　　}　　結(jié)果分析　　截取每一個詞的第一個字　　講一段話拆分成詞的形式　　逐詞遍

21、歷法將詞典中的所有詞按由長到短的順序在文章中逐字搜索,直至文章結(jié)束。也就是說,不管文章有多短,詞典有多大,都要將詞典遍歷一遍。這種方法效率比較低，大一點(diǎn)的系統(tǒng)一般都不使用。　　最大正向匹配法 (ＭａｘｉｍｕｍＭａｔｃｈｉｎｇＭｅｔｈｏｄ)通常簡稱為ＭＭ法。其基本思想為：假定分詞詞典中的最長詞有i個漢字字符，則用被處理文檔的當(dāng)前字串中的前i個字作為匹配字段，查找字典。若字典中存在這樣的一

22、個i字詞，則匹配成功，匹配字段被作為一個詞切分出來。如果詞典中找不到這樣的一個i字詞，則匹配失敗，將匹配字段中的最后一個字去掉，對剩下的字串重新進(jìn)行匹配處理…… 如此進(jìn)行下去，直到匹配成功，即切分出一個詞或剩余字串的長度為零為止。這樣就完成了一輪匹配，然后取下一個i字字串進(jìn)行匹配處理，直到文檔被掃描完為止。　　當(dāng)然，最大匹配算法是一種基于分詞詞典的機(jī)械分詞法，不能根據(jù)文檔上

23、下文的語義特征來切分詞語，對詞典的依賴性較大，所以在實(shí)際使用時，難免會造成一些分詞錯誤，為了提高系統(tǒng)分詞的準(zhǔn)確度，可以采用正向最大匹配法和逆向最大匹配法相結(jié)合的分詞方案（即雙向匹配法，見（四）。）　　全切分要求獲得輸入序列的所有可接受的切分形式，而部分切分只取得一種或幾種可接受的切分形式，由于部分切分忽略了可能的其他切分形式，所以建立在部分切分基礎(chǔ)上的分詞方法不管采取何種歧義糾正策略，都可能會遺

24、漏正確的切分，造成分詞錯誤或失敗。而建立在全切分基礎(chǔ)上的分詞方法，由于全切分取得了所有可能的切分形式，因而從根本上避免了可能切分形式的遺漏，克服了部分切分方法的缺陷。　　全切分算法能取得所有可能的切分形式，它的句子覆蓋率和分詞覆蓋率均為100%，但全切分分詞并沒有在文本處理中廣泛地采用，原因有以下幾點(diǎn)：　　1)全切分算法只是能獲得正確分詞的前提，因?yàn)槿?/p>

25、分不具有歧義檢測功能，最終分詞結(jié)果的正確性和完全性依賴于獨(dú)立的歧義處理方法，如果評測有誤，也會造成錯誤的結(jié)果。　　2)全切分的切分結(jié)果個數(shù)隨句子長度的增長呈指數(shù)增長，一方面將導(dǎo)致龐大的無用數(shù)據(jù)充斥于存儲數(shù)據(jù)庫；另一方面當(dāng)句長達(dá)到一定長度后，由于切分形式過多,造成分詞效率嚴(yán)重下降。　　并行分詞方法：這種分詞方法借助于一個含有分詞詞庫的管道進(jìn)行 ,

26、比較匹配過程是分步進(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)督局．信息處

27、理用現(xiàn)代漢語分詞規(guī)范，中華人民共和國國家標(biāo)準(zhǔn)GB／T13715．92．中國標(biāo)準(zhǔn)出版社，1993　　2 碩士學(xué)位論文.中文自動分詞系統(tǒng)的研究與實(shí)現(xiàn). 周程遠(yuǎn) 20091101　　3碩士學(xué)位論文 .基于條件隨機(jī)場的中文分詞研究與應(yīng)用, 顏軍 20090401　　4 網(wǎng)絡(luò)文章中文分詞入門之最大匹配法發(fā)表于 2009年

28、01月12號由 52nlp 　　5一種基于自動機(jī)的分詞方法.鞍山科技大學(xué).計算機(jī)學(xué)院,東北大學(xué).信息學(xué)院遲呈英，戰(zhàn)學(xué)剛, 姚天順　　6種中文分詞算法優(yōu)劣比較，http：／／www．htmldata．cn／?p=248　　總結(jié)　　分

29、詞是中文自然語言處理的基礎(chǔ)，在現(xiàn)實(shí)中已經(jīng)得到廣泛應(yīng)用。比如，Google的Chrome瀏覽器就內(nèi)置了中文分詞功能。如上圖，我們可以注意到，在Chrome中雙擊無鏈接文本時，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)》等基

30、礎(chǔ)課程，但編寫程序時仍然遇到了很多問題，僅在漢字編碼的問題上就糾纏了很久。幸而在很多細(xì)致的文檔論文的幫助下，使我對分詞程序有了更深的了解。也懂得了算法也需要團(tuán)結(jié)合作才能效率更高。加深了我對各種算法的了解，增強(qiáng)了我的功底。　　自然語言處理是一個正在快速發(fā)展的學(xué)科，但愿我有朝一日能在這個領(lǐng)域大顯身手。　　附錄（程序源代碼）

31、;　　#include <fstream>　　#include <vector>　　#include <string>　　#include <iostream>　　using nam

32、espace std;　　const int START1 = 0XB0,START2 = 0XA1, END1 = 0XF8,END2 = 0XFF;　　const int MAXWORDLEN = 48;　　ifstream fin("segdict.txt");

33、　　ofstream out("out1.txt");　　//--------------------- 建樹部分----------------------　　struct Node3　　{&

34、lt;b>　　string S;　　bool IsWord;　　Node3 *L,*R;　　Node3(string s = "",bool isWord = 0, Node3 *l = 0, Node3 *r = 0):

35、S(s),IsWord(isWord),L(l),R(r){}　　};　　struct Node2　　{　　string S;<

36、p>　　bool IsWord;　　Node3 *Child;　　Node2(string s ="",bool isWord = 0, Node3* child =0):　　S(s),IsWord(isWord),Child(child){}&

37、lt;b>　　};　　struct Node　　{　　string S;　　vector<Node2>v;<b

38、>　　};　　vector<Node>Dic;　　const range =(END1 - START1)*(END2 - START2);//一維數(shù)組范圍　　int array[range];//一維數(shù)組代替哈希表　　void Be

39、gin() //初始化　　{　　for (int i = 0; i < range; i++)　　array[i]=-1;　　}　　void Bui

40、ldTree(string s, Node3 *child)　　{　　int len = s.length();　　string t = s.substr(0,2);　　Node3 *LAST = child;

41、　　if (child == 0)　　LAST = child = new Node3(t, (len == 2),0,0);　　else　　{　　while (LAST->

42、;L != 0)　　LAST = LAST->L;　　if (LAST->S != t)　　{　　LAST->L = new Node3(t,(len == 2),0, 0);

43、;　　LAST = LAST->L;　　}　　}　　if (len > 2)　　BuildTree(s.substr(2,MAXWORDLEN),LAST->R);</p&

44、gt;　　}　　void Dictionary() //構(gòu)造整個結(jié)構(gòu)　　{　　Begin();　　string s;&

45、lt;/b>　　int N,k = 0;　　while(fin >> s)　　{　　Node n;　　n.S = s.substr(0,

46、2);　　int m1 = ((unsigned char)s[0] - START1)*((unsigned char)s[1] - START2)+(unsigned char)s[0] - START1;　　array[m1] = k++;　　out << s << "

47、" << array[m1] << endl;　　fin >> N;　　out << N << endl;　　for (int i = 0; i < N; i++)<p&

48、gt;　　{　　fin >> s;　　out << s << endl;　　string t = s.substr(2,2);　　int LEN = s.len

49、gth();　　int SIZE = n.v.size();　　int Len = s.length();　　if (SIZE == 0 ||(SIZE > 0 && n.v[SIZE-1].S != t))　　n.v.push_back(Node2

50、(t, (Len == 4),0));　　SIZE = n.v.size();　　if (Len > 4)　　BuildTree(s.substr(4,MAXWORDLEN),n.v[SIZE-1].Child);　　}<

51、/p>　　Dic.push_back(n);　　}　　out << "END Array" << endl << endl;　　}

52、　　//------------------查詢部分---------------------　　vector<string>Dest;　　int BinarySearch(int x, string Sec)//二分查找第二個字　　{</

53、p>　　int L = 0,R = Dic[x].v.size() - 1;　　while (L <= R)　　{　　int mid = (L + R) >> 1;　　if (Dic[x]

54、.v[mid].S == Sec)　　return mid;　　else if (Dic[x].v[mid].S < Sec)　　L = mid + 1;　　else R = mid - 1;　　}&l

55、t;/b>　　return -1;　　}　　Node3* RemainSearch(Node3*p, string cc) //順序查找剩下的字　　{<p&

56、gt;　　while (p != 0)　　{　　if (p->S == cc)　　return p;　　else

57、;　　p = p->L;　　}　　return 0;　　}　　unsigned CharToInt(char c)

58、　　{　　return unsigned((unsigned char)c) ;　　}　　bool IsCC(char c)　　{<

59、;/b>　　unsigned val= CharToInt(c);　　return val >= START1 && val < END1;　　}　　bool IsEC(char c)</p&g

60、t;　　{　　unsigned val= CharToInt(c);　　return val < 0x80;　　}　　void FindNum(string src,

61、vector<string>&dest, int &StarPos,int &EndPos)　　{　　int Strlen = src.length();　　while (EndPos < Strlen && !IsC

62、C(src[EndPos]))　　{　　if(!IsCC(EndPos))　　EndPos++;　　EndPos++;

63、;　　}　　if (EndPos > StarPos)　　{　　dest.push_back(src.substr(StarPos,EndPos-StarPos));　　StarPos =

64、EndPos;　　}　　}　　void Segment(string src, vector<string>&dest)　　{</p

65、>　　int StrLen = src.length();　　int StartPos = 0, EndPos;　　while (StartPos < StrLen)　　{　　EndPos = Sta

66、rtPos;　　FindNum(src,dest,StartPos,EndPos);　　if (StartPos >= StrLen) return ;　　unsigned SegLen = 2;　　string HeadCC = src.substr(StartP

67、os, 2);　　cout <<HeadCC <<endl << endl;　　int m1 = ((unsigned char)HeadCC[0]-START1)*((unsigned char)HeadCC[1]-START2)+(unsigned char)HeadCC[0]-START1;

68、　　int HeadIndex = array[m1];　　if (HeadIndex >= 0);　　{　　string SecCC = src.substr(StartPos + 2,2);　　if (S

69、ecCC.length() > 0 && IsCC(SecCC[0]))　　{　　int B2 = BinarySearch(HeadIndex,SecCC);　　if (B2>=0)

70、{　　if (Dic[HeadIndex].v[B2].IsWord)　　SegLen += 2;　　EndPos = StartPos + 4;　　Node3 *p = Dic[HeadIndex].v[B2].Child;&

71、lt;p>　　while(EndPos < StrLen && (p = RemainSearch(p,src.substr(EndPos,2)))!= 0)　　{　　EndPos+= 2;　　if (p->IsWord)

72、　　SegLen = EndPos - StartPos;　　p = p->R;　　}　　}　　}</b&

73、gt;　　}　　dest.push_back(src.substr(StartPos,SegLen));　　StartPos += SegLen;　　}&

74、lt;b>　　}　　int main()　　{　　Dictionary();　　ofstream out2("out2.txt");　　// st

75、ring SS ="有時，我會抬頭，看一看這喧囂的人群，有沒有我想見得身影，若是有那身影，或許我會看著她，看她慢慢的融入人群，直到不見。然后我會低下頭，走著我的道。";　　string SS="中華人民萬歲";　　// string SS= "在詞典中對于特定的首字，前兩字相同的詞條很少，前三字相同的詞條

76、更少。當(dāng)我們以這種形式組織詞典后，除子表的第一層外，各個節(jié)點(diǎn)的兄弟數(shù)目都很小，對它們的查找采用順序查找方法較為適宜。" ;　　//string SS = "主要分為兩大模塊：一個建立一棵樹，一個是查詢。建樹有三個層次，第一層是HASH表，第二層是數(shù)組，用于二分查找使用，第三層是二叉樹。查詢分為直接查詢第一層的HASH表，第二層用二分查找（第二層漢子相同的平均概率是26，一般第

77、二字成詞切相同），第三層直接順序查找，以及查找句子中的數(shù)字和漢子標(biāo)點(diǎn)。";　　Segment(SS,Dest);　　int LEN = Dest.size();　　for (int i =0;i <LEN; i++)　　out2 << &quo

78、t; "<< Dest[i] <<endl;　　system("Pause");　　return 0;　　}　　//----------

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載