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