簡單實現了各個模塊的功能，對整體有了了解，當然不是實用的系統。問題很多，抽時間繼續學習。

系統的整體設計

（1）網絡爬蟲模塊：該模塊是從URL庫中獲得輸入，解析URL中表明的Web服務器地址，建立連接，發送請求和接受數據，將獲得的網頁數據存儲在原始網頁庫中，并從其中提取出連接信息放入網頁結構庫（堆棧或者隊列）中，同時將待抓取的URL放入URL庫，保證整個過程遞歸進行，直到URL庫為空。使用Key-Value數據庫或者文件等實現URL的去重工作保證不對相同的URL重復爬取。

該模塊的主要功能：

下載網頁數據，為搜索引擎系統提供數據來源，通過網頁中的連接信息不斷獲得網絡上的網頁。

種子URL集合的選取原則：

(a) 基于主題的數據采集是采集互聯網上與某一固定主題相關的數據，所以要選取特定的種子URL，根據這些種子URL采集其周圍的數據。

(b) 選擇一些重要的、權威的、出度較大的網站的URL作為種子URL。

基本流程：

本實驗中，采取深度優先的爬取策略，爬取的流程為：首先是初始化，設置網頁爬取的最大深度，將種子連接壓入堆棧，并設置這些連接的深度為1，從硬盤中讀取保存已經訪問過的網頁的文件，將這些已訪問過的URL保存在HashSet集合中。

循環從棧頂取出URL，直到該URL未被訪問過，新建Page對象，設置對象的URL屬性。新建URL對象，調用該對象的openStream方法，從該流中按行依次讀取網頁的內容。如果該網頁的深度小于閾值，則需要獲得該page頁面中的URL。調用getUrlByString方法，該方法中用正則表達式提取文本中的鏈接，正則表達式為String patternString ="<[a|A]\\s+href=([^>]*\\s*>)"，如果提取出的URL沒有在visitedHashSet出現過，則將URL添加到page對象中網頁列表中，并設置該URL的深度為父網頁的深度加一。

完整讀取網頁的中的內容后，需要將該網頁以HTM的文件格式保存在硬盤中，供后續的預處理、分詞、建索引等步驟。該實驗中，用網頁URL的MD5碼作為網頁的唯一標識。函數getMD5就是通過傳入URL字符序列產生唯一的MD5碼。由于網頁的數目較多，因此以1000為單位將網頁保存不同的文件夾下。該實驗中，網頁保存在/file/download/目錄下。

將分析完的URL添加到visitedHashSet中，表明已經訪問過。將網頁中的鏈接列表push到鏈接的堆棧中。依次從堆棧中取出元素，執行以上過程，直到堆棧為空。

將已訪問過的URL寫到URLlist.txt文件中，程序結束。

該模塊的流程圖如下圖所示：

（2）正文提取模塊：網頁中包含各種標簽，廣告等內容，該模塊的功能就是通過基于行塊分布函數的正文提取方法，識別和清除網頁內容噪音內容，并提取網頁的主題，包括網頁的標題、摘要、正文等內容。

該模塊的主要功能：

從給定的網頁中抽取出標題、摘要、正文等信息，去除網頁中的噪音，包括網站的導航信息和相關鏈接廣告等內容。

該模塊的實現方法：

本實驗采用基于行塊分布函數的網頁正文提取方法（開源項目）。

基本思想：脫離HTML標簽，通過建立行塊分布函數，用線性時間找出HTML文件的正文。一個網頁的正文部分一般是網頁中文字信息分布最密集的區域之一，也有可能是較長信息的評論或出現大篇幅的導航信息。這種情況下就要結合行塊的長度信息解決該問題。通過分析網頁中行塊長度的聚升點和聚降點尋找正文。

該算法的基本流程：

首先設置行塊的厚度為3，正文區的密度閾值為150，增大該閾值可以去除網頁正文中成塊的新聞標題，提高準確率，但有可能將部分正文信息去除，降低了召回率。減小該閾值可以保證找到只有一句話的正文，但是降低了召回率。

獲取該HTML文件中的文本，根據<title>標簽，用正則表達式提取出網頁中的標題。將網頁中的HTML規范、注釋信息、javascript腳本、樣式信息、特殊字符等內容用空白符代替，這樣就得到只有文字內容的文本，將文本分行保存在list集合中，提供給后序步驟處理。以3行為一塊求出每塊的長度，即每個塊的文本去掉空白符剩下的字符長度。

設置正文的起始位置start、終止位置end、起始標志boolstart和終止位置boolend。從第0個塊開始依次遍歷每個塊，當第i個塊的長度大于閾值并且起始標志boolstart為false，第i+1、i+2和第i+3行中某行長度不為0，則說明找到一個聚升點。設置起始標志boolstart為false，起始位置start為i。接著繼續往下遍歷，當第i行或第i+1行某行長度為0，說明找到一個聚降點，設置終止位置end為i，終止標志boolend為true。這時就找到一個正文段，提取出行號為start到end的文本作為網頁的正文。繼續遍歷往下的塊信息，只要找到一個聚升點和一個聚降點，則找到一段正文。

當遍歷完所有的塊信息后，設置網頁的正文、摘要（目前摘要的提取是將文本的前30個字符作為摘要。也可將文檔中包含權重最大的詞的一段文本作為文檔的摘要）。

算法結束。

算法的基本流程如下圖所示：

（3）網頁去重模塊：在大量網頁中，存在內容完全相同的網頁，也有一些網頁內容基本相同，只是有細節上細微的不同，例如轉載網頁等。系統需要將這種網頁進行去重處理。該系統采用基于指紋識別的思想對網頁進行重復性判斷。

該模塊的主要功能：

網絡上可能會出現多個域名對應同一個網站的情況或者網站的互相轉載。去除重復的網頁是為了避免同一個網站的內容被多次采集和索引。 網頁消重就是指去除網頁集合中轉載網頁（即文本內容基本相同）的過程。

該模塊的基本思想：

為每個文檔計算出一組指紋（fingerpint），這些指紋可以是網頁內容中的一系列字符串的hash值或者MD5散列值，若兩個文檔擁有一定數量的相同指紋，則認為兩個文檔的內容重疊性較高，即二者是內容轉載的。

算法的基本流程：

分析網頁文檔時，提取并記錄網頁中出現的關鍵詞，同時根據公式賦予每個關鍵詞一個權值，這些關鍵詞的權值構成一個向量空間，可以用來表示網頁。

將網頁中權重最大的前N個關鍵詞按字母進行排序后再拼接成一個字符串，記為Concatenate(sort(T))，用MD5對這個字符串產生散列值MD5(Concatenate(sort(T)))。

若兩個網頁的散列值相同，則認為二者是相互轉載的。在實際程序運行期間，每當需要分析一個新的文檔時，提取文檔的前N個關鍵詞，并按上述方法產生MD5散列值，將該散列值與之前分析完的所有文檔進行比較，當這個新的文檔的MD5散列值已經出現過時，說明這個文檔時重復文檔，刪掉即可。

（4）中文分詞模塊：中文與英文不同，英文詞與詞之間有天然的分隔符，中文詞匯大多是連續的，因此需要進行自動分詞工作。該模塊采用正向最大匹配的算法進行分詞，用Trie樹保存詞典。

該模塊的主要功能：

目前的中文檢索系統中大多支持基于詞的檢索，因此需要對文本進行自動的詞語切分，該過程也就是中文分詞。

該模塊的實現：

目前網絡上有很多的開源分詞工具IKAnalyzer、ICTCLAS、Paoding等等，本實驗中采用自己設計的分詞方法進行分詞。

本實驗采用正向最大匹配的算法進行分詞。

算法的基本思想：

正向最大匹配算法的基本思想：從左到右將待分詞的文本中的幾個連續字符與詞表匹配，如果匹配上則找到一個詞。當下一個掃描不是詞表中的詞或某個詞的前綴，則結束。繼續分析后面的文本。

用Trie樹保存詞典。Trie樹也稱為前綴樹，用Trie樹保存詞典能將文本的所有可能分詞找出，無論該詞有多長。Trie樹還適用于查找單詞前綴，如查找所有以“中華民”開頭的單詞，包括“中華民國”、“中華民族”等。

Trie樹的結構如下圖3-3：

Trie樹的最壞的情況下搜索的時間代價是O(h)，h為Trie樹的層數。

（1）每個結點都是詞語的一個漢字。

（2）結點中的指針指向了該漢字在某一個詞中的下一個漢字。這些指針存放在以漢字為key的hash結構中。

（3）結點中的“#”表示當前結點中的漢字是從根節點到該漢字結點所組成的詞的最后一個字。

正向最大匹配的具體實現過程為：

首先：讀取保存文本內容的文件。

設置起始位置startPosition，startPosition用于保存分詞的開始位置，依次遍歷文本中的每一個字符，先初始化Tocken為空，令position為startPosition的位置，當Trie樹包含position位置的字符letter時，根據指針獲得該字符letter對應的節點node，判斷該node的結尾標識是否為true，為true說明找到一個分詞，found設置為true，繼續遍歷下一個position對應的字符，當遍歷到的字符不是某個詞的前綴時，停止遍歷。

判斷found是否為true，若為true，則將這次遍歷找到的最長的詞保存下來，并將startPosition后移該詞的長度個位置，若found為false，則說明沒有找到一個分詞，將startPosition后移一個位置。當startPosition超出文本的長度時，算法結束。

分完詞的文件保存在file/wordFiles/目錄下。

該過程的流程圖如下圖所示。

（5）倒排索引模塊：該模塊是網頁預處理的核心部分，采用基于增量的倒排索引結構保存倒排文件，便于倒排文件的更新等操作。

倒排索引概念：

倒排索引的索引的對象是文檔或文檔集合中的單詞，存儲這些單詞在一個文檔或者一組文檔中的存儲位置，是對文檔或文檔集合的一種最常用的索引機制。

倒排文件的組成部分：

倒排文件一般包括兩個部分：詞匯表（vocabulary）和記錄表（posting list）。詞匯表是文檔或者文檔集合中所有不同單詞的集合。對于詞匯表中的每一單詞，其在文檔中出現的文檔編號列表的集合構成記錄表。

本實驗采用的索引文件結構：

傳統的靜態信息檢索系統由于文檔集合相對穩定，索引一旦建立很少進行更新，需要更新時要重新建立整個檢索文件。由于搜索引擎的索引結構需要支持高效的更新功能。因此，本實驗中，采用一種增量索引結構。在建立倒排索引時，每個詞項的記錄表以連接塊的形式存放于倒排索引文件中。

本次實驗的索引結構如下圖3-6所示：

該索引結構分為三個文件：

詞項文件：該文件保存三個值的集合，第一個保存文檔集合中出現的所有詞項，用Term表示，第二個值為該詞項對應的IDF值，即詞項的反文檔頻率。該值的計算過程將在后面進行論述。第三個值是該詞項對應的記錄表在記錄表文件中的位置（類型為long的一個偏移量）。

記錄表文件：記錄表中存放posting list集合，每個posting list按塊存儲，存儲的格式如圖中所示：首先是詞項對應的文檔集合的個數，接下來是每個文檔的記錄，包括文檔的編號、文檔中該詞項出現的次數、最后一個是指向位置文件的指針，該指針保存指向位置文件的偏移量。

塊的最后是一個指向下一塊的指針，該指針保存指向記錄表中該詞項對應的另一個posting list塊的位置。

位置文件：該文件保存位置信息，同樣是按塊進行存儲。每個塊中首先是位置的個數，然后是具體的位置列表。

每當新的一批文檔集合需要插入該索引結構時，首先將這批文檔集合在內存中建立索引結構，然后更新該索引結構。

該模塊的實現：

該模塊主要有一下幾個類：

MFile類：用于保存文檔信息，包括文檔的編號、文檔對應的URL、文檔的標題、文檔的摘要、文檔的大小以及用于相關性排序的文檔權重等屬性。

Word類：用于保存新來的一批文檔中的詞項信息，包括該詞的文本內容、詞的權重(即IDF值)、出現該詞的文檔列表等信息。

Vocabulary類：用于保存新來的一批文檔中所有的詞匯表，包括所有詞匯，用HashMap保存。

DWord類：用于保存從硬盤中讀取的詞匯信息，包括該詞的文本內容、出現過該詞的文檔數目、該詞的權重(即IDF值)、該詞在索引文件中的偏移量等信息。

DVocabulary類：該類用于保存從硬盤中讀取的詞匯表信息，包括所有詞匯，用HashMap保存。

Index類：該類用于建立索引結構。

該模塊的類圖如下圖3-7所示：

建立索引結構的過程：

首先，將整個詞項文件讀入內存（由于該文件并不大，因此可以直接放在內存里，供后續步驟使用），每個詞項包括該詞的文本信息、權重和該詞對應的記錄表中對應的偏移量，用DWord對象保存該詞項，并將該DWord對象保存到新建的DVocabulary對象中，讀完后DVocabulary對象保存的就是所有的詞項信息。

分別讀取記錄表文件和位置文件的文件尾位置。

遍歷所有分好詞的文件，新建MFile對象，并設置該對象的標題、文件編號等信息。遍歷該文件中所有的分詞，調用vocabulary對象的add方法，若該詞不存在，則新建Word對象（該詞文本、MFile對象和位置號為構造函數的參數）；若該詞已經存在，則將該文件對象和位置號保存到已有的word對象中。當遍歷完所有分好詞的文件后，vocabulary對象中即保存了新來的這批文檔中的詞項信息。

接著遍歷vocabulary對象中所有的Word對象，根據該Word對象查找dVoabulary對象中是否出現過該詞。

如果沒有出現過該詞，則新建DWord對象，設置該對象的文本、對應的文檔數（即該批文檔的數目）、對應的記錄表的偏移量（即當前記錄表的文件尾位置）。將DWord對象添加到dVoabulary對象中。定位到記錄表的文件尾位置，首先寫入該詞對應的文檔數，然后依次將文件號、指向位置文件的指針寫入記錄文件。將nextPointer位置寫入0，表明該塊與另外一塊相連。

如果該詞在詞項文件中出現過，則首先更新對應的DWord對象的文件數，即在原來的值上加上新來的這批文檔中所包含該詞的文件數。然后根據DWord對象的offset屬性找到該詞在記錄表中第一個記錄塊，循環遍歷這些相連的記錄塊，直到找到最后一個記錄塊的nextPointer指針，此時該指針的值為0，將該nextPointer指針設置為記錄表文件尾位置。然后定位到記錄表的文件尾位置，同樣首先將該詞對應的文件數寫到該文件中，然后依次將文件號和該詞在文件中位置的個數寫入記錄文件，并且將位置列表寫入位置文件。

當處理完這批文檔后，需要更新詞項文件中的內容。遍歷dVoabulary對象中的所有DWord對象，重新計算該詞項的IDF值。該IDF值為詞項的反文檔頻率，計算公式為log2(N/DF)，N為所有的文檔總數，DF為包含該詞項的文檔數量。如果包含該詞項的文檔越多，則說明該詞在區分文檔內容的能力上卻低，蓋茨向的IDF也就越小。計算完權重后，將所有的詞項信息重新寫回到詞項信息文件中。

建立索引的過程即結束。

該過程的流程圖如下圖3-8所示。

（6）相關性排序模塊：該模塊采用空間向量模型對檢索出來文檔進行相關性排序，并將結果反饋給用戶。

相關性排序概念：

用戶在進行信息檢索時，希望獲得與其需求密切相關的檢索結果，因此信息檢索系統的核心問題是：當用給定查詢后，對文檔集中的每一個與用戶查詢相關程度進行判斷。也就是對所有相關文檔按照相關度由大到小的排序過程。

本實驗使用的相關性模型：

三種經典的模型：布爾模型、空間向量模型和概率模型等。本實驗采用的是空間向量模型（好吧，真正的搜索引擎應該pagelink之類的算法，這里用最簡單的，作為示例）。在空間向量模型中，文檔和查詢均被看成由索引項構成的向量。

計算網頁與查詢的相關性。即計算查詢詞與文本索引項構成的兩個向量的夾角。計算公式如下圖3-9所示。

其中dik是文檔di中詞項k的權重，qk是查詢時Q中詞項k的權重。

計算相關度的流程為：

首先創建Dvocabulary對象，讀取保存所有詞項信息的文件index.tl，將每個詞項信息保存到DWord對象中，包括詞項的文本、權重和該詞項對應的記錄表中的偏移量。將該DWord對象保存到Dvocabulary對象中，Dvocabulary對象中即保存了所有的詞項信息。

讀取保存所有文件信息的文件docinfo.txt，以便于根據用戶輸入選擇網頁的ID快速找到相應網頁的URL，標題和摘要等。然后等待用戶輸入。

當用戶輸入完成后，獲取用戶查詢的文本。

對用戶查詢的文本進行分詞，得到查詢詞的列表。

遍歷所有的用戶查詢詞，根據該詞從DVocabulary中得到對應的Dword對象。根據DWord對象中的offset值讀取記錄表文件，若有多塊記錄表，則根據nextPointer依次讀取每個塊，從而從記錄表中得到該詞相關的文件集合。

將各個詞對應的文件集合進行集合的交操作，得到的文件包含所有的查詢詞。

對每個相關文檔用空間向量模型計算該文檔與查詢的相關度。

根據文檔號從文檔信息中得到公式中dik*dik的值。

計算dik*qk和qk*qk的值，從而求出兩個向量的夾角的值。

當求出所有相關文檔的相關度后，按照相關度的值對這些文檔進行排序，并將排序結果展示給用戶。可以通過強制設定某個閾值，控制被檢索出來的文檔的數量。檢索結果可以被用于相關反饋中，以便對原始的查詢式進行修正。

搜索結果如下圖所示。

參考：

劉挺，秦兵，張宇，車萬翔. 信息檢索系統導論.

邱哲，符滔滔，王學松. 開發自己的搜索引擎.

李曉明，閆宏飛，王繼民. 搜索引擎-原理、技術與系統.

王冬，左萬利. 一種增量倒排索引結構的設計與實現.

總結

以上是生活随笔為你收集整理的一个简单检索系统的实现思想的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。