全文搜索引擎技術的研究和實現-資料下載頁

【導讀】論文研究目的和意義···········································································&#183

　　

【正文】 儲成自定義的數據庫格式，索引器和查詢根據需要對原始 Web 數據的調用。以下詳細介紹天網格式的網頁存儲數據庫， 所有的記錄 儲存于一個原始頁面 ，每一個記錄包括一個 原始的 HTML 文檔頁面，在記錄之間沒有界限 ，一個記錄的是有頭 23 部 Header，數據 HTML 文檔和一個空行加一個字符‘ \n’組成，例如： Header+空行 +HTML 數據 +‘ \n’。 Header 中包含了許多屬性，每一個屬性為一個非空行，在 Header 中禁止出現空行 ，每一個屬性和其值以分號“：”做間隔， Header 中的第一個屬性 必須是版本屬性，例如： version： ， Header 中最后一個屬性必須是長度屬性例如： length： 1800，為了簡便，所有的屬性名稱要求是小寫的形式，如下圖所示： 圖 37 天網格式 1 Tianwang format1 24 圖 38 天網格式 2 Tianwang format2 幾個有關的 存儲類 封裝了對文件流的基本操作， UML 設計如下圖 ： 25 圖 39 存儲類 Storage Class 索引模塊 分析 前端 服務程序 在接收查詢關鍵 字時如果直接就在原始網頁文件中去尋找匹配的網頁會導致查詢時間非常的長，因為原始網頁文檔 數 可能是上千萬甚至過億級的，所以我們需要在原始網 頁文檔與查詢操作之間建立一個中間層，這里采用倒排索引的數據結構 和 IASM 格式 索引表 ， IASM 格式 索引表記錄了所有文檔的信息 ， 例如：詞組 +‘ \t’ +文檔編號 序列 號 ， 文檔 編號 +‘ \t’ +上一 文檔結束位置相對整個原始數據 文檔 偏移 字節 數即本文檔的開始字節數 +‘ \t’ +該文檔的 md5哈希值 ， 這兩個 索引結構也是我們的核心數據結構 ， 如下圖所示： 26 圖 310 倒排索引 Inverted Index 圖 311 倒排索引 文件 索引表 ISAM[17] Inverted index file index table ISAM[17] 文檔解析類 其主要分析并存儲從一篇文檔中 解析出來的各個部分標簽內容。 27 圖 311 文檔解析類 Type of document analysis 相關性排序 及 查詢 關鍵字 查詢模塊是直接與用戶進行交互的操作，在接口上有多種實現方式，常見的主要 Web 方式，另外可以通過無線接入方式（如手機）進行 查詢。 關鍵字查詢模塊 工作原理如圖 312所示： 圖 312 查詢模塊工作原理圖 Query module schematic 查詢模塊通過某種接口方式，接受用戶查詢，對查詢進行分詞（ stemming）處理，獲取查詢關鍵字。通過 索引器 獲取與查詢關鍵字匹配的網頁數據，經過排 28 序后返回給用戶。 查詢器中的關鍵問題： （ 1） 檢索結果的排序 ， 由于搜索引擎返回結果非常多，檢索結果是否按用戶預期的順序排列是評價搜索引擎的重要指標之一。一些新的嘗試，比如對用戶偏好的分析技術入個性化搜索等都可以運用在 這里，對不同編號的用戶采用不同的排序策略。 （ 2） 檢索結果的排重能提高數據的質量。檢索結果的數量給排重帶來資源上的開銷及速度上的影響。搜索引擎需要在其中作出權衡。 （ 3） 檢索結果的相似性分析主要用在類似網頁功能中，需要在索引結構中提供支持。 （ 4） 檢索的速度主要依賴索引結構的設計。同時在體系結構上 還有很多技術可以用來提升速度。如 Cache、負載均衡等。 檢索結果的排序采用的是向量空間模型 [18]， 向量空間模型 (或詞組向量模型 )是一個應用于資訊過濾 ， 資訊獲取 ， 索引 以及評估相關性的代數模型 。文件 (語料 )被視為 索引詞 (關鍵字 )形成的多次元向量空間， 索引詞的集合通常為文件中至少出現過一次的詞組。搜尋時，輸入的檢索詞也被轉換成類似于文件的向量，這個模型假設，文件和搜尋詞的相關程度，可以經由比較每個文件 (向量 )和檢索詞 (向量 )的夾角偏差程度而得知。 事實上 ，計算夾角向量之間的余弦比直接計算夾角容易： 1212cosvvvv? ?? 余弦為零表示檢索詞向量垂直于文件向量，即沒有符合，也就是說該文件不含此檢索詞。 本搜索引擎提供關鍵詞查詢服務，在實際的搜索引擎過程中 ，當用戶輸入關鍵字，然后 根據 倒排 索引 表 文件去 匹配 相應的 網頁的 URL， 再在天網格式的原始數據文件中讀取 相應的 HTML 出來， 如果用戶 選擇 繼續查找就從這個偏移位置開始繼續查找 匹配 ， 在實際現實中會出現滾屏，我就只顯示前面一部分出來，這樣用戶看得也比較清楚。 這以功能的原型在 Cquery 類中，如圖 313 所示： 29 圖 313 查詢服務 解析 類 Analysis service category 小結 本搜索引擎的整體 運行 結構為，爬蟲采集器通過在網頁上持續的采集下來 Web網頁，以天網格式的 Web 數據庫存儲格式存放在本地磁盤上， 索引器對 Web網頁數據庫 建立相應的索引表和倒排索引表，查詢器通過獲取用戶的查詢關鍵字通過事先建立好的索引表從 Web 數據庫中查詢出需要的結果頁返回給用戶 ，這樣獨立的三塊 增加了系統的性能和可擴展性 。 該架構下的小型搜索引擎 提供 了 以 下等 功能， 高可用爬蟲系統，支持 HTTP 持續連接， 支持 DNS 緩存， 支持 IP塊限制，支持 過濾不可達 網站，支持鏈接分析提取，支持 可重復的爬取。 天網格式的輸出帶來更好的容錯性， 支持關鍵詞的查詢，正向匹配最大窗口。 30 第四章 全文搜索引擎 的實現 實現技術路線 本 全文搜索引擎基于 Intel x8 Linux（ RedHatLinux）平臺，編程語言為C++，面向對象方式編程 ， 主要使用 C++ STL 和 Linux 線程庫、 信號量 等 。 Web Crawler 采用多線程信號量，互斥鎖同步 策略的方式 ，數據的存儲、計算等采用 STL 中的 map， multimap， vector， iterator， sort 等容器 、迭代器 和算法 。 爬蟲 模塊 運行流程 在 Shell 中爬蟲模塊 的目錄 下執行 相應 命令 讓其在后臺脫離終端的運行 如圖 41： 圖 41 爬蟲的運行 The operation of reptiles 31 爬蟲程序會沿著 文件中的 種子 Url 遞歸的爬下去， 同時爬取的過程中內存里維持著兩個隊列 ，一個是已經訪問的 Url 隊列 ，一個 是未訪問的 Url 隊列，每從一個網頁中解析出新的 Url 就和已經訪問過的 Url 隊列做對比，如果不存在就將其加入到未訪問 Url 隊列里，存在就丟棄掉 ，爬蟲每次爬取的頁面從未訪問 Url 中選取，內存中這兩個 隊列在啟動和結束時都要和磁盤上 的 和 文件進行數據交換 。 分詞以及核心 數據結構文件的建立流程 在索引模塊的目錄下 依次 執行 以 下 命令： （ 1） nohup ./DocIndex amp。，將會得到 ， 文件 ； （ 3） nohup sort |uniq amp。，將會消去重復的 Url； （ 3） nohup ./DocSegment amp。，這一步將得到所有文檔的分詞文件 ，運行時會運用到 詞典文件； （ 4） nohup ./CrtForwardIdx idx amp。，這一步將會得到 每篇文檔的正向索引； （ 5） nohup sort amp。，這一步將會得到 排序后的正向文檔 ； （ 6） nohup ./CrtInvertedIdx amp。，最后這一步將會得到倒排索引文件。 查詢服務器運行流程 查詢服務程序會用到 、 、 、 文件。 TSESearch 接受前臺用戶的查詢關鍵詞首先將其分詞，通過 、 文件和向量空間模型算法計算出 關鍵詞相關的文檔 ID 集合，然后通過順序索引文件 Do 32 ，查詢出相應的動態摘要信息。 關鍵技術 編碼 實現 主要 實現了多線程并行爬蟲， 建立 順序 索引 和倒排索引等文件程序 ，其中部分代碼參考了一些開源 項目 [1925]。 爬蟲方面， 爬蟲采用信號量和線程互斥鎖的同步策略，通過記錄爬取過，不可達，未訪問 URL 中間文件 以達到 可持續 遞歸爬取的目的，可以持續重啟上一次爬取進程。 索引方面， 如果是直接通過原始網頁數據庫文件效率是非常的低下的，本搜索引擎索引的建立過程時通過幾個中間文件的處理來實現，首先由 DocIndex 程序產生 索引表文件， ， 等三個文件，通過命令 ：sort |uniq DocSegment 程序對原始網頁數據庫中的網頁進行分詞，分詞之后產生 .seg 的文件，使用CrtForwardIdx程序對其產生正向索引，最后通過 CrtInvertedIdx 程序產生倒排索引文件。 查詢服務程序通過獲取用戶關鍵詞字符串匹配 倒排索引查詢出對應的 URL 列表，再通過 順序索引表和網頁原始數據庫文件查詢出相應的頁面，返回給用戶。 多線程 爬 蟲 算法 爬蟲搜集器采用多線程并行爬取其中通過加鎖機制達到同步目的 ，并行爬蟲部分 核心代碼如下： //設置信號量每次關閉進程時觸發 內存中 Url數據 和磁盤文件 中 的同步 signal(SIGTERM， SigTerm)； signal(SIGKILL， SigTerm)； signal(SIGINT， SigTerm)； //恢復上一次結束時的狀態 thisGetVisitedUrlMD5()； thisGetVisitedPageMD5()； thisGetUnreachHostMD5()； //將 ipblock 讀入內存 33 thisGetIpBlock()； //打開 種子文件 ifstream ifsSeed(())； //打開天網格式的文件，為后面的輸出做好準備 OpenFilesForOutput()； //指定 創建線程 ID pthread_t *tids = (pthread_t*)malloc(NUM_WORKERS * sizeof(pthread_t))； for(unsigned int i=0； i NUM_WORKERS； i++) { //根據 ID 創建線程 pthread_create( amp。tids[i]， NULL， start， this) } 線程函數 部分 代碼： //創建天網格式的網頁原文文件 string ofsName = DATA_TIANWANG_FILE + . + CStrFun：： itos(pthread_self())； CTianwangFile tianwangFile(ofsName)； int iSleepCnt=0； //循環的下載分析網頁 Url for(；； ) { //打開一個資源鎖 pthread_mutex_lock(amp。mutexCollection)； int t = ()； if(t 0) { cout collection has： t unvisited urls endl； multimapstring， string：： iterator it=()； if( it != () ) { //獲得 Url strUrl = (*it).second； //從內存 Url隊列中刪除該條 ( it )； //解開 一個資源鎖 pthread_mutex_unlock(amp。mutexCollection)； //解析 URL CUrl iUrl； if( (strUrl) == false ) { cout ParseUrlEx error in fetch()： strUrl endl； continue； } if( strGHost != ) { 34 close( nGSock )； nGSock = 1； strGHost = ； } //下載網頁 (( CCrawl* )arg)DownloadFile(amp。tianwangFile， amp。link4SEFile， iUrl， nGSock)； t = 0； } else { pthread_mutex_unlock(amp。mutexCollection)； } } else { pthread_mutex_unlock(amp。mutexCollection)； usleep(1000)； iSleepCnt++； } if( b_fOver == true amp。amp。 iSleepCnt==200) break； } ()； 通過信號量和線程互斥鎖機制使其爬行過程中數據同步和關閉進程后重啟進程后保持上次同步效果的目的。 消重是通過信息摘要算法計算出 Url的 MD5值 ，也 頁面 整體 的 MD5 值來判斷是否重復抓取的，重復的頁面將放棄抓取。 分詞 算法 高效索引的 建立流程 用戶輸入可能是字符編碼 、標點符號等，需要做不同處理或忽略等， 分詞采用正向匹配最小窗口法， 字典是采用的北大 閆宏飛教授寫的 TSE搜索引擎中的 中文 詞典 。 建立正向索引是通過 分詞后的 文件直接生成 ， 然后 通過前面生成的 對其進行排序操作得到 以進行 倒排索引 的建立 。 分詞算法代碼如下： //分詞 預處理 函數 35 string CHzSeg：： SegmentSentenceMM (CDict amp。dict， string inputkeys) const { string s2=； unsigned int i， len； //循環過濾出 中文 查詢關鍵字 while (!()) { unsigned char ch=(unsigned char) inputkeys[0]； if(ch128) //如果是 ASCII 碼值 { i=1； len = ()； while (ilen amp。amp。 ((unsigned char)inputkeys[i]128) amp。amp。 (inputkeys[i]!=10) amp。amp。 (inputkeys[i]!=13)) {// LF， CR i++； } if ((ch!=32) amp。amp。 (ch!=10) amp。amp。 (ch!=13)) {// SP， LF， CR s2 += (0， i) + SEPARATOR； } else { if (ch==10 || ch==13) { s2+=(0， i)； } } if (i = ()) // added by yhf inputkeys=(i)； else break； // continue； } else { if (ch176) {// 中文標點等非漢字字符 i = 0； len = ()； while(ilen amp。amp。 ((unsigned char)inputkeys[i]176) amp。amp。 ((unsigned char)inputkeys[i]=161) amp。amp。 (!((unsigned char)inputkeys[i]==161 amp。amp。 ((unsigned char)inputkeys[i+1]=162 amp。amp。 (unsigned char)inputkeys[i+1]=168))) amp。amp。 (!((unsigned char)inputkeys[i]==161 amp。amp。 ((unsigned char)inputkeys 36 [i+1]=171 amp。amp。 (unsigned char)inputkeys[i+1]=191))) amp。amp。 (!((unsigned char)inputkeys[i]==163 amp。amp。 ((unsigned char)inputkeys[i+1]==172 || (unsigned char)inputkeys[i+1]==161) || (unsigned char)inputkeys[i+1]==168 || (unsigned char)inputkeys[i+1]==169 || (unsigned char)inputkeys[i+1]==186 || (unsigned char)inputkeys[i+1]==187 || (unsigned char)inputkeys[i+1]==191))) { i=i+2； // 假定沒有半個漢字 } if (i==0) i=i+2； // 不處理中文空格 if (!(ch==161 amp。amp。 (unsigned char)inputkeys[1]==161)) { if (i = ()) // 其他的非漢字雙字節字符可能連續輸出 s2 += (0， i) + SEPARATOR； else break； } if (i = ())； inputkeys=(i)； else break； continue； } } // 以下處理漢字串 i = 2； len = ()； while(ilen amp。amp。 (unsigned char)inputkeys[i]=176) i+=2； //調用分詞 程序 s2+=SegmentHzStrMM(dict， (0， i))； if (i = len) inputkeys=(i)； else break； } return s2； } 正向窗口最大匹配分詞核心代碼 ： string CHzSeg：： SegmentHzStrMM (CDict amp。dict， string inputkeys) const { string s2=； // sto