摘要
網(wǎng)絡(luò )中的資源非常豐富，但是如何有效的搜索信息卻是一件困難的事情。建立搜索引擎就是解決這個(gè)問(wèn)題的最好方法。本文首先詳細介紹了基于英特網(wǎng)的搜索引擎的系統結構，然后從網(wǎng)絡(luò )機器人、索引引擎、Web服務(wù)器三個(gè)方面進(jìn)行詳細的說(shuō)明。為了更加深刻的理解這種技術(shù)，本人還親自實(shí)現了一個(gè)自己的搜索引擎——新聞搜索引擎。
新聞搜索引擎是從指定的Web頁(yè)面中按照超連接進(jìn)行解析、搜索，并把搜索到的每條新聞進(jìn)行索引后加入數據庫。然后通過(guò)Web服務(wù)器接受客戶(hù)端請求后從索引數據庫中搜索出所匹配的新聞。
本人在介紹搜索引擎的章節中除了詳細的闡述技術(shù)核心外還結合了新聞搜索引擎的實(shí)現代碼來(lái)說(shuō)明，圖文并茂、易于理解。
Abstract
The resources in the internet are abundant, but it is a difficult job to search some useful information. So a search engine is the best method to solve this problem. This article fist introduces the system structure of search engine based on the internet in detail, then gives a minute explanation form Spider search, engine and web server. In order to understand the technology more deeply, I have programmed a news search engine by myself.
The news search engine is explained and searched according to hyperlink from a appointed web page, then indexs every searched information and adds it to the index database. Then after receiving the customers‘ requests from the web server, it soon searchs the right news form the index engine,
In the chapter of introducing search engine, it is not only elaborate the core technology, but also combine with the modern code,pictures included, easy to understand.
第一章 引言
面對浩瀚的網(wǎng)絡(luò )資源，搜索引擎為所有網(wǎng)上沖浪的用戶(hù)提供了一個(gè)入口，毫不夸張的說(shuō)，所有的用戶(hù)都可以從搜索出發(fā)到達自己想去的網(wǎng)上任何一個(gè)地方。因此它也成為除了電子郵件以外最多人使用的網(wǎng)上服務(wù)。
搜索引擎技術(shù)伴隨著(zhù)WWW的發(fā)展是引人注目的。搜索引擎大約經(jīng)歷了三代的更新發(fā)展：
第一代搜索引擎出現于1994年。這類(lèi)搜索引擎一般都索引少于1，000，000個(gè)網(wǎng)頁(yè)，極少重新搜集網(wǎng)頁(yè)并去刷新索引。而且其檢索速度非常慢，一般都要等待10秒甚至更長(cháng)的時(shí)間。在實(shí)現技術(shù)上也基本沿用較為成熟的IR（Information Retrieval）、網(wǎng)絡(luò )、數據庫等技術(shù)，相當于利用一些已有技術(shù)實(shí)現的一個(gè)WWW上的應用。在1994年3月到4月，網(wǎng)絡(luò )爬蟲(chóng)World Web Worm (WWWW)平均每天承受大約1500次查詢(xún)。
大約在1996年出現的第二代搜索引擎系統大多采用分布式方案（多個(gè)微型計算機協(xié)同工作）來(lái)提高數據規模、響應速度和用戶(hù)數量，它們一般都保持一個(gè)大約50，000，000網(wǎng)頁(yè)的索引數據庫，每天能夠響應10，000，000次用戶(hù)檢索請求。1997年11月，當時(shí)最先進(jìn)的幾個(gè)搜索引擎號稱(chēng)能建立從2，000，000到100，000，000的網(wǎng)頁(yè)索引。Altavista搜索引擎聲稱(chēng)他們每天大概要承受20，000，000次查詢(xún)。
2000年搜索引擎2000年大會(huì )上，按照Google公司總裁Larry Page的演講，Google正在用3,000臺運行Linux系統的個(gè)人電腦在搜集Web上的網(wǎng)頁(yè)，而且以每天30臺的速度向這個(gè)微機集群里添加電腦，以保持與網(wǎng)絡(luò )的發(fā)展相同步。每臺微機運行多個(gè)爬蟲(chóng)程序搜集網(wǎng)頁(yè)的峰值速度是每秒100個(gè)網(wǎng)頁(yè)，平均速度是每秒48.5個(gè)網(wǎng)頁(yè)，一天可以搜集超過(guò)4，000，000網(wǎng)頁(yè)
搜索引擎一詞在國內外因特網(wǎng)領(lǐng)域被廣泛使用，然而他的含義卻不盡相同。在美國搜索引擎通常指的是基于因特網(wǎng)的搜索引擎，他們通過(guò)網(wǎng)絡(luò )機器人程序收集上千萬(wàn)到幾億個(gè)網(wǎng)頁(yè)，并且每一個(gè)詞都被搜索引擎索引，也就是我們說(shuō)的全文檢索。著(zhù)名的因特網(wǎng)搜索引擎包括First Search、Google、HotBot等。在中國，搜索引擎通常指基于網(wǎng)站目錄的搜索服務(wù)或是特定網(wǎng)站的搜索服務(wù)，本人這里研究的是基于因特網(wǎng)的搜索技術(shù)。
第二章 搜索引擎的結構
2.1系統概述
搜索引擎是根據用戶(hù)的查詢(xún)請求，按照一定算法從索引數據中查找信息返回給用戶(hù)。為了保證用戶(hù)查找信息的精度和新鮮度，搜索引擎需要建立并維護一個(gè)龐大的索引數據庫。一般的搜索引擎由網(wǎng)絡(luò )機器人程序、索引與搜索程序、索引數據庫等部分組成。
系統結構圖
2.2搜索引擎的構成
2.2.1網(wǎng)絡(luò )機器人
網(wǎng)絡(luò )機器人也稱(chēng)為“網(wǎng)絡(luò )蜘蛛”(Spider)，是一個(gè)功能很強的WEB掃描程序。它可以在掃描WEB頁(yè)面的同時(shí)檢索其內的超鏈接并加入掃描隊列等待以后掃描。因為WEB中廣泛使用超鏈接，所以一個(gè)Spider程序理論上可以訪(fǎng)問(wèn)整個(gè)WEB頁(yè)面。
為了保證網(wǎng)絡(luò )機器人遍歷信息的廣度和深度需要設定一些重要的鏈接并制定相關(guān)的掃描策略。
2.2.2索引與搜索
網(wǎng)絡(luò )機器人將遍歷得到的頁(yè)面存放在臨時(shí)數據庫中，如果通過(guò)SQL直接查詢(xún)信息速度將會(huì )難以忍受。為了提高檢索效率，需要建立索引，按照倒排文件的格式存放。如果索引不及時(shí)跟新的話(huà)，用戶(hù)用搜索引擎也不能檢索到。
用戶(hù)輸入搜索條件后搜索程序將通過(guò)索引數據庫進(jìn)行檢索然后把符合查詢(xún)要求的數據庫按照一定的策略進(jìn)行分級排列并且返回給用戶(hù)。
2.2.3 Web服務(wù)器
客戶(hù)一般通過(guò)瀏覽器進(jìn)行查詢(xún)，這就需要系統提供Web服務(wù)器并且與索引數據庫進(jìn)行連接?？蛻?hù)在瀏覽器中輸入查詢(xún)條件，Web服務(wù)器接收到客戶(hù)的查詢(xún)條件后在索引數據庫中進(jìn)行查詢(xún)、排列然后返回給客戶(hù)端。
2.3搜索引擎的主要指標及分析
搜索引擎的主要指標有響應時(shí)間、召回率、準確率、相關(guān)度等。這些指標決定了搜索引擎的技術(shù)指標。搜索引擎的技術(shù)指標決定了搜索引擎的評價(jià)指標。好的搜索引擎應該是具有較快的反應速度和高召回率、準確率的，當然這些都需要搜索引擎技術(shù)指標來(lái)保障。
召回率：一次搜索結果中符合用戶(hù)要求的數目與用戶(hù)查詢(xún)相關(guān)信息的總數之比
準確率：一次搜索結果中符合用戶(hù)要求的數目與該次搜索結果總數之比
相關(guān)度：用戶(hù)查詢(xún)與搜索結果之間相似度的一種度量
精確度：對搜索結果的排序分級能力和對垃圾網(wǎng)頁(yè)的抗干擾能力
2.4小節
以上對基于因特網(wǎng)的搜索引擎結構和性能指標進(jìn)行了分析，本人在這些研究的基礎上利用JavaTM技術(shù)和一些Open Source工具實(shí)現了一個(gè)簡(jiǎn)單的搜索引擎——新聞搜索引擎。在接下來(lái)的幾章里將會(huì )就本人的設計進(jìn)行詳細的分析。
第三章 網(wǎng)絡(luò )機器人
3.1什么是網(wǎng)絡(luò )機器人
網(wǎng)絡(luò )機器人又稱(chēng)為Spider程序，是一種專(zhuān)業(yè)的Bot程序。用于查找大量的Web頁(yè)面。它從一個(gè)簡(jiǎn)單的Web頁(yè)面上開(kāi)始執行，然后通過(guò)其超鏈接在訪(fǎng)問(wèn)其他頁(yè)面，如此反復理論上可以?huà)呙杌ヂ?lián)網(wǎng)上的所有頁(yè)面。
基于因特網(wǎng)的搜索引擎是Spider的最早應用。例如搜索巨頭Google公司，就利用網(wǎng)絡(luò )機器人程序來(lái)遍歷Web站點(diǎn)，以創(chuàng )建并維護這些大型數據庫。
網(wǎng)絡(luò )機器人還可以通過(guò)掃描Web站點(diǎn)的主頁(yè)來(lái)得到這個(gè)站點(diǎn)的文件清單和層次機構。還可以?huà)呙璩鲋袛嗟某溄雍推磳?xiě)錯誤等。
3.2網(wǎng)絡(luò )機器人的結構分析
Internet是建立在很多相關(guān)協(xié)議基礎上的，而更復雜的協(xié)議又建立在系統層協(xié)議之上。Web就是建立在HTTP ( Hypertext Transfer Protocol ) 協(xié)議基礎上，而HTTP又是建立在TCP/IP ( Transmission Control Protocol / Internet Protocol ) 協(xié)議之上，它同時(shí)也是一種Socket協(xié)議。所以網(wǎng)絡(luò )機器人本質(zhì)上是一種基于Socket的網(wǎng)絡(luò )程序。
3.2.1如何解析HTML
因為Web中的信息都是建立在HTML協(xié)議之上的，所以網(wǎng)絡(luò )機器人在檢索網(wǎng)頁(yè)時(shí)的第一個(gè)問(wèn)題就是如何解析HTML。在解決如何解析之前，先來(lái)介紹下HTML中的幾種數據。
文本：除了腳本和標簽之外的所有數據 注釋?zhuān)撼绦騿T留下的說(shuō)明文字，對用戶(hù)是不可見(jiàn)的 簡(jiǎn)單標簽：由單個(gè)表示的HTML標簽 開(kāi)始標簽和結束標簽：用來(lái)控制所包含的HTML代碼
我們在進(jìn)行解析的時(shí)候不用關(guān)心所有的標簽，只需要對其中幾種重要的進(jìn)行解析即可。
超連接標簽
超連接定義了WWW通過(guò)Internet鏈接文檔的功能。他們的主要目的是使用戶(hù)能夠任意遷移到新的頁(yè)面，這正是網(wǎng)絡(luò )機器人最關(guān)心的標簽。
圖像映射標簽
圖像映射是另一種非常重要的標簽。它可以讓用戶(hù)通過(guò)點(diǎn)擊圖片來(lái)遷移到新的頁(yè)面中。
表單標簽
表單是Web頁(yè)面中可以輸入數據的單元。許多站點(diǎn)讓用戶(hù)填寫(xiě)數據然后通過(guò)點(diǎn)擊按鈕來(lái)提交內容，這就是表單的典型應用。
表格標簽
表格是HTML的構成部分，通常用來(lái)格式化存放、顯示數據。
我們在具體解析這些HTMl標簽有兩種方法：通過(guò)JavaTM中的Swing類(lèi)來(lái)解析或者通過(guò)Bot包中的HTMLPage類(lèi)來(lái)解析，本人在實(shí)際編程中采用后者。
Bot包中的HTMLPage類(lèi)用來(lái)從指定URL中讀取數據并檢索出有用的信息。下面給出該類(lèi)幾種重要的方法。
HTMLPage構造函數 構造對象并指定用于通訊的HTTP對象
Public HTMLPage(HTTP http) GetForms方法 獲取最后一次調用Open方法檢索到的表單清單
Public Vector getForms() GetHTTP方法 獲取發(fā)送給構造函數的HTTP對象
Public HTTP getHTTP() GetImage方法 獲取指定頁(yè)面的圖片清單
Public Vector getImage() GetLinks方法 獲取指定頁(yè)面的連接清單
Public Vector getLinks() Open方法 打開(kāi)一個(gè)頁(yè)面并讀入該頁(yè)面，若指定了回調對象則給出所有該對象數據
Public void open(String url,HTMLEditorKit.ParserCallback a)
3.2.2 Spider程序結構
網(wǎng)絡(luò )機器人必須從一個(gè)網(wǎng)頁(yè)遷移到另一個(gè)網(wǎng)頁(yè)，所以必須找到該頁(yè)面上的超連接。程序首先解析網(wǎng)頁(yè)的HTML代碼，查找該頁(yè)面內的超連接然后通過(guò)遞歸和非遞歸兩種結構來(lái)實(shí)現Spider程序。
遞歸結構
遞歸是在一個(gè)方法中調用自己本身的程序設計技術(shù)。雖然比較容易實(shí)現但耗費內存且不能使用多線(xiàn)程技術(shù)，故不適合大型項目。
非遞歸結構
這種方法使用隊列的數據結構，當Spider程序發(fā)現超連接后并不調用自己本身而是把超連接加入到等待隊列中。當Spider程序掃描完當前頁(yè)面后會(huì )根據制定的策略訪(fǎng)問(wèn)隊列中的下一個(gè)超連接地址。
雖然這里只描述了一個(gè)隊列，但在實(shí)際編程中用到了四個(gè)隊列，他們每個(gè)隊列都保存著(zhù)同一處理狀態(tài)的URL。
等待隊列 在這個(gè)隊列中，URL等待被Spider程序處理。新發(fā)現的URL也被加入到這個(gè)隊列中
處理隊列 當Spider程序開(kāi)始處理時(shí)，他們被送到這個(gè)隊列中
錯誤隊列 如果在解析網(wǎng)頁(yè)時(shí)出錯，URL將被送到這里。該隊列中的URL不能被移入其他隊列中
完成隊列 如果解析網(wǎng)頁(yè)沒(méi)有出錯，URL將被送到這里。該隊列中的URL不能被移入其它隊列中
同一時(shí)間URL只能在一個(gè)隊列中，我們把它稱(chēng)為URL的狀態(tài)。
以上的圖表示了隊列的變化過(guò)程，在這個(gè)過(guò)程中，當一個(gè)URL被加入到等待隊列中時(shí)Spider程序就會(huì )開(kāi)始運行。只要等待隊列中有一個(gè)網(wǎng)頁(yè)或Spider程序正在處理一個(gè)網(wǎng)頁(yè)，程序就會(huì )繼續他的工作。當等待隊列為空并且當前沒(méi)有任何網(wǎng)頁(yè)時(shí)，Spider程序就會(huì )停止它的工作。
3.2.3如何構造Spider程序
在構造Spider程序之前我們先了解下程序的各個(gè)部分是如何共同工作的。以及如何對這個(gè)程序進(jìn)行擴展。
流程圖如下所示：
IspiderReportable接口
這是一個(gè)必須實(shí)現的接口，可以通過(guò)回調函數接受Spider所遇到的頁(yè)面。接口定義了Spider向他的控制者發(fā)送的幾個(gè)事件。通過(guò)提供對每個(gè)事件的處理程序，可以創(chuàng )建各種Spider程序。下面是他的接口聲明：
public interface IspiderReportable{
public boolean foundInternalLink(String url);
public boolean foundExternalLink(String url);
public boolean foundOtherLink(String url);
public void processPage(HTTP page);
public void completePage(HTTP page,boolean error);
public boolean getRemoveQuery();
public void SpiderComplete(); }
3.2.4如何提高程序性能
Internet中擁有海量的Web頁(yè)面，如果開(kāi)發(fā)出高效的Spider程序是非常重要的。下面就來(lái)介紹下幾種提高性能的技術(shù)：
Java的多線(xiàn)程技術(shù)
線(xiàn)程是通過(guò)程序的一條執行路線(xiàn)。多線(xiàn)程是一個(gè)程序同時(shí)運行多個(gè)任務(wù)的能力。它是在一個(gè)程序的內部進(jìn)行分工合作。
優(yōu)化程序的通常方法是確定瓶頸并改進(jìn)他。瓶頸是一個(gè)程序中最慢的部分，他限制了其他任務(wù)的運行。據個(gè)例子說(shuō)明：一個(gè)Spider程序需要下載十個(gè)頁(yè)面，要完成這一任務(wù)，程序必須向服務(wù)器發(fā)出請求然后接受這些網(wǎng)頁(yè)。當程序等待響應的時(shí)候其他任務(wù)不能執行，這就影響了程序的效率。如果用多線(xiàn)程技術(shù)可以讓這些網(wǎng)頁(yè)的等待時(shí)間合在一起，不用互相影響，這就可以極大的改進(jìn)程序性能。
數據庫技術(shù)
當Spider程序訪(fǎng)問(wèn)一個(gè)大型Web站點(diǎn)時(shí)，必須使用一種有效的方法來(lái)存儲站點(diǎn)隊列。這些隊列管理Spider程序必須維護大型網(wǎng)頁(yè)的列表。如果把他們放在內存中將會(huì )是性能下降，所以我們可以把他們放在數據庫中減少系統資源的消耗。
3.2.5網(wǎng)絡(luò )機器人的代碼分析
程序結構圖如下：
CMSware::cms_if gte vml 1]><[endif?>
程序代碼實(shí)現如下：
package news; /** * 新聞搜索引擎 * 版本 1.0 */
import com.heaton.bot.HTTP;
import com.heaton.bot.HTTPSocket;
import com.heaton.bot.ISpiderReportable;
import com.heaton.bot.IWorkloadStorable;
import com.heaton.bot.Spider;
import com.heaton.bot.SpiderInternalWorkload; /** * 構造一個(gè)Bot程序 */
public class Searcher implements ISpiderReportable {
public static void main(String[] args)
throws Exception { IWorkloadStorable wl = new SpiderInternalWorkload();
Searcher _searcher = new Searcher();
Spider _spider = new Spider(_searcher, "http://127.0.0.1/news.htm", new HTTPSocket(), 100, wl); _spider.setMaxBody(100);
_spider.start(); } // 發(fā)現內部連接時(shí)調用，url表示程序發(fā)現的URL，若返回true則加入作業(yè)中，否則不加入。
public boolean foundInternalLink(String url) {
return false; } // 發(fā)現外部連接時(shí)調用，url表示程序所發(fā)現的URL，若返回true則把加入作業(yè)中，否則不加入。
public boolean foundExternalLink(String url) {
return false; } // 當發(fā)現其他連接時(shí)調用這個(gè)方法。其他連接指的是非HTML網(wǎng)頁(yè)，可能是E-mail或者FTP
public boolean foundOtherLink(String url) {
return false; } // 用于處理網(wǎng)頁(yè)，這是Spider程序要完成的實(shí)際工作。
public void processPage(HTTP http) {
System.out.println("掃描網(wǎng)頁(yè)：" + http.getURL());
new HTMLParse(http).start(); } // 用來(lái)請求一個(gè)被處理的網(wǎng)頁(yè)。
public void completePage(HTTP http, boolean error) { } // 由Spider程序調用以確定查詢(xún)字符串是否應刪除。如果隊列中的字符串應當刪除，方法返回真。
public boolean getRemoveQuery() {
return true; } // 當Spider程序沒(méi)有剩余的工作時(shí)調用這個(gè)方法。
public void spiderComplete() { }
}
3.3小節
在本章中，首先介紹了網(wǎng)絡(luò )機器人的基本概念，然后具體分析了Spider程序的結構和功能。在最后還結合具體代碼進(jìn)行了詳細說(shuō)明。
本人在編程中運用了JavaTM技術(shù)，主要涉及到了net和io兩個(gè)包。此外還用了第三方開(kāi)發(fā)包Bot（由Jeff Heaton提供的開(kāi)發(fā)包）。
第四章 基于lucene的索引與搜索
4.1什么是Lucene全文檢索
Lucene是Jakarta Apache的開(kāi)源項目。它是一個(gè)用Java寫(xiě)的全文索引引擎工具包，可以方便的嵌入到各種應用中實(shí)現針對應用的全文索引/檢索功能。
4.2 Lucene的原理分析
4.2.1全文檢索的實(shí)現機制
Lucene的API接口設計的比較通用，輸入輸出結構都很像數據庫的表==>記錄==>字段，所以很多傳統的應用的文件、數據庫等都可以比較方便的映射到Lucene的存儲結構和接口中。
總體上看：可以先把Lucene當成一個(gè)支持全文索引的數據庫系統。 索引數據源：doc(field1,field2...) doc(field1,field2...) \ indexer / _____________ | Lucene Index| -------------- searcher \
結果輸出：Hits(doc(field1,field2) doc(field1...))
Document：一個(gè)需要進(jìn)行索引的“單元”，一個(gè)Document由多個(gè)字段組成
Field：字段
Hits：查詢(xún)結果集，由匹配的Document組成
4.2.2 Lucene的索引效率
通常書(shū)籍后面常常附關(guān)鍵詞索引表（比如：北京：12, 34頁(yè)，上海：3,77頁(yè)……），它能夠幫助讀者比較快地找到相關(guān)內容的頁(yè)碼。而數據庫索引能夠大大提高查詢(xún)的速度原理也是一樣，想像一下通過(guò)書(shū)后面的索引查找的速度要比一頁(yè)一頁(yè)地翻內容高多少倍……而索引之所以效率高，另外一個(gè)原因是它是排好序的。對于檢索系統來(lái)說(shuō)核心是一個(gè)排序問(wèn)題。
由于數據庫索引不是為全文索引設計的，因此，使用like "%keyword%"時(shí)，數據庫索引是不起作用的，在使用like查詢(xún)時(shí)，搜索過(guò)程又變成類(lèi)似于一頁(yè)頁(yè)翻書(shū)的遍歷過(guò)程了，所以對于含有模糊查詢(xún)的數據庫服務(wù)來(lái)說(shuō)，LIKE對性能的危害是極大的。如果是需要對多個(gè)關(guān)鍵詞進(jìn)行模糊匹配：like"%keyword1%" and like "%keyword2%" ...其效率也就可想而知了。所以建立一個(gè)高效檢索系統的關(guān)鍵是建立一個(gè)類(lèi)似于科技索引一樣的反向索引機制，將數據源（比如多篇文章）排序順序存儲的同時(shí)，有另外一個(gè)排好序的關(guān)鍵詞列表，用于存儲關(guān)鍵詞==>文章映射關(guān)系，利用這樣的映射關(guān)系索引：[關(guān)鍵詞==>出現關(guān)鍵詞的文章編號，出現次數（甚至包括位置：起始偏移量，結束偏移量），出現頻率]，檢索過(guò)程就是把模糊查詢(xún)變成多個(gè)可以利用索引的精確查詢(xún)的邏輯組合的過(guò)程。從而大大提高了多關(guān)鍵詞查詢(xún)的效率，所以，全文檢索問(wèn)題歸結到最后是一個(gè)排序問(wèn)題。
由此可以看出模糊查詢(xún)相對數據庫的精確查詢(xún)是一個(gè)非常不確定的問(wèn)題，這也是大部分數據庫對全文檢索支持有限的原因。Lucene最核心的特征是通過(guò)特殊的索引結構實(shí)現了傳統數據庫不擅長(cháng)的全文索引機制，并提供了擴展接口，以方便針對不同應用的定制?？梢酝ㄟ^(guò)一下表格對比一下數據庫的模糊查詢(xún)：
Lucene全文索引引擎
數據庫
索引
將數據源中的數據都通過(guò)全文索引一一建立反向索引
對于LIKE查詢(xún)來(lái)說(shuō)，數據傳統的索引是根本用不上的。數據需要逐個(gè)便利記錄進(jìn)行GREP式的模糊匹配，比有索引的搜索速度要有多個(gè)數量級的下降。
匹配效果
通過(guò)詞元(term)進(jìn)行匹配，通過(guò)語(yǔ)言分析接口的實(shí)現，可以實(shí)現對中文等非英語(yǔ)的支持。
使用：like "%net%" 會(huì )把netherlands也匹配出來(lái)， 多個(gè)關(guān)鍵詞的模糊匹配：使用like "%com%net%"：就不能匹配詞序顛倒的xxx.net..xxx.com
匹配度
有匹配度算法，將匹配程度（相似度）比較高的結果排在前面。
沒(méi)有匹配程度的控制：比如有記錄中net出現5詞和出現1次的，結果是一樣的。
結果輸出
通過(guò)特別的算法，將最匹配度最高的頭100條結果輸出，結果集是緩沖式的小批量讀取的。
返回所有的結果集，在匹配條目非常多的時(shí)候（比如上萬(wàn)條）需要大量的內存存放這些臨時(shí)結果集。
可定制性
通過(guò)不同的語(yǔ)言分析接口實(shí)現，可以方便的定制出符合應用需要的索引規則（包括對中文的支持）
沒(méi)有接口或接口復雜，無(wú)法定制
結論
高負載的模糊查詢(xún)應用，需要負責的模糊查詢(xún)的規則，索引的資料量比較大
使用率低，模糊匹配規則簡(jiǎn)單或者需要模糊查詢(xún)的資料量少
4.2.3 中文切分詞機制
對于中文來(lái)說(shuō)，全文索引首先還要解決一個(gè)語(yǔ)言分析的問(wèn)題，對于英文來(lái)說(shuō)，語(yǔ)句中單詞之間是天然通過(guò)空格分開(kāi)的，但亞洲語(yǔ)言的中日韓文語(yǔ)句中的字是一個(gè)字挨一個(gè)，所有，首先要把語(yǔ)句中按“詞”進(jìn)行索引的話(huà)，這個(gè)詞如何切分出來(lái)就是一個(gè)很大的問(wèn)題。
首先，肯定不能用單個(gè)字符作(si-gram)為索引單元，否則查“上?！睍r(shí)，不能讓含有“海上”也匹配。但一句話(huà)：“北京天安門(mén)”，計算機如何按照中文的語(yǔ)言習慣進(jìn)行切分呢？“北京 天安門(mén)” 還是“北 京 天安門(mén)”？讓計算機能夠按照語(yǔ)言習慣進(jìn)行切分，往往需要機器有一個(gè)比較豐富的詞庫才能夠比較準確的識別出語(yǔ)句中的單詞。另外一個(gè)解決的辦法是采用自動(dòng)切分算法：將單詞按照2元語(yǔ)法(bigram)方式切分出來(lái)，比如："北京天安門(mén)" ==> "北京 京天 天安 安門(mén)"。這樣，在查詢(xún)的時(shí)候，無(wú)論是查詢(xún)"北京" 還是查詢(xún)"天安門(mén)"，將查詢(xún)詞組按同樣的規則進(jìn)行切分："北京"，"天安安門(mén)"，多個(gè)關(guān)鍵詞之間按與"and"的關(guān)系組合，同樣能夠正確地映射到相應的索引中。這種方式對于其他亞洲語(yǔ)言：韓文，日文都是通用的。
基于自動(dòng)切分的最大優(yōu)點(diǎn)是沒(méi)有詞表維護成本，實(shí)現簡(jiǎn)單，缺點(diǎn)是索引效率低，但對于中小型應用來(lái)說(shuō)，基于2元語(yǔ)法的切分還是夠用的?；?元切分后的索引一般大小和源文件差不多，而對于英文，索引文件一般只有原文件的30%-40%不同，
自動(dòng)切分
詞表切分
實(shí)現
實(shí)現非常簡(jiǎn)單
實(shí)現復雜
查詢(xún)
增加了查詢(xún)分析的復雜程度，
適于實(shí)現比較復雜的查詢(xún)語(yǔ)法規則
存儲效率
索引冗余大，索引幾乎和原文一樣大
索引效率高，為原文大小的30％左右
維護成本
無(wú)詞表維護成本
詞表維護成本非常高：中日韓等語(yǔ)言需要分別維護。 還需要包括詞頻統計等內容
適用領(lǐng)域
嵌入式系統：運行環(huán)境資源有限 分布式系統：無(wú)詞表同步問(wèn)題 多語(yǔ)言環(huán)境：無(wú)詞表維護成本
對查詢(xún)和存儲效率要求高的專(zhuān)業(yè)搜索引擎
4.3 Lucene與Spider的結合
首先構造一個(gè)Index類(lèi)用來(lái)實(shí)現對內容進(jìn)行索引。
<[endif?> 代碼分析如下： package news; /** * 新聞搜索引擎 * * 版本1.0
*/ import java.io.IOException;
import org.apache.lucene.analysis.cn.ChineseAnalyzer;
import org.apache.lucene.document.Document;
import org.apache.lucene.document.Field;
import org.apache.lucene.index.IndexWriter;
public class Index {
IndexWriter _writer = null;
Index() throws Exception {
_writer = new IndexWriter("c:\\News\\index",new ChineseAnalyzer(), true);
} /** * 把每條新聞加入索引中 * @param url 新聞的url * @param title 新聞的標題 * @throws java.lang.Exception */
void AddNews(String url, String title) throws Exception {
Document _doc = new Document();
_doc.add(Field.Text("title", title));
_doc.add(Field.UnIndexed("url", url));
_writer.addDocument(_doc); } /**優(yōu)化并且清理資源 @throws java.lang.Exception */ void close() throws Exception {
_writer.optimize();
_writer.close(); }
}
然后構造一個(gè)HTML解析類(lèi)，把通過(guò)bot程序收集的新聞內容進(jìn)行索引。
<[endif?>
代碼分析如下： package news; /** * 新聞搜索引擎 * 版本1.0 */
import java.util.Iterator;
import java.util.Vector;
import com.heaton.bot.HTMLPage;
import com.heaton.bot.HTTP;
import com.heaton.bot.Link;
public class HTMLParse {
HTTP _http = null;
public HTMLParse(HTTP http) { _http = http; } /**對Web頁(yè)面進(jìn)行解析后建立索引*/ public void start() {
try { HTMLPage _page = new HTMLPage(_http);
_page.open(_http.getURL(), null);
Vector _links = _page.getLinks();
Index _index = new Index();
Iterator _it = _links.iterator();
int n = 0;
while (_it.hasNext()) {
Link _link = (Link) _it.next();
String _herf = input(_link.getHREF().trim());
String _title = input(_link.getPrompt().trim());
_index.AddNews(_herf, _title);
n++;
}
System.out.println("共掃描到" + n + "條新聞");
_index.close();
}
catch (Exception ex) {
System.out.println(ex); }
} /** * 解決java中的中文問(wèn)題 * @param str 輸入的中文 * @return 經(jīng)過(guò)解碼的中文 */ public static String input(String str) {
String temp = null;
if (str != null) {
try {
temp = new String(str.getBytes("ISO8859_1"));
}
catch (Exception e) { }
}
return temp;
}
}
4.4小節
在進(jìn)行海量數據搜索時(shí)，如果使用單純的數據庫技術(shù)，那將是非常痛苦的。速度將是極大的瓶頸。所以本章提出了使用全文搜索引擎Lucene進(jìn)行索引、搜索。
最后，還結合了具體代碼說(shuō)明了如何把Lucene全文搜索引擎和Spider程序互相集合來(lái)實(shí)現新聞搜索的功能。
第五章 基于Tomcat的Web服務(wù)器
5.1什么是基于Tomcat的Web服務(wù)器
Web服務(wù)器是在網(wǎng)絡(luò )中為實(shí)現信息發(fā)布、資料查詢(xún)、數據處理等諸多應用搭建基本平臺的服務(wù)器。Web服務(wù)器如何工作：在Web頁(yè)面處理中大致可分為三個(gè)步驟，第一步，Web瀏覽器向一個(gè)特定的服務(wù)器發(fā)出Web頁(yè)面請求；第二步，Web服務(wù)器接收到Web頁(yè)面請求后，尋找所請求的Web頁(yè)面，并將所請求的Web頁(yè)面傳送給Web瀏覽器；第三步，Web服務(wù)器接收到所請求的Web頁(yè)面，并將它顯示出來(lái)。
Tomcat是一個(gè)開(kāi)放源代碼、運行servlet和JSP Web應用軟件的基于Java的Web應用軟件容器。Tomcat由Apache-Jakarta子項目支持并由來(lái)自開(kāi)放性源代碼Java社區的志愿者進(jìn)行維護。Tomcat Server是根據servlet和JSP規范進(jìn)行執行的，因此我們就可以說(shuō)Tomcat Server也實(shí)行了Apache-Jakarta規范且比絕大多數商業(yè)應用軟件服務(wù)器要好。
5.2用戶(hù)接口設計
5.3.1客戶(hù)端設計
一個(gè)良好的查詢(xún)界面非常重要，例如Googl就以她簡(jiǎn)潔的查詢(xún)界面而聞名。我在設計的時(shí)候也充分考慮了實(shí)用性和簡(jiǎn)潔性。
<[endif?>查詢(xún)界面截圖如下：
搜索結果截圖如下：
5.3.2服務(wù)端設計
主要利用JavaTM Servlet技術(shù)實(shí)現，用戶(hù)通過(guò)GET方法從客戶(hù)端向服務(wù)端提交查詢(xún)條件，服務(wù)端通過(guò)Tomcat的Servlet容器接受并分析提交參數，再調用lucene的開(kāi)發(fā)包進(jìn)行搜索操作。最后把搜索的結果以HTTP消息包的形式發(fā)送至客戶(hù)端，從而完成一次搜索操作。
服務(wù)端Servlet程序的結構如下：
<[endif?>
實(shí)現的關(guān)鍵代碼如下： public void Search(String qc, PrintWriter out) throws Exception { // 從索引目錄創(chuàng )建索引 IndexSearcher _searcher = new IndexSearcher("c:\ews\\index"); // 創(chuàng )建標準分析器
Analyzer analyzer = new ChineseAnalyzer(); // 查詢(xún)條件
String line = qc; // Query是一個(gè)抽象類(lèi)
Query query = QueryParser.parse(line, "title", analyzer);
out.println("<html>");
out.println("<head><title>搜索結果</title></head>");
out.println("<body bgcolor=#ffffff>");
out.println("<center>" + "<form action=‘/NewsServer/results‘ method=‘get‘>" + "<font face=‘華文中宋‘ color=‘#3399FF‘>新聞搜索引擎</font>:" + "<input type=‘text‘ name=‘QueryContent‘ size=‘20‘>" + "<input type=‘submit‘ name=‘submit‘ value=‘開(kāi)始搜索‘>" + "</form></center>" );
out.println("<p>搜索關(guān)鍵字：<font color=red>" + query.toString("title") + "</font></p>");
Hits hits = _searcher.search(query);
out.println(" 總共找到<font color=red>" + hits.length() + "</font>條新聞<br>");
final int HITS_PER_PAGE = 10;
for (int start = 0; start < hits.length(); start += HITS_PER_PAGE) {
int end = Math.min(hits.length(), start + HITS_PER_PAGE);
for (int i = start; i < end; i++) {
Document doc = hits.doc(i);
String url = doc.get("url");
if (url != null) {
out.println( (i + 1) + " <a href=‘" + url + "‘>" +replace(doc.get("title"), qc) +"</a><br>");} else {
System.out.println("沒(méi)有找到！");
}
}
}
out.println("</body></html>");
_searcher.close(); };
5.3在Tomcat上部署項目
Tomcat中的應用程序是一個(gè)WAR（Web Archive）文件。WAR是Sun提出的一種Web應用程序格式，與JAR類(lèi)似，也是許多文件的一個(gè)壓縮包。這個(gè)包中的文件按一定目錄結構來(lái)組織：通常其根目錄下包含有Html和Jsp文件或者包含這兩種文件的目錄，另外還會(huì )有一個(gè)WEB-INF目錄，這個(gè)目錄很重要。通常在WEB-INF目錄下有一個(gè)web.xml文件和一個(gè)classes目錄，web.xml是這個(gè)應用的配置文件，而classes目錄下則包含編譯好的Servlet類(lèi)和Jsp或Servlet所依賴(lài)的其它類(lèi)（如JavaBean）。通常這些所依賴(lài)的類(lèi)也可以打包成JAR放到WEB-INF下的lib目錄下，當然也可以放到系統的CLASSPATH中。
在Tomcat中，應用程序的部署很簡(jiǎn)單，你只需將你的WAR放到Tomcat的webapp目錄下，Tomcat會(huì )自動(dòng)檢測到這個(gè)文件，并將其解壓。你在瀏覽器中訪(fǎng)問(wèn)這個(gè)應用的Jsp時(shí)，通常第一次會(huì )很慢，因為T(mén)omcat要將Jsp轉化為Servlet文件，然后編譯。編譯以后，訪(fǎng)問(wèn)將會(huì )很快。
5.4小節
本章中詳細介紹了如何構架基于Tomcat的Web服務(wù)器，使得用戶(hù)通過(guò)瀏覽器進(jìn)行新聞的搜索，最后還對Tomcat如何部署進(jìn)行了說(shuō)明。
第六章 搜索引擎策略
6.1簡(jiǎn)介
隨著(zhù)信息多元化的增長(cháng)，千篇一律的給所有用戶(hù)同一個(gè)入口顯然已經(jīng)不能滿(mǎn)足特定用戶(hù)更深入的查詢(xún)需求。同時(shí)，這樣的通用搜索引擎在目前的硬件條件下，要及時(shí)更新以得到互聯(lián)網(wǎng)上較全面的信息是不太可能的。針對這種情況，我們需要一個(gè)分類(lèi)細致精確、數據全面深入、更新及時(shí)的面向主題的搜索引擎。
由于主題搜索運用了人工分類(lèi)以及特征提取等智能化策略，因此它比上面提到的前三代的搜索引擎將更加有效和準確，我們將這類(lèi)完善的主題搜索引擎稱(chēng)為第四代搜索引擎。
6.2面向主題的搜索策略
6.2.1導向詞
導向詞就是一組關(guān)鍵詞，它們會(huì )引導搜索器按照一定順序搜索整個(gè)網(wǎng)絡(luò )，使得搜索引擎可以在最短的時(shí)間里面得到最全面的跟某一個(gè)主題相關(guān)的信息。通過(guò)設置導向詞以及它們對應的不同權值，所有標題、作者、正文或超連接文本中含有某一導向詞的網(wǎng)頁(yè)都會(huì )被賦予較高的權值，在搜索的時(shí)候會(huì )優(yōu)先考慮。搜索器在向主控程序獲得URL的時(shí)候也是按照權值由高到低的順序。反之，搜索器在向主控程序提交新的URL和它的權值的時(shí)候，主控程序會(huì )按照權值預先排序，以便下一次有序的發(fā)給搜索器。
6.2.2網(wǎng)頁(yè)評級
在考慮一個(gè)網(wǎng)頁(yè)被另一個(gè)網(wǎng)頁(yè)的引用時(shí)候，不是單純的將被引用網(wǎng)頁(yè)的Hit Number加一，而是將引用網(wǎng)頁(yè)的連接數作為權，同時(shí)將該引用網(wǎng)頁(yè)的重要性也考慮進(jìn)來(lái)（看看上面提到的例子，Yahoo！引用的網(wǎng)頁(yè)顯然比個(gè)人網(wǎng)站引用的網(wǎng)頁(yè)重要，因為Yahoo！本身很重要），就可以得到擴展后的網(wǎng)頁(yè)評分。
最早提出網(wǎng)頁(yè)評分的計算方法是Google。它們提出了一個(gè)“隨機沖浪”模型來(lái)描述網(wǎng)絡(luò )用戶(hù)對網(wǎng)頁(yè)的訪(fǎng)問(wèn)行為。模型假設如下：
1) 用戶(hù)隨機的選擇一個(gè)網(wǎng)頁(yè)作為上網(wǎng)的起始網(wǎng)頁(yè)；
2) 看完這個(gè)網(wǎng)頁(yè)后，從該網(wǎng)頁(yè)內所含的超鏈內隨機的選擇一個(gè)頁(yè)面繼續進(jìn)行瀏覽；
3) 沿著(zhù)超鏈前進(jìn)了一定數目的網(wǎng)頁(yè)后，用戶(hù)對這個(gè)主題感到厭倦，重新隨機選擇一個(gè)網(wǎng)頁(yè)進(jìn)行瀏覽，并重復2和3。
按照以上的用戶(hù)行為模型，每個(gè)網(wǎng)頁(yè)可能被訪(fǎng)問(wèn)到的次數就是該網(wǎng)頁(yè)的鏈接權值。如何計算這個(gè)權值呢？PageRank采用以下公式進(jìn)行計算：
<[endif?> <[endif?>
其中Wj代表第j個(gè)網(wǎng)頁(yè)的權值；lij只取0、1值，代表從網(wǎng)頁(yè)i到網(wǎng)頁(yè)j是否存在鏈接；ni代表網(wǎng)頁(yè)i有多少個(gè)鏈向其它網(wǎng)頁(yè)的鏈接；d代表“隨機沖浪”中沿著(zhù)鏈接訪(fǎng)問(wèn)網(wǎng)頁(yè)的平均次數。選擇合適的數值，遞歸的使用以上公式，即可得到理想的網(wǎng)頁(yè)鏈接權值。該方法能夠大幅度的提高簡(jiǎn)單檢索返回結果的質(zhì)量，同時(shí)能夠有效的防止網(wǎng)頁(yè)編寫(xiě)者對搜索引擎的欺騙。因此可以將其廣泛的應用在檢索器提供給用戶(hù)的網(wǎng)頁(yè)排序上，對于網(wǎng)頁(yè)評分越高的網(wǎng)頁(yè)，就排的越前。
6.2.3權威網(wǎng)頁(yè)和中心網(wǎng)頁(yè)
權威網(wǎng)頁(yè)
顧名思義，是給定主題底下的一系列重要的權威的網(wǎng)頁(yè)。其重要性和權威性主要體現在以下兩點(diǎn)：
2) 從單個(gè)網(wǎng)頁(yè)來(lái)看，它的網(wǎng)頁(yè)內容本身對于這個(gè)給定主題來(lái)說(shuō)是重要的；
3) 從這個(gè)網(wǎng)頁(yè)在整個(gè)互聯(lián)網(wǎng)重的地位來(lái)看，這個(gè)網(wǎng)頁(yè)是被其他網(wǎng)頁(yè)承認為權威的，這主要體現在跟這個(gè)主題相關(guān)的很多網(wǎng)頁(yè)都有鏈接指向這個(gè)網(wǎng)頁(yè)。
由此可見(jiàn)，權威網(wǎng)頁(yè)對于主題搜索引擎的實(shí)現有很重大的意義。主題搜索引擎一個(gè)很關(guān)鍵的任務(wù)就是從互聯(lián)網(wǎng)上無(wú)數的網(wǎng)頁(yè)之中最快最準的找出這些可數的權威網(wǎng)頁(yè)，并為他們建立索引。這也是有效區別主題搜索引擎和前三代傳統通用搜索引擎的重要特征。
中心網(wǎng)頁(yè)
是包含很多指向權威網(wǎng)頁(yè)的超鏈接的網(wǎng)頁(yè)。最典型中心網(wǎng)頁(yè)的一個(gè)例子是Yahoo！，它的目錄結構指向了很多主題的權威網(wǎng)頁(yè)，使得它兼任了很多主題的中心網(wǎng)頁(yè)。由中心網(wǎng)頁(yè)出發(fā)，輕而易舉的就會(huì )到達大量的權威網(wǎng)頁(yè)。因此，它對于主題搜索引擎的實(shí)現也起了很大的意義。
權威網(wǎng)頁(yè)和中心網(wǎng)頁(yè)之間是一種互相促進(jìn)的關(guān)系：一個(gè)好的中心網(wǎng)頁(yè)必然要有超鏈接指向多個(gè)權威網(wǎng)頁(yè)；一個(gè)好的權威網(wǎng)頁(yè)反過(guò)來(lái)也必然被多個(gè)中心網(wǎng)頁(yè)所鏈接。
6.3小節
本章介紹了面向主題的搜索策略，并作了詳細闡述。雖然在新聞搜索中并沒(méi)有應用到搜索策略，但是對于WWW搜索引擎來(lái)說(shuō)，搜索策略是極其重要的。他直接關(guān)系到搜索的質(zhì)量以及匹配度等性能。
參考文獻
文獻資料
1 《Programming Spiders,Bots,and Aggregator in Java》[美]Jeff Heaton著(zhù)
2 《搜索引擎與信息獲取技術(shù)》徐寶文、張衛豐著(zhù)
3 《基于Java的全文搜索引擎Lucene》車(chē)東著(zhù)
4 《主題搜索引擎的設計與實(shí)現》羅旭著(zhù)
5 《Thinking in Java 》[美]Bruce Eckel著(zhù)
開(kāi)發(fā)工具、平臺及資源：
1 Borland Jbuilder 9
2 Sun JDK 1.4.1
3 Jakarta Tomcat 4.1
4 Jakarta Lucene
5 Package Bot
From:
http://www.kissjava.com/doc/j2se/hardin/2005-04-19/4986.html 2005-9
