1、第八章第八章 索引數據庫與搜索引擎索引數據庫與搜索引擎索引數據庫與索引機制索引數據庫與索引機制搜索引擎的誕生與發展搜索引擎的誕生與發展搜索引擎的體系結構搜索引擎的體系結構搜索引擎實例搜索引擎實例n 互聯網信息的爆炸性增長p表層網絡表層網絡 鏈接相連 網站110,460,149p深層網絡深層網絡 數據庫、動態信息 約為表層網絡500倍n 搜索引擎成為最重要的Web信息檢索工具p全面、準確、快速1 索引數據庫與索引機制索引數據庫與索引機制 搜索引擎的核心是索引數據庫。索引數據搜索引擎的核心是索引數據庫。索引數據庫的核心是倒排索引文件。倒排索引文件庫的核心是倒排索引文件。倒排索引文件即即“由文檔特征

2、值指向文檔標識由文檔特征值指向文檔標識”的文件的文件2 搜索引擎的誕生與發展搜索引擎的誕生與發展2.1 搜索引擎的誕生搜索引擎的誕生 起源：起源：FTP文件搜索（以文件搜索（以Archie為代表）為代表） 第一代搜索引擎：第一代搜索引擎：分類目錄（以雅虎為代表）分類目錄（以雅虎為代表） 第二代搜索引擎：第二代搜索引擎：關鍵詞搜索引擎（以關鍵詞搜索引擎（以Google為為代表）代表）2 搜索引擎的誕生與發展搜索引擎的誕生與發展2.2 搜索引擎的分類搜索引擎的分類 根據檢索方式分類：根據檢索方式分類： 分類目錄、關鍵詞搜索引擎、混合搜索引擎分類目錄、關鍵詞搜索引擎、混合搜索引擎 根據信息覆蓋范圍及

3、適用用戶群分類：根據信息覆蓋范圍及適用用戶群分類： 綜合搜索引擎、專用搜索引擎（垂直搜索引擎）綜合搜索引擎、專用搜索引擎（垂直搜索引擎） 根據搜索范圍分類：根據搜索范圍分類： 獨立搜索引擎、集成搜索引擎（元搜索引擎）獨立搜索引擎、集成搜索引擎（元搜索引擎）元搜索引擎元搜索引擎又稱集合式搜索引擎。即將多個搜索引擎又稱集合式搜索引擎。即將多個搜索引擎集成在一起，并提供一個統一的檢索界面。集成在一起，并提供一個統一的檢索界面。 一個有趣的結合，實用強大一個有趣的結合，實用強大免費有趣的搜索引擎。它將兩大搜索引擎免費有趣的搜索引擎。它將兩大搜索引擎Google與與Baidu融二為一。在它們之間平均融二

4、為一。在它們之間平均85鏈接均不相同。鏈接均不相同。 是一個很有創意的網站，把是一個很有創意的網站，把google和和baidu的搜索框結合成了一個可以選擇的搜索框。雖然的搜索框結合成了一個可以選擇的搜索框。雖然看著有點頭暈，但是讓我們省了不少力氣看著有點頭暈，但是讓我們省了不少力氣.提高了搜索效率。提高了搜索效率。2 搜索引擎的誕生與發展搜索引擎的誕生與發展 2.3 搜索引擎的發展趨勢搜索引擎的發展趨勢 個性化；個性化； 智能化；智能化； 整合化；整合化； 垂直化；垂直化； 移動化；移動化； 開放化開放化2 搜索引擎的誕生與發展搜索引擎的誕生與發展 2.3 搜索引擎的發展趨勢（補充）搜索引擎

5、的發展趨勢（補充） 檢索結果的后處理檢索結果的后處理； 基于內容的多媒體搜索；基于內容的多媒體搜索； 即時搜索，如即時搜索，如 與與LBS結合結合, 如如http:/ ； 基于基于P2P技術的搜索技術的搜索； 語音搜索。語音搜索。3 搜索引擎的系統結構搜索引擎的系統結構 一個搜索引擎由以下五個部分組成：一個搜索引擎由以下五個部分組成： 搜索器搜索器 索引器索引器 索引數據庫索引數據庫 檢索器檢索器 用戶接口用戶接口 3.1 搜索器搜索器 搜索器（搜索器（Spider）俗稱蜘蛛、網絡機器人、爬蟲）俗稱蜘蛛、網絡機器人、爬蟲，是一個自動收集網頁的系統程序。，是一個自動收集網頁的系統程序。 搜索器的

6、功能是日夜不停地在互聯網中漫游，搜搜索器的功能是日夜不停地在互聯網中漫游，搜集信息。集信息。不光不光搜集各種類型的新信息，還要定期搜集各種類型的新信息，還要定期更新已經搜集過的舊信息，以避免出現死鏈更新已經搜集過的舊信息，以避免出現死鏈 搜索器首先將文檔格式過濾掉，變成純文本文件搜索器首先將文檔格式過濾掉，變成純文本文件信息送回，然后將其信息送回，然后將其放到放到“網頁數據庫網頁數據庫”中。中。該庫里還記錄了這些網頁的該庫里還記錄了這些網頁的URL，整個網頁的，整個網頁的HTML代碼，網頁標題等等信息。代碼，網頁標題等等信息。 網頁存儲格式網頁存儲格式version: 1.0/ version

7、 numberurl: http:/ URLorigin: http:/ original URLdate: Tue, 15 Apr 2003 08:13:06 GMT / time of harvestip: 2 / IP addressunzip-length: 30233 / If included, the data must be compressedlength: 18133/ data length/ a blank lineXXXXXXXX/ the followings are data partXXXXXXXX.XXXXXXXX/ data end

8、/ insert a new line1）網頁選取策略）網頁選取策略 廣度優先：廣度優先：是指網絡蜘蛛會先抓取起始網頁中鏈是指網絡蜘蛛會先抓取起始網頁中鏈接的所有網頁，然后再選擇其中的一個鏈接網頁，接的所有網頁，然后再選擇其中的一個鏈接網頁，繼續抓取在此網頁中鏈接的所有網頁。繼續抓取在此網頁中鏈接的所有網頁。 深度優先：深度優先： 是指網絡蜘蛛會從起始頁開始，一個是指網絡蜘蛛會從起始頁開始，一個鏈接一個鏈接跟蹤下去，處理完這條線路之后再鏈接一個鏈接跟蹤下去，處理完這條線路之后再轉入下一個起始頁，繼續跟蹤鏈接。轉入下一個起始頁，繼續跟蹤鏈接。 高權重優先：高權重優先：是指對搜索到的文檔集合進行評

9、級，是指對搜索到的文檔集合進行評級，利用計算得到的結果從中挑選評級最高的鏈接作利用計算得到的結果從中挑選評級最高的鏈接作為下一個搜索的對象。為下一個搜索的對象。2）重復爬取策略）重復爬取策略 一致策略：一致策略：即以一定的頻率對所有網頁進即以一定的頻率對所有網頁進行重復爬取，不區分變更頻率不同的網頁行重復爬取，不區分變更頻率不同的網頁 比率策略：比率策略：即對于更新頻率較高的網頁，即對于更新頻率較高的網頁，重復爬取的頻率也較高。重復爬取的頻率也較高。3）友好性策略）友好性策略 網站管理員可以通過設置網絡機器人排除網站管理員可以通過設置網絡機器人排除協議設置網站是否允許蜘蛛爬取、可爬取協議設置網

10、站是否允許蜘蛛爬取、可爬取的網頁范圍，進而限制搜索器的爬取行為的網頁范圍，進而限制搜索器的爬取行為（在（在ROBOT.TXT文件中進行設置，該文件文件中進行設置，該文件必須放在網站根目錄下）。爬取行為的頻必須放在網站根目錄下）。爬取行為的頻率主要有搜索引擎自身設定。率主要有搜索引擎自身設定。 4）并行爬取策略）并行爬取策略 并行爬取策略是針對多個并行搜索器而言并行爬取策略是針對多個并行搜索器而言的。搜索引擎要采用一定的策略協調各個的。搜索引擎要采用一定的策略協調各個搜索器的行為。搜索器的行為。 搜索器一般將搜索器一般將Web空間按照域名、空間按照域名、IP地址地址或國家域名劃分，每個搜索器負責

11、一個子或國家域名劃分，每個搜索器負責一個子空間的窮盡搜索。空間的窮盡搜索。 搜索器的實現常用分布式、并行計算技術搜索器的實現常用分布式、并行計算技術，以提高信息發現和更新的速度。，以提高信息發現和更新的速度。3.2 索引器索引器 索引器的功能是索引器的功能是理解理解搜索器所搜索的純文搜索器所搜索的純文本信息，從中抽取出索引項（屬性），生本信息，從中抽取出索引項（屬性），生成成倒排索引倒排索引文件，進而文件，進而建立索引數據庫建立索引數據庫。 倒排倒排索引即由索引項查找相應的文檔。索引即由索引項查找相應的文檔。 索引項有索引項有客觀索引項和內容索引項客觀索引項和內容索引項倒排索引倒排索引具體步驟

12、具體步驟具體步驟具體步驟分析網頁：分析網頁：提取正文信息并進行分詞；統提取正文信息并進行分詞；統計詞出現的頻率及位置；提取其它相關信計詞出現的頻率及位置；提取其它相關信息，如被其他網頁鏈接次數等；息，如被其他網頁鏈接次數等；建立倒排索引：建立倒排索引：形成由文檔號到索引詞的形成由文檔號到索引詞的正向索引；重組正向索引，建立從關鍵詞正向索引；重組正向索引，建立從關鍵詞到文檔號集合的倒排索引；到文檔號集合的倒排索引；相關度及重要性計算：相關度及重要性計算：通過關鍵詞頻率、通過關鍵詞頻率、位置、表面特征及超鏈分析等因素來決定位置、表面特征及超鏈分析等因素來決定某一個網頁針對某一個關鍵詞的重要性。某一

13、個網頁針對某一個關鍵詞的重要性。單詞單詞-文檔矩陣文檔矩陣文檔集合文檔集合例例1簡單的倒排索引簡單的倒排索引帶有單詞頻率的倒排索引帶有單詞頻率的倒排索引 帶有單詞頻率、文檔頻率和出現位置信息的倒排索引帶有單詞頻率、文檔頻率和出現位置信息的倒排索引 倒排表記錄索引項在文檔中倒排表記錄索引項在文檔中出現的位置，以便檢索器計出現的位置，以便檢索器計算索引項之間的相鄰或接近算索引項之間的相鄰或接近關系（關系（proximity）正向索引正向索引例例2倒倒排排索索引引詞詞位位置置倒倒索索引引索引表也可能要記錄索引項在索引表也可能要記錄索引項在文檔中出現的位置，以便檢索文檔中出現的位置，以便檢索器計算索引

14、項之間的相鄰或接器計算索引項之間的相鄰或接近關系。近關系。 根據相關度算法，根據相關度算法，計算出網頁與關鍵計算出網頁與關鍵詞的相關系數和權詞的相關系數和權重值重值3.3 索引數據庫索引數據庫 索引數據庫是搜索引擎的核心，既是索引索引數據庫是搜索引擎的核心，既是索引器提供的產品，又是搜索器進行工作的基器提供的產品，又是搜索器進行工作的基礎。礎。 索引數據庫由一個接口模塊和四類文件構索引數據庫由一個接口模塊和四類文件構成。四類文件是：主索引（成。四類文件是：主索引（MIF）、倒排索）、倒排索引（引（IXF）、倒排地址表（）、倒排地址表（IAL）、純文本）、純文本文件。文件。主索引主索引多級倒排索

15、引文件多級倒排索引文件詞編號詞編號詞詞記錄地址記錄地址1搜索搜索100322核心核心100893組織組織100654信息信息10106詞詞倒排索引倒排索引文件的存文件的存放位置放位置指向指向IAL的相對地址指針的相對地址指針AP倒排地址表倒排地址表3.4 檢索器檢索器 檢索器的功能是根據用戶的查詢在索引庫檢索器的功能是根據用戶的查詢在索引庫中快速檢出文檔，進行文檔與查詢的相關中快速檢出文檔，進行文檔與查詢的相關度評價，對將要輸出的結果進行排序。度評價，對將要輸出的結果進行排序。 檢索器的工作包括檢索器的工作包括查詢匹配、結果排序和查詢匹配、結果排序和文檔摘要三個部分文檔摘要三個部分。 查詢結果

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

17、式基于用戶訪問模式（即用戶怎么評價）（即用戶怎么評價） （2）排序算法）排序算法 這里我們主要介紹這里我們主要介紹Google的三種鏈接分析的三種鏈接分析算法：算法： PageRank算法算法 HillTop算法算法 Hits算法算法 Pagerank算法算法PageRank（網頁等級）：（網頁等級）：一種能夠自動判斷一種能夠自動判斷網頁重要性的技術。網頁重要性的技術。基本原理：基本原理： 從許多優質的網頁鏈接過來的網頁，從許多優質的網頁鏈接過來的網頁，必定還是優質網頁必定還是優質網頁決定因素：決定因素：反向鏈接數（反向鏈接數（數量數量） 反向鏈接源頁面的反向鏈接源頁面的Pagerank值值

18、（質量質量）反向鏈接源頁面的鏈接數反向鏈接源頁面的鏈接數 （被選中的幾率指標被選中的幾率指標） 具體算法：具體算法：將某個頁面的將某個頁面的 PageRank 除以這個除以這個頁面的正向鏈接數頁面的正向鏈接數,由此得到的值分別和正向鏈由此得到的值分別和正向鏈接所指向的頁面的接所指向的頁面的 PageRank 相加，即得到了相加，即得到了被鏈接的頁面的被鏈接的頁面的 PageRank。 Hits算法算法 算法對返回的匹配頁面計算兩種值算法對返回的匹配頁面計算兩種值,一種是一種是樞紐值樞紐值(Hub Scores)，另一種是，另一種是權威值（權威值（Authority Scores）這兩個值是相互

19、依存、相互影響的。所這兩個值是相互依存、相互影響的。所謂樞紐值，指的是頁面上所有導出鏈接指向頁面謂樞紐值，指的是頁面上所有導出鏈接指向頁面的權威值之和。權威值指的是所有導入鏈接所在的權威值之和。權威值指的是所有導入鏈接所在的頁面的樞紐值之和。的頁面的樞紐值之和。 HillTop算法算法 ： HillTop也是一項搜索引擎結果排序的專利。也是一項搜索引擎結果排序的專利。 HillTop算法的指導思想和算法的指導思想和PageRank的是的是一致的，都是通過網頁被鏈接的數量和質一致的，都是通過網頁被鏈接的數量和質量來確定搜索結果的排序權重。但量來確定搜索結果的排序權重。但HillTop認為認為只計

20、算只計算 來自具有相同主題的相關文檔來自具有相同主題的相關文檔鏈接對于搜索者的價值會更大：即主題相鏈接對于搜索者的價值會更大：即主題相關網頁之間的鏈接對于權重計算的貢獻比關網頁之間的鏈接對于權重計算的貢獻比主題不相關的鏈接價值要更高。主題不相關的鏈接價值要更高。用戶行為模式如何影響網站排名？用戶行為模式如何影響網站排名？ 例如：例如：說一個用戶直接在說一個用戶直接在Google主頁搜索主頁搜索某一個關鍵詞，用戶點擊了第一個結果，某一個關鍵詞，用戶點擊了第一個結果，然后五秒鐘之內點擊了瀏覽器的返回鍵，然后五秒鐘之內點擊了瀏覽器的返回鍵，再次來到再次來到Google主頁，然后又點擊了第三主頁，然后

21、又點擊了第三個結果。再過個結果。再過30分鐘以后，這個用戶才再分鐘以后，這個用戶才再次回到次回到Google主頁。那么主頁。那么Google就可以得就可以得出結論，第三個網站比第一個網站更能給出結論，第三個網站比第一個網站更能給用戶提供有用的信息。如果這種模式大量用戶提供有用的信息。如果這種模式大量反復，那么反復，那么Google就有可能把這兩個網站就有可能把這兩個網站的排名互換。的排名互換。3.5 用戶接口用戶接口 用戶接口的作用是用戶接口的作用是輸入用戶查詢、顯示查輸入用戶查詢、顯示查詢結果、提供用戶相關性反饋機制詢結果、提供用戶相關性反饋機制。 用戶接口的設計和實現使用人機交互的理用戶接

22、口的設計和實現使用人機交互的理論和方法，以充分適應人類的思維習慣。論和方法，以充分適應人類的思維習慣。分為簡單接口和復雜接口。分為簡單接口和復雜接口。 當前，這方面研究集中在對用戶信息需求當前，這方面研究集中在對用戶信息需求的挖掘與發現、改進用戶交互方式（信息的挖掘與發現、改進用戶交互方式（信息可視化）等方面。可視化）等方面。總結：總結：搜索引擎工作流程搜索引擎工作流程 搜集搜集 累計式搜集，增量式搜集；累計式搜集，增量式搜集； 索引索引 重復網頁消除；關鍵詞提取；鏈接分析；重復網頁消除；關鍵詞提取；鏈接分析；倒排索引倒排索引 檢索檢索 查詢匹配；結果排序；文檔摘要查詢匹配；結果排序；文檔摘要

23、搜集搜集索引索引檢索檢索 從具體運行方式上說，系統根據站點從具體運行方式上說，系統根據站點/網頁的網頁的URL信息和網頁之間的鏈接關系，利用網絡蜘蛛在互信息和網頁之間的鏈接關系，利用網絡蜘蛛在互聯網上收集數據；收集的數據分別通過鏈接信息聯網上收集數據；收集的數據分別通過鏈接信息分析器和文本信息分析器處理，保存在鏈接數據分析器和文本信息分析器處理，保存在鏈接數據庫和文本索引數據庫中，同時，網頁質量評估器庫和文本索引數據庫中，同時，網頁質量評估器依據網頁的鏈接關系和頁面結構特征對頁面質量依據網頁的鏈接關系和頁面結構特征對頁面質量進行評估，并將評估的結果保存在索引數據庫中；進行評估，并將評估的結果保

24、存在索引數據庫中；查詢服務器負責與用戶的交互，它根據用戶的檢查詢服務器負責與用戶的交互，它根據用戶的檢索需求，從索引數據庫中讀取對應的索引，并綜索需求，從索引數據庫中讀取對應的索引，并綜合考慮查詢相關性與頁面質量評估結果之間的關合考慮查詢相關性與頁面質量評估結果之間的關系，給出查詢結果列表反饋給用戶。系，給出查詢結果列表反饋給用戶。4 搜索引擎實例搜索引擎實例 GOOGLE 百度百度案例：案例：google 網址：網址：http:/ Google是由美國斯坦福大學的兩位博士是由美國斯坦福大學的兩位博士生拉里生拉里佩吉和謝爾蓋佩吉和謝爾蓋布林于布林于1998年創年創建的。建的。 目前是全球最大、

25、最專業的搜索引擎目前是全球最大、最專業的搜索引擎 1998 年年, 當時在加州門洛帕克當時在加州門洛帕克 (Menlo Park), 拉里拉里佩奇佩奇 與與 謝謝爾蓋爾蓋布林布林 租用了這間房子的車庫作為建立租用了這間房子的車庫作為建立 Google 的據點的據點, 每個每個月月 Google 要交要交 $1,700 (961) 租金給房東租金給房東 Susan Wojcicki. 2000 2000 年年 11 11 月月 11 11 日日: Google : Google 的聯合創始人的聯合創始人, , 時任時任 CEO CEO 的的 拉里拉里佩奇佩奇 (Larry Page, (Larr

26、y Page, 左左) ) 和主席謝爾蓋和主席謝爾蓋布林布林 (Sergey Brin) (Sergey Brin) 在位于山景城的在位于山景城的 Google Google 總部內總部內, , 靠著懶人椅靠著懶人椅 (bean bags(bean bags )2006 2006 年年 5 5 月月 10 10 日日: : 一名一名 Google Google 雇員踩著一架腳踏滑板車雇員踩著一架腳踏滑板車 ( (所有員所有員工均可使用工均可使用), ), 穿越位于加州山景城的公司園區穿越位于加州山景城的公司園區. .檢索范圍檢索范圍檢索方式檢索方式簡單檢索簡單檢索高級檢索高級檢索簡單檢索簡單檢

27、索 邏輯邏輯“與與”：兩詞間加：兩詞間加空格空格 邏輯邏輯“或或”：用：用“OR”表示表示 邏輯邏輯“非非”：兩詞間加：兩詞間加“-”（“-”號前加號前加空格）空格） 強制檢索強制檢索：雙引號雙引號 指定網域指定網域：site: 指定文件類型指定文件類型：filetype:文件類型文件類型邏輯與功能邏輯與功能邏輯非功能邏輯非功能邏輯或功能邏輯或功能強制檢索強制檢索指定網域指定網域指定文件類型指定文件類型特色特色直達與檢索詞直達與檢索詞最相關的網頁最相關的網頁 網址：網址：http:/ 百度（百度（Baidu）是目前全球最優秀的中文信）是目前全球最優秀的中文信息檢索與傳遞技術供應商。中國所有提供

28、息檢索與傳遞技術供應商。中國所有提供搜索引擎的門戶網站中，超過搜索引擎的門戶網站中，超過80%以上都以上都由百度提供搜索引擎技術支持，現有客戶由百度提供搜索引擎技術支持，現有客戶包括新浪、搜狐（包括新浪、搜狐（Chianren）、央視國際）、央視國際、騰訊等。、騰訊等。案例：百度案例：百度檢索范圍檢索范圍檢索方式檢索方式 簡單檢索簡單檢索 高級檢索高級檢索簡單檢索簡單檢索 邏輯邏輯“與與”：兩詞間加空格：兩詞間加空格 邏輯邏輯“或或”：兩詞間加：兩詞間加“|”（前后加空格（前后加空格） 邏輯邏輯“非非”：兩詞間加：兩詞間加“-”（“-”號前加號前加空格）空格） 強制檢索：雙引號強制檢索：雙引號 指定網域：指定網域：site: 指定文件類型：指定文件類型：filetype:文件類型文件類型特色特色網頁快照網頁快照 如果原鏈接已經死掉或者因為網絡的原因如果原鏈接已經死掉或者因為網絡的原因暫時鏈接不通，那么可以通過網頁快照看暫時鏈接不通，那么可以通過網頁快照看到該頁面信息。當然，快照內容不是該頁到該頁面信息。當然，快照內容不是該頁最新頁面；最新頁面； 如果原地址打開很慢