Robot算法分析

总第168期舰船电子工程Vol, 28 No 62008年第6期Ship Electronic EngineeringRobot算法分析江禅志王才元(海军潜艇学院青岛266071)摘要介绍 Robot搜索算法与启发式搜索箅法分析 Robot广度优先策略深度优先策略以及广度、深度结合策略探索 Robot优化策略关键词Robo搜索算法; Robot优化策略中图分类号TP01.6Analysis on the robot ArithmeticJiang Chanzhi Wang CaiyuanNavy Submarine Academy, Qingdao 266071)Abstract This paper introduces search arithmetic and heuristic search arithmetic, and analyzes robot extent precedencetrategies, robot deepness precedence strategies and the combination of this two strategies, and makes a research in Robot opti-Key words Robot approach, Robot seeking strategiesClass Number TP301.6Extract the hyperlinks from d;引言Let U the set of URLs cited in these hyperlinks在搜索引擎中,信息采集 Robot的效率会直for each URL u in U接影响搜索引擎的更新周期和数据的及时性,Robot的实现决定搜索引擎的性能。在搜索网页时,由于各个网站的相应时间不同,存在 Robot的最佳搜索线路问题。Enqueue操作是往队列中F添加一个新的2 Robot搜索算法URL, Dequeue操作给队首的URL作为一个访问标2.1 Robot搜索算法的基本描述记( removed),相当于把队首的URL弹出队列,当所有的URL都被访问之后,则判断条件EmpyLet be a list of initial URLs(F)为真。在实际搜索过程中,由于网络带宽的Let F be a queue;限制和另一端的HTTP服务器的反应延时原因,第For each URL i in I9行的Cet操作耗时最长。Enqueue(i, F);在 Robot的深度及广度优先策略中, Robot收集Web页面至本地数据库中对网页的重要性并没While Empty(F)Dequeue(F)有考虑,于是就出现了启发式网页搜索算法,以期d+-Get(u);//request document d pointed by u使得中国煤化工高2.2CNMHG·收稿日期:2007年7月18日,修回日期:2007年8月30日作者简介:江禅志,男,高级工程师,研究方向:作战模拟2008年第6期舰船电子工程启发式算法基本描述:址且已经被搜索过,则对其引用计数值加1,形成下Uset←网站首页的URL次搜索时的待搜索抵制的优先权加权值,如果未While Uset I null被搜索过,则将该地址加入到地址列表中3.2深度优先策略select the highest ranked URL from Uset into URL. Next它是从起始结点出发,一直搜索到那些不含任if Value( URL. Next)=high threshold then3.3广度-深度结合策略save web. page as a target web page:Robot沿着网络上的超链接搜索,当它到达Else个新的网站,能对引用该网站的超链接进行统计,add all hyperlinks into Uset并对该网站进行检索,且将检索结果呈现给用户End if接着为所获得的URIs运行搜索引擎程序,重复以End while上的步骤。其中,Ⅴaue()为评价函数,用来评价一个网页·广度优先策略:能找到两个Web文档之间或网页中的一个超链接。对网页的评价就是对网的最短路径,不会出现陷进wwW深层文档中而页中关键词相应的权值进行累积;对于超链接的评回不到出发点的情况。但是对于深层Wb文档的价是对该链接的地址信息、 Anchor提示文本信息搜索花费的时间较长。以及所在段落的正文进行类似计算。low. threshold深度优先策略:能遍历一个Web站点或嵌和high. threshold为给定的常量,权值低于bow.套很深的文档集合。但是如果由于Web结构很threshold的URL被认为是无用URL,终止搜索;权深,会造成搜索回不到起点的情况值高于 high threshold的网页被认为是目标网页·广度-深度结合策略:当搜索引擎搜索过启发式搜索算法采用一个集合Uset来储存下个Wb站点或文档时要作上标记,避免搜索引擎步可以访问网页的URLs(Ue初始状态只包含对同一Web站点或文档重复搜索,在搜索引擎的个指向网站首页的URL),通过评价函数对Uset服务器上返回一个值代表该Wb站点或文档已经中的每一个网页进行评价,选取最佳URL对网页被访问过,得到的是能够及时更新的检索结果,具进行评价如果高于某个给定的阈值,则认为得到有很高的查全率。但是当同一时间用户过多时,服个目标网页;否则将网页上所有的超链接加入到务器负担过重可能会造成信息阻塞Uset集合中,如此反复直至Uset为空。启发式搜索算法大大缩短了 Robot信息采集时间4 Robot优化策略3 Robot的遍历策略分析4.1避免重复搜集分布式 Robot系统,注意避免两个 Robot对同Robot的遍历策略是指当 Robot搜索到一个文个文档搜索两次,可以定义两个表,“未访问表档之后,下一步应转到哪个文档的策略问题。由于存储准备取入待访问队列的URL,“已访问表”中Robot检索的 Internet文档数量巨大, Robot遍历策存储已经请求过网页的URL,合理解决多个 Robot略非常重要。 Robot的遍历策略有广度优先策略,并发访问队列F的问题,使队列维护操作的时耗深度优先策略以及广度、深度两者的结合。小于Get操作的时耗。3.I广度优先策略域名与IP的对应关系存在四种关系:一对一度优先策略中把一个Web页面中所有超链接对多、多对一、多对多,后三种情况有可能造成重搜索完,再继续下一层的搜索,直到搜索到最底层复搜集。找出指向同一物理位置URL的多个域名具体方法:从URL列表中取得第一个URL对和P中国煤亿亍名和然后相应的Web文档进行预处理,并在该文档中找到指把这链接出的最开向其他Web文档的超链接。 Robot将找到的超链接始的CNMHG结果一样,应该与 robot中的屏蔽地址列表中的URLs作比较:不是归为一组。以后搜集的时候可以只选择其中的搜索范围内的地址则丢弃,如果是搜索范围内的地(下转第209页)2008年第6期舰船电子工程采样系统都有个延迟,延迟最小就是保证延迟定性,具有很强的使用价值时间在一个开关周期内。如图5由于定时器中断和AD采样中断服务处理程序的指令数固定,因而每周期内AD采样的位置相对于开关周期的开始时间是固定的。选择合适的AD采样滤波参数,更[1] Brown Marty. Practical Switching Power Supply Design有利于跟踪电感的平均电流。AD中断间隔开关(2]张占松蔡宜三开关电源的原理与设计M]北京:周期的开始时间很短,可以保证数字控制器有足够子工业出版社,1998的时间执行完。[3]邢岩蔡宣三.开关型电压调节系统数字仿真的一种新6结语算法[J].通信学报,1988,19(3)[4]李学海.PC单片机实用教程[M].北京:北京航空航本文叙述了DSC控制高压电源的方法,对全天大学出版社,2002桥移相PWM变换器和高压变压器进行了设计。[5]刘和平郑群英.dPC通用数字信号控制器原理与应并在实际应用中证明了此高压电源的可靠性和稳用2007(上接第161页)该服务器时,首先浏览这个文件。根据指定URL个进行搜集,选择的时候应该优先选择有域名的,获取文档:从服务器端得到对应的文档。有的网站对于直接用P访问是被禁止的4.4对已经获取的URL充分处理4.2首先搜集重要的文档Robot在运行过程中,为了提高 Robot与URL体现网页重要度的特征有:1)网页的入度大,集合的交互效率,我们必须对庞大URL列表进行表明被引用的次数多;2)某网页的父网页入度大;充分处理。URL实施模块包括:管理拒绝 Robot访3)网页的镜像度高;4)网页的目录深度小,易于用问的URL,通过 Robot.txt文件说明哪些链接不可户浏览到。访问及拒绝哪些Robo访问等;获取新的URL并准由于搜索引擎开始工作时,前三项特征无法确备添加列表中,从已经获取的文档中分析出新的定,只有最后一项不需要知道网页内容可确定某个URL;添加URL之前的加工处理:URL的存储可以URL是否重要的标准,由于URL长度都小于256在存储占用空间以及访问速度两个方面进行优化。个字符,这使得URL目录深度易判别,所以最后一首先把已获取的URL按字典顺序排列,只存储项是最值得考虑的指导因素。URL的增加部分,可以减少70%的存储量。利用4.3加快 Robot访问速度Hash的方法存储URL,可以加速URL的访问。另形成不同更新时间间隔的URL列表。不同的外。分配URL给不同的 Robot:把从源URL集合中URL一般都具有不同的更新时间间隔,在 Robot访读取的URL根据既定规则分配给不同的 Robot。问过程中,逐渐把URL根据其更新时间间隔归并到不同的URL列表中, Robot则依据时间间隔访參考文獻问,提高 Robot的搜索效率把地域相近的URL分配给同一个 Robot采集,使每一个 Robot所需访向[1]李晓明,宏飞,王继民信息检索[M].北京:科学出的Web服务器的距离较近;开发多种类型的Ro[2]苏新宁信息检索理论与技术[M]北京科学技术文献bot。包括:定题采集型、定点报道型和热点追踪出版社,2004型不同语种的 Robot,根据时差对Rbot分组等。[3]孙建军,成颖信息检索技术[M]北京:科学出版社,与服务器方协作。开发生存于某些站点服务器的 Robot,在服务器端跟踪服务器上文档的修改、[4]宋聚平搜索引擎中 ROBOT搜索算法的优化[J情报删除、增加等情况,根据不同情况向搜索引擎服务器主动发送信息。或者在服务器上生成一个关于[5】王YH中国煤化工佥索关键技术分析CNMHG服务器上文档变更情况的特殊文件,当 Robot访问