【正文】 ................................. 31 測(cè)試環(huán)境 ............................................... 31 測(cè) 試數(shù)據(jù)的建立 ......................................... 31 第六章 結(jié)論與展望 ................................................... 32 結(jié)論 ........................................................ 32 展望 ........................................................ 32 致 謝 .............................................................. 33 參考文獻(xiàn) ............................................................ 34 沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第二章 關(guān)鍵問(wèn)題分析 1 第一章 引 言 本課題的研究背景 社會(huì)發(fā)展到今天，已經(jīng)進(jìn)入了計(jì)算機(jī)的時(shí)代。這就出現(xiàn)了一個(gè)問(wèn)題，既然硬件 無(wú) 法提高，而人的要求又無(wú)法滿足，那應(yīng)該怎么辦呢？辦法是有的 ， 運(yùn)用好的算法，可以節(jié)約硬件資源，提高運(yùn)算效率 ， 一個(gè)很優(yōu)秀的算法可以大大提升這些。 2．索引表組成 索引表由若干索引項(xiàng)組成。 ① 通常將索引非順序文件簡(jiǎn)稱(chēng)為索引文件。 2． 索引文件的建立 建立索引文件的過(guò)程： （ 1） 按輸入記錄的先后次序建立數(shù)據(jù)區(qū)和索引表。通常最高可達(dá)四級(jí)索引： 數(shù)據(jù)文件 一 — 索引表 —— 查找表 —— 第二查找表 —— 第三查找表?；竟δ苋缦拢? 系統(tǒng)支持多文本文檔的導(dǎo)入，是對(duì)多文件進(jìn)行操作。 由于是常用詞表查找，所以本系統(tǒng)查找算法采用順序查找算法實(shí)現(xiàn)。 (1)溢出桶和基桶大小相同，相互之間用指針相鏈接。 多關(guān)鍵字文件 1．多關(guān)鍵字文件 包含有多個(gè)次關(guān)鍵字索引的文件稱(chēng)為多關(guān)鍵字文件。 倒排文件 1．倒排文件的組織方式和特點(diǎn) 倒排文件和多重表文件不同。 5．倒排文件與一般文件組織的區(qū)別 在一般的文件組織中，是先找記錄，然后再找到該記錄所含的各次關(guān)鍵字；而倒排文件中，是先給定次關(guān)鍵字， 然后查找含有該次關(guān)鍵字的各個(gè)記錄，這種文件的查找次序正好與一般文件的查找次序相反，因此稱(chēng)之為 倒排 。 加上“出現(xiàn)頻率”和“出現(xiàn)位置”信息后，我們的索引結(jié)構(gòu)變?yōu)椋? 關(guān)鍵詞 文章號(hào) [出現(xiàn)頻率 ] 出現(xiàn)位置 guangzhou 1[2] 3， 6 he 2[1] 1 i 1[1] 4 live 1[1] 5 lived 1[1] 2 lives 1[1] 2 shanghai 2[1] 3 tom 1[1] 1 以 “ live” 這行為例我們說(shuō)明一下該結(jié)構(gòu)： live 在文章 1中出現(xiàn)了 2次，文章 2 中出現(xiàn)了一次，它的出現(xiàn)位置為“ 2,5,2”這表示什么呢？我們需要結(jié)合文章號(hào)和出現(xiàn)頻率來(lái)分析，文章 1中出現(xiàn)了 2 次，那么“ 2,5”就表示 live 在文章 1 中出現(xiàn)的兩個(gè)位置，文章 2 中出現(xiàn)了一次，剩下的“ 2”就表示 live 是文章2中第 2 個(gè)關(guān)鍵字。 而用普通的順序匹配算法，不建索引，而是對(duì)所有文章的內(nèi)容進(jìn)行字符串匹配，這個(gè)過(guò)程將會(huì)相當(dāng)緩慢，當(dāng)文章數(shù)目很大時(shí)，時(shí)間往往是無(wú)法忍受的。 ② 成功時(shí)的順序查找的平均查找長(zhǎng)度： 在等概率情況下， pi=1/n(1≤i≤n) ，故成功的平均查找長(zhǎng)度為 (n+?+2+1)/n=(n+1)/2 即查找成功時(shí)的平均比較次數(shù)約為表長(zhǎng)的一半。 二分查找要求：線性表是有序表，即表中結(jié)點(diǎn)按關(guān)鍵字有序，并且要用向量作為表的存儲(chǔ)結(jié)構(gòu)。 //繼續(xù)在 R[low..mid1]中查找 else low=mid+1； //繼續(xù)在 R[mid+1..high]中查找 } return 0； //當(dāng) lowhigh 時(shí)表示查找區(qū)間為空，查找失敗 } //BinSeareh 二分查找算法的執(zhí)行過(guò)程 先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直到找到或找不到該記錄為止。 ③ 樹(shù)中某結(jié)點(diǎn) i與其左 (右 )孩子連接的左 (右 )分支上的標(biāo)記 、 (、 、)表示：當(dāng)待查關(guān)鍵字 KR[i].key(KR[i].key)時(shí)，應(yīng)走左 (右 )分支到達(dá) i的左 (右 )孩子，將該孩子的關(guān)鍵字進(jìn)一步和 K比較。 （ 3）二分查找的平均查找長(zhǎng)度 設(shè)內(nèi) 部結(jié)點(diǎn)的總數(shù)為 n=2h1，則判定樹(shù)是深度為 h=lg(n+1)的滿二叉樹(shù) (深度 h 不計(jì)外部結(jié)點(diǎn) )。為保持表的有序性，在順序結(jié)構(gòu)里插入和刪除都必須移動(dòng)大量的結(jié)點(diǎn)。 （ 2）索引表 抽取各塊中的最大關(guān)鍵字及其起始位置構(gòu)成一個(gè)索引表 ID[l..b]，即： ID[i](1≤i≤b)中存放第 i 塊的最大關(guān)鍵字及該塊在表 R 中的起始位置。blk取極小值 +1 ，即當(dāng)采用順序查找確定塊時(shí)，應(yīng)將各塊中的結(jié)點(diǎn)數(shù)選定為 。即可直接顯示該詞前后的一些相關(guān)信息。 //出現(xiàn)頻率 }file[10000]。 FILE *in,*out,*fp。 if(d[0] != 10) { strcat(a,d)。 } rewind(in)。 39。)) amp。 file[n].place = ftell(in) strlen(a)。im。 查詢(xún)的實(shí)現(xiàn)主要由兩個(gè)函數(shù)來(lái)完成，這兩個(gè)函數(shù)是 ： ::GetWindowText(::GetDlgItem(m_hWnd, IDC_EDITTEXT1), sz, 256)。 （ 2）做到用戶(hù)界面的一致性，在界面設(shè)計(jì)中應(yīng)該保持界面的一致性。從以上分析看出我們?cè)O(shè)計(jì)的每個(gè)模塊都是作為一個(gè)獨(dú)立的應(yīng)用程序提供給系統(tǒng)的，因此它和系統(tǒng)的聯(lián)系并不是太大，就它本身來(lái)說(shuō)它出錯(cuò)的可能性很小，因?yàn)樗捎玫亩际亲罨镜慕M件組成的。通過(guò)這次畢業(yè)設(shè)計(jì)，使我知道了做一個(gè)好的系統(tǒng)并不是一件簡(jiǎn)單的事情，需要考慮的問(wèn)題實(shí)在是太多了，從需求分析上看，要獲得用戶(hù)對(duì)整個(gè)程序的功能要求。由于畢設(shè)時(shí)間有限，不能將這些功能全部實(shí)現(xiàn)，希望在以后的日子里，找閑暇時(shí)間將這些功能一一實(shí)現(xiàn)，爭(zhēng)取做成一個(gè)功能強(qiáng)大，完成健壯的軟件工具。由此，我也理解了為什么學(xué)業(yè)的層次越高，課題越難，對(duì)論文的要求也越高了。 。在他悉心的指導(dǎo)下我能按部就班的完成 題目的設(shè)計(jì)。本系統(tǒng)只完成了對(duì)文本文件的搜索功能，可在此功能上擴(kuò)展到查找基它一些文件，如網(wǎng)頁(yè)文件， word 文檔 ,Excel 文檔等文件的搜索。 沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第六章 結(jié)論與展望 33 第六章 結(jié)論與展望 結(jié)論 畢業(yè)設(shè)計(jì)快結(jié)束了，我的體會(huì)很多，這次畢業(yè)設(shè)計(jì)是對(duì)我的大學(xué)兩年學(xué)習(xí)的總結(jié)，使我的專(zhuān)業(yè)知識(shí) 和實(shí)際應(yīng)用的緊密結(jié)合起來(lái)。上面已經(jīng)論述了本工具的錯(cuò)誤處理機(jī)制是通過(guò)設(shè)置捕捉陷阱并將錯(cuò)誤通過(guò)錯(cuò)誤提示消息框告知使用者的，這也是提高系統(tǒng)穩(wěn)定性的重要方面；另外統(tǒng)一的界面可以很好的控制使用者的操作，使其更 加規(guī)范，合理；事件驅(qū)動(dòng)機(jī)制，也很好的明確了各個(gè)控件的任務(wù)，避免了處理不明確，任務(wù)混淆，提高系統(tǒng)的穩(wěn)定性。用戶(hù)對(duì)于界面視覺(jué)效果和軟件操作方式的易用性的關(guān)心，要遠(yuǎn)遠(yuǎn)大于他對(duì)底層到底用什么樣的代碼去實(shí)現(xiàn)的關(guān)心。 } 此函數(shù)完成的功能為把 inname 所指向的文件按照 Term Dictionary(詞庫(kù)文件 )建立倒排索引后，寫(xiě)入 outname 所指文件。 m = strlen(a)。 } } if(strcmp(a,b) == 0) { strcpy(file[n].word,a)。 } if( ((e[0] == 10) || (e[0] == 39。amp。im。t\n)。 int i。 //所在文件名 long place。本題使用的方法為倒排文件索引方法，既對(duì)導(dǎo)入的文本文件先按照詞庫(kù)文件建立倒排索引。 ① 以二分查找來(lái)確定塊，分塊查找成功時(shí)的平均查找長(zhǎng)度 ASLblk=ASLbn+ASLsq≈lg(b+1)1+(s+1)/2≈lg(n/s+1)+s/2 ② 以順序查找確定塊，分塊查找成功時(shí)的平均查找長(zhǎng)度 ASL39。 二分查找表存儲(chǔ)結(jié)構(gòu) 二分查找表由 分塊有序 的線性表和索引表組成。既使采用高效率的排序方法也要花費(fèi) O(nlgn)的時(shí)間。 由此可見(jiàn)，成功的二分查找過(guò)程恰好是走了一條從判定樹(shù)的根到被查結(jié)點(diǎn)的路徑，經(jīng)歷比較的關(guān)鍵字次數(shù)恰為該結(jié)點(diǎn)在樹(shù)中的層數(shù)。樹(shù)中圓結(jié)點(diǎn)內(nèi)的數(shù)字表示該結(jié)點(diǎn)在有序表中的位置。這一過(guò)程重復(fù)直至找到關(guān)鍵字為 K的結(jié)點(diǎn)，或者直至當(dāng)前的查找區(qū)間為空 (即查找失敗 )時(shí)為止。 ⑤ 順序查找的缺點(diǎn) 沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第二章 關(guān)鍵問(wèn)題分析 12 查找效率低，因此，當(dāng) n較大時(shí)不宜采用順序查找。 基于順序結(jié)構(gòu)的順序查找算法 （ 1）類(lèi)型說(shuō)明 typedef struct{ KeyType key； InfoType otherinfo； //此類(lèi)型依賴(lài)于應(yīng)用 }NodeType； 沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第二章 關(guān)鍵問(wèn)題分析 11 typedef NodeType SeqList[n+1]； //0 號(hào)單元用作哨兵 （ 2）具體算法 int SeqSearch(Seqlist R， KeyType K) { //在順序表 R[1..n]中順序查找關(guān)鍵字為 K的結(jié)點(diǎn)， //成功時(shí)返回找到的結(jié)點(diǎn)位置，失敗時(shí)返回 0 int i； R[0].key=K； //設(shè)置哨兵 for(i=n； R[i].key!=K。 假設(shè)要查詢(xún)單詞 “ live”，搜索引擎先對(duì)詞典二元查找、找到該詞，通過(guò)指向頻率文件的指針讀出所有文章號(hào)，然后 返回結(jié)果。倒排索引把這個(gè)關(guān)系倒過(guò)來(lái)，變成：“關(guān)鍵詞”對(duì)“擁有該關(guān)鍵詞的所有文章號(hào)”。 3．倒排文件的更新 在插入和刪除記錄時(shí)，還要修改倒排表。 多重表的更新操作 1．插入新記錄 相同次關(guān)鍵字鏈表不按主關(guān)鍵字大小鏈接時(shí)，在主 文件中插入新記錄