索引數據庫與搜索引擎

第八章索引數據庫與搜索引擎索引數據庫與索引機制搜索引擎的誕生與發(fā)展搜索引擎的體系結構搜索引擎實例引言互聯網信息的爆炸性增長表層網絡鏈接相連網站110,460,149深層網絡數據庫、動態(tài)信息約為表層網絡500倍搜索引擎成為最重要的Web信息檢索工具全面、準確、快速注:引自NetCraft1索引數據庫與索引機制搜索引擎的核心是索引數據庫。索引數據庫的核心是倒排索引文件。倒排索引文件即“由文檔特征值指向文檔標識”的文件2搜索引擎的誕生與發(fā)展2.1搜索引擎的誕生起源：FTP文件搜索（以Archie為代表）第一代搜索引擎：分類目錄（以雅虎為代表）第二代搜索引擎：關鍵詞搜索引擎（以Google為代表）2搜索引擎的誕生與發(fā)展2.2搜索引擎的分類根據檢索方式分類：分類目錄、關鍵詞搜索引擎、混合搜索引擎根據信息覆蓋范圍及適用用戶群分類：綜合搜索引擎、專用搜索引擎（垂直搜索引擎）根據搜索范圍分類：獨立搜索引擎、集成搜索引擎（元搜索引擎）元搜索引擎又稱集合式搜索引擎。即將多個搜索引擎集成在一起，并提供一個統(tǒng)一的檢索界面。

一個有趣的結合，實用強大免費有趣的搜索引擎。它將兩大搜索引擎Google與Baidu融二為一。在它們之間平均85％鏈接均不相同。

是一個很有創(chuàng)意的網站，把google和baidu的搜索框結合成了一個可以選擇的搜索框。雖然看著有點頭暈，但是讓我們省了不少力氣.提高了搜索效率。2搜索引擎的誕生與發(fā)展2.3搜索引擎的發(fā)展趨勢個性化；智能化；整合化；垂直化；移動化；開放化2搜索引擎的誕生與發(fā)展2.3搜索引擎的發(fā)展趨勢（補充）檢索結果的后處理；基于內容的多媒體搜索；即時搜索，如/instant；與LBS結合,如/xian

；基于P2P技術的搜索；語音搜索。3搜索引擎的系統(tǒng)結構一個搜索引擎由以下五個部分組成：搜索器索引器索引數據庫檢索器用戶接口

www索引器檢索器用戶接口robot…robot文檔庫索引庫圖：搜索引擎的組成和結構3.1搜索器搜索器（Spider）俗稱蜘蛛、網絡機器人、爬蟲，是一個自動收集網頁的系統(tǒng)程序。搜索器的功能是日夜不停地在互聯網中漫游，搜集信息。不光搜集各種類型的新信息，還要定期更新已經搜集過的舊信息，以避免出現死鏈搜索器首先將文檔格式過濾掉，變成純文本文件信息送回，然后將其放到“網頁數據庫”中。該庫里還記錄了這些網頁的URL，整個網頁的HTML代碼，網頁標題等等信息。

網頁存儲格式version:1.0 //versionnumberurl:/ //URLorigin:/ //originalURLdate:Tue,15Apr200308:13:06GMT //timeofharvestip:2 //IPaddressunzip-length:30233 //Ifincluded,thedatamustbecompressedlength:18133 //datalength

//ablanklineXXXXXXXX //thefollowingsaredatapartXXXXXXXX….XXXXXXXX //dataend

//insertanewline1）網頁選取策略廣度優(yōu)先：是指網絡蜘蛛會先抓取起始網頁中鏈接的所有網頁，然后再選擇其中的一個鏈接網頁，繼續(xù)抓取在此網頁中鏈接的所有網頁。

深度優(yōu)先：

是指網絡蜘蛛會從起始頁開始，一個鏈接一個鏈接跟蹤下去，處理完這條線路之后再轉入下一個起始頁，繼續(xù)跟蹤鏈接。高權重優(yōu)先：是指對搜索到的文檔集合進行評級，利用計算得到的結果從中挑選評級最高的鏈接作為下一個搜索的對象。2）重復爬取策略一致策略：即以一定的頻率對所有網頁進行重復爬取，不區(qū)分變更頻率不同的網頁比率策略：即對于更新頻率較高的網頁，重復爬取的頻率也較高。3）友好性策略網站管理員可以通過設置網絡機器人排除協議設置網站是否允許蜘蛛爬取、可爬取的網頁范圍，進而限制搜索器的爬取行為（在ROBOT.TXT文件中進行設置，該文件必須放在網站根目錄下）。爬取行為的頻率主要有搜索引擎自身設定。4）并行爬取策略并行爬取策略是針對多個并行搜索器而言的。搜索引擎要采用一定的策略協調各個搜索器的行為。搜索器一般將Web空間按照域名、IP地址或國家域名劃分，每個搜索器負責一個子空間的窮盡搜索。

搜索器的實現常用分布式、并行計算技術，以提高信息發(fā)現和更新的速度。3.2索引器索引器的功能是理解搜索器所搜索的純文本信息，從中抽取出索引項（屬性），生成倒排索引文件，進而建立索引數據庫。

倒排索引即由索引項查找相應的文檔。索引項有客觀索引項和內容索引項倒排索引具體步驟具體步驟分析網頁：提取正文信息并進行分詞；統(tǒng)計詞出現的頻率及位置；提取其它相關信息，如被其他網頁鏈接次數等；建立倒排索引：形成由文檔號到索引詞的正向索引；重組正向索引，建立從關鍵詞到文檔號集合的倒排索引；相關度及重要性計算：通過關鍵詞頻率、位置、表面特征及超鏈分析等因素來決定某一個網頁針對某一個關鍵詞的重要性。單詞-文檔矩陣文檔集合例1簡單的倒排索引帶有單詞頻率的倒排索引帶有單詞頻率、文檔頻率和出現位置信息的倒排索引倒排表記錄索引項在文檔中出現的位置，以便檢索器計算索引項之間的相鄰或接近關系（proximity）正向索引例2倒

排

索

引詞

位

置

倒

索

引索引表也可能要記錄索引項在文檔中出現的位置，以便檢索器計算索引項之間的相鄰或接近關系。

根據相關度算法，計算出網頁與關鍵詞的相關系數和權重值3.3索引數據庫索引數據庫是搜索引擎的核心，既是索引器提供的產品，又是搜索器進行工作的基礎。索引數據庫由一個接口模塊和四類文件構成。四類文件是：主索引（MIF）、倒排索引（IXF）、倒排地址表（IAL）、純文本文件。主索引多級倒排索引文件詞編號詞記錄地址1搜索100322核心100893組織100654信息10106詞倒排索引文件的存放位置指向IAL的相對地址指針AP倒排地址表3.4檢索器檢索器的功能是根據用戶的查詢在索引庫中快速檢出文檔，進行文檔與查詢的相關度評價，對將要輸出的結果進行排序。

檢索器的工作包括查詢匹配、結果排序和文檔摘要三個部分。查詢結果的文檔摘要主要有兩種生成機制：靜態(tài)摘要和動態(tài)摘要。一般現階段的搜索引擎運用動態(tài)摘要生成技術。搜索結果排序技術（1）影響結果排序的主要因素（2）排序算法（1）影響結果排序的主要因素內容相關度—基于相關度算法（搜索引擎怎么評價）網站或網頁權威度—基于鏈接分析（即其它網站怎么評價）網站或網頁的實用度—基于用戶訪問模式（即用戶怎么評價）

……（2）排序算法這里我們主要介紹Google的三種鏈接分析算法：PageRank算法HillTop算法Hits算法Pagerank算法PageRank（網頁等級）：一種能夠自動判斷網頁重要性的技術。基本原理：

從許多優(yōu)質的網頁鏈接過來的網頁，必定還是優(yōu)質網頁決定因素：反向鏈接數（數量）反向鏈接源頁面的Pagerank值（質量）反向鏈接源頁面的鏈接數（被選中的幾率指標）

具體算法：將某個頁面的PageRank除以這個頁面的正向鏈接數,由此得到的值分別和正向鏈接所指向的頁面的PageRank相加，即得到了被鏈接的頁面的PageRank。Hits算法算法對返回的匹配頁面計算兩種值,一種是樞紐值(HubScores)，另一種是權威值（AuthorityScores）這兩個值是相互依存、相互影響的。所謂樞紐值，指的是頁面上所有導出鏈接指向頁面的權威值之和。權威值指的是所有導入鏈接所在的頁面的樞紐值之和。HillTop算法：

HillTop也是一項搜索引擎結果排序的專利。HillTop算法的指導思想和PageRank的是一致的，都是通過網頁被鏈接的數量和質量來確定搜索結果的排序權重。但HillTop認為只計算來自具有相同主題的相關文檔鏈接對于搜索者的價值會更大：即主題相關網頁之間的鏈接對于權重計算的貢獻比主題不相關的鏈接價值要更高。用戶行為模式如何影響網站排名？例如：說一個用戶直接在Google主頁搜索某一個關鍵詞，用戶點擊了第一個結果，然后五秒鐘之內點擊了瀏覽器的返回鍵，再次來到Google主頁，然后又點擊了第三個結果。再過30分鐘以后，這個用戶才再次回到Google主頁。那么Google就可以得出結論，第三個網站比第一個網站更能給用戶提供有用的信息。如果這種模式大量反復，那么Google就有可能把這兩個網站的排名互換。3.5用戶接口

用戶接口的作用是輸入用戶查詢、顯示查詢結果、提供用戶相關性反饋機制。用戶接口的設計和實現使用人機交互的理論和方法，以充分適應人類的思維習慣。分為簡單接口和復雜接口。

當前，這方面研究集中在對用戶信息需求的挖掘與發(fā)現、改進用戶交互方式（信息可視化）等方面?？偨Y：搜索引擎工作流程搜集累計式搜集，增量式搜集；索引重復網頁消除；關鍵詞提??；鏈接分析；倒排索引檢索查詢匹配；結果排序；文檔摘要搜集索引檢索從具體運行方式上說，系統(tǒng)根據站點/網頁的URL信息和網頁之間的鏈接關系，利用網絡蜘蛛在互聯網上收集數據；收集的數據分別通過鏈接信息分析器和文本信息分析器處理，保存在鏈接數據庫和文本索引數據庫中，同時，網頁質量評估器依據網頁的鏈接關系和頁面結構特征對頁面質量進行評估，并將評估的結果保存在索引數據庫中；查詢服務器負責與用戶的交互，它根據用戶的檢索需求，從索引數據庫中讀取對應的索引，并綜合考慮查詢相關性與頁面質量評估結果之間的關系，給出查詢結果列表反饋給用戶。4搜索引擎實例GOOGLE百度案例：google網址：Google是由美國斯坦福大學的兩位博士生拉里·佩吉和謝爾蓋·布林于1998年創(chuàng)建的。目前是全球最大、最專業(yè)的搜索引擎1998年,當時在加州門洛帕克(MenloPark),拉里·佩奇與謝爾蓋·布林租用了這間房子的車庫作為建立Google的據點,每個月Google要交$1,700(￡961)租金給房東SusanWojcicki.2000年11月11日:Google的聯合創(chuàng)始人,時任CEO的拉里·佩奇(LarryPage,左)和主席謝爾蓋·布林(SergeyBrin)在位于山景城的Google總部內,靠著懶人椅(beanbags

)2006年5月10日:一名Google雇員踩著一架腳踏滑板車(所有員工均可使用),穿越位于加州山景城的公司園區(qū).①檢索范圍②檢索方式簡單檢索高級檢索簡單檢索邏輯“與”：兩詞間加空格邏輯“或”：用“OR”表示邏輯“非”：兩詞間加“-”（“-”號前加空格）強制檢索：雙引號指定網域：site:指定文件類型：filetype:文件類型邏輯與功能邏輯非功能邏輯或功能強制檢索指定網域指定文件類型③特色直達與檢索詞最相關的網頁網址：

百度（Baidu）是目前全球最優(yōu)秀的中文信息檢索與傳遞技術供應商。中國所有提供搜索引擎的門戶網站中，超過80%以上都由百度提供搜索引擎技術支持，現有客戶包括新浪、搜狐（Chianren）、央視國際、騰訊等。案例：百度①檢索范圍②檢索方式簡單檢索高級檢索簡單檢索邏輯“與”：兩詞間加空格邏輯“或”：兩詞間加“|”（前后加空格）邏輯“非”：兩詞間加“-”（“-”號前加空格）強制檢索：雙引號指定網域：site:指定文件類型：filetype: