網(wǎng)絡(luò)搜索引擎的分析

1、本 科 生 畢 業(yè) 論 文網(wǎng)絡(luò)搜索引擎的分析院 系： 信息科學(xué)與技術(shù) 專(zhuān) 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 學(xué)生姓名： 學(xué) 號(hào)： 指導(dǎo)教師： 摘要隨著互聯(lián)網(wǎng)的飛速發(fā)展，信息革命引發(fā)的一個(gè)特別的工具-搜索引擎，其作用是在幾十億之間現(xiàn)有的網(wǎng)站中找出具體的用戶(hù)想要查找的資料。大家都知道，網(wǎng)絡(luò)搜索引擎已成為最重要的網(wǎng)絡(luò)信息搜索工具，以獲取以無(wú)法估計(jì)的速度出現(xiàn)的網(wǎng)頁(yè)信息。到目前為止，很多以前流行的搜索引擎已經(jīng)漸漸消失，其他新的搜索引擎又開(kāi)始出現(xiàn)。但是在近幾年出現(xiàn)的基于各種不同搜索算法的搜索引擎中， google已經(jīng)成為最流行的和成功的搜索引擎之一，google為何能夠成功在很大程度上歸因于簡(jiǎn)單而優(yōu)雅的pagera

2、nk算法。該算法的實(shí)現(xiàn)原理很簡(jiǎn)單，當(dāng)用戶(hù)提交他或她的想要查詢(xún)信息時(shí)，搜索引擎分析其數(shù)據(jù)庫(kù)中已經(jīng)存放網(wǎng)站，然后返回用戶(hù)想要查詢(xún)的超鏈接列表。更重要的是，此列表按照與用戶(hù)查詢(xún)信息的相關(guān)度進(jìn)行排序，以方便用戶(hù)準(zhǔn)確有效地找到想要查詢(xún)的網(wǎng)頁(yè)。本論文首先討論搜索引擎的發(fā)展歷史、現(xiàn)實(shí)重要意義以及其發(fā)展趨勢(shì)。接著詳細(xì)介紹網(wǎng)頁(yè)排序算法的實(shí)現(xiàn)原理、該算法的優(yōu)缺點(diǎn)和如何改進(jìn)該算法、以及對(duì)網(wǎng)頁(yè)排序算法進(jìn)行實(shí)例分析，進(jìn)一步論述了google采用的網(wǎng)頁(yè)排序算法為何會(huì)取得如此大的成功。最后重點(diǎn)地介紹如何構(gòu)建簡(jiǎn)單有效的搜索引擎，這也是全文的難點(diǎn)，這里只是實(shí)現(xiàn)搜索引擎的核心功能，還有更多搜索的功能急需進(jìn)一步完善。關(guān)鍵詞： 搜索

3、引擎 網(wǎng)頁(yè)排序算法 構(gòu)建搜索引擎 超鏈接abstractwith the development of internet, the information revolution gives rise to the search engine, a special tool whose task is to identify specifically information among billions of existing websites those are relevant to the users query. as we all know, web search engines ha

4、ve become the most important tools to access information that appear at the speed unevaluated. by now, many of search engines have gone out of business while others have merged. however, among millions of them based on various algorithms that have emerged in recent years, google has become one of th

5、e most popular and successful one and this companys triumph largely attributes to the simple but elegant algorithm, pagerank algorithm. this principle of this algorithm implements as follows. when a user submits his or her query, the search engine analyzes its repository of stored web sites and retu

6、rns the list of hyperlinks to those that contain information requested by the query. most importantly, this list is ordered so that most relevant web sites come up first, which might be convenient for the users to find the targets wanted. in this paper it begins our topic with the search engines his

7、tory of development, its practical significance and the future trend developed. then we discuss the principle of pagerank algorithm in detail, the algorithms merit and shortage, also the modified methods about this algorithm and numerical tests on pagerank algorithm. and it indicates that why google

8、s core search algorithm have so much potential for development. the last but not least, how to build effective search engines will be introduced. and how to efficiently build a simple engine will be the focus of this paper. in addition, the search engine is constructed to only achieve the core funct

9、ion, and there are many urgent functions to be improved.keywords: search engine pagerank algorithm build the index hyperlink目 錄摘要iabstractii第一章 前言11.1搜索引擎的歷史11.2搜索引擎的分類(lèi)21.3搜索引擎的現(xiàn)實(shí)意義31.4搜索引擎的發(fā)展趨勢(shì)4第二章 搜索引擎原理52.1搜索引擎原理分析52.1.1收集信息62.1.2建立索引72.1.3查詢(xún)并返回結(jié)果72.1.4用戶(hù)接口72.2pagerank算法82.2.1算法原理82.2.2算法實(shí)例分析92.2

10、.2.1第一次計(jì)算第二次計(jì)算第n次計(jì)算142.2.3算法的不足偏重舊網(wǎng)頁(yè)主題飄移現(xiàn)象專(zhuān)業(yè)站點(diǎn)被忽視網(wǎng)頁(yè)中超鏈接對(duì)網(wǎng)站pr值的影響152.2.4算法的改進(jìn)具有時(shí)間反饋的改進(jìn)基于網(wǎng)頁(yè)鏈接和內(nèi)容分析的改進(jìn)17第三章 構(gòu)建搜索引擎193.1lucene入門(mén)193.1.1什么是lucene193.1.2lucene的特點(diǎn)193.1.3lucene構(gòu)建搜索引擎基本流程建立索引搜索流程213.2lucene檢索結(jié)果排序223.2.1

11、評(píng)分算法公式223.2.2評(píng)分算法的特點(diǎn)與不足223.2.3評(píng)分算法公式的改進(jìn)233.2.4另一種評(píng)分算法-向量空間算法243.3lucene構(gòu)建搜索引擎253.3.1構(gòu)建運(yùn)行環(huán)境253.3.2搜索引擎的代碼實(shí)現(xiàn)索引建立查詢(xún)2搜索結(jié)果28第四章 結(jié)論31致謝32參考文獻(xiàn)33第一章 前言1.1 搜索引擎的歷史實(shí)際上所說(shuō)搜索引擎是在近10年的不斷發(fā)展中逐步形成的，建立在互聯(lián)網(wǎng)中和計(jì)算機(jī)技術(shù)之上。其實(shí)也有人說(shuō)搜索引擎的鼻祖就是黃頁(yè)，誕生于19世紀(jì)末，因?yàn)辄S頁(yè)在電話(huà)誕生后成為了以電話(huà)為主體的信息門(mén)戶(hù)，而且黃頁(yè)把有電話(huà)的企業(yè)分門(mén)別類(lèi)，的確與現(xiàn)的搜索引擎

12、有相似之處。下面就簡(jiǎn)短地介紹搜索引擎的發(fā)展歷史1：Ø 1990 年由montreal 的mcgill university 學(xué)生alan emtage、peter deutsch、bill wheelan 發(fā)明的archie。后來(lái),程序員們開(kāi)發(fā)出了一個(gè)名叫“spider”(蜘蛛)的“robot”(機(jī)器人)程序,它能自動(dòng)以人類(lèi)無(wú)法達(dá)到的速度不斷重復(fù)地在網(wǎng)絡(luò)上檢索信息。Ø 1993年matthew gray開(kāi)發(fā)了 world wide web wanderer，這是第一個(gè)利用html網(wǎng)頁(yè)之間的鏈接關(guān)系來(lái)檢測(cè)萬(wàn)維網(wǎng)規(guī)模的“機(jī)器人（robot）”程序。開(kāi)始，它僅僅用來(lái)統(tǒng)計(jì)互聯(lián)網(wǎng)上的

13、服務(wù)器數(shù)量，后來(lái)也能夠捕獲網(wǎng)址（url）。Ø 1994年，第一個(gè)既可搜索又可瀏覽的分類(lèi)目錄einet galaxy(tradewave galaxy)誕生。除了網(wǎng)站搜索，它還支持gopher和telnet 搜索。Ø 1994年7月，卡內(nèi)基·梅隆大學(xué)（carnegie mellon university） 的michael mauldin將john leavitt的spider程序接入到其索引程序中，創(chuàng)建了lycos。除了相關(guān)性排序外，lycos還提供了前綴匹配和字符相近限制，lycos第一個(gè)在搜索結(jié)果中使用了網(wǎng)頁(yè)自動(dòng)摘要，而最大的優(yōu)勢(shì)還是它遠(yuǎn)勝過(guò)其它搜索引擎的數(shù)據(jù)

14、量。Ø 1995年12月，dec的正式發(fā)布altavista。altavista是第一個(gè)支持自然語(yǔ)言搜索的搜索引擎，第一個(gè)實(shí)現(xiàn)高級(jí)搜索語(yǔ)法的搜索引擎（如and, or, not等)。Ø 1999年2月，google完成了從alpha版到beta版的蛻變。google以網(wǎng)頁(yè)級(jí)別（pagerank）為基礎(chǔ)，判斷網(wǎng)頁(yè)的重要性，使得搜索結(jié)果的相關(guān)性大大增強(qiáng)。而且google在pagerank、動(dòng)態(tài)摘要、網(wǎng)頁(yè)快照、dailyrefresh、多文檔格式支持、地圖、股票、詞典、尋人等集成搜索、多語(yǔ)言支持等，像altavista一樣，再一次徹底改變了搜索引擎的定義。Ø 2000年

15、1月，超鏈分析專(zhuān)利發(fā)明人、前infoseek資深工程師李彥宏與好友徐勇（加州伯克利分校博士）在北京中關(guān)村創(chuàng)立了百度（baidu）公司。2001年8月發(fā)布b搜索引擎beta版（此前baidu只為其它門(mén)戶(hù)網(wǎng)站搜狐、新浪、tom等提供搜索引擎），2001年10月22日正式發(fā)布baidu搜索引擎。Ø 2005年6月，新浪正式推出自主研發(fā)的搜索引擎“愛(ài)問(wèn)”。1.2 搜索引擎的分類(lèi)計(jì)算機(jī)技術(shù)飛速發(fā)展，關(guān)于搜索引擎的定義和發(fā)展過(guò)程，按其工作方式主要可分為全文搜索引擎、目錄索引類(lèi)搜索引擎和元搜索引擎三類(lèi)2。Ø 全文搜索引擎全文搜索引擎是名副其實(shí)的搜索引擎，它通過(guò)從互聯(lián)網(wǎng)上提取各網(wǎng)頁(yè)的信息而

16、建立的數(shù)據(jù)庫(kù)中，檢索與用戶(hù)查詢(xún)條件匹配的相關(guān)記錄，然后按一定的順序返回給用戶(hù)。而數(shù)據(jù)庫(kù)的建立是通過(guò)一個(gè)叫網(wǎng)絡(luò)機(jī)器人或叫網(wǎng)絡(luò)蜘蛛的軟件，定期自動(dòng)分析網(wǎng)絡(luò)上的各種鏈接并獲取網(wǎng)頁(yè)信息內(nèi)容，按規(guī)則加以分析整理，記入數(shù)據(jù)庫(kù)。此搜索引擎主要依靠網(wǎng)絡(luò)機(jī)器人搜索數(shù)據(jù)，因此需要的數(shù)據(jù)庫(kù)容量非常龐大，但是收集內(nèi)容往往不夠準(zhǔn)確?？梢钥闯?，百度和google就是典型的全文搜索引擎系統(tǒng)： Ø 目錄索引類(lèi)搜索引擎目錄索引類(lèi)搜索引擎雖然也具有搜索功能，卻從嚴(yán)格意義上來(lái)講不能算是真正的搜索引擎。因?yàn)榇怂阉饕媸峭ㄟ^(guò)人工的方式收集整理網(wǎng)絡(luò)資料形成數(shù)據(jù)庫(kù)的，能夠提供更為準(zhǔn)確的查詢(xún)結(jié)果，但收集的內(nèi)容卻非常有限。用戶(hù)完全可

17、以不用進(jìn)行關(guān)鍵詞查詢(xún)，僅靠分類(lèi)目錄也可找到需要的信息。主要代表如yahoo雅虎，open directory project（dmoz），網(wǎng)易搜索。 Ø 元搜索引擎元搜索引擎可以在接受用戶(hù)查詢(xún)請(qǐng)求時(shí)，同時(shí)在其他多個(gè)引擎上進(jìn)行搜索，并將搜索結(jié)果返回給用戶(hù)。著名的元搜索引擎有infospace、dogpile、vivisimo。 1.3 搜索引擎的現(xiàn)實(shí)意義互聯(lián)網(wǎng)正以前所未有的態(tài)勢(shì)改變整個(gè)世界，它現(xiàn)在已經(jīng)成為了人類(lèi)有史以來(lái)資源數(shù)量最多、資源種類(lèi)最全、資源規(guī)模最大的一個(gè)綜合信息庫(kù)。其信息來(lái)源豐富、分布廣泛，各種類(lèi)型信息資源異構(gòu)地分布于網(wǎng)絡(luò)空間中，如果不能使龐雜的信息有序化，就很難獲取。如何準(zhǔn)

18、確有效地從互聯(lián)網(wǎng)上獲取信息，搜索引擎的重要性就顯得越來(lái)越重要。搜索引擎的工作原理實(shí)質(zhì)是信息的獲取，傳統(tǒng)的信息獲取技術(shù)是通過(guò)線(xiàn)性匹配查找的資源，這種方法無(wú)需對(duì)查找資源中的信息進(jìn)行預(yù)處理，僅適用于資源較少的情況。但面對(duì)當(dāng)前海量的信息，如何能夠快速、準(zhǔn)確、全面地獲取信息呢？一般信息獲取可為以下幾個(gè)部分：1) 在獲取信息之前，必須先構(gòu)建文本數(shù)據(jù)庫(kù)。這個(gè)文本數(shù)據(jù)用來(lái)保存所有用戶(hù)可能檢索的信息，數(shù)據(jù)庫(kù)的信息可能會(huì)不斷地變化。但是一旦文本模型確定下來(lái)后，就不應(yīng)對(duì)其再進(jìn)行大的變動(dòng)。2) 有了這種文本模型后，就應(yīng)該根據(jù)數(shù)據(jù)庫(kù)內(nèi)的文本建立索引。索引可以大大提高信息檢索的速度。采用哪種方式取決于信息檢索系統(tǒng)的規(guī)模。

19、大型信息檢索系統(tǒng)均采用倒排的方式來(lái)建立索引。3) 建立好索引后，就可以開(kāi)始對(duì)其進(jìn)行檢索。通常是用戶(hù)提交一個(gè)檢索請(qǐng)求，該請(qǐng)求將被分析，然后利用文本操作進(jìn)行處理。對(duì)于真實(shí)的信息檢索系統(tǒng)，在真正處理查詢(xún)請(qǐng)求前還可以進(jìn)行一些預(yù)處理。4) 根據(jù)用戶(hù)的查詢(xún)返回檢索結(jié)果，通常需要對(duì)檢索結(jié)果進(jìn)行一定的排序與過(guò)濾，以便把重要的檢索信息排在最前面。 用流程圖表示搜索引擎工作流程如下： 圖1-1 搜索引擎工作流程1.4 搜索引擎的發(fā)展趨勢(shì)在互聯(lián)網(wǎng)的發(fā)展初期，網(wǎng)站的數(shù)量比較少，信息查找相對(duì)容易。但是伴隨著網(wǎng)絡(luò)信息以指數(shù)的膨脹速度增長(zhǎng)，單純的簡(jiǎn)單搜索已經(jīng)遠(yuǎn)遠(yuǎn)無(wú)法滿(mǎn)足用戶(hù)的需要。因此各類(lèi)搜索引擎的品牌越來(lái)越多，如最初的g

20、oogle、yahoo到現(xiàn)今的baidu、msn、sogou等滿(mǎn)足大眾信息檢索需求的專(zhuān)業(yè)搜索網(wǎng)站也應(yīng)運(yùn)而生?，F(xiàn)在的搜索引擎往往將自己的搜索范圍擴(kuò)大到整個(gè)因特網(wǎng)上，然而數(shù)據(jù)庫(kù)規(guī)模龐大，為了提高查詢(xún)速度而往往忽視了查詢(xún)信息質(zhì)量。對(duì)于一次檢索，大型搜索引擎往往有成千上萬(wàn)條符合要求的信息，而用戶(hù)只會(huì)瀏覽其中幾十條，也就是說(shuō)用戶(hù)并不需要得到所有符合檢索要求的信息，因此全面、準(zhǔn)確、快速是衡量搜索引擎的重要標(biāo)準(zhǔn)。搜索引擎的發(fā)展趨勢(shì)應(yīng)該是更強(qiáng)調(diào)人的因素，用戶(hù)只需告訴搜索引擎想要查詢(xún)什么，而無(wú)需理會(huì)如何實(shí)現(xiàn)。而搜索引擎應(yīng)該具有判斷性收集信息的功能，即根據(jù)特定用戶(hù)的行為來(lái)決定信息的取舍，提供多樣化服務(wù)，也就是說(shuō)將

21、自動(dòng)分類(lèi)技術(shù)、中文內(nèi)容分析技術(shù)及區(qū)域識(shí)別技術(shù)應(yīng)用到大型搜索引擎中，除了在信息檢索速度、更新頻率等基本技術(shù)指標(biāo)方面處于領(lǐng)先地位外，相關(guān)網(wǎng)頁(yè)檢索、糾錯(cuò)、模糊查詢(xún)、語(yǔ)音查詢(xún)技術(shù)也具有較高的水準(zhǔn)3。目前各搜索引擎的搜索功能仍然處理數(shù)據(jù)庫(kù)基礎(chǔ)建設(shè)和流程挖掘?qū)用妫阉鹘Y(jié)果仍處于對(duì)數(shù)據(jù)初步加工過(guò)程。但相信在不遠(yuǎn)的將來(lái)，搜索必然搜索流程的多次加工和搜索輸出項(xiàng)的個(gè)性化發(fā)展。一方面搜索巨頭的發(fā)展必將導(dǎo)致搜索服務(wù)繼續(xù)呈現(xiàn)高度集中的趨勢(shì)；另一方面搜索技術(shù)、權(quán)力、需要、主體、利益等方面發(fā)生潛移默化的變化，又開(kāi)始呼喚中小服務(wù)商的崛起以及與之密切相關(guān)的搜索領(lǐng)域的多樣化競(jìng)爭(zhēng)格局，搜索商業(yè)的集中和發(fā)散同時(shí)存在。第二章 搜索引擎

22、原理2.1 搜索引擎原理分析搜索引擎一般由搜索軟件、索引軟件和查詢(xún)軟件組成，其中搜索軟件用來(lái)在網(wǎng)絡(luò)上收集網(wǎng)絡(luò)信息；索引軟件對(duì)收集到網(wǎng)頁(yè)的信息進(jìn)行自動(dòng)標(biāo)引，并建立索引數(shù)據(jù)庫(kù)；查詢(xún)軟件則通過(guò)查詢(xún)索引數(shù)據(jù)庫(kù)為用戶(hù)提供服務(wù)。各種網(wǎng)絡(luò)搜索引擎通過(guò)網(wǎng)絡(luò)搜索軟件定期或不定期地在網(wǎng)絡(luò)上搜索信息，并對(duì)搜索到網(wǎng)絡(luò)信息進(jìn)行收集和整理，從而建立可供查詢(xún)的索引數(shù)據(jù)庫(kù)。因此搜索引擎的工作包括以下三個(gè)過(guò)程：一是在互聯(lián)網(wǎng)中發(fā)現(xiàn)、搜索網(wǎng)頁(yè)信息；二是對(duì)搜索的信息進(jìn)行提取和組織，生成索引數(shù)據(jù)庫(kù)；三是由檢索程序根據(jù)用戶(hù)輸入的查詢(xún)關(guān)鍵詞，在索引數(shù)據(jù)庫(kù)中快速查詢(xún)出相關(guān)文檔，進(jìn)行文檔與查詢(xún)內(nèi)容的相關(guān)度比較，對(duì)檢出結(jié)果進(jìn)行排序，并將查詢(xún)結(jié)果

23、返回給用戶(hù)。以下是搜索引擎的基本結(jié)構(gòu)4： 圖2-1 搜索引擎系統(tǒng)結(jié)構(gòu)圖 下面詳細(xì)地分析搜索引擎的工作三個(gè)流程以及相關(guān)的用戶(hù)接口：2.1.1 收集信息搜索引擎中網(wǎng)頁(yè)的采集工作主要由網(wǎng)絡(luò)搜索軟件(如robot、spider、worm)完成, 開(kāi)發(fā)出性能良好的網(wǎng)絡(luò)搜索軟件是一個(gè)艱巨的工作。由于網(wǎng)絡(luò)帶寬窄、網(wǎng)頁(yè)更新快, 搜索引擎的網(wǎng)絡(luò)搜索軟件搜集所有網(wǎng)頁(yè)已經(jīng)成為不可能的事情，優(yōu)先獲取重要網(wǎng)頁(yè)逐漸成了網(wǎng)絡(luò)信息搜索中重點(diǎn)研究的問(wèn)題。不同種類(lèi)的搜索引擎有各自的信息收集方式和范圍，這樣就導(dǎo)致不同的搜索在檢索結(jié)果的數(shù)量以及質(zhì)量產(chǎn)生很大的差別。例如有些搜索引擎會(huì)把搜索范圍發(fā)往每一個(gè)站點(diǎn)，記錄下每一網(wǎng)頁(yè)的所有文本內(nèi)

24、容；有些搜索引擎則會(huì)搜索那些剛剛被更新的網(wǎng)站，然后再將其鏈接收集起來(lái)；有些搜索引擎首先分析數(shù)據(jù)庫(kù)中的地址，以判別哪個(gè)站點(diǎn)最受歡迎，然后再去記錄這些網(wǎng)站的信息。當(dāng)然，除了主動(dòng)搜索方式外，用戶(hù)還可以手動(dòng)提交網(wǎng)頁(yè)的url，即由網(wǎng)站的擁有者自行向搜索引擎提交網(wǎng)頁(yè)，并將提交的網(wǎng)頁(yè)放入搜索引擎數(shù)據(jù)庫(kù)中。2.1.2 建立索引搜索引擎的第二個(gè)過(guò)程是對(duì)搜索軟件采集到的信息進(jìn)行自動(dòng)標(biāo)引，建立可供查詢(xún)的索引數(shù)據(jù)庫(kù)。當(dāng)然不同搜索引擎的索引數(shù)據(jù)庫(kù)規(guī)模和記錄的內(nèi)容是不同的，數(shù)據(jù)庫(kù)的規(guī)模將直接影響查詢(xún)的召回率。例如，有些搜索引擎對(duì)網(wǎng)頁(yè)內(nèi)容全文索引，即對(duì)網(wǎng)頁(yè)中每一單詞進(jìn)行索引；有些搜索引擎對(duì)網(wǎng)頁(yè)某些特征或分類(lèi)進(jìn)行信息提??；還

25、有一些搜索引擎則根據(jù)網(wǎng)頁(yè)的熱門(mén)程度來(lái)決定是否對(duì)網(wǎng)頁(yè)建立索引。2.1.3 查詢(xún)并返回結(jié)果搜索引擎的最后一個(gè)階段是負(fù)責(zé)接收用戶(hù)請(qǐng)求和對(duì)該請(qǐng)求進(jìn)行檢索，并按相關(guān)度返回給用戶(hù)。大多數(shù)搜索引擎除具備分類(lèi)瀏覽和自由詞全文檢索等基本功能外，還包括詞語(yǔ)檢索、范圍檢索、概念檢索以及位置檢索等。2.1.4 用戶(hù)接口前面介紹搜索引擎的具體三個(gè)流程，下面談一下用戶(hù)接口的作用。用戶(hù)接口主要是輸入用戶(hù)查詢(xún)、顯示查詢(xún)結(jié)果以及提供用戶(hù)相關(guān)性反饋機(jī)制。其最主要目的是方便用戶(hù)使用搜索引擎，高效率、多方式地從搜索引擎中獲取有效、及時(shí)地信息。在眾多智能搜索系統(tǒng)中,超鏈接分析是近期大家主要研究的問(wèn)題, 而搜索引擎google所采用的p

26、agerank 算法尤其得到認(rèn)可,下面就重點(diǎn)介紹pagerank算法的原理。2.2 pagerank算法2.2.1 算法原理Ø pagerank算法5是1998年由斯坦福大學(xué)的sergey brin 和lawrence page 提出,它是基于以下原理:如果網(wǎng)頁(yè)a存在一條指向網(wǎng)頁(yè)p的超鏈,則認(rèn)為網(wǎng)頁(yè)a得到網(wǎng)頁(yè)p的認(rèn)可;如果有多個(gè)網(wǎng)頁(yè)指向網(wǎng)頁(yè)a,則認(rèn)為網(wǎng)頁(yè)p的地位比較重要,即當(dāng)網(wǎng)頁(yè)a有一個(gè)鏈接指向網(wǎng)頁(yè)p時(shí),就認(rèn)為網(wǎng)頁(yè)p獲得了一定的分?jǐn)?shù),該分值的多少取決于網(wǎng)頁(yè)a 的重要程度,即網(wǎng)頁(yè)a 的重要性越大,網(wǎng)頁(yè)p獲得的分?jǐn)?shù)就越高.Ø 由于考慮到互聯(lián)網(wǎng)上的鏈接相互指向的復(fù)雜程度6,每個(gè)網(wǎng)

27、頁(yè)所得的分?jǐn)?shù)的計(jì)算過(guò)程是一個(gè)迭代的過(guò)程,最終網(wǎng)頁(yè)將依照所得分?jǐn)?shù)排序并將排序的結(jié)果交給用戶(hù),這個(gè)量化的分?jǐn)?shù)就是pagerank值.用pagerank量化公式表示如下: 假設(shè)pr(a)是網(wǎng)頁(yè)a的頁(yè)面級(jí)別； d 為界于(0,1)區(qū)間的衰減系數(shù),一般取0.85左右； 表示指向網(wǎng)頁(yè)a的其它網(wǎng)頁(yè)； 為網(wǎng)頁(yè)向外指出的鏈接數(shù)目. page rank公式如下： (2.1)Ø 事實(shí)上，根據(jù)上述公式可知，pr值的計(jì)算并不是僅僅一次就能完成的；由于網(wǎng)頁(yè)之間的相互鏈接，任意網(wǎng)頁(yè)pr的變化，都會(huì)引起其他與之相關(guān)鏈接關(guān)系的網(wǎng)頁(yè)pr的變化，因此計(jì)算某一網(wǎng)頁(yè)的pr值，都要經(jīng)過(guò)多次反復(fù)計(jì)算，在達(dá)到一定次數(shù)的重復(fù)計(jì)算后，

28、各網(wǎng)頁(yè)基本達(dá)到穩(wěn)定。Ø 由上述公式可知，某網(wǎng)頁(yè)有較多的鏈入網(wǎng)頁(yè)，則說(shuō)明其它許多網(wǎng)頁(yè)都認(rèn)為該網(wǎng)頁(yè)比較重要的；若較高pr的網(wǎng)頁(yè)指向該網(wǎng)頁(yè)，則認(rèn)為有更重要的網(wǎng)頁(yè)認(rèn)為該網(wǎng)頁(yè)重要；若其它網(wǎng)頁(yè)都只一條鏈接指向該網(wǎng)頁(yè)p，則認(rèn)為許多網(wǎng)頁(yè)都認(rèn)為該網(wǎng)頁(yè)比較重要，這樣網(wǎng)頁(yè)p被推薦的機(jī)會(huì)就會(huì)更大。網(wǎng)頁(yè)的pr值越高，那么該網(wǎng)頁(yè)在檢索結(jié)果列表的位置就越靠近。2.2.2 算法實(shí)例分析 我們清楚了pagerank算法迭代公式為： 下面我們來(lái)舉個(gè)實(shí)例具體分析pagerank算法的實(shí)現(xiàn)：假設(shè)有五個(gè)網(wǎng)頁(yè)，它們之間的鏈接關(guān)系如下：圖2-2 初始鏈接結(jié)構(gòu)根據(jù)上述迭代公式，每個(gè)網(wǎng)頁(yè)的pr初始值為1，其中衰減因子d為0.75，這

29、樣每個(gè)網(wǎng)頁(yè)就相當(dāng)有0.25(1-d)不用于傳遞，即每個(gè)網(wǎng)頁(yè)中0.75被平均地傳遞到其它鏈出網(wǎng)頁(yè)中，下列是迭代公式的計(jì)算過(guò)程： 第一次計(jì)算l 首先，對(duì)于網(wǎng)頁(yè)a，它有一個(gè)鏈出網(wǎng)頁(yè)，考慮衰減因子之后，網(wǎng)頁(yè)a有0.25不用傳遞，其它0.75被傳遞到網(wǎng)頁(yè)b。 同理，網(wǎng)頁(yè)b、網(wǎng)頁(yè)c、網(wǎng)頁(yè)d也同樣只有一個(gè)鏈出網(wǎng)頁(yè)。l 其次，對(duì)于網(wǎng)頁(yè)e，它有三個(gè)鏈出網(wǎng)頁(yè)a、b、d，這樣在考慮衰減因子后，網(wǎng)頁(yè)中的0.75被平均傳遞到網(wǎng)頁(yè)a、b、d。l 最后，得到第一次計(jì)算結(jié)果的pr情況：l 網(wǎng)頁(yè)apr(a)=0.25(網(wǎng)頁(yè)a未傳遞給其它網(wǎng)頁(yè))+0.25(來(lái)自網(wǎng)頁(yè)e) =0.5即l 網(wǎng)頁(yè)bpr(b)=0.25(網(wǎng)頁(yè)

30、b未傳遞給其它網(wǎng)頁(yè))+0.75(來(lái)自網(wǎng)頁(yè)a)+0.25(來(lái)自網(wǎng)頁(yè)e)+0.75（來(lái)自網(wǎng)頁(yè)d）=1.25 即l 網(wǎng)頁(yè)cpr(c)= 0.25(網(wǎng)頁(yè)c未傳遞給其它網(wǎng)頁(yè))=0.25即 pr(c)=0.25l 網(wǎng)頁(yè)dpr(d)=0.25(網(wǎng)頁(yè)d未傳遞給其它網(wǎng)頁(yè))+0.75(來(lái)自網(wǎng)頁(yè)c)+0.25(來(lái)自網(wǎng)頁(yè)e)=1.25即l 網(wǎng)頁(yè)epr(e) =0.25(網(wǎng)頁(yè)e未傳遞給其它網(wǎng)頁(yè))+0.75(網(wǎng)頁(yè)b未傳遞給其它網(wǎng)頁(yè))=1.00即 l 這樣可以得到第一次計(jì)算過(guò)程中網(wǎng)頁(yè)之間傳遞的pr情況如下： 圖2-3 第一次計(jì)算后網(wǎng)頁(yè)鏈接 第二次計(jì)算由于第一次計(jì)算后改變各網(wǎng)頁(yè)的pr值，勢(shì)必會(huì)引起與它相鄰網(wǎng)頁(yè)p

31、r值的改變，例如對(duì)于網(wǎng)頁(yè)a，網(wǎng)頁(yè)e的pr值改變必然會(huì)引起網(wǎng)頁(yè)a的pr值改變。因此計(jì)算仍然需要繼續(xù)。第二次計(jì)算各網(wǎng)頁(yè)的pr值與第一次計(jì)算各網(wǎng)頁(yè)的pr值方法相似，計(jì)算過(guò)程如下：l 網(wǎng)頁(yè)apr(a)=0.25(網(wǎng)頁(yè)a未傳遞給其它網(wǎng)頁(yè))+0.50(來(lái)自網(wǎng)頁(yè)e)=0.75即l 網(wǎng)頁(yè)bpr(b)=0.25(網(wǎng)頁(yè)b未傳遞給其它網(wǎng)頁(yè))+0.375(來(lái)自網(wǎng)頁(yè)a)+0.25(來(lái)自網(wǎng)頁(yè)e)+0.9375（來(lái)自網(wǎng)頁(yè)d）=1.8125 即l 網(wǎng)頁(yè)cpr(c) =0.25l 網(wǎng)頁(yè)dpr(d)=0.25(網(wǎng)頁(yè)d未傳遞給其它網(wǎng)頁(yè))+0.1875(來(lái)自網(wǎng)頁(yè)c)+ 0.25(來(lái)自網(wǎng)頁(yè)e)=0.6875即l 網(wǎng)頁(yè)e pr(e) =

32、0.25(網(wǎng)頁(yè)e未傳遞給其它網(wǎng)頁(yè))+0.75(網(wǎng)頁(yè)b未傳遞給其它網(wǎng)頁(yè)) =1.00即 這樣就可以得到第二次計(jì)算后 圖2-4 第二次計(jì)算后網(wǎng)頁(yè)鏈接情況 第n次計(jì)算 每次計(jì)算后各網(wǎng)頁(yè)pr值隨著改變，從而引起了新一輪的計(jì)算，這樣不斷進(jìn)行迭代計(jì)算各網(wǎng)頁(yè)的pr值，直至各網(wǎng)頁(yè)的pr值趨于穩(wěn)定狀態(tài)，最終的穩(wěn)定狀態(tài)pr值將作為各網(wǎng)頁(yè)的最終pr值。由上述計(jì)算過(guò)程可以看出，pagerank算法使所有網(wǎng)頁(yè)的總和非常巧妙地達(dá)到平衡，就像物理中能量守恒定律，所有網(wǎng)頁(yè)的pr值總和保持不變。例如上述計(jì)算中，各網(wǎng)頁(yè)的初始pr值總和為5，第一次計(jì)算后各網(wǎng)頁(yè)的pr值總和也為5，第二次計(jì)算后各網(wǎng)頁(yè)的pr值總和也為5。

33、同時(shí)，我們可以發(fā)現(xiàn)網(wǎng)頁(yè)之間可以通過(guò)相互鏈接7來(lái)獲得反饋值，例如由上述計(jì)算可知，各網(wǎng)頁(yè)相互鏈接，各網(wǎng)頁(yè)與其它網(wǎng)頁(yè)鏈接可以得到鏈接網(wǎng)頁(yè)的反饋值。由此我們可以想到假如在一個(gè)網(wǎng)站上，網(wǎng)站擁有者可以根據(jù)各網(wǎng)頁(yè)鏈接的設(shè)置來(lái)影響到網(wǎng)頁(yè)的pr值，從而使網(wǎng)頁(yè)的pr值受到更多主觀因素的影響。例如google如果認(rèn)為某網(wǎng)站具有較大的影響力，那么它會(huì)把這個(gè)網(wǎng)站的pr值設(shè)置高一些，這樣就可以方便用戶(hù)更加準(zhǔn)確搜索到對(duì)應(yīng)的網(wǎng)站；假如google認(rèn)為某網(wǎng)站是低質(zhì)量的垃圾網(wǎng)站，那么它就會(huì)把該網(wǎng)站的pr值設(shè)置相對(duì)低一點(diǎn)。2.2.3 算法的不足pagerank算法提出是成功的，符合網(wǎng)絡(luò)發(fā)展搜索引擎的運(yùn)作趨勢(shì)，google的成功運(yùn)作

34、就是一個(gè)極好例子。但是pagerank算法還存在一些明顯的不足，因?yàn)閜agerank算法的提出是基于傳統(tǒng)文獻(xiàn)引文分析方法，并不完全適應(yīng)于網(wǎng)絡(luò)環(huán)境。因?yàn)榫W(wǎng)頁(yè)尤其是一些門(mén)戶(hù)站點(diǎn)的網(wǎng)頁(yè)有太多的分散主題，不像一篇學(xué)術(shù)文獻(xiàn)通常有較為集中的主題；而且由于網(wǎng)絡(luò)世界的開(kāi)放性，網(wǎng)頁(yè)是時(shí)刻變化的，人們可以根據(jù)需要進(jìn)行內(nèi)容以及鏈接的變更，也可以采用有效的鏈接策略來(lái)影響網(wǎng)頁(yè)的pr值，不像傳統(tǒng)學(xué)術(shù)文獻(xiàn)一經(jīng)出版就很少進(jìn)行更改。況且網(wǎng)站和網(wǎng)頁(yè)日益商業(yè)化，很多公司的網(wǎng)頁(yè)不會(huì)鏈接到其對(duì)手的網(wǎng)站。下面詳細(xì)介紹pagerank算法的不足之處。 偏重舊網(wǎng)頁(yè)從公式（2-1） （2-1） 可以看出pagerank算法偏重

35、舊網(wǎng)頁(yè)8，因?yàn)閺?1)式中可以看出決定一個(gè)網(wǎng)頁(yè)pr值的主要因素是指向該網(wǎng)頁(yè)的鏈接個(gè)數(shù)，但由于網(wǎng)頁(yè)在網(wǎng)絡(luò)存在的時(shí) 間越長(zhǎng)，那么它被鏈接的機(jī)會(huì)就越大。這樣由(1)式可以看出舊網(wǎng)頁(yè)pr值比 新網(wǎng)頁(yè)pr值大，也就是說(shuō)pagerank偏重舊網(wǎng)頁(yè)。 主題飄移現(xiàn)象 由于pagerank算法僅僅對(duì)互聯(lián)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)分析，無(wú)法區(qū)分網(wǎng)頁(yè)中的鏈接和該網(wǎng)頁(yè)有關(guān)還是無(wú)關(guān)的，即無(wú)法判斷網(wǎng)頁(yè)間主題的相關(guān)性，這樣容易在最后的推薦結(jié)果出現(xiàn)大量與主題無(wú)關(guān)卻又與具有很高的pagerank值的網(wǎng)頁(yè)，即出現(xiàn)所謂的主題飄移現(xiàn)象9。例如你在google查詢(xún)“圖片”，但又因?yàn)槟承┲匾W(wǎng)站但又與本次查詢(xún)主題無(wú)關(guān)的網(wǎng)站pr值過(guò)高而

36、出現(xiàn)在最前方，這樣會(huì)加重用戶(hù)搜索到相應(yīng)目標(biāo)的速度，在一定程度上加重了用戶(hù)的負(fù)擔(dān)。 專(zhuān)業(yè)站點(diǎn)被忽視專(zhuān)業(yè)站點(diǎn)的訪(fǎng)問(wèn)量遠(yuǎn)遠(yuǎn)少于通俗站點(diǎn)的訪(fǎng)問(wèn)量10，比如某個(gè)學(xué)術(shù)網(wǎng)站，它的內(nèi)容再好，也不可能在短時(shí)間內(nèi)迅速地得到大量的超級(jí)鏈接，所以無(wú)法得到合適的排名。但是專(zhuān)業(yè)站點(diǎn)的論述往往比通俗站點(diǎn)的論述更深刻、更有價(jià)值。 網(wǎng)頁(yè)中超鏈接對(duì)網(wǎng)站pr值的影響網(wǎng)頁(yè)中的超鏈接形式11各異應(yīng)該區(qū)別對(duì)待，而公式(1) 卻無(wú)法正確對(duì)待一個(gè)網(wǎng)頁(yè)中指向的超鏈接。例如下圖：(b)圖在(a)圖的基礎(chǔ)上在網(wǎng)頁(yè)a增加三個(gè)指向重要網(wǎng)頁(yè)d、網(wǎng)頁(yè)e和網(wǎng)頁(yè)f的超鏈接。從客觀分析，應(yīng)該網(wǎng)頁(yè)a的pr值應(yīng)該有所增加。但是由公式(1

37、)分析，網(wǎng)頁(yè)a的pr值不變，而且由于網(wǎng)頁(yè)a的鏈接數(shù)據(jù)增加，因此網(wǎng)站b的pr值有所減少，這樣不合常理的。產(chǎn)生這種情況的主要原因是過(guò)于簡(jiǎn)單地判定一個(gè)網(wǎng)頁(yè)指出的超鏈接會(huì)對(duì)該網(wǎng)頁(yè)產(chǎn)生負(fù)面影響。其實(shí)應(yīng)該分別看待這個(gè)問(wèn)題：如果網(wǎng)頁(yè)a中的一個(gè)超鏈接所指向的網(wǎng)頁(yè)b在內(nèi)容上與該網(wǎng)頁(yè)內(nèi)容相關(guān)，則此超鏈接增加網(wǎng)頁(yè)a的pr值，否則該超鏈接會(huì)減少網(wǎng)頁(yè)a的pr值。 圖2-5 網(wǎng)頁(yè)間鏈接結(jié)構(gòu)2.2.4 算法的改進(jìn) 根據(jù)上述對(duì)page rank算法不足之處的分析，可以看出一個(gè)新網(wǎng)站、小網(wǎng)站或者專(zhuān)業(yè)學(xué)術(shù)網(wǎng)站，由于它們不可能在短時(shí)間內(nèi)迅速得到大量的超級(jí)鏈接，這樣就會(huì)影響到搜索返回結(jié)果排名順序的可靠性，因此必須對(duì)pagerank算

38、法進(jìn)行加以改進(jìn)，為此我們可以從下面幾個(gè)方面進(jìn)行改進(jìn)11。 具有時(shí)間反饋12的改進(jìn)由公式(1)可以pagerank算法存在偏重于舊網(wǎng)頁(yè)的缺點(diǎn)，不能地反映網(wǎng)頁(yè)的實(shí)際重要性，也不能很好地滿(mǎn)足客戶(hù)的要求。因此應(yīng)將某些關(guān)于日期的因素加入，比如網(wǎng)頁(yè)的發(fā)布日期，因此網(wǎng)頁(yè)發(fā)布日期的引入能夠使在網(wǎng)絡(luò)上存在時(shí)間長(zhǎng)的網(wǎng)頁(yè)在檢索結(jié)果排名中沉下去，而新網(wǎng)頁(yè)迅速升起來(lái)。但由于很多網(wǎng)頁(yè)都是由系統(tǒng)自動(dòng)生成，并且大量html網(wǎng)頁(yè)的格式不規(guī)范，很難在網(wǎng)頁(yè)中提取到此網(wǎng)頁(yè)的發(fā)布時(shí)間。因此如何才能更好地表征新網(wǎng)頁(yè)的特征呢？可以這樣考慮，把網(wǎng)頁(yè)存在的時(shí)間通過(guò)搜索引擎搜索周期數(shù)來(lái)表征，它的核心思想是考慮到搜索引擎的搜索周期為

39、半個(gè)月到一個(gè)月，因此若一個(gè)網(wǎng)頁(yè)存在的時(shí)間很久，那么它在一個(gè)搜索周期內(nèi)此網(wǎng)頁(yè)可能被搜索到多次。如果把我們一個(gè)網(wǎng)頁(yè)無(wú)論被搜索到多次，都看作是搜索到一次，那么就可以有效地克服pagerank算法偏重于舊網(wǎng)頁(yè)。 基于網(wǎng)頁(yè)鏈接和內(nèi)容分析的改進(jìn)n 在pagerank算法中，由于知名網(wǎng)站被大量網(wǎng)站鏈接，這使得此知名網(wǎng)站獲得較高的pr值，這樣相對(duì)于某個(gè)特定的查詢(xún)，即使它與查詢(xún)微弱相關(guān)也會(huì)排在檢索結(jié)果的前列，也就是出現(xiàn)了主題漂移現(xiàn)象，因此主題漂移使得查詢(xún)的相關(guān)性遭到極大的破壞。如何才能有效地克服pagerank這種缺點(diǎn)呢？由此可以使用基于網(wǎng)頁(yè)鏈接和內(nèi)容的分析，對(duì)查詢(xún)主題進(jìn)行相關(guān)性評(píng)價(jià)。n 假設(shè)q

40、為查詢(xún)主題；為查詢(xún)文檔；項(xiàng)i在查詢(xún)q中出現(xiàn)的次數(shù)；項(xiàng)i在文檔中出現(xiàn)的次數(shù)；是www上包含項(xiàng)i的文檔數(shù)目的估計(jì)值；這樣就可以得到主題q與文檔的相似度可以按以下公式計(jì)算： (2-2)n 在鏈接關(guān)系的基礎(chǔ)上，加入頁(yè)面與查詢(xún)主題的相關(guān)性權(quán)重，以使得所產(chǎn)生的pagerank值高的頁(yè)面是針對(duì)用戶(hù)查詢(xún)主題的，這就形成了wpagerank算法。改進(jìn)公式如下： (2-3)其中a為給定的一個(gè)網(wǎng)頁(yè)，假設(shè)指向它的網(wǎng)頁(yè)；分別網(wǎng)頁(yè)所含的鏈接數(shù)；d為衰減因子， 一般取0.85；為網(wǎng)頁(yè)a的wpagerank值。n 對(duì)于上述wpagerank算法公式可以這樣理解，假設(shè)網(wǎng)絡(luò)上有一個(gè)主題瀏覽者wpagerank13是訪(fǎng)問(wèn)到網(wǎng)頁(yè)a的

41、概率，它從初始頁(yè)面集出發(fā)，按照頁(yè)面鏈接前進(jìn)，從不執(zhí)行back操作。在每一個(gè)頁(yè)面，瀏覽者對(duì)此頁(yè)面的鏈接感興趣的概率和此鏈接與主題的相關(guān)性成正比例。也有可能瀏覽者對(duì)此頁(yè)面的鏈接不感興趣，這個(gè)可能的概率是d。從直觀上看，如果有多個(gè)頁(yè)面指向某個(gè)頁(yè)面，則該頁(yè)面的pagerank值必定會(huì)提高，但是wpagerank不一定會(huì)高；若有wpagerank很高的頁(yè)面指向它，則此頁(yè)wpagerank也會(huì)很高。因此可以很大地避免主題飄移的現(xiàn)象。第三章 構(gòu)建搜索引擎3.1 lucene入門(mén)3.1.1 什么是lucenelucene是一個(gè)用java寫(xiě)的全文檢索引擎工具包14，可以方便地嵌入各種應(yīng)用中以實(shí)現(xiàn)全文檢索/索引功

42、能，雖然它不是一個(gè)完整的全文檢索引擎，但是它是一個(gè)全文檢索引擎的架構(gòu)，提供了完整的查詢(xún)引擎和索引引擎及部分文本分析引擎。lucene的目的是為軟件開(kāi)發(fā)人員提供一個(gè)簡(jiǎn)單易用的工具包，以方便地在目標(biāo)系統(tǒng)中實(shí)現(xiàn)全文檢索的功能，或者以此為基礎(chǔ)建立起完整的全文檢索引擎。lucene功能強(qiáng)大，能夠?qū)θ魏螖?shù)據(jù)做索引和搜索。lucene不管數(shù)據(jù)源是什么格式，只要它能被轉(zhuǎn)化為文字的形式，就可以被lucene所分析利用。例如在word、html、pdf還是其他什么形式的文件，只要可以從中抽取出文字形式的內(nèi)容就可以被lucene所用，就可以對(duì)它們進(jìn)行索引以及搜索。lucene是一個(gè)開(kāi)放源代碼的項(xiàng)目，自從問(wèn)世之時(shí)起，

43、就引發(fā)了開(kāi)發(fā)源代碼社區(qū)的巨大響應(yīng)。主要因?yàn)閘ucene提供一個(gè)全文檢索引擎的架構(gòu)，具有可擴(kuò)展性且易理解，因而它不僅被用于構(gòu)建具體的全文檢索應(yīng)用，而且也將它集成到了各種系統(tǒng)軟件中，以及用它來(lái)構(gòu)建各種web應(yīng)用，甚至某些商業(yè)軟件也采用lucene作為其內(nèi)部全文檢索系統(tǒng)的核心。3.1.2 lucene的特點(diǎn)lucene作為一個(gè)全文檢索引擎，具有以下突出的優(yōu)點(diǎn)：Ø 索引文件獨(dú)立于應(yīng)用平臺(tái)，lucene定義了一套以8位字節(jié)為基礎(chǔ)的索引文件格式，使得能夠兼容或者在不同的系統(tǒng)平臺(tái)下共享建立的索引文件。Ø 由于其源碼的開(kāi)放性，任何人都可以從網(wǎng)站上獲取最新源碼，并進(jìn)行二次開(kāi)發(fā)，擴(kuò)展其功能。&

44、#216; 強(qiáng)大的面向?qū)ο笙到y(tǒng)架構(gòu)，有利于功能擴(kuò)展，以模塊化的思想來(lái)學(xué)習(xí)，更有利于理解。Ø 擴(kuò)展索引的時(shí)候不斷創(chuàng)建新的索引文件，然后定期地把這些小索引文件合并到原先的大索引文件中。Ø 在傳統(tǒng)全文檢索引擎的倒排索引基礎(chǔ)上，實(shí)現(xiàn)分塊索引，能夠?qū)π碌奈募⑿∥募饕?，提升索引速度，再與原索引進(jìn)行合并，以達(dá)到優(yōu)化的目的。當(dāng)然，lucene也有許多不足之處：Ø 不提供在internet上采集信息的功能，也就是說(shuō)沒(méi)有提供專(zhuān)門(mén)的搜索軟件對(duì)網(wǎng)頁(yè)信息進(jìn)行自動(dòng)采集。Ø 如何將用戶(hù)最感興趣、最重要的網(wǎng)頁(yè)放在搜索結(jié)果的靠前位置，lucene在這方面還有待完善。Ø 只

45、支持文本格式，如txt，html等，不支持word，pdf等文件。Ø 由于中文分詞的特殊性，lucene在設(shè)計(jì)時(shí)并沒(méi)有考慮亞洲文字的特殊性，因此不能對(duì)有中文內(nèi)容的文件進(jìn)行有效的搜索和查找。3.1.3 lucene構(gòu)建搜索引擎基本流程 建立索引索引技術(shù)主要有3種：倒排索引，后綴數(shù)組和簽名文件15。其中l(wèi)ucene采用的索引技術(shù)為倒排索引技術(shù)，它對(duì)于關(guān)鍵詞的搜索非常有效。從整體看，lucene建立索引有以下4步：l 提取文本為了能夠使用lucene對(duì)文檔數(shù)據(jù)建立索引，需要將建立索引的文檔數(shù)據(jù)轉(zhuǎn)換成lucene可以處理的類(lèi)型。例如為word文檔數(shù)據(jù)建立索引，首先應(yīng)從此文檔中提

46、取文本信息，這樣可以有利于lucene的分析。圖3-1 多類(lèi)文檔處理l 構(gòu)建document為了將前面所提取出來(lái)的文本組裝成lucene可以識(shí)別的格式，應(yīng)建立適當(dāng)?shù)膁ocument，因?yàn)槿魏涡枰M(jìn)行索引的文件都必須被轉(zhuǎn)化為document對(duì)象才能被索引和搜索到。l 分析并建立索引在提取了需要lucene建立索引的數(shù)據(jù)并且創(chuàng)建了document之后，接下來(lái)lucene會(huì)首先對(duì)所要建立索引的數(shù)據(jù)進(jìn)行分析，以使得在建立索引時(shí)可以更加容易地處理這些數(shù)據(jù)，然后索引器會(huì)按lucene所規(guī)定的索引格式將數(shù)據(jù)寫(xiě)入索引文件中。 搜索流程Ø 初始化lucene的檢索工具indexsearc

47、her所有檢索都會(huì)用到lucene中最基本的檢索工具indexsearcher，但在使用indexsearcher之前，還要對(duì)其進(jìn)行初始化。即需要設(shè)置索引存放的路徑，這樣才能讓查詢(xún)器定位索引，用于后面進(jìn)行搜索。Ø 構(gòu)建query在使用query之前，需要首先生成一個(gè)query對(duì)象，需指明查詢(xún)字段采用什么樣的方式進(jìn)行查詢(xún)，如模糊查詢(xún)、語(yǔ)義查詢(xún)、短語(yǔ)查詢(xún)、范圍查詢(xún)以及組合查詢(xún)等。Ø 搜索并處理返回結(jié)果在構(gòu)建完query對(duì)象后，就可以使用前面已經(jīng)初始化好的indexsearcher工具進(jìn)行檢索。indexsearcher提供了良好的檢索接口，用戶(hù)只需簡(jiǎn)單地將query對(duì)象傳入，就

48、可以一個(gè)返回結(jié)果。3.2 lucene檢索結(jié)果排序3.2.1 評(píng)分算法公式lucene用于計(jì)算某個(gè)關(guān)鍵字在對(duì)應(yīng)于某個(gè)文檔的得分：. (3-1)其中表示詞條t在文檔d中出現(xiàn)的詞頻；表示詞條t在文檔中的倒排詞頻；表示在索引過(guò)程中設(shè)置的字段參數(shù)；表示在字段中存儲(chǔ)了多少詞條。3.2.2 評(píng)分算法的特點(diǎn)與不足Ø 從公式（3-1）可以此評(píng)分算法的特點(diǎn)：1) 查詢(xún)的關(guān)鍵詞在一個(gè)文檔的位置并不重要，例如要查詢(xún)的關(guān)鍵詞在正文、標(biāo)題或標(biāo)注等，lucene評(píng)分公式并不在乎。2) 如果一個(gè)文檔中含有該查詢(xún)關(guān)鍵的次數(shù)越多，那么得分就越高。3) 若一個(gè)文檔中，如果除了該查詢(xún)?cè)~之外，其他不相關(guān)詞越多，則該得分就越

49、低。Ø 同時(shí)，可以發(fā)現(xiàn)lucene評(píng)分算法的不足：1) 查找精確度不夠，例如我們總希望要查找的關(guān)鍵詞出現(xiàn)在正文中，而lucene不在乎被查詢(xún)的關(guān)鍵詞在文檔中位置，即使查找的關(guān)鍵詞出現(xiàn)在標(biāo)注中，該評(píng)分算法也無(wú)法識(shí)別。2) 沒(méi)有很好地體現(xiàn)網(wǎng)頁(yè)鏈入的度與鏈出的度。3.2.3 評(píng)分算法公式的改進(jìn)對(duì)lucene評(píng)分算法公式的改進(jìn)應(yīng)全面考慮影響網(wǎng)頁(yè)相關(guān)性的因素，使得新得分更客觀、更準(zhǔn)確，進(jìn)一步提高查詢(xún)效率。由于lucene不提供在internet上采集信息的功能，因此很難從網(wǎng)絡(luò)收集網(wǎng)頁(yè)信息。但可以考慮從以下幾個(gè)方面對(duì)lucene的評(píng)分公式進(jìn)行改進(jìn)：Ø 網(wǎng)頁(yè)文檔的鏈接主要考慮互聯(lián)網(wǎng)各網(wǎng)頁(yè)

50、的鏈入情況與鏈出情況，這就要考慮采用前面的pagerank算法，采取基于“從許多優(yōu)質(zhì)的網(wǎng)頁(yè)鏈接過(guò)來(lái)的網(wǎng)頁(yè)，必定是優(yōu)質(zhì)網(wǎng)頁(yè)”的思想，也就是說(shuō)一個(gè)網(wǎng)頁(yè)的得票越多，則認(rèn)為它的重要性越高。Ø 網(wǎng)頁(yè)的響應(yīng)時(shí)間網(wǎng)頁(yè)的響應(yīng)時(shí)間成為評(píng)價(jià)搜索的一個(gè)重要指標(biāo)，它也是評(píng)分應(yīng)該考慮的問(wèn)題之一。如果一個(gè)網(wǎng)頁(yè)的響應(yīng)時(shí)間過(guò)長(zhǎng)，那么用戶(hù)也許會(huì)關(guān)閉此網(wǎng)頁(yè)，而瀏覽其它網(wǎng)頁(yè)。因此網(wǎng)頁(yè)的響應(yīng)時(shí)間也成為lucene評(píng)分應(yīng)該考慮的問(wèn)題所在。Ø 關(guān)鍵詞在網(wǎng)頁(yè)的位置采用lucene評(píng)分公式應(yīng)該考慮關(guān)鍵詞在網(wǎng)頁(yè)中的位置，一般關(guān)鍵詞會(huì)出現(xiàn)在正文，但也有可能出現(xiàn)在網(wǎng)頁(yè)的其它位置，例如出現(xiàn)在網(wǎng)頁(yè)中的鏈接位置、標(biāo)題位置以及標(biāo)注位置

51、等等，這時(shí)要視此關(guān)鍵詞在網(wǎng)頁(yè)中位置的重要性而進(jìn)行加分或減分。Ø 日志記錄用戶(hù)行為如果僅僅從網(wǎng)頁(yè)本身的頁(yè)面信息和網(wǎng)頁(yè)在網(wǎng)絡(luò)上的鏈接關(guān)系來(lái)分析此網(wǎng)頁(yè)的質(zhì)量，而忽略了網(wǎng)頁(yè)的點(diǎn)擊率和網(wǎng)頁(yè)的平均訪(fǎng)問(wèn)時(shí)間，那么檢索結(jié)果很難令人滿(mǎn)意。因?yàn)榫W(wǎng)頁(yè)的點(diǎn)擊率可以反映出此網(wǎng)頁(yè)與用戶(hù)的相關(guān)度，點(diǎn)擊率越高，相關(guān)度就越高，那么檢索結(jié)果排序時(shí)位置就越應(yīng)該靠前。同理，假如用戶(hù)瀏覽某個(gè)網(wǎng)頁(yè)時(shí)間越長(zhǎng)，說(shuō)明此網(wǎng)頁(yè)的質(zhì)量越高。而這些用戶(hù)行為都可以用日志來(lái)記錄。3.2.4 另一種評(píng)分算法-向量空間算法lucene評(píng)分公式主要從定量計(jì)算的角度對(duì)檢索結(jié)果進(jìn)行排序，但我們也可以考慮從語(yǔ)句相似度的角度來(lái)對(duì)檢索結(jié)果進(jìn)行評(píng)分排序?？梢赃@樣

52、考慮：在向量空間模型16中，文檔被表示成一個(gè)k維向量，其中k的大小為所有被索引的文檔中的索引項(xiàng)個(gè)數(shù)，而索引項(xiàng)通常情況文檔中的一個(gè)詞語(yǔ)或短語(yǔ)。而k維中每一項(xiàng)的值是該索引項(xiàng)在文檔中的權(quán)重，一般情況下權(quán)重的大小是大于或者等于0的值，若該索引項(xiàng)在文檔中不存在，則權(quán)重為0；否則權(quán)重大于0。用向量表示文檔，其中表示索引項(xiàng)i在文檔j中的權(quán)重。同理用向量表示查詢(xún)語(yǔ)句，這樣就可以利用文檔和查詢(xún)語(yǔ)句的相似性來(lái)得出查詢(xún)與文檔的相關(guān)性。而如何由文檔和查詢(xún)語(yǔ)句的相似性來(lái)得出查詢(xún)與文檔的相關(guān)性呢？可以考慮采用余弦系數(shù)來(lái)計(jì)算文檔和向量的相似程度。計(jì)算結(jié)果的數(shù)值在0與1之間，值越大，說(shuō)明相似程度相大，因此查詢(xún)與文檔的相關(guān)性就

53、越大，那么對(duì)檢索結(jié)果進(jìn)行排序時(shí)，就應(yīng)該把此文檔的排名位置越靠前。3.3 lucene構(gòu)建搜索引擎3.3.1 構(gòu)建運(yùn)行環(huán)境 操作系統(tǒng)： windows xpjava平臺(tái): jdk 1.5server: tomcat 5.5開(kāi)發(fā)環(huán)境: eclipse 搜索引擎的代碼實(shí)現(xiàn) 索引建立首先建立索引器并進(jìn)行初始化，在lucene中indexwriter類(lèi)可以用來(lái)建立索引，它的功能是將文檔加入索引，同時(shí)控制索引過(guò)程中的各種參數(shù)。在構(gòu)建搜索引擎過(guò)程中，聲明索引器并進(jìn)行初始化如下：/索引器聲明private indexwriter writer=null;/索引器初始化write

54、r=new indexwriter(constants.index_store_path,new standardanalyzer(),true);接著向建立索引的文件構(gòu)造一個(gè)document對(duì)象，并添加在一個(gè)用戶(hù)自定義的域中，以便作為索引查詢(xún)，代碼實(shí)現(xiàn)如下： /生成文檔對(duì)象 document doc=new document(); /獲取文件流 fileinputstream is=new fileinputstream(f);reader reader=new bufferedreader(new inputstreamreader(is); /添加索引內(nèi)容 doc.add(field.t

55、ext("contents", reader); doc.add(field.keyword("path", f.getabsolutepath(); 查詢(xún) 查詢(xún)主要利用servlet和jsp頁(yè)面消息的交互驅(qū)動(dòng)實(shí)現(xiàn)，可以在servlet程序中doget函數(shù)中獲取要查詢(xún)的關(guān)鍵詞，并在建立的索引中檢索關(guān)鍵詞，最后返回檢索結(jié)查。實(shí)現(xiàn)代碼如下：mystructure data=new mystructure();long time=0;try request.setcharacterencoding("utf-8"); /設(shè)置編

56、碼轉(zhuǎn)碼為utf-8 string search=(string) request.getparameter("secontent"); /獲取客戶(hù)端輸入的/搜索字符串if(!justify) /判斷是否第一次搜索，如果是則建立索引 querystr=new perform();time=querystr.predo(); justify=true; data=querystr.runquery(search.tostring(); data.setindextime(time);catch(exception e) e.printstacktrace(); 以下是搜索查詢(xún)界面：圖3-2 搜索界面 搜索結(jié)果搜索結(jié)果主要實(shí)現(xiàn)將前面檢索到的結(jié)果由servlet獲取，并返回給jsp頁(yè)面顯示出來(lái)。實(shí)現(xiàn)代碼如下：servlet實(shí)現(xiàn)將檢索結(jié)果返回：request.setattribute("searchresult",data); requestdispatcher=rd=request