webspider的原理与结构(二)

《webspider的原理与结构(二)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、WebSpider的原理与结构（二）WebSpider的Url检索算法引言WebSpider的url处理过程简介在信息采集的过程中，为了避免重复采集相同的页面，需要记住已经发现的页面（包括已经采集过的页面，正在采集的页面和等待采集的页面）。采集中凡遇到一个页面，需要判断该页面的URL是否已发现的url。若不是新发现的url，则将其丢弃；否则将它放入待采集url队列。引言url检索算法的速度和所占用的内存空间的大小都什么重要。特别是在有中心节点的分布式WebSpider中，如果url检索算法的速度较慢的话就会在中心节点形成瓶颈，严重影响整个系统的采集速度和可扩展性

2、。现有算法占用存储空间较大，对重复率高的url集合检索速度较慢。Rabin指纹算法Rabin指纹生成算法基于由美国哈佛大学教授拉宾(Rabin)提出的方法，其思想如下：Rabin算法性质拉宾的方案具有如下性质：如果字符串A的指纹不同于字符串B的指纹，那么字符串A也不同于字符串B：f(A)≠f(B)=>A≠B运算速度较快3RP算法基本思想：RP算法算法描述RP算法特点记录一条url只需一位判断url是否已经访问过时，只需用索引寻址，即基址加上偏移量，对相应的位的状态进行判断即可。这样即简化了检索的过程，提高了检索速度，又有效地节省了存储空间。实验分析HfIp为ha

3、sh函数的算法中，当一个要检索的url的hash值对应的地址已经保存有url时必须要进行字符串的匹配。从网上采集的url中重复的较多，那么这种字符串匹配是经常发生的。当两个较长的url重复时，就可能得进行上百次字符的匹配，所以严重影响了检索的效率，用时较多，速度较慢。随着实验的url数量增加，这种字符串比较发生得越频繁，速度就更慢。但是RP算法则不存在这样的情况，对每个url的比较都是一次一个位的状态的判断而已，所以用时较少，速度较快。相关算法研究比较查找树Igloo1.2用的就是用Tries树进行url检索的。Trie树利用字符串的公共前缀来节约存储空间。用于

4、url检索时，检索算法的时间代价是O(n)，其中n是Trie树的层数(包括分支结点和元素结点在内)，也就是url的字符串长度。查找树但是，url的组成除了字母外还包括一些符号等，平均长度也要50个字符以上，某些较长的url要超过100个字符，那么除了较靠近根的节点由于存储的都是协议部分而孩子节点较少，其他的一般都有几十个孩子节点，树高要超过50，每个节点存储一个字符，这也需要很大的空间，一般内存空间是无法承受的。而且一次检索都要做几十次甚至上百次字符比较，使得检索速度较慢。hash算法首先用一个hash函数计算url的hash值，然后到hash值对应的地址去检索

5、，如果该地址未存储url则此url为新发现的url，将其存储到此地址；如果该地址已经存储了url则同该地址处的url逐一进行比较（链式解决冲突的情况下），找到相同的url，则此url不是新发现的，做丢弃处理，未找到则将其添加到此链表中。hash算法用hash算法对url进行检索，要存储url，占用存储空间较大。在检索过程中根据url的hash值寻址，大大提高了检索速度，但是当url重复率较高的时候，这种方法就不得不进行较多的字符串匹配操作，这将严重影响url的检索速度，然而，WebSpider采集过程中从页面解析出来的url却是重复率非常高的。所以这种算法应用在

6、WebSpider上进行url检索，也很难获得十分理想的效果。其他基于Rabin算法的url检索算法chao设计了一个基于Rabin指纹算法的url检索算法。该算法将通过Rabin算法计算得到的url的指纹映射成16进制数组成的字符串，再把此字符串存储在一棵键树中，然后利用此键树对url检索。Chao算法与RP算法比较鸣谢感谢陈涛师弟对本环节的实验提供大力支持RP算法的局限对小量的url检索没有优势可能发生冲突美丽的梦想记忆函数设计一个函数F＝f（x），F的初态f（x0）。现x＝a经过f（a）计算得到F’。当下个数据x’参加计算得到F’’，我们就能通过F’’判断

7、出x’是否等于a。心得体会实验是一种研究，探索和验证方法，所以不要在实验前就把实验结果定下来了。注意多交流和自己表述的准确性，使我们的实验室真正成为一个研究的团队。执着和自信能给你带来无穷的力量抓住一闪而过的灵感TheEndThankyou！