物聯(lián)網(wǎng)導(dǎo)論第12章搜索引擎v

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)行簡(jiǎn)要分析。內(nèi)容回顧12.1 搜索引擎簡(jiǎn)介12.2 搜索引擎體系結(jié)構(gòu)12.3 物聯(lián)網(wǎng)搜索引擎搜索引擎有哪些？有哪三大模塊組成？本章內(nèi)容12.1 搜索引擎簡(jiǎn)介Web搜索引擎搜索引擎一個(gè)能夠

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

3、r”（1993.6 MIT）里程碑： WebCrawler（1994），Lycos（1994）商用Google的建立：斯坦福博士生Larry Page 和 Sergey Brin 創(chuàng)立了Google網(wǎng)絡(luò)爬蟲(chóng)模塊：主要功能是通過(guò)對(duì)網(wǎng)絡(luò)爬蟲(chóng)模塊：主要功能是通過(guò)對(duì)Web頁(yè)面的解析，根據(jù)頁(yè)面的解析，根據(jù)Web頁(yè)面之間的連接關(guān)系抓取這些頁(yè)面，并儲(chǔ)存頁(yè)面信息交給索引頁(yè)面之間的連接關(guān)系抓取這些頁(yè)面，并儲(chǔ)存頁(yè)面信息交給索引模塊處理。模塊處理。索引模塊：主要完成對(duì)于抓取的數(shù)據(jù)進(jìn)行預(yù)處理建立關(guān)鍵字索索引模塊：主要完成對(duì)于抓取的數(shù)據(jù)進(jìn)行預(yù)處理建立關(guān)鍵字索引以便搜索模塊輸出。引以便搜索模塊輸出。搜索模塊：對(duì)于用戶的關(guān)

4、鍵詞，根據(jù)數(shù)據(jù)庫(kù)的索引知識(shí)給出合搜索模塊：對(duì)于用戶的關(guān)鍵詞，根據(jù)數(shù)據(jù)庫(kù)的索引知識(shí)給出合理的搜索結(jié)果。理的搜索結(jié)果。Web搜索引擎的結(jié)構(gòu)Web搜索引擎的工作模式12.1 搜索引擎簡(jiǎn)介12.2 搜索引擎體系結(jié)構(gòu)12.3 物聯(lián)網(wǎng)搜索引擎搜索引擎具有怎樣的體系結(jié)構(gòu)和相關(guān)技術(shù)？本章內(nèi)容Web搜索引擎的3個(gè)重要問(wèn)題響應(yīng)時(shí)間：一般來(lái)說(shuō)合理的響應(yīng)時(shí)間在秒這個(gè)數(shù)量級(jí)響應(yīng)時(shí)間：一般來(lái)說(shuō)合理的響應(yīng)時(shí)間在秒這個(gè)數(shù)量級(jí)關(guān)鍵詞搜索：得到合理的匹配結(jié)果關(guān)鍵詞搜索：得到合理的匹配結(jié)果搜索結(jié)果排序：如何對(duì)海量的結(jié)果數(shù)據(jù)排序搜索結(jié)果排序：如何對(duì)海量的結(jié)果數(shù)據(jù)排序搜索引擎的體系結(jié)構(gòu)搜索引擎的體系結(jié)構(gòu)信息采集信息采集索引技術(shù)索引技術(shù)

5、搜索服務(wù)搜索服務(wù)體系結(jié)構(gòu)：信息采集搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)Web搜索引擎的信息采集模塊主要功能：Web上收集頁(yè)面信息，即Web機(jī)器人（爬蟲(chóng)）程序基于超文本傳輸協(xié)議（Hypertext Transfer Protocol, 簡(jiǎn)稱HTTP）體系結(jié)構(gòu)：信息采集搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)典型的基于超文本傳輸協(xié)議的網(wǎng)絡(luò)應(yīng)答網(wǎng)絡(luò)爬蟲(chóng)程序的工作模式搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)網(wǎng)絡(luò)爬蟲(chóng)程序根據(jù)網(wǎng)絡(luò)爬蟲(chóng)程序根據(jù)HTTP協(xié)議，發(fā)送請(qǐng)協(xié)議，發(fā)送請(qǐng)求，并通過(guò)求，并通過(guò)TCP連接接受服務(wù)器的應(yīng)答。連接接受服務(wù)器的應(yīng)答。由于由于Web搜索引擎需要抓取數(shù)以億計(jì)的搜索引擎需要抓取數(shù)以

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

7、信息（URL）放入U(xiǎn)RL連接庫(kù)里。爬蟲(chóng)程序遞歸執(zhí)行該過(guò)程直到URL鏈接庫(kù)為空。信息采集優(yōu)化搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)網(wǎng)絡(luò)連接優(yōu)化策略網(wǎng)絡(luò)連接優(yōu)化策略持久性連接持久性連接多進(jìn)程并發(fā)設(shè)計(jì)多進(jìn)程并發(fā)設(shè)計(jì)域名系統(tǒng)的緩存策略：由于網(wǎng)絡(luò)爬蟲(chóng)程序會(huì)域名系統(tǒng)的緩存策略：由于網(wǎng)絡(luò)爬蟲(chóng)程序會(huì)頻繁調(diào)用域名系統(tǒng)，域名系統(tǒng)緩存可提高爬頻繁調(diào)用域名系統(tǒng)，域名系統(tǒng)緩存可提高爬蟲(chóng)程序性能。蟲(chóng)程序性能。LRU（Least Recently Used）算法）算法LFU（Lease Frequently Used）算法）算法FIFO（First-In, First-Out）算法）算法網(wǎng)頁(yè)抓取算法搜索引擎體系結(jié)構(gòu)信息采

8、集索引技術(shù)搜索服務(wù)深度優(yōu)先算法深度優(yōu)先算法在在Web收集頁(yè)面信息時(shí)，使用一個(gè)或一組預(yù)收集頁(yè)面信息時(shí)，使用一個(gè)或一組預(yù)定義定義URL地址開(kāi)始，然后根據(jù)頁(yè)面內(nèi)容中的超地址開(kāi)始，然后根據(jù)頁(yè)面內(nèi)容中的超鏈接深度抓取頁(yè)面，直到搜索結(jié)束（沒(méi)有新鏈接深度抓取頁(yè)面，直到搜索結(jié)束（沒(méi)有新的的URL）。）。廣度優(yōu)先算法廣度優(yōu)先算法在在Web收集頁(yè)面信息時(shí)，使用一個(gè)或一組預(yù)收集頁(yè)面信息時(shí)，使用一個(gè)或一組預(yù)定義定義URL地址開(kāi)始，然后根據(jù)頁(yè)面內(nèi)容中的超地址開(kāi)始，然后根據(jù)頁(yè)面內(nèi)容中的超鏈接廣度抓取頁(yè)面，抓取下一層的鏈接廣度抓取頁(yè)面，抓取下一層的URL直到這直到這一層的一層的URL完全被抓取，直到搜索結(jié)束時(shí)返回。完全被抓

9、取，直到搜索結(jié)束時(shí)返回。網(wǎng)頁(yè)抓取算法（續(xù)）搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)基于內(nèi)容算法基于內(nèi)容算法根據(jù)關(guān)鍵字、主題文檔的相似度和鏈接文本根據(jù)關(guān)鍵字、主題文檔的相似度和鏈接文本（Linked texts）估計(jì)鏈接值，并確定相應(yīng)搜）估計(jì)鏈接值，并確定相應(yīng)搜索策略的算法。索策略的算法。鏈接文本是包含對(duì)鏈接文本是包含對(duì)URL鏈接解釋說(shuō)明和內(nèi)容摘鏈接解釋說(shuō)明和內(nèi)容摘要的文字信息。要的文字信息?；诨贖ITS的算法的算法主要思想：在抓取主要思想：在抓取Web頁(yè)面時(shí)，采用頁(yè)面時(shí)，采用Authority/Hub抓取策略。抓取策略。Authority表示該頁(yè)表示該頁(yè)面被其他頁(yè)面所引用的次數(shù)（頁(yè)面入度值

10、，面被其他頁(yè)面所引用的次數(shù)（頁(yè)面入度值，in-degree value）。）。Hub表示其他頁(yè)面引用該表示其他頁(yè)面引用該頁(yè)面的次數(shù)（頁(yè)面出度值，頁(yè)面的次數(shù)（頁(yè)面出度值，out-degree value）。）。網(wǎng)頁(yè)抓取算法（續(xù)2）搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)PageRank（Google的傳奇技術(shù)）的傳奇技術(shù)）定義定義PageRank： 我們假設(shè)有我們假設(shè)有T1Tn個(gè)頁(yè)面指?jìng)€(gè)頁(yè)面指向頁(yè)面向頁(yè)面A（即（即 引用）。參數(shù)引用）。參數(shù)d是一個(gè)阻尼因子，是一個(gè)阻尼因子，其取值區(qū)間屬于其取值區(qū)間屬于(0,1)，我們通常取值為，我們通常取值為0.85。C(A)定義為指向頁(yè)面定義為指向頁(yè)面A的其他

11、頁(yè)面的連接數(shù)，的其他頁(yè)面的連接數(shù)，頁(yè)面頁(yè)面A的的PageRank或或PR(A)值可以通過(guò)下面的值可以通過(guò)下面的公式得到：公式得到：注意：注意：PageRank值是值是Web頁(yè)面的概率分布表頁(yè)面的概率分布表示，所以所有示，所以所有Web頁(yè)面的頁(yè)面的PageRank值的和是值的和是1。11()( )( )(1)(.)( )()nnPR TPR TPR AddC TC T體系結(jié)構(gòu)：索引技術(shù)搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)Web爬蟲(chóng)抓取回來(lái)的頁(yè)面信息，需要放入索引數(shù)據(jù)庫(kù)里。索引建立的好壞對(duì)于搜索引擎有很大的影響，優(yōu)秀的索引能夠顯著的提高搜索引擎系統(tǒng)運(yùn)行的效率及檢索結(jié)果的品質(zhì)。文本分析技術(shù)是建立

12、數(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ù)難題。中文分詞完全不同于英文分詞，英文行文中，單詞間以空格分隔；而中文只有字/句/段有明顯分隔符，唯獨(dú)詞沒(méi)有形式上的分隔符存在。索引建立：倒排文件模型搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)倒排文件（倒排文件（inverted file），是指一個(gè)詞），是指一個(gè)詞匯集合匯集合W和一個(gè)文檔集合和一個(gè)文檔集合D之間對(duì)應(yīng)關(guān)之間對(duì)應(yīng)關(guān)系的數(shù)據(jù)結(jié)構(gòu)。系的數(shù)據(jù)結(jié)構(gòu)。建立倒

13、排文件索引是建立索引數(shù)據(jù)庫(kù)的建立倒排文件索引是建立索引數(shù)據(jù)庫(kù)的核心工作。核心工作。索引建立：倒排文件模型搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)索引模塊架構(gòu)體系結(jié)構(gòu)：搜索服務(wù)搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)搜索服務(wù)是Web搜索引擎工作流程的最后一步，根據(jù)用戶提交的查詢關(guān)鍵字展開(kāi)搜索，將匹配結(jié)果返回給用戶。搜索服務(wù)的好壞直接影響Web搜索引擎的用戶滿意程度。搜索服務(wù)：結(jié)果顯示搜索引擎體系結(jié)構(gòu)信息采集索引技術(shù)搜索服務(wù)接受用戶的輸入，提交用戶搜索請(qǐng)求。根據(jù)搜索結(jié)果列表合理的展示給用戶。在保護(hù)隱私的前提下，記錄用戶使用行為的詳細(xì)信息，以便提高下次服務(wù)的滿意度。搜索服務(wù)：網(wǎng)頁(yè)快照搜索引擎體系結(jié)構(gòu)

14、信息采集索引技術(shù)搜索服務(wù)Web上的數(shù)據(jù)每時(shí)每刻都在變化著，所以隨時(shí)存在著檢索到的頁(yè)面信息已經(jīng)不存在的可能。Web搜索引擎為了提高服務(wù)質(zhì)量，需要對(duì)搜索到的頁(yè)面信息進(jìn)行快照，以便在原來(lái)頁(yè)面信息失效的情況下，保證用戶能夠通過(guò)快照功能查看頁(yè)面。類Google Web搜索引擎的實(shí)例分析*類Google搜索引擎的架構(gòu)URL服務(wù)器Web頁(yè)面抓取器存儲(chǔ)服務(wù)器URL解釋器排序器Page Rank 搜索器類Google Web搜索引擎的實(shí)例分析*Google數(shù)據(jù)倉(cāng)庫(kù)的結(jié)構(gòu)類Google Web搜索引擎的實(shí)例分析*查詢?cè)u(píng)估流程查詢?cè)u(píng)估流程解析查詢（解析查詢（Query）把單詞轉(zhuǎn)化成把單詞轉(zhuǎn)化成wordID從每個(gè)單詞

15、的短桶文檔列表開(kāi)始查找從每個(gè)單詞的短桶文檔列表開(kāi)始查找掃描文檔列表直到有一個(gè)文檔匹配了所有的搜索詞語(yǔ)掃描文檔列表直到有一個(gè)文檔匹配了所有的搜索詞語(yǔ)計(jì)算這個(gè)文檔對(duì)應(yīng)的查詢的評(píng)分計(jì)算這個(gè)文檔對(duì)應(yīng)的查詢的評(píng)分如果到達(dá)短桶的文檔列表結(jié)尾，從每個(gè)單詞的全桶如果到達(dá)短桶的文檔列表結(jié)尾，從每個(gè)單詞的全桶(full barrel)文檔列表開(kāi)始查找，跳到第文檔列表開(kāi)始查找，跳到第4 步步如果沒(méi)有到達(dá)任何文檔列表的結(jié)尾，跳到第如果沒(méi)有到達(dá)任何文檔列表的結(jié)尾，跳到第4步步根據(jù)評(píng)分對(duì)匹配的文檔排序，然后返回評(píng)分最高的根據(jù)評(píng)分對(duì)匹配的文檔排序，然后返回評(píng)分最高的k個(gè)個(gè)12.1 搜索引擎簡(jiǎn)介12.2 搜索引擎體系結(jié)構(gòu)12

16、.3 物聯(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í)別物從智能物體角度思考搜索引擎與物體之間的關(guān)系，主動(dòng)識(shí)別物體并提取有用信息。體并提取有用信息。從用戶角度上的多模態(tài)信息利用，使查詢結(jié)果更精確，更智能，從用戶角度上的多模態(tài)信息利用，使查詢結(jié)果更精確，更智能，更定制化。更定制化。本章小結(jié)內(nèi)容回顧內(nèi)容回顧本章介紹了搜索引擎的發(fā)展歷程，重點(diǎn)討論了搜索引本章介紹了搜索引擎的發(fā)展歷程，重點(diǎn)討論了搜索引擎的體系結(jié)構(gòu)（信息采集，索引技術(shù)，搜索服務(wù)），擎的體系結(jié)構(gòu)（信息采集，索引技術(shù)，搜索服務(wù)），并提出了物聯(lián)網(wǎng)背景下搜索引擎的新思考。并提出了物聯(lián)網(wǎng)背景下搜索引擎的新思考。重點(diǎn)掌握重點(diǎn)掌握掌握掌握Web搜索引擎的三大模塊（網(wǎng)絡(luò)爬蟲(chóng)模塊，索引搜索引擎的三大模塊（網(wǎng)絡(luò)爬蟲(chóng)模塊，索引模塊，搜索模塊）的作用。模塊，搜索模塊）的作用。了解搜索引擎需要解決的三個(gè)問(wèn)題（響應(yīng)時(shí)間，關(guān)鍵了解搜索引擎需要解決的三個(gè)問(wèn)題（響應(yīng)時(shí)間，關(guān)鍵詞