文學(xué)研究助手與模式匹配算法KMP

1、北京理工大學(xué)珠海學(xué)院計算機(jī)學(xué)院課程設(shè)計北京理工大學(xué)珠海學(xué)院課程設(shè)計說明書 2010 2011 學(xué)年第二學(xué)期題目: 文學(xué)研究助手與模式匹配算法kmp 學(xué) 院： 計算機(jī)科學(xué)與技術(shù)學(xué)院 專業(yè)班級： 學(xué) 號： 學(xué)生姓名： 指導(dǎo)教師： 成 績： 時 間： 北京理工大學(xué)珠海學(xué)院課程設(shè)計任務(wù)書 2010 2011學(xué)年第二學(xué)期學(xué)生姓名： 專業(yè)班級： 指導(dǎo)教師： 工作部門： 一、課程設(shè)計題目文學(xué)研究助手與模式匹配算法kmp二、課程設(shè)計內(nèi)容（含技術(shù)指標(biāo)）【問題描述】文學(xué)研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個實現(xiàn)這一目標(biāo)的文字統(tǒng)計系統(tǒng)【任務(wù)要求】英文小說存于一個文本文件中。待統(tǒng)計的詞匯集

2、合要一次輸入完畢，即統(tǒng)計工作必須在程序的一次運行之后就全部完成。程序的輸出結(jié)果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在的行的行號，格式自行設(shè)計。待統(tǒng)計的“單詞”在文本串中不跨行出現(xiàn)，它或者從行首開始，或者前置以一個空格符。模式匹配要基于kmp算法。推廣到更一般的模式集匹配問題，并設(shè)待查模式串可以跨行（提示：定義操作getachar）?！緶y試數(shù)據(jù)】文本文件為testword.c待統(tǒng)計的詞集：if、else、for、while、return、void、int、char、typedef、struct三、進(jìn)度安排1初步設(shè)計：寫出初步設(shè)計思路，進(jìn)行修改完善，并進(jìn)行初步設(shè)計。2詳細(xì)設(shè)計：根據(jù)確定的設(shè)計思想，進(jìn)一步

3、完善初步設(shè)計內(nèi)容，按要求編寫出數(shù)據(jù)結(jié)構(gòu)類型定義、各算法程序、主函數(shù)。編譯分析調(diào)試錯誤。3測試分析：設(shè)計幾組數(shù)據(jù)進(jìn)行測試分析，查找存在的設(shè)計缺陷，完善程序。4報告撰寫：根據(jù)上面設(shè)計過程和結(jié)果，按照要求寫出設(shè)計報告。5答辯考核驗收：教師按組（人）檢查驗收，并提出相關(guān)問題，以便檢驗設(shè)計完成情況。四、基本要求1在設(shè)計時，要嚴(yán)格按照題意要求獨立進(jìn)行設(shè)計，不能隨意更改。若確因條件所限，必須要改變課題要求時，應(yīng)在征得指導(dǎo)教師同意的前提下進(jìn)行。 2在設(shè)計完成后，應(yīng)當(dāng)場運行和答辯，由指導(dǎo)教師驗收，只有在驗收合格后才能算設(shè)計部分的結(jié)束。 3設(shè)計結(jié)束后要寫出課程設(shè)計報告，以作為整個課程設(shè)計評分的書面依據(jù)和存檔材料。

4、設(shè)計報告以規(guī)定格式的電子文檔書寫、打印并裝訂，報告格式嚴(yán)格按照模板要求撰寫，排版及圖、表要清楚、工整。從總體來說，所設(shè)計的程序應(yīng)該全部符合要求，問題模型、求解算法以及存儲結(jié)構(gòu)清晰；具有友好、清晰的界面；設(shè)計要包括所需要的輔助程序，如必要的數(shù)據(jù)輸入、輸出、顯示和錯誤檢測功能；操作使用要簡便；程序的整體結(jié)構(gòu)及局部結(jié)構(gòu)要合理；設(shè)計報告要符合規(guī)范。 課程負(fù)責(zé)人簽名： 年 月 日題目選題四：文學(xué)研究助手與模式匹配算法kmp摘 要 本實踐課題重在對文本的查詢，在實際應(yīng)用中有重大作用。通過本程序，可統(tǒng)計所需文本的一個或多個詞匯在文本中出現(xiàn)的次數(shù)與位置，其作用在于給使用者研究一篇文學(xué)著作時提供幫助。當(dāng)研究一片

5、文學(xué)著作時，不緊要理解著作的內(nèi)容和寓意，有是更需要分析作者的寫作手法和習(xí)慣，這是統(tǒng)計著作中詞匯的出現(xiàn)次數(shù)與位置成了文學(xué)研究的重點課題。本程序就可以為文學(xué)研究者提供這類幫助。本程序基于模式匹配算法kmp實現(xiàn)，為普通模式匹配的改進(jìn)，優(yōu)點在與時間復(fù)雜度由原來的o（n*m）變?yōu)閛（n+m）,即是說統(tǒng)計時間大大縮短。當(dāng)要統(tǒng)計的詞匯量很大時，計算機(jī)統(tǒng)計所需時間將很漫長，如果使用者急需使用統(tǒng)計結(jié)果，這是又因為統(tǒng)計太慢導(dǎo)致研究受阻，這樣就得不償失了。而本程序?qū)⒋蟠蟾纳七@種狀況，讓計算機(jī)在短時間內(nèi)統(tǒng)計出使用者想要的統(tǒng)計結(jié)果。本程序雖然精簡，但是對模式匹配算法kmp的使用極其靈活，需開發(fā)者深刻理解模式匹配算法km

6、p，思路清晰，靈活調(diào)用模式匹配算法kmp的函數(shù)，否則開發(fā)者將極難開發(fā)成功。關(guān)鍵詞：文學(xué)研究 模式匹配 kmp目 錄摘 要6關(guān)鍵詞61 課程設(shè)計相關(guān)81.1題目要求81.1.1實驗所在地點82 課程設(shè)計實施92.1設(shè)計思路92.1.1課程設(shè)計時間分配92.2源程序代碼實現(xiàn)102.3 程序調(diào)試演示與分析12參考文獻(xiàn)15心得體會16教師評語17計算機(jī)學(xué)院課程設(shè)計答辯記錄表181 課程設(shè)計相關(guān)1.1題目要求【問題描述】文學(xué)研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個實現(xiàn)這一目標(biāo)的文字統(tǒng)計系統(tǒng)【任務(wù)要求】1) 英文小說存于一個文本文件中。待統(tǒng)計的詞匯集合要一次輸入完畢，即統(tǒng)計工作必

7、須在程序的一次運行之后就全部完成。程序的輸出結(jié)果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在的行的行號，格式自行設(shè)計。待統(tǒng)計的“單詞”在文本串中不跨行出現(xiàn)，它或者從行首開始，或者前置以一個空格符。2) 模式匹配要基于kmp算法。3) 推廣到更一般的模式集匹配問題，并設(shè)待查模式串可以跨行（提示：定義操作getachar）?！緶y試數(shù)據(jù)】1) 文本文件為testword.c2) 待統(tǒng)計的詞集：if、else、for、while、return、void、int、char、typedef、struct【成績評定】1) 完成“任務(wù)要求”第1項成績評定為“及格”-“中”。2) 完成“任務(wù)要求”第2項至第3項成績評定為“

8、良”及以上。1.1.1實驗所在地點本實驗實行所在地點于學(xué)校教學(xué)樓多媒體實驗室jb405，如圖1-1 北理工珠海學(xué)院教學(xué)樓機(jī)車樓化工樓多媒體實驗室網(wǎng)絡(luò)實驗室無機(jī)化學(xué)圖1-1 學(xué)校設(shè)施組織結(jié)構(gòu)圖2 課程設(shè)計實施2.1設(shè)計思路 本實踐重在對模式匹配算法kmp的調(diào)用。kmp算法在數(shù)據(jù)結(jié)構(gòu)（c語言版）中的第82頁有詳細(xì)解釋，在此不予以解釋。我的大概思路是：1打開文件2輸入想要匹配的一組字符串3讀取文件的一行4把每一個字符串在該行中實行模式匹配kmp5重復(fù)步驟3和46輸出結(jié)果2.1.1課程設(shè)計時間分配 本課程時間分為4天，16個課時，設(shè)計工作時間分配由學(xué)生自行分配。我的課程設(shè)計工作分配時間表如表2-1。表

9、2-1 詳情分工時間備注思路梳理與理論了解第一天 可實行部分編程編程實現(xiàn)第二天注意寫備注程序檢驗與改善第三天準(zhǔn)備寫說明書程序設(shè)計說明書整理第四天打印，答辯 開發(fā)一個軟件，就算再小，時間分配上也是很重要的。在第一天，我將了解模式匹配算法kmp的設(shè)計思路，再梳理出我設(shè)計本程序的大概思路。當(dāng)思路梳理得差不多的時候就可以開始編程，第一天的編程還是以編寫程序框架為主，先要把思路的框架寫出來，為第二天的編程實現(xiàn)作準(zhǔn)備。第二天開始正式變成實現(xiàn)，在第一天編寫出的程序框架的基礎(chǔ)上，填寫程序的實際內(nèi)容。由于第一天已編寫出大概框架，因此實際編程事半工倍。第三天實行程序的檢驗與改善。第二天編寫出來的程序已能夠?qū)崿F(xiàn)所需

10、功能，但程序的格式還比較亂，也沒有對讀取出錯進(jìn)行處理。在這一天里，將對程序進(jìn)行檢驗與改善，令程序更完美。在閑暇之余，還可以適當(dāng)為課程設(shè)計說明書作準(zhǔn)備，寫出說明書模版以及完成部分內(nèi)容。第四天對課程設(shè)計說明書進(jìn)行進(jìn)一部的整理和完成，并在答辯之前把說明書打印出來。2.2源程序代碼實現(xiàn)#include #include #define maxstrlen 255 /最大串長typedef char sstringmaxstrlen+1; /串的定長順序存儲表示int nextmaxstrlen; /kmp算法中用到的nextint index(sstring s,sstring t,int pos)

11、/kmp算法,p82int i=pos,j=1; while(i=s0&jt0) return (i-t0); else return 0;int lenth(sstring str) /求串長int i=1;while(stri) i+;return(i-1);void find(char name,sstring keys) /查找函數(shù) sstring text; /用于存放從小說文件讀取的一行字符串 int i=1,j=0,k,q=0; /i用于存放行號，j用于存放列號,k用于輸出格式的控制,q用于統(tǒng)計出現(xiàn)次數(shù)file *fp;if (!(fp=(fopen(name,r) /打開小說文

12、件printf(打開文件出錯!n);exit(0); keys0=lenth(keys); /求關(guān)鍵字的長度printf(n%sn,&keys1); /打印關(guān)鍵字while (!feof(fp) /如果還沒到小說文件末尾，則繼續(xù)循環(huán)k=0;fgets(&text1,maxstrlen,fp); /從小說文件中讀取一行字符串，存入text串中text0=lenth(text); /求讀入的串的長度j=index(text,keys,j+1); /調(diào)用kmp算法，統(tǒng)計關(guān)鍵字在該行出現(xiàn)的位置，若匹配不成功則返回0if (j!=0)printf(行=%d,列=%d,i,j); k+; /若匹配成功則打

13、印行號和列號while(j!=0) /若該行找到了關(guān)鍵字，則繼續(xù)尋找看是否還能匹配成功j=index(text,keys,j+1); /調(diào)用kmp算法從剛找到的列號后一字符起匹配if (j!=0) printf(,%d,j);k+; /若匹配成功，則打印列號i+; /行號加1，在下一行中尋找q+=k; /累加k以統(tǒng)計關(guān)鍵字出現(xiàn)次數(shù)if (k)printf(n);/輸出格式控制printf(%s出現(xiàn)%d次。n,&keys1,q);/打印關(guān)鍵字出現(xiàn)次數(shù)void main()char name50; /存儲輸入的小說路徑字符串sstring words10; /定義字符串?dāng)?shù)組，用于存儲輸入的關(guān)鍵字i

14、nt m,n,i;printf(-歡迎使用文學(xué)研究助手-);/打印標(biāo)題while(1)/不停循環(huán)，直至完成查詢或者退出服務(wù)printf(是否需要為你服務(wù)：需要輸入1，不需要輸入0。n);/詢問是否需要服務(wù)scanf(%d,&m);/輸入判斷是否需要服務(wù)if(m=1)/需要服務(wù)時執(zhí)行printf(輸入你想查詢的文檔名字:n);scanf(%s,name);/輸入文件名printf(輸入查詢字符串的個數(shù)：n);scanf(%d,&n);/輸入查詢字符串個數(shù)printf(輸入你要查詢的字符串:n);for (i=0;in;i+)scanf(%s,&wordsi1); /用戶一次性輸入要查找的關(guān)鍵字，

15、wordsi0用于存放字符串的長度for (i=0;in;i+)find(name,wordsi); /對于每一個關(guān)鍵字，調(diào)用查找函數(shù)進(jìn)行查找統(tǒng)計break;else if(m=0)/不需要服務(wù)時執(zhí)行break;else printf(輸入錯誤!nn);/輸入不合規(guī)范時執(zhí)行2.3 程序調(diào)試演示與分析如上圖所示，運行程序先詢問你是否需要服務(wù)，輸入1后開始提供服務(wù)。首先輸入想查詢的文檔名字，這里輸入測試文檔text.c，即本程序的源文件，再輸入個數(shù)，這里為測試需要輸入10個。然后一次性輸入想查詢的字符串，這里為if、else、for、while、return、void、int、char、typed

16、ef、struct。輸入完成以后程序就會開始自動統(tǒng)計，結(jié)果如下： 分析結(jié)果發(fā)現(xiàn)，程序統(tǒng)計完自動退出。再對比統(tǒng)計結(jié)果是否正確，發(fā)現(xiàn)結(jié)果是正確的，表明程序正常運行并統(tǒng)計出了正確的數(shù)據(jù)。參考文獻(xiàn) 1嚴(yán)蔚敏，吳偉民：數(shù)據(jù)結(jié)構(gòu)（c語言版）m，清華大學(xué)出版社2007年版，第80-84頁。 心得體會 通過這一次課程實踐，我獲益良多，明白了很多之前不明白的，注意到了很多之前沒注意的東西。雖然這個程序比較短，可短而精，特別是對于模式匹配算法kmp的運用尤其靈活。另外，我注意了很多細(xì)節(jié)，從中學(xué)到了很多?？偟膩碚f包括以下幾點：1對于錯誤信息的處理問題。本程序有打開文件、輸入判斷等運用，如果對錯誤信息不加以處理，將會導(dǎo)致程序運行時使用戶不清楚或感到程序忽然死亡的情況。對這一細(xì)節(jié)加以處理后不僅程序美觀，條理清晰，還對用戶的使用提供了方便，容易上手。2注釋應(yīng)盡量詳細(xì)。詳細(xì)的注釋不僅能夠讓看的人清晰明了，對編程者本人的思路整理有好處，使得在編程的過程中不易產(chǎn)生混亂。3編程時注意對程序的優(yōu)化。雖然計算機(jī)的處理速度很快，可是當(dāng)處理的信息一旦太多時，計算機(jī)容易反應(yīng)不過來。為了避免這種情況的發(fā)生，程序應(yīng)當(dāng)簡潔、省時省空間，力求在時間復(fù)雜度和空間復(fù)雜度之上有所優(yōu)勢，節(jié)約資源。4思路是編程的核心，在編程之前一定要理清思路，這樣編程時才會事半工倍。如果在編程是遇到了瓶頸，應(yīng)當(dāng)