【正文】 軟件本身所帶的查找功能多數(shù)是基于模 式匹配（逐個(gè)字符比較）的方式制作的，當(dāng)處理大規(guī)模文件時(shí)查詢效率很低。 ① 主文件：文件本身。 沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第二章 關(guān)鍵問(wèn)題分析 2 索引表必須按主關(guān)鍵字有序，而主文件本身則可以按主關(guān)鍵字有序或無(wú)序。 （ 2）索引非順序文件 (Indexed NonSequentail File) 主文件按主關(guān)鍵字無(wú)序 的 文件稱索引非順序文件。 ③ 索引順序文件的主文件是有序的，適合于隨機(jī)存取、順序存取。 索引文件的存儲(chǔ) 1．索引文件的存儲(chǔ) 索引文件在存儲(chǔ)器上分為兩 個(gè)區(qū)：索引區(qū)和數(shù)據(jù)區(qū)。 沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第二章 關(guān)鍵問(wèn)題分析 3 索引文件的操作 1．檢索操作 檢索分兩步進(jìn)行： ① 將外存上含有索引區(qū)的頁(yè)塊送 入 內(nèi)存，查找所需記錄的物理地址 ② 將含有該記錄的頁(yè)塊送 入 內(nèi)存 需要 注意 的是 ： ① 索引表不大時(shí)，索 引表可一次讀入內(nèi)存，在索引文件中檢索只需兩次訪問(wèn)外存：一次讀索引，一次讀記錄。查找表的建立可以為占據(jù)多個(gè)頁(yè)塊的索引表的查閱減少外存訪問(wèn)次數(shù)。 3． 動(dòng)態(tài)索引 當(dāng)數(shù)據(jù)文件在使用過(guò)程中記錄變動(dòng)較多時(shí)，利用二叉排序樹(shù) (或 AVL 樹(shù) )、沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第二章 關(guān)鍵問(wèn)題分析 4 B_樹(shù) (或其變型 )等樹(shù)表結(jié)構(gòu)建立的索引，為動(dòng)態(tài)索引。 （ 3）外存的索引表的查找性能評(píng)價(jià) 由于訪問(wèn)外存的時(shí)間比內(nèi)存中查找的時(shí)間大得多，所以外存的索引表的查找性能主要著眼于訪問(wèn)外存的次數(shù)，即索引表的深度。本系統(tǒng)采用倒排文件的方法對(duì)原文件建立索引，索引文件與原文件之前用指針鏈接，查詢時(shí)先在由鍵盤(pán)輸入查找關(guān)鍵字，然后 到索引文件的詞文件中查找與查找關(guān)鍵字相同的字段，如果兩者相同，通過(guò)鏈接的指針，可給出該詞在原文中的位置，并將其前后約 20個(gè)字符顯示出來(lái)。 本系統(tǒng)是對(duì)常用詞表進(jìn)行查找的工具，因此詞庫(kù)文件由手動(dòng)添加。 沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第二章 關(guān)鍵問(wèn)題分析 5 第二章 關(guān)鍵問(wèn)題分析 索引算法分析 散列文件的組織方式 散列文件是利用散列存儲(chǔ)方式組織的文件，亦稱直接存取文件。需要將第m+1 個(gè)同義詞存放到另一個(gè)桶中，通常稱此桶為 溢出桶 。 散列文件的查找操作 在散列文件中查找的過(guò)程： （ 1） 根據(jù)給定值求出散列桶地址 （ 2） 將基桶的記錄讀人內(nèi)存，進(jìn)行順序查找 （ 3） 若找到關(guān)鍵字等于給定值的記錄，則檢索成功；否則，讀人溢出桶的 沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第二章 關(guān)鍵問(wèn)題分析 6 記錄繼續(xù)進(jìn)行查找。 （ 3） 存取速度快；不需要索引區(qū)，節(jié)省存儲(chǔ)空間。 具體組織方式： 對(duì)每個(gè)需要查詢的次關(guān)鍵字建立一個(gè)索引，同時(shí)將具有相同次關(guān)鍵字的記錄鏈接成一 個(gè)鏈表，并將此鏈表的頭指針、鏈表長(zhǎng)度及次關(guān)鍵字，作為索引表的一個(gè)索引項(xiàng)。 多重表的更新操作 1．插入新記錄 相同次關(guān)鍵字鏈表不按主關(guān)鍵字大小鏈接時(shí)，在主 文件中插入新記錄后，將記錄在各個(gè)次關(guān)鍵字鏈表中插在鏈表的頭指針之后即可。 倒排文件中的次關(guān)鍵字索引稱做倒排表。 3．倒排文件的更新 在插入和刪除記錄時(shí)，還要修改倒排表。英文單詞由于用空格分隔，比較好處理。倒排索引把這個(gè)關(guān)系倒過(guò)來(lái)，變成：“關(guān)鍵詞”對(duì)“擁有該關(guān)鍵詞的所有文章號(hào)”。我們注意到關(guān)鍵字是 按字符順序排列的，因此可以用二元搜索算法快速定位關(guān)鍵詞。 假設(shè)要查詢單詞 “ live”，搜索引擎先對(duì)詞典二元查找、找到該詞，通過(guò)指向頻率文件的指針讀出所有文章號(hào)，然后 返回結(jié)果。順序查找 (Sequential Search)是一種最簡(jiǎn)單的查找方法。 基于順序結(jié)構(gòu)的順序查找算法 （ 1）類型說(shuō)明 typedef struct{ KeyType key； InfoType otherinfo； //此類型依賴于應(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。 ③ 表中各結(jié)點(diǎn)的查找概率并不相等的 ASL 若事先知道表中各結(jié)點(diǎn)的查找概率不相等和它們的分布情況，則應(yīng)將表中結(jié)點(diǎn)按查找概率由小到大地存放，以便提高順序查找的效率。 ⑤ 順序查找的缺點(diǎn) 沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第二章 關(guān)鍵問(wèn)題分析 12 查找效率低，因此，當(dāng) n較大時(shí)不宜采用順序查找。 二分查找的基本思想 二分查找的基本思想是：（設(shè) R[low..high]是當(dāng)前的查找區(qū)間） （ 1）首先確定該區(qū)間的中點(diǎn)位置： （ 2）然后將待查的 K值與 R[mid].key 比較：若相等，則查找成功并返回此位置，否則須確定新的查找區(qū)間，繼續(xù)二分查找，具體方法如下： ① 若 R[mid].keyK，則由表的有序性可知 R[mid..n].keys 均大于 K，因此若表 中存在關(guān)鍵字等于 K 的結(jié)點(diǎn)，則該結(jié)點(diǎn)必定是在位置 mid 左邊的子表R[1..mid1]中，故新的查找區(qū)間是左子表 R[1..mid1]。這一過(guò)程重復(fù)直至找到關(guān)鍵字為 K的結(jié)點(diǎn)，或者直至當(dāng)前的查找區(qū)間為空 (即查找失敗 )時(shí)為止。 圖 二分查找算 法的執(zhí)行過(guò)程 1 沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第二章 關(guān)鍵問(wèn)題分析 14 圖 二分查找算法的執(zhí)行過(guò)程 2 二分查找判定樹(shù) 二分查找過(guò)程可用二叉樹(shù)來(lái)描述：把當(dāng)前查找區(qū)間的中間位置上的結(jié)點(diǎn)作為根，左子表和右子表中的結(jié)點(diǎn)分別作為根的左子樹(shù)和右子樹(shù)。樹(shù)中圓結(jié)點(diǎn)內(nèi)的數(shù)字表示該結(jié)點(diǎn)在有序表中的位置。 （ 2）二分查找判定樹(shù)的查找 二分查找就是將給定值 K與二分查找判定樹(shù)的根結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較。 由此可見(jiàn)，成功的二分查找過(guò)程恰好是走了一條從判定樹(shù)的根到被查結(jié)點(diǎn)的路徑，經(jīng)歷比較的關(guān)鍵字次數(shù)恰為該結(jié)點(diǎn)在樹(shù)中的層數(shù)。因此在等概率假設(shè)下，二分查找成功時(shí)的平均查找長(zhǎng)度為： ASLbn≈lg(n+1) 1 二分查找在查找失敗時(shí)所需比較的關(guān)鍵字個(gè)數(shù)不超過(guò)判定樹(shù)的深度，在最壞情況下查找成功的比較次數(shù)也不超過(guò)判定樹(shù)的深度。既使采用高效率的排序方法也要花費(fèi) O(nlgn)的時(shí)間。 對(duì)那些查找少而又經(jīng)常需要改動(dòng)的線性表， 可采用鏈表作存儲(chǔ)結(jié)構(gòu)，進(jìn)行順序查找。 二分查找表存儲(chǔ)結(jié)構(gòu) 二分查找表由 分塊有序 的線性表和索引表組成。 分塊查找的基本思想 分塊查找的基本思想是： （ 1）首先查找索引表 索引表是有序表，可采用二分查找或順序查找，以確定待 查的結(jié)點(diǎn)在哪一塊。 ① 以二分查找來(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。 （ 3） 結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu) 各塊可放在不同的向量中，也可將每一塊存放在一個(gè)單鏈表中。本題使用的方法為倒排文件索引方法，既對(duì)導(dǎo)入的文本文件先按照詞庫(kù)文件建立倒排索引。 程序總體模塊圖 搜 索 引 擎查 找信 息所 在文 件建 立詳 細(xì)信 息索 引建 立倒 排文 件索 引建立查詢索 引建立索引查詢?nèi)?得查 詢信 息顯 示查 詢結(jié) 果 圖 程序總體模塊圖 沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第 四 章 詳細(xì)設(shè)計(jì) 21 第四章 詳細(xì)設(shè)計(jì) 深入剖析倒排文件索引算法 一個(gè)搜索引擎的靈魂就是索引數(shù)法，只有好的算法才能完成快速搜索的任務(wù)。 //所在文件名 long place。 char b[32]={0}。 int i。t\n)。t\n)。amp。im。amp。amp。amp。 } if( ((e[0] == 10) || (e[0] == 39。 (b[0] != NULL) ) { if(strcmp(a,b) != 0) { m = strlen(b)。 } } if(strcmp(a,b) == 0) { strcpy(file[n].word,a)。 fwrite(amp。 m = strlen(a)。 b[i] = 0。 } 此函數(shù)完成的功能為把 inname 所指向的文件按照 Term Dictionary(詞庫(kù)文件 )建立倒排索引后，寫(xiě)入 outname 所指文件。 :GetWindowText（）函數(shù)是獲得查詢關(guān)健字。用戶對(duì)于界面視覺(jué)效果和軟件操作方式的易用性的關(guān)心，要遠(yuǎn)遠(yuǎn)大于他對(duì)底層到底用什么樣的代碼去實(shí)現(xiàn)的關(guān)心。 沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第 四 章 詳細(xì)設(shè)計(jì) 27 程序主界面如圖 所示： 圖 程序主界面 沈陽(yáng)航空工業(yè)學(xué)院學(xué)士學(xué)位論文 第 四 章 詳細(xì)設(shè)計(jì) 28 圖顯示輸入查詢關(guān)鍵字： 圖 輸入查詢關(guān)鍵字