一种基于非贪婪策略的网络蜘蛛搜索.pdf

第23卷第2期计算技术与自动化Vol123,No12
2004年6月ComputingTechnologyandAutomationJun12004

文章编号:1003-6199(2004)02-0035-05

一种基于非贪婪策略的网络蜘蛛搜索算法

李学勇1,田立军1,谭义红1,欧阳柳波2,李国徽3

(1.长沙大学数学与信息科学系,湖南长沙410003;2.湖南大学软件学院,湖南长沙410082;

3.华中科技大学计算机科学与技术学院,武汉430074)

摘要:在分析传统网络蜘蛛搜索策略缺点的基础上,提出了一种非贪婪的链接选择策
略,进而提出了一种基于非贪婪策略的启发式搜索算法。针对国外四所著名大学计算机系网
站中计算机论文资源的搜索实验表明,新算法可以有效提高搜索效率。
关键词:专业搜索引擎;网络蜘蛛;搜索策略;非贪婪策略
中图分类号:TP18;TP391文献标识码:A

AWebSpider’sSearchingAlgorithmBasedonNon-GreedyPolicy

LIXue2Yong1,TIANLi2Jun1,TANYi2Hong1,OUYANGLiu2Bo2,LIGuo2Hui3
(1.DepartmentofMathmaticsandInformationScience,ChangshaUniversity,Changsha410003,China;
2.SoftwareSchool,HunanUniversity,Changsha410082,China;
3.CollegeofComputerScienceandTechnology,HuazhongUniversityofScienceandTechnology,Wuhan430074,China)

Abstract:BasedontheanalysesofthedeficienciesofthetraditionalWebspider’ssearchingstrategies,
thispaperproposesanon-Greedylink-selectionpolicy.Thenaheuristicsearchingalgorithmbasedonnon-
Greedypolicyisproposed.Wevalidateournewalgorithmbyexperimentsofsearchingcomputer-relevantpa2
persontheWebsitesoffourfamouscomputerdepartments.Theresultsshowthatthenewalgorithmhasbet2
terperformance.
Keywords:topic-specificsearchengine;Webspider;searchingstrategy;non-Greedypolicy

图的遍历搜索策略(如广度或深度优先算法)已不
1引言再适用。以何种策略访问Web,成为近年来专业搜
索引擎网络蜘蛛研究的主要问题之一[3-11]。
近年来,随着WWW技术的广泛应用和人们针对这一问题,国内外的学者做了许多有益的
对个性化信息检索服务需要的日益增长,传统的通研究工作。目前的专业搜索引擎主要采用基于领
用搜索引擎,如Google、Fast、AltaVista和GoTo等域知识分析的“启发式”搜索策略,即先通过在线获
正面临巨大的挑战[1-3]。面对这一挑战,各类适应得的领域知识评价待访问链接的价值,借以推断信
特定人群需要的“专业搜索引擎”(Topic-Specific息资源的分布情况,然后按最好优先原则选择价值
SearchEngine)应运而生并引起研究者的重视[1,3]。最大的链接进行下一步的搜索。按照所采用的领
由于专业搜索引擎搜索的内容只限于特定主题或域知识和评价链接价值方法的不同,现有的搜索策
专门领域,因而被通用搜索引擎所广泛采用的基于略主要分为两大类:基于内容相似度评价的搜索策

收稿日期:2003-12-10
基金项目:国家自然科学基金(60203017)和国家科技基础性研究专项资金项目(2001DEA20016-02-04)资助。
作者简介:李学勇(1972—),男,湖南邵东人,博士研究生,讲师,研究方向:计算机网络,智能搜索引擎。

©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.
63计算技术与自动化2004年6月

略和基于Web结构评价的搜索策略。前者的主要计算器按照某种评价方法(如链接文本与预先定义
特点是利用页面中的文本信息作为领域知识指导的主题集的相似度)计算出每个链接的价值;暂时
搜索,并根据页面