數(shù)據(jù)挖掘以及搜索引擎經(jīng)典第1頁，共34頁，2023年，2月20日，星期六Outline BasicWWWTechnologiesWeb的基本概念BasicCrawling基本的爬取算法第2頁，共34頁，2023年，2月20日，星期六URI：UniformResourceIdentifier

-UniformResourceIdentifiersURL:UniformResourceLocatorsURN:UniformResourceNamesEveryresourceavailableontheWebhasanaddressthatmaybeencodedbyaURL

URIstypicallyconsistofthreepieces:Thenamingschemeofthemechanismusedtoaccesstheresource.(HTTP,FTP)ThenameofthemachinehostingtheresourceThenameoftheresourceitself,givenasapath第3頁，共34頁，2023年，2月20日，星期六URL,URN與URI的關系URL,URN是URI的子集。URI是以某種統(tǒng)一的（標準化的）方式標識資源的簡單字符串。

URI一般由三部分組成：

1.訪問資源的命名機制。

2.存放資源的主機名。

3.資源自身的名稱，由路徑表示。第4頁，共34頁，2023年，2月20日，星期六URIExample/TR

ThereisadocumentavailableviatheHTTPprotocolResidingonthemachineshostingAccessibleviathepath"/TR"第5頁，共34頁，2023年，2月20日，星期六HypertextTransferProtocol(HTTP)Aconnection-orientedprotocol(TCP)usedtocarryWWWtrafficbetweenabrowserandaserverOneofthetransportlayerprotocolsupportedbyInternetHTTPcommunicationisestablishedviaaTCPconnectionandserverport80第6頁，共34頁，2023年，2月20日，星期六OnaWebserverorHypertextTransferProtocoldaemon,port80istheportthattheserver"listensto"orexpectstoreceivefromaWebclient,assumingthatthedefaultwastakenwhentheserverwasconfiguredorsetup.Aportcanbespecifiedintherangefrom0-65536ontheNCSAserver.However,theserveradministratorconfigurestheserversothatonlyoneportnumbercanberecognized.Bydefault,theportnumberforaWebserveris80.Experimentalservicesmaysometimesberunatport8080第7頁，共34頁，2023年，2月20日，星期六GETMethodinHTTP第8頁，共34頁，2023年，2月20日，星期六HTMLHyperlink

<ahref="relations/alumni">alumni</a>AlinkisaconnectionfromoneWebresourcetoanotherIthastwoends,calledanchors,andadirectionStartsatthe"source"anchorandpointstothe"destination"anchor,whichmaybeanyWebresource(e.g.,animage,avideoclip,asoundbite,aprogram,anHTMLdocument)第9頁，共34頁，2023年，2月20日，星期六Anchortest(錨文本）Anchortextisthehyperlinkedwordsonawebthewordsyouclickonwhenyouclickalink.

Here‘sanexample,reciprocallinks,inwhich“reciprocallinks”istheanchortext.

錨文本主要是為訪問者提供指向網(wǎng)頁內(nèi)容的說明。

第10頁，共34頁，2023年，2月20日，星期六Outline BasicWWWTechnologiesWeb的基本概念BasicCrawling基本的爬取算法第11頁，共34頁，2023年，2月20日，星期六Web是一個有向圖<href…><href…><href…><href…><href…><href…><href…>網(wǎng)頁為節(jié)點網(wǎng)頁中的HyperLink為有向邊Crawl==圖遍歷,right?第12頁，共34頁，2023年，2月20日，星期六CompletenessObservationsCompletenessisnotguaranteed假設從一個page出發(fā)能到達web上的任何一個page.實際情況并不一定這樣Howtomakeitbetter:moreseeds,morediverseseeds,portscannermaybehelp第13頁，共34頁，2023年，2月20日，星期六常用算法DepthFirstSearchWidthFirstSearch第14頁，共34頁，2023年，2月20日，星期六Depth-FirstSearch1234567numbers=orderinwhichnodesarevisited8910第15頁，共34頁，2023年，2月20日，星期六Depth-FirstSearchPROCEDURESPIDER(G,{SEEDS}) InitializeCOLLECTION<bigfileofURLpairs>//結果存儲 InitializeVISITED<bighash-table>//已訪問URL列表

ForeveryROOTinSEEDS InitializeSTACK<stackdatastructure>//待爬取URL棧 LetSTACK:=push(ROOT,STACK)

WhileSTACKisnotempty,

DoURLcurr:=pop(STACK)

UntilURLcurrisnotinVISITED insert-hash(URLcurr,VISITED) PAGE:=look-up(URLcurr)//爬取頁面 STORE(<URLcurr,PAGE>,COLLECTION)

ForeveryURLi

inPAGE,//鏈接提取

push(URLi,STACK) ReturnCOLLECTION第16頁，共34頁，2023年，2月20日，星期六Width-firstSearch12563710numbers=orderinwhichnodesarevisited489第17頁，共34頁，2023年，2月20日，星期六Width-firstSearchPROCEDURESPIDER(G,{SEEDS}) InitializeCOLLECTION<bigfileofURLpairs>//結果存儲 InitializeVISITED<bighash-table>//已訪問URL列表

ForeveryROOTinSEEDS InitializeQUEUE<queuedatastructure>//待爬取URL隊列 LetQUEUE:=EnQueue(ROOT,QUEUE)

WhileQUEUEisnotempty,

DoURLcurr:=DeQueue(QUEUE)

UntilURLcurrisnotinVISITED insert-hash(URLcurr,VISITED) PAGE:=look-up(URLcurr)//爬取頁面 STORE(<URLcurr,PAGE>,COLLECTION)

ForeveryURLi

inPAGE,//鏈接提取

EnQueue(URL,QUEUE) ReturnCOLLECTION第18頁，共34頁，2023年，2月20日，星期六面向領域的垂直檢索采用類似A*算法，best-first，分支限界算法等的變形搜索算法，利用最大堆，選取目前最相似的網(wǎng)頁的鏈接，繼續(xù)進行爬去。第19頁，共34頁，2023年，2月20日，星期六BestfirstAlgorithmInput:user’squeryQ,andalistLofURLs,sim(Q,P)>,PL;

Output:ApagesetS,wheresim(Q,P)>;PS;

S=L;OPEN=L;whileOPEN!=nulldo1.PickthebestnodeBfromOPEN.//measuredbysim2.searchpagespointedbypageB3.Foreachpagepdo:a.Ifithasnotbeenrecorded:computesim(p,Q),addittoSandOpenifsim(p,Q)>,andrecorditsparentB.done第20頁，共34頁，2023年，2月20日，星期六Sim(Q,p)的計算因素網(wǎng)站的重要性及和Q的相關性p的父親節(jié)點f(p)對Q相關性的遺傳性如將1/2sim(f(p),Q)加到sim(p,Q)錨文本與Q的相關性網(wǎng)頁文本內(nèi)容與Q的相關性由p指向的網(wǎng)頁中是否與Q在語義上相關第21頁，共34頁，2023年，2月20日，星期六Crawler的任務和方法批量爬取在一個時間段盡量多的網(wǎng)頁通用搜索引擎：涉及的網(wǎng)頁內(nèi)容盡量豐富，質(zhì)量盡量高（例如不要集中在少數(shù)網(wǎng)站，不要那些沒什么內(nèi)容的網(wǎng)頁）主題搜索引擎：盡量符合主題內(nèi)容（例如某新聞主題，可能需要特別關注若干網(wǎng)站）增量爬取用盡量少的時間，盡量收集目前系統(tǒng)中沒有（或者有但發(fā)生了更新）的網(wǎng)頁，同時發(fā)現(xiàn)系統(tǒng)中已有的哪些網(wǎng)頁現(xiàn)在實際上已經(jīng)不存在網(wǎng)上了第22頁，共34頁，2023年，2月20日，星期六提高質(zhì)量：“全”和“好”數(shù)量覆蓋率搜索引擎索引的網(wǎng)頁（一次收集）占目標區(qū)域中所有可能網(wǎng)頁數(shù)量的百分比質(zhì)量覆蓋率搜索引擎索引的網(wǎng)頁中“高質(zhì)量”網(wǎng)頁占目標區(qū)域中所有可能重要網(wǎng)頁數(shù)量的百分比何謂“高質(zhì)量網(wǎng)頁”？PageRankHITS(Hyperlink-InducedTopicSearch)…第23頁，共34頁，2023年，2月20日，星期六鏈接提取和規(guī)格化目標：得到網(wǎng)頁中所含URL的標準型URL的處理和過濾避免多次抓取被不同url指向的相同網(wǎng)頁IP地址和域名之間的多對多關系（見以前的討論）大規(guī)模網(wǎng)站用于負載平衡的技術：內(nèi)容鏡像“virtualhosting”和“Proxypass”：不同的主機名映射到同一個IP地址，發(fā)布多個邏輯網(wǎng)站的需要（Apache支持）相對URL需要補齊基礎URL第24頁，共34頁，2023年，2月20日，星期六對URL進行規(guī)格化比如:,/,/index.htm都是一會事,所以要進行規(guī)格化用一個標準的字符串表示協(xié)議利用canonical主機名字查DNS會返回IP和一個canonical名字顯式加上一個端口號（80也加上）規(guī)格化并清理好文檔路徑例如將/books/../papers/sigmod1999.ps寫成/papers/sigmod1999.ps第25頁，共34頁，2023年，2月20日，星期六禮貌工作：不給網(wǎng)站造成明顯負載隨著人們自我保護的意識越來越強，這問題越來越重要不希望搜索引擎上“黑名單”第26頁，共34頁，2023年，2月20日，星期六Robotexclusion檢查在服務器文檔根目錄中的文件，robots.txt包含一個路徑前綴表，crawlers不應該跟進去抓文檔，例如#AltaVistaSearchUser-agent:AltaVistaIntranetV2.0W3CWebreqDisallow:/Out-Of-Date#excludesomeaccess-controlledareasUser-agent:*Disallow:/Team//不允許爬取的部分Disallow:/ProjectDisallow:/Systems限制只是對crawlers，一般瀏覽無妨“君子協(xié)定”（你的crawler可以不遵守）第27頁，共34頁，2023年，2月20日，星期六消除已經(jīng)訪問過的URL檢查某個URL是否已經(jīng)被抓過了在將一個新的URL放到工作池之前要很快，不要在這里形成性能瓶頸（檢查將要訪問磁盤）可以通過計算并對比（規(guī)格化后的）URL的MD5來實現(xiàn)利用訪問的時空局部性兩級hash函數(shù)（改善對空間局部性的利用）主機名+端口號，散列到高位（例如高24位）路徑散列到低位（例如后面的40位）用B-樹管理符合條件（即未被訪問過）的URLs放到crawler的任務中.第28頁，共34頁，2023年，2月20日，星期六爬取器的陷阱防止系統(tǒng)異常病態(tài)HTML文件例如，有的網(wǎng)頁含有68kBnull字符誤導爬取器的網(wǎng)站用CGI程序產(chǎn)生無限個網(wǎng)頁用軟目錄創(chuàng)建的很深的路徑/Flyfactory/hatchline/hatchline/hatchline/flyfactory/flyfactory/flyfactory/flyfactory/flyfactory/flyfactory/flyfactory/flyfactory/hatchlineHTTP服務器中的路徑重映射特征第29頁，共34頁，2023年，2月20日，星期六爬取器的陷阱：解決方案不存在完美的自動方案，積累歷史數(shù)據(jù)很重要。檢查URL的長度保護模塊（Guards）定期收集爬取中的統(tǒng)計數(shù)據(jù)發(fā)現(xiàn)太突出的網(wǎng)站（例如收集過程過多出現(xiàn)它），就將它放到保護模塊中，以后就不考慮來自于它的URL。不爬取動態(tài)的內(nèi)容（unsolvedproblem），例如由CGI表格查詢產(chǎn)生的清除非文本類型的URLs（即它的MIME類型不是text/****）第30頁，共34頁，2023年，2月20日，星期六避免在重復的網(wǎng)頁上再提取鏈接減少爬取中的