索引數(shù)據(jù)庫與搜索引擎

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

一個有趣的結(jié)合，實(shí)用強(qiáng)大免費(fèi)有趣的搜索引擎。它將兩大搜索引擎Google與Baidu融二為一。在它們之間平均85％鏈接均不相同。

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

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

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

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

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

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

深度優(yōu)先：

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

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

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

排

索

引詞

位

置

倒

索

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

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

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

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

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

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

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

用戶接口的作用是輸入用戶查詢、顯示查詢結(jié)果、提供用戶相關(guān)性反饋機(jī)制。用戶接口的設(shè)計和實(shí)現(xiàn)使用人機(jī)交互的理論和方法，以充分適應(yīng)人類的思維習(xí)慣。分為簡單接口和復(fù)雜接口。

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

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

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