数据挖掘以及搜索引擎经典pptchap4

Outline•Basic–Web的基本概念•BasicCrawling–基本的爬取算法URI：UniformResourceIdentifier-UniformResourceIdentifiers–URL:UniformResourceLocators–URN:UniformResourceNames•EveryresourceavailableontheWebhasanaddressthatmaybeencodedbyaURL•URIstypicallyconsistofthreepieces:–Thenamingschemeofthemechanismusedtoaccesstheresource.(HTTP,FTP)–Thenameofthemachinehostingtheresource–Thenameoftheresourceitself,givenasapathURL,URN与URI的关系•URL,URN是URI的子集。•URI是以某种统一的（标准化的）方式标识资源的简单字符串。URI一般由三部分组成：1.访问资源的命名机制。2.存放资源的主机名。3.资源自身的名称，由路径表示。URIExample••ThereisadocumentavailableviatheHTTPprotocol•Residingonthemachineshosting•Accessibleviathepath/TRHypertextTransferProtocol(HTTP)•Aconnection-orientedprotocol(TCP)usedtocarry•OneofthetransportlayerprotocolsupportedbyInternet•HTTPcommunicationisestablishedviaaTCPconnectionandserverport80OnaWebserverorHypertextTransferProtocoldaemon,port80istheportthattheserverlistenstoorexpectstoreceivefromaWebclient,assumingthatthedefaultwastakenwhentheserverwasconfiguredorsetup.Aportcanbespecifiedintherangefrom0-65536ontheNCSAserver.However,theserveradministratorconfigurestheserversothatonlyoneportnumbercanberecognized.Bydefault,theportnumberforaWebserveris80.Experimentalservicesmaysometimesberunatport8080GETMethodinHTTPHTMLHyperlink•ahref=relations/alumnialumni/a•AlinkisaconnectionfromoneWebresourcetoanother•Ithastwoends,calledanchors,andadirection•Startsatthesourceanchorandpointstothedestinationanchor,whichmaybeanyWebresource(e.g.,animage,avideoclip,asoundbite,aprogram,anHTMLdocument)Anchortest(锚文本）•Anchortextisthehyperlinkedwordsonawebpage-thewordsyouclickonwhenyouclickalink.Here‘sanexample,reciprocallinks,inwhich“reciprocallinks”istheanchortext.锚文本主要是为访问者提供指向网页内容的说明。Outline•Basic–Web的基本概念•BasicCrawling–基本的爬取算法Web是一个有向图href…href…href…href…href…href…href…网页为节点网页中的HyperLink为有向边Crawl==图遍历,right?CompletenessObservationsCompletenessisnotguaranteed•假设从一个page出发能到达web上的任何一个page.•实际情况并不一定这样•Howtomakeitbetter:–moreseeds,morediverseseeds,–portscannermaybehelp常用算法•DepthFirstSearch•WidthFirstSearchDepth-FirstSearch1234567numbers=orderinwhichnodesarevisited8910Depth-FirstSearchPROCEDURESPIDER(G,{SEEDS})InitializeCOLLECTIONbigfileofURL-pagepairs//结果存储InitializeVISITEDbighash-table//已访问URL列表ForeveryROOTinSEEDSInitializeSTACKstackdatastructure//待爬取URL栈LetSTACK:=push(ROOT,STACK)WhileSTACKisnotempty,DoURLcurr:=pop(STACK)UntilURLcurrisnotinVISITEDinsert-hash(URLcurr,VISITED)PAGE:=look-up(URLcurr)//爬取页面STORE(URLcurr,PAGE,COLLECTION)ForeveryURLiinPAGE,//链接提取push(URLi,STACK)ReturnCOLLECTIONWidth-firstSearch12563710numbers=orderinwhichnodesarevisited489Width-firstSearchPROCEDURESPIDER(G,{SEEDS})InitializeCOLLECTIONbigfileofURL-pagepairs//结果存储InitializeVISITEDbighash-table//已访问URL列表ForeveryROOTinSEEDSInitializeQUEUEqueuedatastructure//待爬取URL队列LetQUEUE:=EnQueue(ROOT,QUEUE)WhileQUEUEisnotempty,DoURLcurr:=DeQueue(QUEUE)UntilURLcurrisnotinVISITEDinsert-hash(URLcurr,VISITED)PAGE:=look-up(URLcurr)//爬取页面STORE(URLcurr,PAGE,COLLECTION)ForeveryURLiinPAGE,//链接提取EnQueue(URL,QUEUE)ReturnCOLLECTION面向领域的垂直检索•采用类似A*算法，best-first，分支限界算法等的变形搜索算法，利用最大堆，选取目前最相似的网页的链接，继续进行爬去。BestfirstAlgorithmInput:user’squeryQ,andalistLofURLs,sim(Q,P),PL;Output:ApagesetS,wheresim(Q,P);PS;S=L;OPEN=L;whileOPEN!=nulldo1.PickthebestnodeBfromOPEN.//measuredbysim2.searchpagespointedbypageB3.Foreachpagepdo:a.Ifithasnotbeenrecorded:computesim(p,Q),addittoSandOpenifsim(p,Q),andrecorditsparentB.doneSim(Q,p)的计算因素•网站的重要性及和Q的相关性•p的父亲节点f(p)对Q相关性的遗传性–如将1/2sim(f(p),Q)加到sim(p,Q)•锚文本与Q的相关性•网页文本内容与Q的相关性•由p指向的网页中是否与Q在语义上相关Crawler的任务和方法•批量爬取–在一个时间段尽量多的网页•通用搜索引擎：涉及的网页内容尽量丰富，质量尽量高（例如不要集中在少数网站，不要那些没什么内容的网页）•主题搜索引擎：尽量符合主题内容（例如某新闻主题，可能需要特别关注若干网站）•增量爬取–用尽量少的时间，尽量收集目前系统中没有（或者有但发生了更新）的网页，同时发现系统中已有的哪些网页现在实际上已经不存在网上了提高质量：“全”和“好”•数量覆盖率–搜索引擎索引的网页（一次收集）占目标区域中所有可能网页数量的百分比•质量覆盖率–搜索引擎索引的网页中“高质量”网页占目标区域中所有可能重要网页数量的百分比•何谓“高质量网页”？–PageRank–HITS(Hyperlink-InducedTopicSearch)–…链接提取和规格化•目标：得到网页中所含URL的标准型•URL的处理和过滤–避免多次抓取被不同url指向的相同网页–IP地址和域名之间的多对多关系（见以前的讨论）•大规模网站用于负载平衡的技术：内容镜像•“virtualhosting”和“Proxypass”：不同的主机名映射到同一个IP地址，发布多个逻辑网站的需要（Apache支持）–相对URL•需要补齐基础URL对URL进行规格化•比如:://://都是一会事,所以要进行规格化•用一个标准的字符串表示协议•利用canonical主机名字–查DNS会返回IP和一个canonical名字•显式加上一个端口号（80也加上）•规格化并清理好文档路径–例如将/books/../papers/sigmod1999.ps写成/papers/sigmod1999.ps礼貌工作：不给网站造成明显负载•随着人们自我保护的意识越来越强，这问题越来越重要•不希望搜索引擎上“黑名单”Robotexclusion•检查–在服务器文档根目录中的文件，robots.txt•包含一个路径前缀表，crawlers不应该跟进去抓文档，例如#AltaVistaSearchUser-agent:AltaVistaIntranetV2.0W3CWebreqDisallow:/Out-Of-Date#excludesomeaccess-controlledareasUser-agent:*Disallow:/Team//不允许爬取的部分Disallow:/ProjectDisallow:/Systems•限制只是对crawlers，一般浏览无妨–“君子协定”（你的crawler可以不遵守）消除已经访问过的URL•检查某个URL是否已经被抓过了–在将一个新的URL放到工作池之前–要很快，不要在这里形成性能瓶颈（检查将要访问磁盘）–可以通过计算并对比（规格化后的）URL的MD5来实现•利用访问的时空局部性–两级hash函数（改善对空间局部性的利用）•主机名+端口号，散列到高位（例如高24位）•路径散列到低位（例如后面的40位）•用B-树管理•符合条件（即未被访问过）的URLs放到crawler的任务中.爬取器的陷阱•防止系统异常–病态HTML文件•例如，有的网页含有68kBnull字