信息檢索與web搜索課件 14學(xué)習(xí)資料

信息檢索與Web搜索

第14講Web采集Crawling授課人：高曙明

*改編自“現(xiàn)代信息檢索”網(wǎng)上公開課件（/~wangbin）*改編自“現(xiàn)代信息檢索”網(wǎng)上公開課件（/~wangbin）2概述Web采集：是從Web中收集網(wǎng)頁的過程必要性：因?yàn)闆]有集中的有組織的網(wǎng)頁集目標(biāo)：盡可能高效地采集更多數(shù)目的有用頁面相應(yīng)的軟件稱為Web采集器、網(wǎng)絡(luò)爬蟲、網(wǎng)絡(luò)蜘蛛（WebCrawler,spider）23基本的采集過程初始化采集URL種子隊(duì)列；重復(fù)如下過程：從隊(duì)列中取出URL下載并分析網(wǎng)頁從網(wǎng)頁中抽取更多的URL將這些URL放到隊(duì)列中這里有個(gè)“Web的連通性很好”的基本假設(shè)34Web采集示意圖45課堂思考:下列爬蟲有什么問題？urlqueue:=(somecarefullyselectedsetofseedurls)whileurlqueueisnotempty:myurl:=urlqueue.getlastanddelete()mypage:=myurl.fetch()fetchedurls.add(myurl)newurls:=mypage.extracturls()formyurlinnewurls:ifmyurlnotinfetchedurlsandnotinurlqueue:urlqueue.add(myurl)addtoinvertedindex(mypage)56采集器面對(duì)的問題規(guī)模問題:規(guī)模巨大，必須規(guī)?？蓴U(kuò)展，要分布式處理質(zhì)量問題：抓取“有用”網(wǎng)頁，必須進(jìn)行選擇、去重等效率問題：一秒采集數(shù)百數(shù)千網(wǎng)頁，必須充分利用資源魯棒性問題：存在采集器陷阱和作弊網(wǎng)頁禮貌性問題：對(duì)同一網(wǎng)站的訪問要遵照協(xié)議規(guī)定，并且訪問的間隔必須要足夠新鮮度(freshness)問題：保證包含索引網(wǎng)頁的較新版本，必須要定期更新或者重采67采集器必須具有的功能特點(diǎn)魯棒性

能夠處理采集器陷阱、重復(fù)頁面、超大頁面、超大網(wǎng)站、動(dòng)態(tài)頁面等問題7禮貌性

不要高頻率采集某個(gè)網(wǎng)站

僅僅采集robots.txt所規(guī)定的可以采集的網(wǎng)頁8Robots.txt文件1994年起使用的采集器協(xié)議，規(guī)定了采集器對(duì)網(wǎng)站的訪問限制例子：User-agent:*Disallow:/yoursite/temp/User-agent:searchengineDisallow:/采集時(shí)，要將每個(gè)站點(diǎn)的robots.txt放到高速緩存中，這一點(diǎn)相當(dāng)重要89Exampleofarobots.txt()User-agent:PicoSearch/1.0Disallow:/news/information/knight/Disallow:/nidcd/...Disallow:/news/research_matters/secure/Disallow:/od/ocpl/wag/User-agent:*Disallow:/news/information/knight/Disallow:/nidcd/...Disallow:/news/research_matters/secure/Disallow:/od/ocpl/wag/Disallow:/ddir/Disallow:/sdminutes/910采集器的基本架構(gòu)10采集器模板11URL集合分類11尚未見的URL集合12待采集URL池待采集URL池是一個(gè)數(shù)據(jù)結(jié)構(gòu)，它存放并管理那些已經(jīng)發(fā)現(xiàn)但是還沒有采集的URL集合可能包含來自同一主機(jī)的不同頁面需要避免在同一時(shí)間采集這些來自同一主機(jī)的頁面必須要保證采集線程任務(wù)飽和1213URL

規(guī)范化(normalization)從網(wǎng)頁中抽取的URL有些是相對(duì)地址比如，在網(wǎng)站下，會(huì)采集到aboutsite.html該頁面的絕對(duì)地址為：/aboutsite.html在網(wǎng)頁分析過程中，必須要將相對(duì)URL地址規(guī)范化1314抓取與分析抓?。豪胔ttp協(xié)議返回某個(gè)URL對(duì)應(yīng)的網(wǎng)頁，抓取到的頁面被寫入一個(gè)臨時(shí)存儲(chǔ)器分析：從采集到的網(wǎng)頁中抽取文本及鏈接，并將文本、錨文本、鏈接等信息傳給索引器和其它需要這些信息的模塊1415內(nèi)容重復(fù)判別和URL過濾內(nèi)容重復(fù)判別目的:對(duì)每個(gè)抓取的頁面，判斷它是否已被索引方法:采用文檔指紋或者shingle的方法判別結(jié)果:忽略那些已經(jīng)在索引中的重復(fù)頁面URL過濾目的:確定某個(gè)抽取的URL是否應(yīng)該被URL池收錄方法:排除某些域、基于robots.txt進(jìn)行排除結(jié)果:忽略那些不必要和不允許采集的URL1516分布式采集基本思想：運(yùn)行多個(gè)采集線程，分布在不同節(jié)點(diǎn)上，節(jié)點(diǎn)分散在不同地理位置上

具體做法：將需要采集的主機(jī)分配到不同節(jié)點(diǎn)上，原則是每個(gè)節(jié)點(diǎn)對(duì)“就近”的主機(jī)進(jìn)行采集，比如，地理位置在亞洲的采集器主要關(guān)注亞洲域名下網(wǎng)站的采集問題：前面介紹的采集流程是否還適用？如何實(shí)現(xiàn)每個(gè)節(jié)點(diǎn)對(duì)“就近”的主機(jī)進(jìn)行采集？1617分布式采集架構(gòu)1718分布式采集中的內(nèi)容重復(fù)檢測(cè)分布式采集架構(gòu)中的內(nèi)容重復(fù)檢測(cè)會(huì)很復(fù)雜很難基于主機(jī)名劃分文檔的指紋或shingle，即無法防止相同或者高度相似的內(nèi)容會(huì)出現(xiàn)在不同的Web服務(wù)器上文檔的指紋流或shingle流當(dāng)中幾乎不存在局部性文檔會(huì)隨時(shí)間不斷變化，因此在連續(xù)性采集中，需要從已下載內(nèi)容集合中去掉過時(shí)的指紋或shingle將文檔的指紋或shingle與URL綁定1819Google數(shù)據(jù)中心(wazfaring.com)1920待采集URL的輸出策略確定URL輸出次序需要考慮的因素：禮貌性:不要非常頻繁的訪問某個(gè)Web服務(wù)器比如，可以在兩次服務(wù)器訪問之間設(shè)置一個(gè)時(shí)間間隔優(yōu)先級(jí):對(duì)頻繁改變的高質(zhì)量網(wǎng)頁優(yōu)先能否采用一個(gè)簡(jiǎn)單的優(yōu)先級(jí)隊(duì)列加以實(shí)現(xiàn)？2021Mercator中的待采集URL緩沖池2122Mercator中的待采集URL緩沖池URL從上部流入緩沖池2223URL從上部流入緩沖池前端隊(duì)列(Frontqueue)管理優(yōu)先級(jí)23Mercator中的待采集URL緩沖池24URL從上部流入緩沖池前端隊(duì)列(Frontqueue)管理優(yōu)先級(jí)后端隊(duì)列(Backqueue)保證禮貌性24Mercator中的待采集URL緩沖池25URL從上部流入緩沖池前端隊(duì)列(Frontqueue)管理優(yōu)先級(jí)后端隊(duì)列(Backqueue)實(shí)現(xiàn)禮貌性每個(gè)隊(duì)列都是FIFO25Mercator中的待采集URL緩沖池2626前端隊(duì)列(Frontqueue)Mercator中的待采集URL緩沖池2727Mercator中的待采集URL緩沖池前端隊(duì)列(Frontqueue)優(yōu)先級(jí)分配器給每個(gè)URL分配一個(gè)0到F之間的優(yōu)先級(jí)整數(shù)2828Mercator中的待采集URL緩沖池前端隊(duì)列(Frontqueue)優(yōu)先級(jí)分配器給每個(gè)URL分配一個(gè)0到F之間的優(yōu)先級(jí)整數(shù)然后將URL添加到相應(yīng)的隊(duì)列中2929Mercator中的待采集URL緩沖池前端隊(duì)列(Frontqueue)優(yōu)先級(jí)分配器給每個(gè)URL分配一個(gè)0到F之間的優(yōu)先級(jí)整數(shù)然后將URL添加到相應(yīng)的隊(duì)列中分配優(yōu)先級(jí)可以基于啟發(fā)式信息：更新率、PageRank等等3030后端隊(duì)列(Backqueue)Mercator中的待采集URL緩沖池3131Mercator中的待采集URL緩沖池后端隊(duì)列(Backqueue)恒定情形1：

當(dāng)采集器在運(yùn)行時(shí)，每個(gè)后端隊(duì)列不為空恒定情形2：

每個(gè)后端隊(duì)列中僅存放來自同一主機(jī)的URL維護(hù)一張主機(jī)到后端隊(duì)列的表3232Mercator中的待采集URL緩沖池后端隊(duì)列(Backqueue)維護(hù)一個(gè)堆結(jié)構(gòu)，在堆中：每個(gè)后端隊(duì)列對(duì)應(yīng)一個(gè)元素元素值為該隊(duì)列對(duì)應(yīng)的主機(jī)重新訪問的最早時(shí)間te該時(shí)間te

由下列因素確定

(i)上次訪問該主機(jī)的時(shí)間(ii)時(shí)間間隔的啟發(fā)式方法3333Mercator中的待采集URL緩沖池后端隊(duì)列(Backqueue)采集線程與后端隊(duì)列的交互(i)抽取堆中的當(dāng)前根節(jié)點(diǎn)

q(q

是一個(gè)后端隊(duì)列)

(ii)抓取q中的頭部URLu

...判斷q

是否為空，并對(duì)為空的情況進(jìn)行處理3434Mercator中的待采集URL緩沖池后端隊(duì)列

q為空后的處理重復(fù)下列操作(i)從前端隊(duì)列中將一系列URLu推入并且(ii)將

u

加到相應(yīng)的后端隊(duì)列中......直到得到一個(gè)u，u的主機(jī)沒有對(duì)應(yīng)的后端隊(duì)列為止然后將

u

放入

q

并為它在堆中建立一個(gè)新元素后端隊(duì)列(Backqueue)35Mercator中的待采集URL緩沖池URLs從上流入到緩沖池前端隊(duì)列管理優(yōu)先級(jí)后端隊(duì)列保證禮貌性3536分布式索引基于詞項(xiàng)分割的分布式索引將詞項(xiàng)詞典劃分成多個(gè)子集，每個(gè)子集及其倒排記錄表放在一個(gè)節(jié)點(diǎn)上由于包含不同查詢?cè)~項(xiàng)的查詢流往往與不同的機(jī)器集合相關(guān)，因此允許更高的并行度存在問題多詞查詢處理的開銷非常大，甚至可能超過高并發(fā)度帶來的好處實(shí)現(xiàn)劃分結(jié)果的負(fù)載平衡很困難，實(shí)現(xiàn)動(dòng)態(tài)索引困難3637分布式索引基于文檔分割的分布式索引每個(gè)節(jié)點(diǎn)包含一個(gè)文檔子集的索引查詢時(shí)，將查詢廣播到所有節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)返回排名最高的k個(gè)結(jié)果，然后合并產(chǎn)生最終k個(gè)結(jié)果更為普遍使用文檔分割方法將來自同一個(gè)主機(jī)的網(wǎng)頁全部分到同一個(gè)節(jié)點(diǎn)，可能造成訪問的均衡性不好將每個(gè)URL哈希到索引節(jié)點(diǎn)空間3738連接服務(wù)器(connectivityserver)目的：支持Web圖連接查詢的快速處理給定的URL指向了哪些URL？給定的URL被哪些URL所指向？核心任務(wù)：在內(nèi)存中有效存儲(chǔ)Web圖對(duì)每個(gè)網(wǎng)頁采用整數(shù)編號(hào)建立兩個(gè)鄰接表，分別記錄每個(gè)網(wǎng)頁指向了哪些URL，被哪些URL所指向3839減少所需存儲(chǔ)空間的方法基本思想：利用鄰接表中許多行存在其相似行的特點(diǎn)，對(duì)鄰接表進(jìn)行壓縮表示具體方法：從上到下遍歷鄰接表，對(duì)每一行基于前面的7行進(jìn)行編碼：指定行偏移量，給出刪除的整數(shù)和增加的整數(shù)一個(gè)例子:可以將下面的第4