WebSpider的原理与结构(二).ppt

Web Spider的原理与结构,（二） Web Spider的Url检索算法,引 言,Web Spider的url处理过程简介 在信息采集的过程中，为了避免重复采集相同的页面，需要记住已经发现的页面（包括已经采集过的页面，正在采集的页面和等待采集的页面）。采集中凡遇到一个页面，需要判断该页面的URL是否已发现的url。若不是新发现的url，则将其丢弃；否则将它放入待采集url队列。,引言,url检索算法的速度和所占用的内存空间的大小都什么重要。 特别是在有中心节点的分布式Web Spider中，如果url检索算法的速度较慢的话就会在中心节点形成瓶颈，严重影响整个系统的采集速度和可扩展性。 现有算法占用存储空间较大，对重复率高的url集合检索速度较慢。,Rabin指纹算法,Rabin指纹生成算法基于由美国哈佛大学教授拉宾(Rabin)提出的方法，其思想如下：,Rabin算法性质,拉宾的方案具有如下性质： 如果字符串A的指纹不同于字符串B的指纹，那么字符串A也不同于字符串B：f(A)f(B)=AB 运算速度较快,3 RP算法,基本思想：,RP算法算法描述,RP算法特点,记录一条url只需一位 判断url是否已经访问过时，只需用索引寻址，即基址加上偏移量，对相应的位的状态进行判断即可。这样即简化了检索的过程，提高了检索速度，又有效地节省了存储空间。,实验,分析,HfIp为hash函数的算法中，当一个要检索的url的hash值对应的地址已经保存有url时必须要进行字符串的匹配。从网上采集的url中重复的较多，那么这种字符串匹配是经常发生的。当两个较长的url重复时，就可能得进行上百次字符的匹配，所以严重影响了检索的效率，用时较多，速度较慢。随着实验的url数量增加，这种字符串比较发生得越频繁，速度就更慢。但是RP算法则不存在这样的情况，对每个url的比较都是一次一个位的状态的判断而已，所以用时较少，速度较快。,相关算法研究比较,查找树 Igloo1.2用的就是用Tries树进行url检索的。 Trie树利用字符串的公共前缀来节约存储空间。用于url检索时，检索算法的时间代价是O(n)，其中n是Trie树的层数(包括分支结点和元素结点在内)，也就是url的字符串长度。,查找树,但是，url的组成除了字母外还包括一些符号等，平均长度也要50个字符以上，某些较长的url要超过100个字符，那么除了较靠近根的节点由于存储的都是协议部分而孩子节点较少，其他的一般都有几十个孩子节点，树高要超过50，每个节点存储一个字符，这也需要很大的空间，一般内存空间是无法承受的。而且一次检索都要做几十次甚至上百次字符比较，使得检索速度较慢。,hash算法,首先用一个hash函数计算url的hash值，然后到hash值对应的地址去检索，如果该地址未存储url则此url为新发现的url，将其存储到此地址；如果该地址已经存储了url则同该地址处的url逐一进行比较（链式解决冲突的情况下），找到相同的url，则此url不是新发现的，做丢弃处理，未找到则将其添加到此链表中。,hash算法,用hash算法对url进行检索，要存储url，占用存储空间较大。在检索过程中根据url的hash值寻址，大大提高了检索速度，但是当url重复率较高的时候，这种方法就不得不进行较多的字符串匹配操作，这将严重影响url的检索速度，然而，Web Spider采集过程中从页面解析出来的url却是重复率非常高的。所以这种算法应用在Web Spider上进行url检索，也很难获得十分理想的效果。,其他基于Rabin算法的url检索算法,chao设计了一个基于Rabin指纹算法的url检索算法。该算法将通过Rabin算法计算得到的url的指纹映射成16进制数组成的字符串，再把此字符串存储在一棵键树中，然后利用此键树对url检索。,Chao算法与RP算法比较,鸣谢,感谢陈涛师弟对本环节的实验提供大力支持,RP算法的局限,对小量的url检索没有优势 可能发生冲突,美丽的梦想,记忆函数 设计一个函数Ff（x），F的初态f（x0）。现xa经过f（a）计算得到F。当下个数据x参加计算得到F，我们就能通过F判断出x是否等于a。,心得体会,实验是一种研究，探索和验证方法，所以不要在实验