網絡搜索引擎的設計與實現

郭永利，盧穎穎

0 引言

隨著互聯網技術的飛速發展，互聯網中的信息量也越來越大，如何更加有效地利用這些信息資源，已經越來越受到人們的關注。互聯網中存在的信息來源十分廣泛，與此同時，存在的形式也是多種多樣，包括圖像、文本、視頻、音頻等不同的形式，面對著不同來源，不同形式的海量信息，如何準確、快速地找到自己所需要的信息成為我們在使用互聯網時候所面臨的一個問題，因此，開發一個搜索引擎就非常必要。目前，成熟的搜索引擎如 Lycos、Yahoo、Google、百度等各有優點[1]，如Google比Yahoo能更快、更準確搜索到所需信息，百度中文搜索引擎支持網頁信息檢索，圖片，Flash，音樂等多媒體信息的檢索等，而本文搜索引擎的開發是通過網絡爬蟲抓取信息，然后再通過一定的技術對網頁信息進行提取、處理，將抓取到的信息存放在索引數據庫中，通過一些查詢接口實現信息檢索，幫助用戶在海量的信息中迅速地、準確地找到用戶真正感興趣的信息。

1 搜索引擎的設計

1.1 搜索引擎結構設計

搜索引擎是指根據一定的策略、運用特定的計算機程序從互聯網上搜集信息，在對信息進行組織和處理后，為用戶提供檢索服務，將用戶檢索相關的信息展示給用戶的系統。搜索引擎主要包括全文索引、目錄索引、元搜索引擎、垂直搜索引擎、集合式搜索引擎、門戶搜索引擎與免費鏈接列表等。全文搜索引擎是目前廣泛應用的主流搜索引擎[2-3]。它可以對被索引的文章中的每一個詞建立索引，在用戶檢索時，檢索程序就會根據事先建立好的索引進行查找，并將查找的結果反饋給用戶。本文的主要工作就是使用 Java設計并實現了一個Web全文搜索引擎，搜索引擎結構設計如圖1所示：

圖1 搜索引擎結構

1.2 網絡蜘蛛結構設計

創建搜索引擎的第一步就是要設計一個程序在海量的互聯網信息中漫游，并抓取網頁信息。這個程序被稱為網絡蜘蛛，網絡蜘蛛也被稱為自動搜索機器人，它主要用于分析網頁上的每一個超鏈接，并根據超鏈接鏈到其他網頁中的超鏈接[4]，網絡蜘蛛結構設計如圖2所示：

圖2 網絡蜘蛛結構

1.3 索引器結構設計

搜索引擎對網絡蜘蛛抓取到的網頁信息進行整理，這一過程稱為“創建索引”。索引器結構設計如圖3所示：

圖3 索引器結構

1.4 檢索器結構設計

搜索引擎每時每刻都要收到來自大量用戶的幾乎是同時發出的查詢，它按照每個用戶的要求檢查自己的索引，在極短時間內找到用戶需要的資料。檢索器結構設計如圖4所示：

圖4 檢索器結構

2 網絡蜘蛛的實現

2.1 網絡蜘蛛爬行策略實現算法

互聯網可以看成一個超級大的“圖”，網絡蜘蛛的遍歷網頁算法采用圖的寬度優先遍歷(BFS)算法，其爬行策略實現算法如下[5]：

1）將入口URL入隊至待訪問URL的隊列中去。

2）URL從待訪問URL隊列出隊，使用開源HTML解析庫HTMLParser對給出的入口URL進行解析，判斷抓取到的URL是否在已訪問URL集合中，若不在，則將URL存儲在待訪問URL的隊列中去（入隊），若存在則什么也不做。

3）使用HTMLParser對出隊的URL進行解析，解析該URL的標題、內容、關鍵詞、創建時間等信息。

4）使用Lucene為HTMLParser解析到的網頁信息創建索引。

5）出隊的URL添加至已訪問URL集合中去。

6）重復（2）～（5）的過程。

2.2 網絡蜘蛛的具體實現

（1）數據結構：隊列和散列表（哈希表）

首先要構建用于存儲抓取到的URL待訪問的URL隊列，在構建隊列時需要考慮以下兩方面因素：

1）隊列中將要存儲的元素個數非常之多并且數量無法確定；

2）在隊列的隊頭和隊尾處經常進行刪除和添加操作。

針對以上兩點，使用java集合類LinkedList的鏈式存儲結構來實現未訪問URL隊列。這個未訪問URL隊列主要用來存儲爬蟲抓取到的 URL，通過一系列的出隊入隊操作實現對網頁的寬度優先遍歷。

（2）要構建散列表。在根據未訪問URL隊列對URL進行抓取和解析的時候，還需要一個數據結構散列表來存儲已經訪問過的URL來避免對同一個URL的重復抓取和解析。在URL從未訪問隊列出隊以后，首先，判斷一下，它有沒有在這個數據結構中，只有當該URL不在這個已訪問URL集合中時才對其進行其他操作。否則，將該URL丟棄。這個數據結構需要具有以下兩個特點：

1）結構中存儲的URL不可以重復。

2）由于URL數量眾多，考慮到查找性能問題，需要該結構能夠快速地查找。

針對以上兩點，采用Java集合類HashSet來實現存儲已訪問URL的散列表集合類。

這個已訪問URL集合主要是記錄網絡蜘蛛已經訪問過的URL，在網絡蜘蛛訪問一個從未訪問URL隊中出隊的U RL時，首先判斷一下這個URL是否已經在已訪問URL集合中存在，不存在的時候再進行訪問，這樣可以避免對同一URL多次不必要的訪問。

（3）網絡蜘蛛抓取網頁

HTMLParser是用一個純java寫的html解析庫，它不依賴于其它的java庫文件，主要用于改造或提取html。它能超高速解析html，而且不會出錯。使用HTMLParser的HTML鏈接提取功能提取網頁中的鏈接的過程如下：

1）創建過濾器，過濾a標簽中的URL：NodeFilter filt er = new TagNameFilter("a");

2）創建解析器：Parser parser = new Parser();

3）使用 parser.setURL(url)和setEncoding()設置需要解析的URL和編碼方式；

4）獲取解析的結果：NodeList list = parser.extractAll NodesThatMatch(filter);

5）遍歷得到的解析結果；

6）在將解析到的URL存入未訪問URL隊列之前需要對其進行一些檢查，把一些錯誤的鏈接或者是無法訪問的鏈接過濾掉。

3 索引器的實現

使用Lucene創建索引，Lucene是一個開放源代碼的全文檢索引擎工具包[6-8]，即它不是一個完整的全文檢索引擎，而是一個全文檢索引擎的架構，提供了完整的查詢引擎和索引引擎。Lucene提供了五個基礎的類，對文檔進行索引，下面是使用Lucene為HtmlDoc實例創建索引的相關操作。

1）創建分詞器，這里使用的是Lucene默認的分詞器；

2）設置IndexWriter類的相關配置：

3）設置索引的保存路徑：

4）創建 Lucene索引器：IndexWriter writer = new IndexWriter(dir,iwc);

5）創建Document對象：Document doc = new Document();

6）為Document對象添加HTMLField域；

7）添加 Document至索引器中去：writer.addDocument(doc);

8）關閉索引器：writer.close();

4 檢索器的實現

4.1 使用Lucene執行檢索

1）創建IndexReader對象讀取索引器創建的索引；

2）創建分詞器Analyzer對用戶輸入的字符串進行分詞處理；

3）使用IndexReader對象創建檢索器IndexSearcher；

4）使用分詞器 Analyzer創建QueryParser對象，解析用戶輸入的檢索字符串；

5）取得解析檢索字符串返回的Query對象；

6）使用 Query對象執行檢索將默認排序結果放置到TopDocs結果集；

7）得到檢索結果總數量：hitsSize = results.totalHits;。

4.2 高亮顯示檢索結果

1）設置高亮顯示html標簽

2）創建高亮顯示對象：Highlighter highlighter = new Highlighter(formatter,scorer);

3）設置高亮顯示附近字符串大小：Fragmenter fragmenter = new SimpleFragmenter(200);

4）設置高亮：highlighter.setTextFragmenter(fragmenter);

5 檢索測試

用戶可以在檢索器的文本框內輸入需要檢索的關鍵詞，點擊搜索按鈕，檢索器將自動顯示與關鍵詞相關的檢索結果，搜索“上海車展”檢索器返回檢索結果效果。如圖5所示：

圖5 檢索結果示意圖

6 總結

搜索引擎是一種信息檢索服務系統，它可以幫助用戶在互聯網上快速地查找對自己有用的信息。通過網絡爬蟲抓取信息，然后在通過一定的技術對網頁信息進行提取、處理，將抓取到的信息存放在索引數據庫中，通過一些查詢接口實現信息檢索。本搜素引擎的設計與實現是基于全文搜索進行的，設計了網絡蜘蛛、索引器和檢索器的結構，并利用Jav a語言進行了搜素引擎的實現，通過檢索實驗，檢索速度<=200ms，該搜索引擎是一個比較高效的檢索工具，但是系統實現的網絡蜘蛛并非真正意義上的全自動，而是必須給定網頁入口并告訴網絡蜘蛛要抓多少張網頁，它才能正常抓取網頁，同時檢索策略有待進一步改進，以便進一步提升檢索速度。

[1]孫宏.搜索引擎技術與發展綜述[J].計算機光盤軟件與應用，2012（14）：10-15.

[2]李國芳.全文搜索引擎快速搭建的設計與實現[J].計算機與現代化,2012（11）：18-21.

[3]克羅夫特(美).搜索引擎:信息檢索實踐[M].北京：機械工業出版社,2010：69-83.

[4]李浩.網絡蜘蛛的研究與實現[J].科技信息，2012（26）：18-23.

[5]陳建峽.基于PageRank的Lucene排序算法優化與實現[J].計算機工程與科學，2012（10）：19-23.

[6]劉敏娜.基于 Lucene的中文分詞技術改進[J].咸陽師范學院學報，2012（02）：25-28.

[7]麥肯德利斯等(美).Lucene實戰[M].北京：人民郵電出版社，2011：53-92.

[8]于天恩.Lucene搜索引擎開發權威經典[M].北京：中國鐵道出版社，2008：134-182.