專業(yè)搜索引擎的排序算法研究

1、南京師范大學碩士學位論文專業(yè)搜索引擎的排序算法研究姓名：徐金雷申請學位級別：碩士專業(yè)：教育技術學指導教師：楊曉江20070508摘要搜索引擎是一項嶄新而深奧的技術，包括分詞、文檔分類、特征提取、索引、存儲、檢索和排序等一系列技術環(huán)節(jié)。在這些環(huán)節(jié)中，排序是和用戶最相關的一個關鍵環(huán)節(jié)，當用戶輸入關鍵詞檢索時，如果搜索引擎已經將用戶希望的網頁檢索出來了，但是卻將這些網頁捧在若干頁后，則用戶幾乎不可能瀏覽到該網頁，這樣大大降低了用戶的滿意度。本文主要研究了搜索引擎的排序問題。本文首先通過文獻調研，研究通用搜索引擎排序的一般方法，如詞頻和位置加權算法、DirectHit算法、Alexa的網站排名算法、G

2、oogle的排序算法等，從這些方法中借鑒出通用搜索引擎排序的重要因素，分析了這些因素的求解方法，通過實驗對可能的因素進行了求解。此外，鑒于基礎教育搜索引擎是一個專業(yè)的搜索引擎，筆者研究發(fā)現(xiàn)：使用專業(yè)搜索引擎的用戶有特定的專業(yè)背景，對排序的期望值更高，希望檢索山的頁面都是很相關的。通搜索引擎對某個關鍵詞檢索出的頁面是分布于多個主題的，不符合用戶的需求。筆者提出了主題相關度因素，對每個頁面計算和主題相關韻程度，再與通用搜索引擎排序的若干因素合理整合，使專業(yè)搜索引擎的排序更加符合用戶的需要。本文在基礎教育搜索引擎上進行了排序實驗，實驗證明，這種排序策略是合理可行的。本文在研究排序的同時，對搜索引擎的

3、用戶評價進行了大量的調研，對幾大搜索引擎的性能、檢索方式、檢索結果和用戶負擔等方面進行了比較研究。以期對我們的項目研究有所借鑒。關鍵詞：專業(yè)搜索引擎，排序算法，主題相關度，基礎教育，用戶評價IllAbstractSearchengineitselfisanewandesoterictechnique，includingsometechnical aspects like segmentation，document classify， feature extraction，indexing，storage，retrieval and rankingIn these areas， ranking

4、is most relevant to usersWhen users input a keyword，if search engine locates the web pages users wanted to bottom pages，it is almost impossible for the user to browse through the website，thus greatly reducing the users sati8factionThis paper is mainly on the search engine ranking problemWe first stu

5、dy the literature，and research on the common ranking algorithms of universal search engines， such as the word frequency and location algorithm,Direct Hit algorithm，Alexa website ranking algorithm，Googles ranking algorithmWe research on the important factors of the ranking of search engineThrough exp

6、eriments we work out some possible factorsMoreover，basic education search engine is a specific searchengineThe users of specific search engines have specific backgrounds， hoping the retrieved pages are relatedIn universal search enginea keyword search on the web page is located in a variety of topic

7、sWe put topic relativity factor and calculate itWe combine this factor with universal search engineIt can help the ranking of professional search engine meet usersneedThe experiments show that this ranking strategy is reasonable and feasibleBased on the research of ranking at the same time，we do lot

8、s of research on the usersevaluation of search engineAnd comparative study on several major search engines such as the performance，retrieving means，and search results，hoping to promote our research proj ectsKeywords：Specific Search Engine，Ranking Algorithm，Topic Relativity， Basic Education，Users Eva

9、lua七ion學位論文獨創(chuàng)性聲明本人鄭重聲明：1、堅持以“求實、創(chuàng)新”的科學精神從事研究工作。2、本論文是我個人在導師指導下進行的研究工作和取得的研究成果。3、本論文中除引文外，所有實驗、數(shù)據(jù)和有關材料均是真實的。4、本論文中除引文和致謝的內容外，不包含其他人或其它機構已經發(fā)表或撰寫過的研究成果。5、其他同志對木研究所做的貢獻均已在論文中作了聲明并表示了謝意。作者簽名：日期：至臣i!：墨學位論文使用授權聲明本人完全了解南京師范大學有關保留、使用學位論文的規(guī)定，學校有權保留學位論文并向國家主管部門或其指定機構送交論文的電子版和紙質版：有權將學位論文用于非贏利目的的少量復制并允許論文進入學校圖書館

10、被查閱；有權將學位論文的內容編入有關數(shù)據(jù)庫進行檢索；有權將學位論文的標題和摘要匯編出版。保密的學位論文在解密后適用本規(guī)定。作者簽名：日期：芝1歪2：!業(yè)：第1章前言11專業(yè)搜索引擎排序算法的研究背景111搜索引擎的發(fā)展1、搜索引擎的誕生與發(fā)展搜索引擎1作為網絡信息搜尋的工具，它以一定的策略在互聯(lián)網中搜集、發(fā)現(xiàn)信息，對信息進行理解、提取、組織和處理。并為用戶提供檢索服務。所有搜索引擎的祖先2，是1990年由Montreal的McGillulliveBity學生AlEmtage、PeterDeutsch、BillWheelan發(fā)明的Archie(ArchieFAQ)。當時WoddWideWeb還朱

11、出現(xiàn)。Archie是第一個自動索引互聯(lián)網上匿名FrP網站文件的程序，但它還不是真正的搜索引擎。Archie是一個可搜索的FTP文件名列表，用戶必須輸入精確的文件名搜索，然后Arehie會a告訴_|IJ戶哪一個FTP地址可以下載該文件由于專門用于檢索信息的Robot程序像蜘蛛(spider)-樣在網絡間爬來爬去，因此，搜索引擎的Robot程序被稱為spider(Spider FAQ)程序。tH=界上第一個Spider樣序，是MIT Matthew Gray的World砸de Web Wanderer，川丁追蹤互聯(lián)網發(fā)展規(guī)模。剛開始它只用來統(tǒng)計互聯(lián)網上的服務器數(shù)量，后來則發(fā)展為也能夠捕獲網址(UR

12、L)。1993年2月，6個Stanford(斯坦福)大學生的想法是分析字詞關系，以對互聯(lián)網上的大量信息作更有效的檢索。這就是Excite。后來曾以概念搜索聞名，2002年5月，被Infospace收購的Exdte停止自己的搜索引擎，改用元搜索引擎Dogpile。1994年4月，Stanford兩名博士生，美籍華AJenyYang(楊致遠)llDavid Filo共同創(chuàng)辦了Yahoo。隨著訪問量和收錄鏈接數(shù)的增長，YahooI|錄開始支持簡單的數(shù)據(jù)庫搜索。因為Yahoo的數(shù)據(jù)是手工輸入的，所以不能真正被歸為搜索引擎，事實上只是一個可搜索的目錄。搜索效率明顯提高。(Yahoo以后陸續(xù)使用Altav

13、ista、lnktomi、G009le提供搜索引擎服務)Info-ek(SteveKitschAnnounFreeDemosOfthelnfoseekSearchEngine)是另一個重要的搜索引擎，雖然公司聲稱1994年1月已創(chuàng)立，但直到年底它的搜索引擎才與公眾見面。起初，Infoseek只是一個不起眼的搜索引擎，它沿襲Yahoo,釋lLycos的概念，并沒有什么獨特的革新。但是它的發(fā)展史和后來受到的眾口稱贊證明，起初第一個登臺并不總是很重要Infoseek友善的片j戶界面、大量附加服務(such asUPStracking，News，adirectory,andthelike)使它聲望日隆

14、。而1995年12月與Netscape的戰(zhàn)略性協(xié)議，使它成為個強勢搜索引擎：當用戶點i蕾Netscape瀏覽器上的搜索按鈕時，彈出lnfoseek的搜索服務，而此前由Yahoo提供該服務31995年，一種新的搜索引擎形式出現(xiàn)了元搜索引擎(AMeta SearchEngineRoundup)。用戶只需提交一次搜索請求，由元搜索引擎負責轉換處理后提交給多個預先選定的獨立搜索引擎，并將從各獨立搜索引擎返回的所有查洵結果，集中起來處理后再返同給用戶。DEC的AlmVism(2001年夏季起部分網友需通過p_xy訪問，無p-roxy可tLJqbseach單選altavista搜索，只能顯示第一頁搜索結果

15、)是一個遲到者，1995年12月才登場亮相(AltaVistaPublic Beta Press Release)。但是，大量的創(chuàng)新功能使它迅速劍達當時搜索引擎的頂峰。林瑞宜陳榕虎搜索引擎新研究情報探索2005年5月2http：www,foshanwcomscoseose07htm3 Infoseek后來曾以相關性聞名，2001年2月，Infoseek停止了自己的搜索引輦，開始改用Overture的搜索結果AJtavista最突出的優(yōu)勢是它的速度。而A】tavism的另一些新功能，則永遠改變了搜索引擎的定義AltaVmta是第一個支持自然語言搜索的搜索引擎，AltaVista是第一個實現(xiàn)高級搜

16、索語法的搜索引擎(如AND，OR,NOT等)用戶可以用Al蝴sta搜索Newsgroups(新聞組)的內容并從互聯(lián)網上獲得文章，還可以搜索圖片名稱中的文字、搜索Titles、搜索Java applets，搜索ActiveXobjects。AltaVmta也聲稱是第一個支持用戶自己向網頁索引庫提交或刪除URL的搜索引擎。并能在244,時內上線AltaVista最有趣的新功能之一，是搜索有鏈接指向某個URL的所有網站。1998年lO月之前，Google只是Smfd大學的一個小項目BackRub。1995年博士生LarryPage開始學習搜索引擎設計，于1997年9月15日注冊Tgooglee,on

17、l的域名，1997年底，在SemeyBrin幣lSeott Hassan、Alan Sterberg的共同參與下，BachRub開始提供Demo。1999年2月，Google完成了從Alpha版到Beta舨的蛻變。ch酒e公司則把1998年9上J27EI認作自己的生日。Google在Pagerank、動態(tài)摘要、網頁快照、DailyRcfiesh、多文檔格式支持、地圖股票詞典尋人等集成搜索、多語言支持、用戶界面等功能上的革新，像Altavista-樣，再一次永遠改變了搜索引擎的定義。2、中文搜索引擎的發(fā)展七人天網是國家“九五”重點科技攻關項目“中文編碼和分布式中英文信息發(fā)現(xiàn)”的研究成果，由北人計

18、算機系網絡與分布式系統(tǒng)研究室開發(fā)，于1997年lO月29E1正式在CERNET上提供服務。2000年初成立天網搜索引擎新課題組，由國家973重點基礎研究發(fā)展規(guī)劃項目基金資助開發(fā)，收錄網頁約6000萬，利塒教育網優(yōu)勢，有強人的FTP搜索功能。2000年1月，超鏈分析專利發(fā)明人、前hfoscek資深工程師李彥宏與好友徐勇(加州伯克利分校博士)在北京中關村創(chuàng)立了百度(Baidu)公司。2001年8月發(fā)布BaiduCorn搜索引擎Beta版(此前Baidu只為其它門戶網站如搜狐新浪Tom等提供搜索引擎)，2001年10月22日正式發(fā)布Baidu搜索引擎。Baidu雖然只提供中文搜索，但目前收錄中文網頁

19、超過9000萬，可能是最大的的中文數(shù)據(jù)庫。Baidu搜索引擎的其它特色包括：網頁快照、網頁預覽預覽全部網頁、相關搜索詞、錯別字糾正提示、新聞搜索，Hash搜索、信息快遞搜索。2002年3月閃電計劃(Blitzen Project)開始后，技術升級明顯加快112搜索引擎的技術架構搜索引擎的原理，可以看做三步：從互聯(lián)網上抓取網頁一建立索引數(shù)據(jù)庫一在索引數(shù)據(jù)庫中搜索排序。從互聯(lián)網上抓取網頁國l則能夠從互聯(lián)網上自動收集網頁的Spider系統(tǒng)程序，自動訪問互聯(lián)網，并沿著任何網頁中的所有URL爬劍其它網頁，重復這過程，并把爬過的所有網頁收集回來。建立索引數(shù)據(jù)庫由分折索引系統(tǒng)程序對收集回來的網頁進行分析，提

20、取相關網頁信息(包括網頁所在URL、編碼類型、頁面內容包含的關鍵詞、關鍵詞位置、生成時間、大小、與其它網頁的鏈接關系等)，根據(jù)一定的相關度算法進行大量復雜計算，得到每一個網頁針對頁面內容中及超鏈中每一個關鍵詞的相關度(或重要性)，然后用這些相關信息建立網頁索引數(shù)據(jù)庫。在索引數(shù)據(jù)庫中搜索排序一當用戶輸入關鍵詞搜索后，由搜索系統(tǒng)程序從網頁索引數(shù)據(jù)庫中找到符合該關鍵詞的所有相關網頁。因為所有相關網頁針對該關鍵詞的相關度早己算好，所以只需按照現(xiàn)成的相關度數(shù)值排序。相關度越高，排名越靠前。最后，由頁面生成系統(tǒng)將搜索結果的鏈接地址和頁面內容摘要等內容組織起來返回給用戶。113基礎教育搜索引擎的應運而生及系

21、統(tǒng)架構自從面向2l世紀教育振興行動計劃首次明確將“教育信息化”確定為教育發(fā)展的2重要主題并將教育資源建設定為重點，各企業(yè)、學校、部門紛紛投入大量的人力、物力建設教育資源。到今天分布在全國各地服務器的基礎教育資源是無法統(tǒng)計的，而且它每天都像滾雪球一樣在不斷的增長2001年6月教育部頒布基礎教育課程改革綱要(試行)，提出了基礎教育課程改革的具體目標，其中之一是培養(yǎng)學生搜集和處理信息的能力、獲取新知識的能力、分析和解決問題的能力以及交流與合作的能力?；A教育專業(yè)搜索引擎(以下簡稱BERSE)作為基礎教育領域的專業(yè)搜索引擎的誕生也就不足為怪了，它的誕生是基礎教育資源建設和基礎教育改革發(fā)展的必然結果，也

22、是廣大從事基礎教育研究工作、教學工作人員離不開的工具，對學生來說也是培養(yǎng)他們rr技能的平臺之一。圖卜1基礎教育搜索引擎的系統(tǒng)架構圖BERSE系統(tǒng)的結構如圖1-1所示，本系統(tǒng)主要包括控制器、網絡蜘蛛、資源分類器、索引器，商業(yè)服務、檢索器和相關數(shù)據(jù)庫等主要模塊。這些模塊是互相聯(lián)系的，它fJ的功能劃分并不是完全獨立的，相互間存在著內在聯(lián)系。它們的主要功能描述如下：控制器：控制系統(tǒng)良好運行的各項參數(shù)，如服務器分配、數(shù)據(jù)調度、負載平衡等。網絡蜘蛛：它是一個Web Crawler，它負責不問斷地從互聯(lián)網上搜集、更新基礎教育資源并存儲劍文檔下載庫中。分類器、索引器：對網絡蜘蛛搜集劍的資源進行處理分類，并建立

23、索引存儲到索引數(shù)據(jù)庫中商業(yè)服務；為基礎教育資源開發(fā)商提供產品推介平臺，同時也是本系統(tǒng)實現(xiàn)其商業(yè)利潤的一個模塊。檢索器：為本系統(tǒng)的用戶提供基礎教育資源搜索、導航服務。114捧序在搜索引擎中的作用和地位當前互聯(lián)網已經達到數(shù)十億網頁的規(guī)模，并且正在以海量的速度增氏，由于其規(guī)模如此3之龐大，用戶在查詢資料的時候，經常面對搜索引擎返回的成千上萬的網頁鏈接，而用戶點擊這些鏈接后發(fā)現(xiàn)如下問題：1)某些網頁的確包含用戶輸入的搜索詞，可是內容卻并非是相關的；2)某些網頁早已更新，用戶查詢的主題甚至已不存在；3)某些網頁的信息已十分陳舊失去意義；4)某些網頁確有用戶所需要的資料，但是質量不高，或朱達到用戶所期望的

24、層次。為使所點擊的最初若干鏈接能滿足需要，因此搜索引擎應盡可能在不遺漏相關網頁的基礎上，將最恰當?shù)淖羁尚诺木W頁鏈接放在返回結果的最前面。因此，搜索引擎的排序算法，成為搜索引擎最核心和關鍵的技術之一，也是現(xiàn)今網絡服務研究的熱點之一從用戶角度來說，如果搜索引擎的排序結果不合理，那么他也不愿意使用該搜索引擎。一個搜索引擎的排序直接決定用戶使用的滿意度。襄11中國搜索引擎用戶不滿意因素及比倒不滿意因素所占比飼搜索結果重復50*搜索結果排序欠佳43搜索結果太雜亂37搜索結果不合時宜36廣告太多35根據(jù)某搜索引擎2000年4月的近50萬的_Hj戶點擊情況的查詢日忐所作的一項統(tǒng)計表12用戶在前5頁的翻頁統(tǒng)計

25、頁號l2345百分比47薯121l冀714510317可見，用戶絕大部分的瀏覽集中在前幾頁，往后的頁面被用戶瀏覽到的幾率越米越小，有的頁面幾乎不被用戶瀏覽到。115專業(yè)搜索引擎捧序的研究現(xiàn)狀國內該方面的研究比較少，主要集中在對某些著名搜索引擎的研究上，如對Google的研究。發(fā)表的論文數(shù)量并不多，并且大部分是介智性的，實刖性不強。但是近幾年國內搜索引擎的發(fā)展速度加快，有代表性的是百度和天網，其中百度關于排序的研究成果沒有公開發(fā)表，天網的最新專著搜索引擎一技術、原理與系統(tǒng)公開了其捧序的部分信息國外這方面的研究成果相對要多，具有代表性的是對Google捧序算法的研究，其中尤以對PageRank及其

26、HITS相關研究居多。比較成熟的算法有：1)詞頻和位置加權排序算法2)Direct Hit算法3)Alexa的網站排名算法4)Google的排序算法5)開源搜索引擎如lucene的排序思想搜索引擎排序算法作為商業(yè)機密不作公開，因為一旦公開，則必有一些網站會針對其中的一些因素，在自己的網站上進行加強，從而獲得較高的捧名，打亂互聯(lián)網的公平競爭原則所以，一般的研究主要是基于某些搜索引擎搜索現(xiàn)狀的推理和猜測。近些年，一個新興的高級技術行業(yè)SEO(搜索引擎優(yōu)化)發(fā)展很快，SEO主要為企業(yè)4網站提供服務，目的是通過一些網絡技術手段使企業(yè)網站提高在Alexa或Google等搜索引擎中的捧名，提升用戶點擊的幾

27、率，獲得更多的商機。通過SEO手段提高排名要繳納一定的費用。一般捧名越前繳費越多然而SEO獲得捧名的手段有時候是不合法不公平的，所以一些大的搜索引擎如Alexa和Google等，對這類通過不正當手段獲得高排名的網站會不定期進行檢查，采取嚴厲的懲罰措施甚至封殺。SEO和搜索引擎之間一直不問斷地進行斗爭116專業(yè)搜索引擎捧序的面臨的主要問題1、從用戶角度在通用搜索引擎中，為了使用戶能比較快捷地得到想要的資源，排序環(huán)節(jié)起到了很重要的作用。Google之所以能成為全球搜索第一品牌，其優(yōu)秀的排序結果是決定性因素之一在中國搜索引擎明戶所不滿意的因素調查如下：1)搜索結果的重復502)排序結果欠佳433)搜

28、索結果太雜亂374)搜索結果不合時宜365)廣告過多35用戶對排序的結果不滿意占了很大的比重。剛戶認為，排序在前的網站往往不是最新的；前面的網頁內容不是自己最需要的，很多是對白己沒有剛的信息；有時候為了找到一個有用的網頁需要往后翻好幾頁等。2、從Web資源本身就我們的項目基礎教育資源搜索引擎來說，在開放的網絡教育資源環(huán)境中，利剛搜索引擎查找所需的Web資源，往往不能很容易的得到所需的資源，這是因為：1)教育資源的文檔生存周期比較長，更新比較慢；2)教育領域學科較多，很多學科之間存在交義現(xiàn)象；3)數(shù)據(jù)量大，即便最符合用戶意圖的頁面已經被檢索出來了，但是很難捧到最前面。在基礎教育資源搜索引擎系統(tǒng)的

29、背景下，對排序有特定的要求：基礎教育資源搜索引擎是一個專業(yè)搜索引擎，通用搜索引擎的排序策略在一定程度上不能滿足其需要。通用搜索引擎的排序主要考慮詞頻和網頁權威性等。而BERSE不能僅僅沿用通用搜索引擎的排序思想，必須設計符合自身專業(yè)搜索引擎的排序策略。這是在文本分類基礎之上的又一次資源提煉?，F(xiàn)有待檢索的文檔資源都是經過文檔分類程序處理的，絕大部分資源是符合基礎教育特性的。但是總有少數(shù)和基礎教育的聯(lián)系不緊密，排序程序在呈現(xiàn)排序結果時盡量將這些文檔排后。117專業(yè)搜索引擎捧序研究的意義筆者參與開發(fā)的基礎教育資源搜索引擎是一個典型的專業(yè)搜索引擎，組織索引了大量的網絡教育資源，是基礎教育領域的信息查詢

30、工具之一。面向的用戶是從事基礎教育的老師、教研工作者、家長和中小學學生，這些用戶使用該搜索引擎的目的性很強。如果該搜索引擎不能將非常重要的資源檢索出來并排到前面，將極大地影響該搜索引擎的用戶滿意度。因此，如何設計基礎資源的搜索引擎的排序就顯得尤為重要。在通用搜索引擎中鍵入檢索詞，得到的輸出結果是多方面的，包含多個主題和領域。雖然眾多網絡用戶的需求是多方面的，但是對某個具體身份的_H戶而言，他很可能需要特定的輸出結果，通用搜索引擎的排序結果往往不能滿足特定用戶對特定專題的需求。以下分別從5三個例子來看：飼一：一個中學語文老師想查找一些魯迅的文章，輸入關鍵詞“魯迅”進行檢索，他想要的是關于魯迅的一

31、些生平或者作品，但是檢索結果如圖1-2圖12。魯迅”在百度中的檢索結果首頁從檢索結果可以看出，用戶在首頁就很難直接找到跟魯迅相關的作品，如“魯迅美術學院”，該頁最下端還有“魯迅教育集團”等不相關的信息。例二：物理老師檢索“杠桿”，希望能找劍和物理教學相關的輔助材料。百度中的檢索結果如圖l-3。6圖1-3“杠桿”在百度中的檢索結果首頁百度首頁上的前幾項中僅有兩項和物理教學有相關，大部分是無關的。如果這個物理老師想要更多的資源，他則需往后翻頁去瀏覽尋找。例三：一個語文老師想介紹一些和泰山相關的知識，但是檢索結果如圖14。圖1-4“泰山”在百度中的檢索結果首頁7對這個語文老師來說，其中只有兩個網址是

32、有用的，而其他的網址則沒有什么參考價值，要想獲得更多的資源，還得往后翻頁?？傊?，有的搜索引擎能滿足相當一部分用戶的搜索需求，但是如果用戶是特定的某個領域的，有專一主題的需求時，排序的結果就不能滿足這些用戶了。所以，本文就專業(yè)搜索引擎的排序作研究，有很大的現(xiàn)實意義。12本文的主要工作121研究思路本文研究的思路首先是研究現(xiàn)今各大成功的通_fl搜索引擎的排序策略，從中分析影響搜索引擎排序的因素。然后對專業(yè)搜索引擎的特殊性作分析，得出專業(yè)搜索引擎不同于通_lJ搜索引擎的總體原則，最后在通用搜索引擎排序研究的基礎之上，創(chuàng)造適合專業(yè)搜索引擎排序的因素，并整合成合理的算法。通過實驗不斷的調整算法使攤序更加

33、有效。122研究主要內容本文著重研究對排序影響重要的若干因素并適當求解，設計排序算法，就基礎教育搜索引擎項目實例進行排序實驗，在實驗的過程中對算法進行調整。提煉算法使之符合一般意義的專業(yè)搜索引擎。123研究的成果和創(chuàng)新本文對各大搜索引擎的排序算法作了研究，在此基礎上，分析和歸納了適合通用搜索引擎排序的重要因素，并對其中的若干因素作出求解。本文詳細分析了專業(yè)搜索引擎捧序的特殊要求，提出了專業(yè)搜索引擎排序的原則。設計了適合基礎教育搜索引擎捧序的算法，并通過一系列實驗證明算法的合理和可行。同時不斷地改進。由基礎教育搜索引擎的排序算法提煉升華，本文提出了適合一般專業(yè)搜索引擎的捧序算法，具有推廣的意義。

34、8第2章信息檢索中的排序21傳統(tǒng)信息檢索的相關捧序技術給定幕個文檔集合D，大小為M；設兩篇文檔“、“2D，一個查詢q，用什么標準來衡量“1與“2相比，誰和q更相關呢?”這方面最經典的、最有影響力的工作是Gerald Sahon等在30多年前提出的“向量空間模型”(vector space model，VSM)。該模型做了如下假設：文檔d和查詢q的相關性可以由它們所包含的共有詞匯情況來描述。這樣，文檔d和查詢q就都被簡化成詞匯的集合(多重集)。不失一般性，令為一個詞典，1為詞項，N為它的規(guī)模，則d=(礦，毋，咿)q=(fP，哆，彬)4其中，mt、珥O=l，2，)表示相應詞項山現(xiàn)的次數(shù)，即詞頻TF

35、如果次數(shù)為0，則表示該詞項在文檔或查詢中沒有出現(xiàn)。在通常的應_HJ系統(tǒng)中，人們直接用佩、珥來表示d采l q。d和q的相關度評價就以這兩個向量的某種“相近程度”為基礎。1)詞項在文檔和查詢中出現(xiàn)的次數(shù)(詞頻)是一個基本量，我們稱為“詞頻”，規(guī)格化表示：d=(，馴姚2轟查詢q也有同樣的表示，這里wt也稱為詞頻，這種方式用詞頻來表示該詞項在文檔和查詢中的權重。2)若一個詞項在很多文檔中出現(xiàn)，盡管它可能在某個文檔內部出現(xiàn)的頻率較高，但是對于不同文檔的區(qū)分能力就不會很強，因此它的權重應該相對小些，這就引出了該詞的文檔頻率DF的概念用島表示詞項在文檔集合D中涉及的文檔個數(shù)，M表示集合D的大小，則文檔頻率為

36、DF()=魯我們需要一個和DF成反比的量，稱之為倒置文檔頻率IDF，常用的一種定義是F：lg(|rM-)。這樣結合詞頻，就有了經典的7FF權重的設計：12弼嘲2瓦mI xlg(爭給定某種權重的定量設計，求文檔和查詢的相關性就變成了求d和q向量的某種距離，最常用的是余弦(cos)距離：毗護鬻這些理論，源于傳統(tǒng)信息檢索領域，針對的是普通的文本。搜索引擎一原理、技術與實現(xiàn)李曉明p176表10-3補償因子定義表922通用搜索引擎的排序算法和策略本文通過大量的中外文獻調研，歸納了現(xiàn)今通用搜索引擎的排序算法，主要有以下幾種：221詞頻和位置加權捧序算法詞頻位置加權排序算法是一種只從關鍵詞出現(xiàn)的相對密度進行

37、排序的方法。在計算關鍵詞的相對密度時應該考慮：關鍵詞出現(xiàn)的位置、出現(xiàn)的次數(shù)、文檔的躍度。其中關鍵詞出現(xiàn)的位置應該考慮這樣幾個位置：標題(Title)、元標記(META)、關鍵詞(Keyword)、鏈接文本(AnchorText)。在本算法中，詞對文檔的相關性與詞在該文檔中的權值成正比下表是不同關鍵字在不同位置的權重值分布。表2關鍵詞和詞頻位置關系的權值裹關鍵詞位置權值關鍵詞位置權值外部鏈接文字10每句開頭15標題10加粗或斜體1域名7文本用法lH1，H2號字體5Title屬性l每段句首5A1t屬性05路徑或文件名4Meta描述0，5關鍵詞堆積Mcta關鍵詞0054(keywords)該算法的優(yōu)

38、點在于簡單、易實現(xiàn)，它的不足之處在于：該算法比較適J【l=I于結構化文檔數(shù)據(jù)，如期刊數(shù)據(jù)等，對自由的互聯(lián)網來說，很難保證文檔的結構和文檔的質量。222DirectHit算法Direct Hit是Ask Jeeves公司的一種注重信息質量和用戶行為反饋的排序算法，它的基本思想是：用戶輸入檢索詞條t后，如果用戶在瀏覽搜索引擎提供的n條結果記錄中第i條記錄(RUL)時，停留了較長時問，則說明記錄i與關鍵詞t具有較高的相關度；如果用戶停留時間較短，用戶很快返回結果記錄瀏覽第j條記錄，說明記錄i與關鍵詞t相關度較小由此可見，同一個詞在不同的時間進行檢索，得到的結果集排序可能不同，BPDirect Hit

39、捧序是一種依賴用戶搜索行為的動態(tài)排序。在該排序算法中，網頁排序結果由兩部分決定；URL被點擊次數(shù)和被瀏覽的時間長度。該算法的優(yōu)點是：首先它利用了用戶的反饋信息進行排序，在一定程度上滿足了“J【f=l戶保障原則”；其次，該算法在排序時考慮了信息的質量。而該算法的不足之處在于：一是用戶行為比較隨意，很難保證捧序結果的準確性；二是在多頁的檢索結果中，大部分用戶只瀏覽前幾頁的結果，因此對于一些排名較示或者新登錄的網站很難有機會獲得點擊，從而一直無法提高自己的排名。323Alexa的網站捧名算法Alexa是以發(fā)布世界網站排名而引人注目的一個網站。在URL數(shù)量上，Alexa位居世界四大名搜索引擎第一位，已

40、經超過了350億。101，Alexa的世界網站排名1)綜合排名，也可以叫做絕對排名，即特定的一個網站在所有350多億網站中的名次Alexa每三個月公布一次新的網站綜合排名此排名的依據(jù)是用戶鏈接數(shù)(Users Reach)和頁面瀏覽數(shù)(Page Views)三個月累積的幾何平均值。2)分類捧名，一是按主題分類，比如新聞，娛樂，購物等，Mexa給出某個特定網站在同一類網站中的名次。Alexa將其收集到的網站共分了16個大類，每個類下又分為多個主題。二是按語言分類，比如英文網站、中文網站、法文網站、德文網站等，給出特定站點在所有此類語言網站中的名次。Mexa提供了21種不同語言網站的分類排名。其中中

41、文網站還細分成簡體中文和繁體中文兩種。對于中文網站的排名只發(fā)布捧在前100名的網站名單。2、Alexa對網站排名的前提條件1)Mexa的網站排名是按照每個特定網站的被訪問量進行排名的。訪問量越大，排名越靠前。2)訪問量是針對定義在域上的網站進行統(tǒng)計的如：sinaccn，newssinatoman和techsinatOmcn將被視作同一網站進行計數(shù)，因為它們同屬于sins COilcn這個域。3)提供同樣內容的網站將被視為同一網站計算。比如說，傳播研究網使用wt mediaresearchc091Cll$1http：vnwmediaresearchca兩個域名發(fā)布同樣的內容，那么將被作為同一個網

42、站來計算。4)納入統(tǒng)計的訪問量僅來自使用AlexaI具欄(AlexaToolbar)的用戶。也就是說，只有用戶下載了Alexa工具欄，并將其嵌入自己的瀏覽器。這樣，該用戶訪問某個網站的話，訪問的記錄才能算作被訪問網站的訪問量。據(jù)Alexa統(tǒng)計，現(xiàn)在使用該工具欄的用戶達數(shù)百萬。5)AlexaI具欄僅在windows操作系統(tǒng)下，Internet Exploer瀏覽器中管用，使用其它操作系統(tǒng)或者瀏覽器的訪問將不能被計數(shù)。6)遇到有安全保護或加密的站點(如使用https協(xié)議)，Alexa工具欄將自動關閉，因此那些安全系數(shù)高的網站，Alexa將不能對其進行搜索和統(tǒng)計捧名3、Alexa對網站訪問量算法1)

43、某個特定網站被捧名時，依據(jù)的訪問量數(shù)據(jù)是基于該網站3個月訪問量記錄的累積。也就是說Alexa每三個月發(fā)布一次排名結果，即通常說的名次。它的計算主要取決于用戶鏈接數(shù)(Users Reach)和頁面瀏覽數(shù)(Page Views)Alexa系統(tǒng)每天對每個網站的用戶鏈接數(shù)和頁面瀏覽數(shù)進行統(tǒng)計，通過這兩個量的三個月累積值的幾何平均得出當前名次變動是指與前三個月的比較2)用戶鏈接數(shù)(Users Reach)指通過Internet訪問某個特定網站的人數(shù)。用訪問某個特定網站的人數(shù)占所有Internet塒戶數(shù)的比例來表示。即：用戶鏈接數(shù)=(訪問人數(shù)全部Alexa用戶數(shù))10096 Alexa以每百萬人作為計數(shù)單

44、位。以雅虎(Yahoo)為例，如果它的用戶鏈接數(shù)為28的話，就是說，隨意抽取一百萬的Iaternet用戶，其中有280，000人訪問Yahoo3)頁面瀏覽數(shù)(PageViews)是指用戶訪問了某個特定網站的多少個頁面。是所有訪問該網站的朋戶瀏覽的頁面數(shù)之和。每個用戶瀏覽的頁面數(shù)取平均值，是所有訪問該網站的用戶每天每人瀏覽的獨立頁面數(shù)的平均。同一人、同一天、對同一頁面的多次瀏覽只記一次。4、影響Alexa網站排名的其它因素1)受使用Alexa工具欄用戶的語言、地域、文化等各方面的影響。因此英文網站相對于其它語言的網站，訪問量數(shù)據(jù)更容易被充分地統(tǒng)計。2)由于某種需要，用戶可能過多的訪問alexaC

45、Om，amazoIL coarchiveorgY-個網站，所以這幾個網站的訪問量可能被過高的統(tǒng)計。3)很容易受網站對自己宣傳的程度、打廣告的多少、別的網站為其建立鏈接的多少的影響224Google的捧序算法Google是全世界被使用的最多的通用搜索引擎。與其它搜索引擎比較，除高性能和易用以外，一個決定性的因素是其優(yōu)秀的搜索結果。Google搜索結果的質量在很大程度上受益于PageRanl【_個精密的排序網頁文件等級的方式。PageRank的思想源于學術引文機制：當從網頁A鏈接到網頁B時，就認為網頁A投了網頁B一票，增加了網頁B的重要性，最后根據(jù)網頁B的得票數(shù)評定其重要性計算公式為：衛(wèi)PR(A)

46、=0一d)+d芝：PR(p,)c(B)ftl其中：PR(A)：頁面A的網頁級別PR(pI)：頁面n的網頁級別C(B)：頁面B鏈出的鏈接數(shù)量d：阻尼系數(shù)，取值在0-I之間，一般取085N：互聯(lián)網上所有網頁的數(shù)量Google采用一種近似的迭代的方法計算網頁的網頁級別，即給每個網頁一個初始值，然后利用上面的公式，進行有限次迭代運算得到網頁的級別值。在迭代的過程中，每個網頁的網頁級別和收斂于整個網絡的頁面數(shù)。每個頁面的平均網頁級別是l，實際上的值在(1-d)和(心J+(1-d)之間。PageRank只是Google用來排序的一個重要因素，Google還運用了很多其他因素來排序，這里就不展開了PageR

47、ank是由Google的創(chuàng)始人Larry Page希lSergey Brin在斯坦福大學開發(fā)出的一套用于網頁評級的系統(tǒng)組織管理工具，PageRank利用了互聯(lián)網獨特的民主特性及其巨大的鏈接結構，在浩翰的鏈接資源中，Google提取出上億個超級鏈接進行分析，制作出一個巨人的網絡地圖(Map)。依據(jù)此地圖，PageRan技術能夠快速地計算出網頁的級別(Rank)，從而進行捧序輸出。它的基本思想主要是來自傳統(tǒng)文獻計量學中的文獻引文分析，即一篇文獻的質量和重要性可以通過其它文獻對其引川的數(shù)量來衡量，也就是說，一篇文獻被其它文獻引心越多，則文獻質量就越高。在這樣一個假設基礎之上，一個網頁的質量和重要性也

48、可以通過其它網頁對其超文本鏈接的數(shù)量來衡量。具體來說，假如網頁A有一個指向網頁B的鏈接，Google就認為“網頁A投了網頁B一票”。Google根據(jù)網頁被鏈接的數(shù)量來評定其重要性。如果說，最后指向A的網頁數(shù)為100，而指向B的網頁數(shù)只有l(wèi)O，則說明網頁A比網頁B更加重要。另外，在實際計算網頁的PageRank值時，除了考慮網頁得票數(shù)(即鏈接)的純數(shù)量之外，Google還考慮到網頁A的所有鏈入網頁(鏈接到某網頁的其它網頁稱為該網頁的鏈入網頁)對它的推薦能力(即由于它們對網頁A的鏈接，使人們認為網頁A的重要程度)希I推薦程度(即它們認為網頁A的重要程度)。一個網頁本身的PageRank值越高，則它

49、對其鏈出網頁(從某個網頁鏈出的網頁稱為該網頁的鏈出網頁)的推薦能力就越大；一個網頁的鏈出網頁越少，那么它對其中一個鏈出網頁的推薦程度就越高。據(jù)此，Google計算出每個網頁的重要性綜合指標，即網頁級別。重要的、高質量的網頁可獲得較高的網頁級別，從而在搜索結果中可獲較高的排位。(當然，如果與查詢項目不匹配，再重要的網頁也毫無意義。Google采用完善的超文12本匹配分析技術，實現(xiàn)為用戶查找既重要又準確的網頁)假設網頁A有網頁T1，T2，Tn的鏈接指向它，我們可以用以下公式來簡要表達Google關于網頁PageRank值的計算：PR(A)=(1一d)十d(PR(T1)C(T1)十十PR(Tn)c(

50、Tn)其中，PR(A)是指網頁A的PageRank值；T1，T2，Tn是網頁A的鏈入網頁：PIc(Ti)是指網頁Ti的PageRank值(i=1。2n)；C(Ti)是指網頁Ti的鏈出網頁的數(shù)量(i=l，2，n)，即指向其它網頁的數(shù)量；d是權重因子，取0d1，通常取085，本文實驗取的值就是085；PR(Tn)c(Tn)為鏈接指向網頁的網頁Tn投與網頁的網頁級別值，亦稱MiniPageRank。可以看出，某一網頁A的PageRank為其它網頁Tn(鏈接指向網頁A的網頁)的PageRank除去Tn網頁外向鏈接的數(shù)量后的總和，其主要取決于三個因素：(1)該網頁的鏈入數(shù)量；(2)該網頁的鏈入網頁本身的

51、PageRank值；(3)該網頁的鏈入網頁本身的鏈出數(shù)量。根據(jù)以上公式，一個網頁的鏈入數(shù)量越多、這些鏈入網頁的PageRank值越高，這些鏈入網頁本身的鏈山數(shù)量越少，則該網頁的PageRank值越高。假定有如下一個較簡單的網絡結構圖(如下圖所示)，則幽中每個頁面的PageRank值計算如下：圍2-；四個頁面的鏈接關系初始時每個網頁都設置其Page Rank為1PR(A)=0115(base)+011275(from C)=012775PR(B)=0115(base)+010425(from A)=011925PR(O=0115(base)+010425(from A)+011275(from

52、B)+011275(from D)=014475PR(D)=0115(base)+010425(from Page A)=011925 經過143次遞歸計算后得到如下值：PR(A)=114131522515PR(B)=015503931379PR(C)=114860614724PR(D)=015503931379在網頁的PageRank值計算過程中，Google首先給每一個網頁賦一個初始PageRank值，然后根據(jù)PageRank算法進行遞歸計算，直至相鄰兩次計算的差值相差小于某一個值(1010)就可以收斂了。PageRank技術根據(jù)網頁之間的鏈接結構對網頁的重要性進行客觀的評價，并將網頁的PageRank值應用于檢索結果的排序，網頁Rank值越高，表明其越重要，排序也越前。這樣，在很大程度上避免和減少了人為因素，做到客觀地將最恰當?shù)臋z索結果展現(xiàn)給州戶。消除了網站等級、論資排輩等觀念，使真正有信息資源價值的任何小網站的網頁，在被檢索時，和13名網站的網頁占有同等的地位，使搜索用戶不會被虛假捧名靠前的網站所阻隔，保證了網民們有價值的信息暢通無阻。225SALSA算法在保留PageRank隨機漫游和HITS中HUB值和SALSA權威值思想的同時，SALSA算法考慮了用戶后退瀏覽網頁的情況，取消了BUB值和權威值的互相加強關系。226HILTS算法(