算法課程設計---中文分詞程序設計與實現

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

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

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

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

2、 　　指導教師： 　　成績： 　　2012年 3 月 2 日　　目錄

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

4、文分詞，就是把一個漢語句子按照其中詞的含義進行切分。隨羞人們更深入熬研究，中文信息處理技術得到了廣泛應用，并對中文分詞技術的要求也越來越高。中文分詞技術已經引起多方的關注，并成為中文信息處理的一個前沿課題l卜21。目前在自然語言處理技術中，中文處理技術遠遠落后于西文處理技術，許多西文的處理方法中文不能直接采用，就是因為中文必須進行分詞處理。中文分詞是其它中文信息處理的基礎，搜索弓|擎只是中文分詞的一個應用，其它應用比如機器翻譯(MT)、

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

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

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

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

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

10、這種冗余操作，我們提出將詞典的詞尾部分以自動機的形式來組織。為此，我們將組成單詞的每個字以一種鏈表節(jié)點的形式存儲，其抽象數據結構的定義如下：　　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;　　}　　結果分析　　截取每一個詞的第一個字　　講一段話拆分成詞的形式　　逐詞遍

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

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

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

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

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

26、比較匹配過程是分步進行的 ,每一步可以對進入管道中的詞同時與詞庫中相應的詞進行比較 ,由于同時有多個詞進行比較匹配 ,因而分詞速度可以大幅度提高。這種方法涉及到多級內碼理論和管道的詞典數據結構。（詳細算法可以參考吳勝遠的《并行分詞方法的研究》。）　　參考文獻　　1 國家技術監(jiān)督局．信息處

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

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

29、詞是中文自然語言處理的基礎，在現實中已經得到廣泛應用。比如，Google的Chrome瀏覽器就內置了中文分詞功能。如上圖，我們可以注意到，在Chrome中雙擊無鏈接文本時，Chrome選中的不是一個字，也不是一句話，而是一個詞。當然，中文分詞在數據挖掘等方面的應用就更加明顯了。掌握自然語言處理的基本知識，已經成為IT行業(yè)對計算機專業(yè)學生的基本要求。　　雖然我曾經系統(tǒng)學習過《算法》《數據結構》等基

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

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);//一維數組范圍　　int array[range];//一維數組代替哈希表　　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() //構造整個結構　　{　　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、更少。當我們以這種形式組織詞典后，除子表的第一層外，各個節(jié)點的兄弟數目都很小，對它們的查找采用順序查找方法較為適宜。" ;　　//string SS = "主要分為兩大模塊：一個建立一棵樹，一個是查詢。建樹有三個層次，第一層是HASH表，第二層是數組，用于二分查找使用，第三層是二叉樹。查詢分為直接查詢第一層的HASH表，第二層用二分查找（第二層漢子相同的平均概率是26，一般第

77、二字成詞切相同），第三層直接順序查找，以及查找句子中的數字和漢子標點。";　　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è)設計

溫馨提示

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

算法課程設計---中文分詞程序設計與實現

文檔簡介

溫馨提示

最新文檔

評論

算法課程設計---中文分詞程序設計與實現

文檔簡介

溫馨提示

最新文檔

評論

免費下載