第12章_搜索引擎v1.1

1、內(nèi)容提要提供“普適性的數(shù)據(jù)分析與服務(wù)”的搜索搜索引擎引擎才能詮釋出物聯(lián)網(wǎng)“更深入的智能化”的內(nèi)涵。本章將介紹搜索引擎的基本概念，體系結(jié)構(gòu)和相關(guān)技術(shù)。第11章介紹了海量信息存儲(chǔ)技術(shù)和數(shù)據(jù)中心物聯(lián)網(wǎng)對(duì)海量數(shù)據(jù)存儲(chǔ)的需求三種網(wǎng)絡(luò)存儲(chǔ)體系結(jié)構(gòu)數(shù)據(jù)中心的基本概念以及典型的數(shù)據(jù)中心如何降低數(shù)據(jù)中心的成本本章重點(diǎn)介紹搜索引擎的基本概念，包括發(fā)展歷程，體系結(jié)構(gòu)（信息采集，索引技術(shù)，搜索服務(wù)），并針對(duì)一個(gè)類Google Web搜索引擎進(jìn)行簡要分析。內(nèi)容回顧12.1 搜索引擎簡介搜索引擎簡介12.2 搜索引擎體系結(jié)構(gòu)12.3 物聯(lián)網(wǎng)搜索引擎搜索引擎有哪些？有哪三大模塊組成？本章內(nèi)容12.1 搜索引擎簡介Web搜索

2、引擎搜索引擎一個(gè)能夠在合理響應(yīng)時(shí)間內(nèi)，根據(jù)用戶的查詢關(guān)鍵詞，返回一個(gè)包含相關(guān)信息的結(jié)果列表（hits list）服務(wù)的綜合體。傳統(tǒng)的Web搜索引擎是基于查詢關(guān)鍵詞的，對(duì)于相同的關(guān)鍵詞，會(huì)得到相同的查詢結(jié)果。常見Web搜索引擎搜索引擎的發(fā)展搜索引擎的起源可追溯到1992年，由NCSA維護(hù)的“Whats NEW!”頁面。第一個(gè)原始搜索引擎W3Catalog（1993.9）第一個(gè)Web機(jī)器人程序“World Wide Web Wanderer”（1993.6 MIT）里程碑： WebCrawler（1994），Lycos（1994）商用Google的建立：斯坦福博士生Larry Page 和 Ser

3、gey Brin 創(chuàng)立了Google網(wǎng)絡(luò)爬蟲模塊網(wǎng)絡(luò)爬蟲模塊：主要功能是通過對(duì)Web頁面的解析，根據(jù)Web頁面之間的連接關(guān)系抓取這些頁面，并儲(chǔ)存頁面信息交給索引模塊處理。索引模塊索引模塊：主要完成對(duì)于抓取的數(shù)據(jù)進(jìn)行預(yù)處理建立關(guān)鍵字索引以便搜索模塊輸出。搜索模塊搜索模塊：對(duì)于用戶的關(guān)鍵詞，根據(jù)數(shù)據(jù)庫的索引知識(shí)給出合理的搜索結(jié)果。Web搜索引擎的結(jié)構(gòu)Web搜索引擎的工作模式12.1 搜索引擎簡介12.2 搜索引擎體系結(jié)構(gòu)搜索引擎體系結(jié)構(gòu)12.3 物聯(lián)網(wǎng)搜索引擎搜索引擎具有怎樣的體系結(jié)構(gòu)和相關(guān)技術(shù)？本章內(nèi)容Web搜索引擎的3個(gè)重要問題響應(yīng)時(shí)間響應(yīng)時(shí)間：一般來說合理的響應(yīng)時(shí)間在秒這個(gè)數(shù)量級(jí)關(guān)鍵詞搜索關(guān)

4、鍵詞搜索：得到合理的匹配結(jié)果搜索結(jié)果排序搜索結(jié)果排序：如何對(duì)海量的結(jié)果數(shù)據(jù)排序搜索引擎的體系結(jié)構(gòu)搜索引擎的體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)體系結(jié)構(gòu)：信息采集搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)Web搜索引擎的信息采集模塊主要功能：Web上收集頁面信息，即Web機(jī)器人（爬蟲）程序基于超文本傳輸協(xié)議（Hypertext Transfer Protocol, 簡稱HTTP）體系結(jié)構(gòu)：信息采集搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)典型的基于超文本傳輸協(xié)議的網(wǎng)絡(luò)應(yīng)答網(wǎng)絡(luò)爬蟲程序的工作模式搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)網(wǎng)絡(luò)爬蟲程序網(wǎng)絡(luò)爬蟲程序根據(jù)HTTP協(xié)議，發(fā)送請(qǐng)求，并通過TCP連接接受

5、服務(wù)器的應(yīng)答。由于Web搜索引擎需要抓取數(shù)以億計(jì)的頁面，所以建立快速分布式的網(wǎng)絡(luò)爬蟲程序才能滿足搜索引擎對(duì)性能和服務(wù)的要求，其物理實(shí)現(xiàn)可能是一組終端。網(wǎng)絡(luò)爬蟲程序的工作模式搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)爬蟲程序物理設(shè)備架構(gòu)圖網(wǎng)絡(luò)爬蟲程序的基礎(chǔ)結(jié)構(gòu)搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)網(wǎng)絡(luò)爬蟲程序的基礎(chǔ)結(jié)構(gòu)搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)首先網(wǎng)絡(luò)爬蟲程序從URL鏈接庫讀取一個(gè)或多個(gè)URL作為初始輸入并進(jìn)行域名解析然后根據(jù)域名解析結(jié)果（IP）訪問Web服務(wù)器，建立TCP連接，發(fā)送請(qǐng)求，接受應(yīng)答，儲(chǔ)存接受數(shù)據(jù)，并分析提取鏈接信息（URL）放入U(xiǎn)RL連接庫里。爬蟲程序遞歸執(zhí)行該過程

6、直到URL鏈接庫為空。信息采集優(yōu)化搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)網(wǎng)絡(luò)連接優(yōu)化策略網(wǎng)絡(luò)連接優(yōu)化策略持久性連接多進(jìn)程并發(fā)設(shè)計(jì)域名系統(tǒng)的緩存策略域名系統(tǒng)的緩存策略：由于網(wǎng)絡(luò)爬蟲程序會(huì)頻繁調(diào)用域名系統(tǒng)，域名系統(tǒng)緩存可提高爬蟲程序性能。LRU（Least Recently Used）算法LFU（Lease Frequently Used）算法FIFO（First-In, First-Out）算法網(wǎng)頁抓取算法搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)深度優(yōu)先算法深度優(yōu)先算法在Web收集頁面信息時(shí)，使用一個(gè)或一組預(yù)定義URL地址開始，然后根據(jù)頁面內(nèi)容中的超鏈接深度抓取頁面，直到搜索結(jié)束（沒有新的UR

7、L）。廣度優(yōu)先算法廣度優(yōu)先算法在Web收集頁面信息時(shí)，使用一個(gè)或一組預(yù)定義URL地址開始，然后根據(jù)頁面內(nèi)容中的超鏈接廣度抓取頁面，抓取下一層的URL直到這一層的URL完全被抓取，直到搜索結(jié)束時(shí)返回。網(wǎng)頁抓取算法（續(xù)）搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)基于內(nèi)容算法基于內(nèi)容算法根據(jù)關(guān)鍵字、主題文檔的相似度和鏈接文本（Linked texts）估計(jì)鏈接值，并確定相應(yīng)搜索策略的算法。鏈接文本是包含對(duì)URL鏈接解釋說明和內(nèi)容摘要的文字信息。基于基于HITS的算法的算法主要思想：在抓取Web頁面時(shí)，采用Authority/Hub抓取策略。Authority表示該頁面被其他頁面所引用的次數(shù)（頁面入度值

8、，in-degree value）。Hub表示其他頁面引用該頁面的次數(shù)（頁面出度值，out-degree value）。網(wǎng)頁抓取算法（續(xù)2）搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)PageRank（Google的傳奇技術(shù)）的傳奇技術(shù)）定義PageRank： 我們假設(shè)有T1Tn個(gè)頁面指向頁面A（即 引用）。參數(shù)d是一個(gè)阻尼因子，其取值區(qū)間屬于(0,1)，我們通常取值為0.85。C(A)定義為指向頁面A的其他頁面的連接數(shù)，頁面A的PageRank或PR(A)值可以通過下面的公式得到：注意：PageRank值是Web頁面的概率分布表示，所以所有Web頁面的PageRank值的和是1。11()( )(

9、 )(1)(.)( )()nnPR TPR TPR AddC TC T體系結(jié)構(gòu)：索引技術(shù)搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)Web爬蟲抓取回來的頁面信息，需要放入索引數(shù)據(jù)庫里。索引建立的好壞對(duì)于搜索引擎有很大的影響，優(yōu)秀的索引能夠顯著的提高搜索引擎系統(tǒng)運(yùn)行的效率及檢索結(jié)果的品質(zhì)。文本分析技術(shù)是建立數(shù)據(jù)索引信息的支撐技術(shù)。索引建立：預(yù)處理搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)當(dāng)Web搜索引擎獲得數(shù)據(jù)信息以后，首先需要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，如將句子切分成有意義的詞匯。由于中文的特殊性在切分句子時(shí)會(huì)產(chǎn)生二義性，如何合理的切分詞匯是一個(gè)技術(shù)難題。中文分詞中文分詞完全不同于英文分詞，英文行文中，單詞間

10、以空格分隔；而中文只有字/句/段有明顯分隔符，唯獨(dú)詞沒有形式上的分隔符存在。索引建立：倒排文件模型搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)倒排文件倒排文件（inverted file），是指一個(gè)詞匯集合W和一個(gè)文檔集合D之間對(duì)應(yīng)關(guān)系的數(shù)據(jù)結(jié)構(gòu)。建立倒排文件索引是建立索引數(shù)據(jù)庫的核心工作。索引建立：倒排文件模型搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)索引模塊架構(gòu)體系結(jié)構(gòu)：搜索服務(wù)搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)搜索服務(wù)是Web搜索引擎工作流程的最后一步，根據(jù)用戶提交的查詢關(guān)鍵字展開搜索，將匹配結(jié)果返回給用戶。搜索服務(wù)的好壞直接影響Web搜索引擎的用戶滿意程度。搜索服務(wù)：結(jié)果顯示搜索引擎體

11、系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)接受用戶的輸入，提交用戶搜索請(qǐng)求。根據(jù)搜索結(jié)果列表合理的展示給用戶。在保護(hù)隱私的前提下，記錄用戶使用行為的詳細(xì)信息，以便提高下次服務(wù)的滿意度。搜索服務(wù)：網(wǎng)頁快照搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)Web上的數(shù)據(jù)每時(shí)每刻都在變化著，所以隨時(shí)存在著檢索到的頁面信息已經(jīng)不存在的可能。Web搜索引擎為了提高服務(wù)質(zhì)量，需要對(duì)搜索到的頁面信息進(jìn)行快照，以便在原來頁面信息失效的情況下，保證用戶能夠通過快照功能查看頁面。類Google Web搜索引擎的實(shí)例分析*類Google搜索引擎的架構(gòu)URL服務(wù)器Web頁面抓取器存儲(chǔ)服務(wù)器URL解釋器排序器Page Rank 搜索器類Go

12、ogle Web搜索引擎的實(shí)例分析*Google數(shù)據(jù)倉庫的結(jié)構(gòu)類Google Web搜索引擎的實(shí)例分析*查詢?cè)u(píng)估流程查詢?cè)u(píng)估流程1.解析查詢（Query）2.把單詞轉(zhuǎn)化成wordID3.從每個(gè)單詞的短桶文檔列表開始查找4.掃描文檔列表直到有一個(gè)文檔匹配了所有的搜索詞語5.計(jì)算這個(gè)文檔對(duì)應(yīng)的查詢的評(píng)分6.如果到達(dá)短桶的文檔列表結(jié)尾，從每個(gè)單詞的全桶(full barrel)文檔列表開始查找，跳到第4 步7.如果沒有到達(dá)任何文檔列表的結(jié)尾，跳到第4步8.根據(jù)評(píng)分對(duì)匹配的文檔排序，然后返回評(píng)分最高的k個(gè)12.1 搜索引擎簡介12.2 搜索引擎體系結(jié)構(gòu)12.3 物聯(lián)網(wǎng)搜索引擎物聯(lián)網(wǎng)搜索引擎物聯(lián)網(wǎng)背景下的搜索引擎應(yīng)具有哪些新特點(diǎn)？本章內(nèi)容12.3 物聯(lián)網(wǎng)搜索引擎物聯(lián)網(wǎng)時(shí)代搜索引擎的新思考物聯(lián)網(wǎng)時(shí)代搜索引擎的新思考從智能物體角度思考搜索引擎與物體之間的關(guān)系，主動(dòng)識(shí)別物體并提取有用信息。從用戶角度上的多模態(tài)信息利用，使查詢結(jié)果更精確，更智能，更定制化。本章小結(jié)內(nèi)容回顧內(nèi)容回顧本章介紹了搜索引擎的發(fā)展歷程，重點(diǎn)討論了搜索引擎的體系結(jié)構(gòu)（信息采集，索引技術(shù)，搜索服務(wù)），并提出了物聯(lián)網(wǎng)背景下搜索引擎的新思考。重點(diǎn)掌握重點(diǎn)掌握掌握Web搜索引擎