《北京理工大学信息检索课件-3-robots》由会员分享，可在线阅读，更多相关《北京理工大学信息检索课件-3-robots（65页珍藏版）》请在金锄头文库上搜索。
1、Talk 3. Robot and Storage LIN DAI 2012.9 Information Retrieval 2 Outline 1. 信息采集信息采集 2. 网页内容网页内容提取提取 3. 字符字符编码编码 4. 去去重重 5. 存储存储 信息采集信息采集 1. 网络爬虫网络爬虫 2. 礼貌性礼貌性 3. 网站地图网站地图 4. 时新性时新性 5. 主题爬虫主题爬虫 6. 分布式爬虫分布式爬虫 网络爬虫 网络爬虫的任务就是从指定的数据源下载网络爬虫的任务就是从指定的数据源下载 信息。信息。 需要良好的可扩展性和高度模块化需要良好的可扩展性和高度模块化： 网页总数数量巨大（粗
2、略估计在百亿数量级）网页总数数量巨大（粗略估计在百亿数量级） 重复信息重复信息 遵守礼貌性遵守礼貌性 分布式爬取和存储分布式爬取和存储 爬虫基本结构 WWW 抓 取 DNS 分 析 内容 去重 URL 过滤 URL 去重 待采集URL池 指纹 URL库 分布式爬虫基本结构 WWW 抓 取 DNS 分 析 内容 去重 URL 过滤 主机 分配 URL 去重 待采集RUL池 指纹 URL库 其他其他 主机主机 其他其他 主机主机 URL池 URL池：用于存储URL信息。其中错误URL用于存 储下载失败的URL，在一定的时机，将重新尝试对 其进行下载。而待采集的URL则存储的是等待被下 载引擎采集的
3、URL。 一个完整的URL由协议名、服务器地址和路径组成。 http:/ 协议名 服务器地址 路径 DNS DNS：完成域名到真实主机IP地址的转换 202.108.33.60 DNS: 瓶颈 DNS解析相对较慢的（需要数秒的时间）， 网络爬虫通常采用DNS缓存和异步处理的方 式来消除该瓶颈 DNS缓存机制：将最近解析成功的主机URL 放入DNS缓存中 异步DNS 企业级的爬虫系统通常采用异步的DNS查询方 式 DNS查询的线程T向DNS服务器发送查询消息， 并且进入定时等待状态。得到DNS解析结果时， 则立即通知相应的采集线程。 尝试等待的次数为5的倍数，等待的时间随着 尝试的次数的增加而
4、指数级增加，最后一次等待的超时时间为90秒左右。 桌面爬虫 只需要搜集到所有需要建立索引的文件路 径 监视主机的活动，对新建立或者内容被改 变的文档，加入索引或者修改相应的索引。 礼貌性 爬虫总是希望同一时刻下载上百个甚至更 多的网页。 影响真实用户的访问 网络爬虫应当遵从礼貌策略（politeness policy）： 不会同时在同一网站上抓取多个页面 同一服务器的两次请求之间有一定的等待时间 网络服务器禁止不遵从礼貌性原则的爬虫 访问的访问 每秒下载100个 网页，每分钟最 多可以下载1个 页面，则请求队 列中至少需要来 自6000个不同网 站的URL。 robots.txt 爬虫限制协议
5、（robots exclusion protocol） User-agent: * Disallow: /news Allow: /advertise User-agent: Googlebot Disallow: Sitemap: http:/ 第一个命令块要求所有的爬虫可以访问第一个命令块要求所有的爬虫可以访问/advertise目录下的网页，目录下的网页， 但是不能访问但是不能访问/news目录下的网页。目录下的网页。 第二个命令块规定第二个命令块规定Googlebot爬虫可以爬取该网站的所有内容。爬虫可以爬取该网站的所有内容。 第三个命令块给出本站的网站地图，这是一个可选的指令。第三个
6、命令块给出本站的网站地图，这是一个可选的指令。 网站地图 网站有时候希望主动告诉爬虫程序某些网 页的更新频率，以实现新内容的快速获取。 或者网站希望将一些不能被爬虫发现的信 息被爬虫抓取。 网站地图（sitemap）给出一个解决这种问 题的简便办法。 http:/ ls+90210&id=C279796CE42B4762B8F51C21020BF248 http:/ 2012-06-13 always http:/ always 0.8 时新性 高可用性的搜索引擎应该将最新的网页内 容呈现给用户。 静态页面: HTTP协议提供了HEAD命令 动态生成的页面:必须下载网页全部内容 时新性定义 时
7、新性一般定义为所下载的所有页面中新 页面所占的比例。 对时新性进行优化的办法是不下载这些频 繁更新的页面。 时新性 年龄 假设某个页面的变化频率为，即该页面每 天变化次。该页面被采集t天之后，其年龄 的期望值为： Age ,t = P 页面在时刻t被更新t x dxt0 式中 t x 为页面的年龄，将年龄乘以其概 率。网页的更新一般遵循泊松分布。 将上式中的概率P替换为泊松分布，得到： Age ,t = ext x dxt0当=1/7，也就是每周更新一次时，页面年龄 期望值的曲线如图。 -1-0.500.511.522.5302468age day Y 值 线性 (Y 值) 主题爬虫 垂直搜索
8、引擎能够为用户提供更准确的内 容和更好的搜索体验 主题爬虫: 需要对更加聪明的爬虫，自动判 断并下载与给定主题相关的页面。 主题爬虫基本结构 WWW 抓 取 DNS 分 析 内容 去重 URL 过滤 URL 去重 待采集RUL池 指纹 URL库 URL Relevance 相关性计算 链接的锚文本 页面内容 分布式爬虫 采用分布式爬虫的原因： 第一，可以利用更多的计算资源进行信息采 集，包括CPU、内存、存储和网络带宽等。 第二，可以将爬虫服务器放在被采集网站的距 离较近的地方，以提高信息采集的效率。 第三，采用分布式爬虫可以减少每个服务器处 理的网站数量。 每个爬虫实例根据一定规则，承担对特
9、定 网站内容的爬取 使用URL中的主机部分进行HASH计算得到。考 虑地域、字母顺序、网站规模、更新频率等先 验知识。 一个网站只由一个爬虫处理： URL分配的不均衡 容易遵守礼貌性策略 降低爬虫之间交换URL的数量和频率 return 网页内容提取 搜索引擎在对 内容进行索引 之前，必须从 网页中去除这 些噪音信息 Observation:正文部分的HTML相对较少 Finn等人基于这个观察提出了一个简单的算 法。 目标函数 bn=1表示第n个词是标签，否则bn=0。 寻找正文开始的最小位置i和正文结束的最 大位置j，最大化小于i和大于j的标签数量， 与介于i和j之间的非标签的数量。 bn+
10、 1 bn+jii1bnNjlimitation 只有当非正文部分的词条标签比例小于正 文部分的词条标签比例，该算法才能工作。 去除该限制的启发式策略包括： 采用搜索窗口，对低斜率部分进行搜索 利用标点符号判定正文部分 dom Gupta等人（2003）提出一种基于DOM结构提 取这要内容的方法。使用多种技术过滤掉树节 点中的图片、脚本、广告、连接列表、布局表 格等，最后留下内容部分。 Yu等人（2003）利用网页的视觉特征，构建出 网页可视块的布局结构，并用于提取正文内 容。 基于文档斜率的内容提取方法适用于于仅存在 单个内容块的网页，基于DOM树的方法对于具 有多个内容块的网页也具有很好的
11、效果。 return 字符编码 在互联网上的网页采用数十种编码方法 目前使用最广泛的西文字符集及其编码是 ASCII 字符集和 ASCII 码 标准ASCII 字符集：使用 7 个二进位对字符进行 编码，共有 128 个字符，其中有 96 个可打印字 符 扩展ASCII 字符集：使用 8 位代码。 GB码、国标码 GB 2312-1980：1980年发布的信息交换用汉 字编码字符集 基本集，常被通称为国标码。 GB2312编码通行于我国内地。新加坡等地也采 用此编码。 冲突：每个字节第8bit设置为1同西文加以区别， 如果第8bit为0，则表示西文字符。 GBK编码标准兼容GB2312，共收录
12、汉字21003 个、符号883个，并提供1894个造字码位，简、 繁体字融于一库。 Unicode 除了以上编码外，世界上还存在着几十中 编码方式，同一个二进制数字可以被解释 成不同的符号。 Unicode编码将世界上所有的符号都纳入其 中，从根本上消除了乱码。 常见：UTF-8, UTF-16, UTF-32. UNICODE UTF-8 0000 0000 - 0000 007F 0XXX XXXX 0000 0080 - 0000 07FF 110X XXXX 10XX XXXX 0000 0800 - 0000 FFFF 1110 XXXX 10XX XXXX 10XX XXXX 00
13、01 0000 - 001F FFFF 1111 0XXX 10XX XXXX 10XX XXXX 10XX XXXX 0020 0000 - 03FF FFFF 1111 10XX 10XX XXXX 10XX XXXX 10XX XXXX 10XX XXXX 0400 0000 - 7FFF FFFF 1111 110X 10XX XXXX 10XX XXXX 10XX XXXX 10XX XXXX 10XX XXXX return 去重 互联网中有30%左右的网页是重复的或者相 似的。 重复的信息不但不会给用户带来新的信息， 还会增加爬虫、索引和检索的工作量和存 储量。 两类任务：URL
14、去重和内容去重 URL去重 爬虫解析所下载的网页，分析网页内的 URL，将新发现的放入待下载队列等候下 载。 爬虫需要一种快速的算法决定新发现的URL 是否已经在等待下载或已经被下载。 在小型系统中，基于树结构的方法可以很 好的满足要求。 Bloom filter HASH表的一个缺陷是较高的冲突率 布隆过滤器（Bloom Filter）:通过多个HASH 函数降低冲突的发生 如果这些HASH函数中任何一个判断该元素不在 集合中，那肯定就不在 相反，如果它们都判断该元素已经存在，则该 元素存在的可能性很大。 假设我们有一个如下图所示的二进制位数组集合， 每一个二进制位标识某个hash值是否出现
15、过。 S=x1, x2,xn ，Bloom Filter使用k个相互独立的 哈希函数（Hash Function），它们分别将集合 中的每个元素映射到1,m的范围中。 m 在下图中，k=3，且有两个哈希函数选中同一个位置（从左 边数第五位）。 Bloom Filter的错误率 Bloom Filter的错误率取决于哈希函数的个数 和位组的大小。 k = ln2 (m/n)时，错误率取得最小值。 在错误率不大于的情况下，m至少要等于n log2(1/)才能表示任意n个元素的集合。 内容重复检测 完全重复内容的检测： 不考虑字符位置：所有字符的和作为校验和 考虑字符位置：循环冗余校验Cyclic Redundancy
