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

1、Outline,Basic WWW Technologies Web的基本概念 Basic Crawling 基本的爬取算法,URI：Uniform Resource Identifier,-Uniform Resource Identifiers URL: Uniform Resource Locators URN: Uniform Resource Names Every resource available on the Web has an address that may be encoded by a URL URIs typically consist of three piec

2、es: The naming scheme of the mechanism used to access the resource. (HTTP, FTP) The name of the machine hosting the resource The name of the resource itself, given as a path,URL,URN与URI的关系,URL,URN是URI的子集。 URI是以某种统一的（标准化的）方式标识资源的简单字符串。 URI一般由三部分组成： 1. 访问资源的命名机制。 2. 存放资源的主机名。 3. 资源自身的名称，由路径表示。,URI Exa

3、mple,/TR There is a document available via the HTTP protocol Residing on the machines hosting Accessible via the path /TR,Hypertext Transfer Protocol (HTTP),A connection-oriented protocol (TCP) used to carry WWW traffic between a browser and a server One of the transport l

4、ayer protocol supported by Internet HTTP communication is established via a TCP connection and server port 80,On a Web server or Hypertext Transfer Protocol daemon, port 80 is the port that the server listens to or expects to receive from a Web client, assuming that the default was taken when the se

5、rver was configured or set up. A port can be specified in the range from 0-65536 on the NCSA server. However, the server administrator configures the server so that only one port number can be recognized. By default, the port number for a Web server is 80. Experimental services may sometimes be run

6、at port 8080,GET Method in HTTP,HTML Hyperlink,alumni A link is a connection from one Web resource to another It has two ends, called anchors, and a direction Starts at the source anchor and points to the destination anchor, which may be any Web resource (e.g., an image, a video clip, a sound bite,

7、a program, an HTML document),Anchor test (锚文本）,Anchor text is the hyperlinked words on a web page - the words you click on when you click a link. Heres an example, reciprocal links, in which “reciprocal links” is the anchor text. 锚文本主要是为访问者提供指向网页内容的说明。,Outline,Basic WWW Technologies Web的基本概念 Basic C

8、rawling 基本的爬取算法,Web是一个有向图, , , ,网页为节点 网页中的HyperLink为有向边 Crawl = 图遍历, right?,Completeness Observations,Completeness is not guaranteed 假设从一个page出发能到达web上的任何一个page. 实际情况并不一定这样 How to make it better: more seeds, more diverse seeds, port scanner maybe help,常用算法,Depth First Search Width First Search,Depth

9、-First Search,Depth-First Search,PROCEDURE SPIDER(G, SEEDS) Initialize COLLECTION /结果存储 Initialize VISITED /已访问URL列表 For every ROOT in SEEDS Initialize STACK /待爬取URL栈 Let STACK := push(ROOT, STACK) While STACK is not empty, Do URLcurr := pop(STACK) Until URLcurr is not in VISITED insert-hash(URLcurr

10、, VISITED) PAGE := look-up(URLcurr)/爬取页面 STORE(, COLLECTION) For every URLi in PAGE,/链接提取 push(URLi, STACK) Return COLLECTION,Width-first Search,Width-first Search,PROCEDURE SPIDER(G, SEEDS) Initialize COLLECTION /结果存储 Initialize VISITED /已访问URL列表 For every ROOT in SEEDS Initialize QUEUE /待爬取URL队列 L

11、et QUEUE := EnQueue(ROOT, QUEUE) While QUEUE is not empty, Do URLcurr := DeQueue(QUEUE) Until URLcurr is not in VISITED insert-hash(URLcurr, VISITED) PAGE := look-up(URLcurr)/爬取页面 STORE(, COLLECTION) For every URLi in PAGE,/链接提取 EnQueue(URL, QUEUE) Return COLLECTION,面向领域的垂直检索,采用类似A*算法，best-first，分支限

12、界算法等的变形搜索算法，利用最大堆，选取目前最相似的网页的链接，继续进行爬去。,Best first Algorithm Input: users query Q, and a list L of URLs, sim(Q,P), PL; Output: A page set S, where sim(Q,P); PS; S=L; OPEN = L ; while OPEN != null do 1. Pick the best node B from OPEN. / measured by sim 2. search pages pointed by page B 3. For each pa

13、ge p do: a. If it has not been recorded: compute sim(p,Q), add it to S and Open if sim(p,Q) , and record its parent B. done,Sim(Q,p)的计算因素,网站的重要性及和Q的相关性 p 的父亲节点f(p)对Q相关性的遗传性 如将1/2 sim(f(p),Q)加到sim(p,Q) 锚文本与Q的相关性 网页文本内容与Q的相关性 由p指向的网页中是否与Q在语义上相关,Crawler的任务和方法,批量爬取 在一个时间段尽量多的网页 通用搜索引擎：涉及的网页内容尽量丰富，质量尽量高（

14、例如不要集中在少数网站，不要那些没什么内容的网页） 主题搜索引擎：尽量符合主题内容（例如某新闻主题，可能需要特别关注若干网站） 增量爬取 用尽量少的时间，尽量收集目前系统中没有（或者有但发生了更新）的网页，同时发现系统中已有的哪些网页现在实际上已经不存在网上了,提高质量：“全”和“好”,数量覆盖率 搜索引擎索引的网页（一次收集）占目标区域中所有可能网页数量的百分比 质量覆盖率 搜索引擎索引的网页中“高质量”网页占目标区域中所有可能重要网页数量的百分比 何谓“高质量网页”？ PageRank HITS (Hyperlink-Induced Topic Search ) ,链接提取和规格化,目标：

15、得到网页中所含URL的标准型 URL的处理和过滤 避免多次抓取被不同url指向的相同网页 IP地址和域名之间的多对多关系（见以前的讨论） 大规模网站用于负载平衡的技术：内容镜像 “virtual hosting”和“Proxy pass”：不同的主机名映射到同一个IP地址，发布多个逻辑网站的需要（Apache支持） 相对URL 需要补齐基础URL,对URL进行规格化,比如:, 用一个标准的字符串表示协议 利用canonical主机名字 查DNS会返回IP和一个canonical名字 显式加上一个端口号（80也加上） 规格化并清理好文档路径 例如将/books/./papers/sigmod19

16、99.ps写成/papers/sigmod1999.ps,礼貌工作：不给网站造成明显负载,随着人们自我保护的意识越来越强，这问题越来越重要 不希望搜索引擎上“黑名单”,Robot exclusion,检查 在服务器文档根目录中的文件，robots.txt 包含一个路径前缀表，crawlers不应该跟进去抓文档，例如 #AltaVista Search User-agent: AltaVista Intranet V2.0 W3C Webreq Disallow: /Out-Of-Date #exclude some access-controlled areas User-agent: * D

17、isallow: /Team /不允许爬取的部分 Disallow: /Project Disallow: /Systems 限制只是对crawlers，一般浏览无妨 “君子协定”（你的crawler可以不遵守）,消除已经访问过的URL,检查某个URL是否已经被抓过了 在将一个新的URL放到工作池之前 要很快，不要在这里形成性能瓶颈（检查将要访问磁盘） 可以通过计算并对比（规格化后的）URL的MD5来实现 利用访问的时空局部性 两级hash函数（改善对空间局部性的利用） 主机名+端口号，散列到高位（例如高24位） 路径散列到低位（例如后面的40位） 用B-树管理 符合条件（即未被访问过）的UR

18、Ls放到crawler的任务中.,爬取器的陷阱,防止系统异常 病态HTML文件 例如，有的网页含有68 kB null字符 误导爬取器的网站 用CGI程序产生无限个网页 用软目录创建的很深的路径 HTTP服务器中的路径重映射特征,爬取器的陷阱：解决方案,不存在完美的自动方案，积累历史数据很重要。 检查URL的长度 保护模块（Guards） 定期收集爬取中的统计数据 发现太突出的网站（例如收集过程过多出现它），就将它放到保护模块中，以后就不考虑来自于它的URL。 不爬取动态的内容（unsolved problem），例如由CGI表格查询产生的 清除非文本类型的URLs（即它的MIME类型不是text/*）,避免在重复的网页上再提取链接,减少爬取中的别名冗余网页（不仅本身开销，还有其中的相对链接v） 重复网页的检测：镜像网页和网站 检测完全重复的网页（exact duplica