北京理工大学信息检索课件-3-robots

[e-mail]2012.9InformationRetrieval2Outline1.信息采集2.网页内容提取3.字符编码4.去重5.存储信息采集1.网络爬虫2.礼貌性3.网站地图4.时新性5.主题爬虫6.分布式爬虫网络爬虫•网络爬虫的任务就是从指定的数据源下载信息。•需要良好的可扩展性和高度模块化：–网页总数数量巨大（粗略估计在百亿数量级）–重复信息–遵守礼貌性–分布式爬取和存储爬虫基本结构池•URL池：用于存储URL信息。其中错误URL用于存储下载失败的URL，在一定的时机，将重新尝试对其进行下载。而待采集的URL则存储的是等待被下载引擎采集的URL。•一个完整的URL由协议名、服务器地址和路径组成。协议名服务器地址路径DNS•DNS：完成域名到真实主机IP地址的转换•news.sina.com.cn202.108.33.60DNS:瓶颈•DNS解析相对较慢的（需要数秒的时间），网络爬虫通常采用DNS缓存和异步处理的方式来消除该瓶颈•DNS缓存机制：将最近解析成功的主机URL放入DNS缓存中异步DNS•企业级的爬虫系统通常采用异步的DNS查询方式•DNS查询的线程T向DNS服务器发送查询消息，并且进入定时等待状态。得到DNS解析结果时，则立即通知相应的采集线程。•尝试等待的次数为5的倍数，等待的时间随着尝试的次数的增加而指数级增加，最后一次等待的超时时间为90秒左右。桌面爬虫•只需要搜集到所有需要建立索引的文件路径•监视主机的活动，对新建立或者内容被改变的文档，加入索引或者修改相应的索引。礼貌性•爬虫总是希望同一时刻下载上百个甚至更多的网页。•影响真实用户的访问•网络爬虫应当遵从礼貌策略（politenesspolicy）：–不会同时在同一网站上抓取多个页面–同一服务器的两次请求之间有一定的等待时间•网络服务器禁止不遵从礼貌性原则的爬虫访问的访问每秒下载100个网页，每分钟最多可以下载1个页面，则请求队列中至少需要来自6000个不同网站的URL。robots.txt•爬虫限制协议（robotsexclusionprotocol）User-agent:*Disallow:/newsAllow:/advertiseUser-agent:GooglebotDisallow:Sitemap:第一个命令块要求所有的爬虫可以访问/advertise目录下的网页，但是不能访问/news目录下的网页。第二个命令块规定Googlebot爬虫可以爬取该网站的所有内容。第三个命令块给出本站的网站地图，这是一个可选的指令。网站地图•网站有时候希望主动告诉爬虫程序某些网页的更新频率，以实现新内容的快速获取。•或者网站希望将一些不能被爬虫发现的信息被爬虫抓取。•网站地图（sitemap）给出一个解决这种问题的简便办法。urlloc=Beverly+Hills+90210&id=C279796CE42B4762B8F51C21020BF248/loc/urlurlloc=world+news/loclastmod2012-06-13/lastmodchangefreqalways/changefreq/urlurlloc=local+news/locchangefreqalways/changefreqpriority0.8/priority/url时新性•高可用性的搜索引擎应该将最新的网页内容呈现给用户。•静态页面:HTTP协议提供了HEAD命令•动态生成的页面:必须下载网页全部内容时新性定义•时新性一般定义为所下载的所有页面中新页面所占的比例。•对时新性进行优化的办法是不下载这些频繁更新的页面。时新性年龄•假设某个页面的变化频率为λ，即该页面每天变化λ次。该页面被采集t天之后，其年龄的期望值为：Ageλ,t=P页面在时刻t被更新t−xdxt0•式中t−x为页面的年龄，将年龄乘以其概率。网页的更新一般遵循泊松分布。•将上式中的概率P替换为泊松分布，得到：Ageλ,t=λe−λxt−xdxt0当λ=1/7，也就是每周更新一次时，页面年龄期望值的曲线如图。-1-0.500.511.522.5302468agedayY值线性(Y值)主题爬虫•垂直搜索引擎能够为用户提供更准确的内容和更好的搜索体验•主题爬虫:需要对更加聪明的爬虫，自动判断并下载与给定主题相关的页面。主题爬虫基本结构•相关性计算–链接的锚文本–页面内容分布式爬虫•采用分布式爬虫的原因：–第一，可以利用更多的计算资源进行信息采集，包括CPU、内存、存储和网络带宽等。–第二，可以将爬虫服务器放在被采集网站的距离较近的地方，以提高信息采集的效率。–第三，采用分布式爬虫可以减少每个服务器处理的网站数量。•每个爬虫实例根据一定规则，承担对特定网站内容的爬取–使用URL中的主机部分进行HASH计算得到。考虑地域、字母顺序、网站规模、更新频率等先验知识。•一个网站只由一个爬虫处理：–URL分配的不均衡–容易遵守礼貌性策略–降低爬虫之间交换URL的数量和频率return网页内容提取•搜索引擎在对内容进行索引之前，必须从网页中去除这些噪音信息•Observation:正文部分的HTML相对较少Finn等人基于这个观察提出了一个简单的算法。目标函数•bn=1表示第n个词是标签，否则bn=0。•寻找正文开始的最小位置i和正文结束的最大位置j，最大化小于i和大于j的标签数量，与介于i和j之间的非标签的数量。bn+1−bn+jii1bnNjlimitation•只有当非正文部分的词条标签比例小于正文部分的词条标签比例，该算法才能工作。•去除该限制的启发式策略包括：–采用搜索窗口，对低斜率部分进行搜索–利用标点符号判定正文部分dom•Gupta等人（2003）提出一种基于DOM结构提取这要内容的方法。使用多种技术过滤掉树节点中的图片、脚本、广告、连接列表、布局表格等，最后留下内容部分。•Yu等人（2003）利用网页的视觉特征，构建出网页可视块的布局结构，并用于提取正文内容。•基于文档斜率的内容提取方法适用于于仅存在单个内容块的网页，基于DOM树的方法对于具有多个内容块的网页也具有很好的效果。return字符编码•在互联网上的网页采用数十种编码方法•目前使用最广泛的西文字符集及其编码是ASCII字符集和ASCII码–标准ASCII字符集：使用7个二进位对字符进行编码，共有128个字符，其中有96个可打印字符–扩展ASCII字符集：使用8位代码。GB码、国标码•GB2312-1980：1980年发布的《信息交换用汉字编码字符集基本集》，常被通称为国标码。•GB2312编码通行于我国内地。新加坡等地也采用此编码。•冲突：每个字节第8bit设置为1同西文加以区别，如果第8bit为0，则表示西文字符。•GBK编码标准兼容GB2312，共收录汉字21003个、符号883个，并提供1894个造字码位，简、繁体字融于一库。Unicode•除了以上编码外，世界上还存在着几十中编码方式，同一个二进制数字可以被解释成不同的符号。•Unicode编码将世界上所有的符号都纳入其中，从根本上消除了乱码。•常见：UTF-8,UTF-16,UTF-32.UNICODEUTF-800000000-0000007F0XXXXXXX00000080-000007FF110XXXXX10XXXXXX00000800-0000FFFF1110XXXX10XXXXXX10XXXXXX00010000-001FFFFF11110XXX10XXXXXX10XXXXXX10XXXXXX00200000-03FFFFFF111110XX10XXXXXX10XXXXXX10XXXXXX10XXXXXX04000000-7FFFFFFF1111110X10XXXXXX10XXXXXX10XXXXXX10XXXXXX10XXXXXXreturn去重•互联网中有30%左右的网页是重复的或者相似的。•重复的信息不但不会给用户带来新的信息，还会增加爬虫、索引和检索的工作量和存储量。•两类任务：URL去重和内容去重URL去重•爬虫解析所下载的网页，分析网页内的URL，将新发现的放入待下载队列等候下载。•爬虫需要一种快速的算法决定新发现的URL是否已经在等待下载或已经被下载。•在小型系统中，基于树结构的方法可以很好的满足要求。Bloomfilter•HASH表的一个缺陷是较高的冲突率•布隆过滤器（BloomFilter）:通过多个HASH函数降低冲突的发生–如果这些HASH函数中任何一个判断该元素不在集合中，那肯定就不在–相反，如果它们都判断该元素已经存在，则该元素存在的可能性很大。假设我们有一个如下图所示的二进制位数组集合，每一个二进制位标识某个hash值是否出现过。S={x1,x2,…,xn}，BloomFilter使用k个相互独立的哈希函数（HashFunction），它们分别将集合中的每个元素映射到{1,…,m}的范围中。m在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位）。BloomFilter的错误率•BloomFilter的错误率取决于哈希函数的个数和位组的大小。–k=ln2·(m/n)时，错误率取得最小值。–在错误率不大于є的情况下，m至少要等于nlog2(1/є)才能表示任意n个元素的集合。内容重复检测•完全重复内容的检测：–不考虑字符位置：所有字符的和作为校验和–考虑字符位置：循环冗余校验CyclicRedundancycheck–复杂的散列算法，如MD5、SHA1近似重复文档的检测•近似重复的网页：相似度超过一个很高（90%）的阈值•场景：–检索：O(N)–发现：O(N2)•去重算法的效率要求非常高。Shingling算法•基于词袋（BagofWords）方法不够高效•Shingling算法•文档d的n-shingle为d中所有n个连续词的序列EG:“Informationretrievalistheareaofstudyconcernedwithsearchingfordocuments”，4-shingling：“Informationretrievalisthe”、“retrievalisthearea”、“istheareaof”、…、“withsearchingfordocuments”。steps1)获取文档的词表。从网页中删除HTML标签、标点符号，提取词汇列表。如果是中文网页，提取所有的字；2)提取n-gram序列，通常使用重叠的n-gram序列；3)计算每个n-gram的哈希值，得到哈希值集合H(d)；4)对H(d)中的元素实施M次独立的随机置换，取每次置换后的最小值形成大小为M的集合𝜓(d)，得到d的梗概。•通常使用64位以上的hash值，M取值大于200。对于给定的两篇文档d1和d2，其相似度为|𝜓(d1)⋂1𝜓(d2)|∕𝑀。fingerprint生成指纹的算法框架如下：1)获取文档的词表。从网页中删除HTML标签、标点符号，提取词汇列表。如果是中文网页，提取所有的字；2)提取n-gram序列，通常使用重叠的n-gram序列；3)根据某些选择