搜索引擎进行信息检索的优化策略方法(关键词:搜索引擎PageRanky网络链接图一矩阵汇点目录目录(组图))

　　搜索引擎进行信息检索的优化策略方法(关键词:搜索引擎PageRanky网络链接图一矩阵汇点目录目录(组图))

　　中文搜索引擎中网页排序模型的优化与实现摘要 由于网页质量千差万别，对网页进行基于网络链接图的质量排序变成了现代搜索引擎 的一个重要部件。本文详细介绍了两种目前使用较为广泛的网页排序算法，并采用了 PageRank 算法应用于实际系统。在对网页排序模块的实现进行优化时，我们系统分析了造 成*敏*感*词*稀疏矩阵一向量乘法运算低效的原因，并结合网络链接图的实际情况提出了几种 不同的优化策略。然后，我们采用了其中五种优化策略作了实验性能比较，并综合考虑各 种优化策略的运算效率和存储量需求，选择了适合实际系统的优化策略。同时，我们提出 Pa‘geRank 算佳在实现时的一个变通处理一除汇。最后，本文阐述了搜索引擎未来的发展 趋势。 关键词:搜索引擎 PageRanky 网络链接图一稀疏矩阵汇点 目录 文摘 英文文摘 作者声明 章绪论1.1.引言 1.2.搜索引擎的整体架构 1.3.超链接的网络结构 章网页排序算法2.1.筛选出高质量页面的规则前提 2.2.查询与权威信息源 2.3.Web 环境下页面链接关系的利用 2.4.网页排序算法 2.4.1.HITS 算法 2.4.2.PageRank 算法 2.5.关于网页质量的几个问题 章高效的PageRank算法的实现 3.1.稀疏矩阵-向量乘法运算的优化 3.1.1.底层分析 3.1.2.分块技术 3.1.3.软件优化 3.2.网络链接图中汇点的消除 3.2.1.什么是除汇 3.2.2.如何除汇 章优化实现与实验数据分析4.1.PageRank 的基本实现技术 4.2.分块策略 4.3.优化实现 4.3.1.不收录零元的固定大小分块策略的实现 4.3.2.行压缩存储策略的实现 4.3.3.限定长度行压缩存储策略的实现 4.3.4.针对网络链接图的稀疏矩阵存储策略的实现 4.3.5.矩阵重排策略的实现 4.4.实验数据分析 4.4.1.运算效率分析 4.4.2.存储量需求分析 4.4.3.实际应用 章网络信息检索技术未来的发展参考文献 致谢 绪论1.1 引言 Internet 正以200%的用户增长率迅速发展，成为人们工作和生活不可缺少的信息来 源。

　　到目前为止，Google 上可索引的网络页面数达13.2'7 亿(U，而且每天以几百万的数度 递增。与此同时，Web 文件具有分布、动态变化、结构复杂等特点，使得用户根本无法 了解庞大的、瞬息万变的信息资源。由此，人们在信息海洋中搜索自己所需要的信息的能 力显得愈发重要。传统的信息搜索技术荃于较规范的信息库，相对于Web 上的信息总量， 总数规模比较小。同时，由于网络信息固有的特点，同在网络上的不同页面，不能受到相 同的对待，这就是网页重要性的问题。因此，在网络信息获取及检索过程中，有必要引入 页面外因素加以综合考虑，如信息源的名望、质量和引用数等。 网络信息检索的发展已初具规模。搜索引擎成了人们在网上检索信息的必要工具。现 行的搜索引擎有索引基于Web 机器人的Altavista,InfoSeekGuide,Excite 和Google 还有基于分层结构和模板的Yahoo和ALIWEB 等121 除搜索引擎外，还有其它诸如软件 代理和合作过滤系统等信息检索技术。有人已经将机器自学习与信息检索结合起来以提高 信息检索的效能3()4(1 在经典的信息检索系统中，系统的性能一般由三方面评定:查全率，查准率，前功 个页面的查准率。

　　在网络信息检索系统中，网页的质盘千差万别，所以检索结果仅与主题 相关还远远不够。现代搜索引攀重视的，己不再是简单地向用户提供与查询条目相关的页 面信息，利用网络链接结构来提高检索结果质童的方法开始获得重视. 网络爬行器(WebCrawler)的创始人Pinkerton 曾打过这样一个比方:“来设想一下 我们走进一个图书馆并对管理员说 旅‘游’，图书管理员会给你一个白脸”。当然，管理员 实际上不会木无表情地盯着你，而是会向你多问一些问题以得到对问题更好的理解。 不幸的是，搜索引擎不会像图书管理员那样问问题以集中搜索范围，也不能像人类那 样可以依仗判断或经验。因此，网页基于相关性(Relativity)的排序变得非常重要。 本课题是在己有的对中文搜索引擎原型的开发基础上，对网页排序模块进行开发。对 网页排序算法进行研究，实现及实现手段上的优化。目前存在的系统FlyingSender 在Linux 下用C/C++实现，基本模块已经完成。我们将在此基础上开展对网络信息检索技术的进一 步研究。 论文首先简单介绍了搜索引擎的整体构架，阐述网页排序模块在整个系统中的位置。 其次详细介绍了两种网页排序算法一一HITS 算法和PageRank 算法(在实际系统中我们 采用后者)。

　　接着，我们从对优化的实现入手，主要探讨了*敏*感*词*稀疏矩阵户向量乘法运算 如何在运算时间和空间消耗上达到高效，并提出了几个自己的观点;同时提出 PageRank 算法在实现时的一 个变通处理— 除汇。然后，我们用详实的实验数据对各种稀疏矩阵- 向量乘法运算的优化策略作了详细比较，并根据实验结果结合运算效率和存储量消耗选择 了适合实际系统的优化策略。最后，我们对网络信息检索技术的未来发展作了初步探讨。 1.2.搜索引擎的整体架构 搜素引擎的结构和工作流程如下 (参看图1.1).- 图1.1 搜索引擎的塞本结构 I、从一组自定义的*敏*感*词*页面开始，域名解析器(URLResolver)将域名转化为绝对 URL 地址即IP 地址，提交给搜索机器人 (Crawler). 我们在整体测试中发现，如果让域名解析器逐个解析域名，它将成为整个系统的 瓶颈。于是我们在本地设置了一个DNS 服务器，并采用异步10 和多线程的方法，尽 量让程序使用CPU 的资源，减少对网络或硬盘的操作次数，从而提高了整个模块的 效率。 参考文献[1] [2)RichardK.Belew,JudeW.Shavlik.MachineLearningandInformationRetrieval [3]H.Chen.MachineLearningforInformationRetrieval:NeuralNetworks,Symbolic LearningandGeneticAlgorithms.JASIS.April1995,46(3):194-216 (4]JunghooCho,HectorGarcia-Molina.TheEvolutionoftheWebandImplicationforan IncrementalCrawler.Stanford,CA94305,1999 [5]RFC1320TheMD4Message-DigestAlgorithm 汇6]http/://webmasters/rank.html (71NeeranM.Karnik,AnandR.Tripathi.DesignIssuesinMobileAgentProgramming Systems.UniversityofMinnesota.1998 [8]DIGITAL EQUIPMENT CORPORATION.AltaVista search engine.http:H / (9]JonM.Kleinberg.AuthoritativeSourceinaHyperlinkedEnvironment.Poceedingofthe MinthAnnuaACM-SIAMSymposiumonDiscreteAlgorithms.1998,668-677 [101WilliamGoffman.AMathematicalProfessionalSocietySignalstheMaturingof ScientometricsandInformetrics.TheScientist.Aug1995,9(16) [川JamesE.Pitkow.CharaterizingWorlderWideWebEcologies.PhDthesis.GeorgiaInstitue ofTechnology.June1997 [12]PeterPirolli,JamesPitkowandRamanaRao.SilkrfomaSow'sEar:ExtractingUsable StructurerfomtheWeb.InMichaelJ.Tauber,VictiruaBellotti,RobinJeffries,Jock D.MackinlayandJakobNielsen,editors,ProceedingsoftheConferenceonHumanFactors inComputingSystems:CommonGround.April1996:118-125 (13]RonWeiss,BienvenidoVelez,MarkA.Sheldon,ChanathipManprempre, PeterSzilagyi, AndrzejdudaandDavidK.Gifford.HyPursuit:AHierarchicalNetwork SearchEngine thatExploitsContent-LinkHypertextClustering.InProceedingsofthe7'ACM ConferenceonHypertext.March1996:180-193 [14JEllenSpertus.Parasite:MiningStructuralInformationontheWeb.InProceedingsofthe SixthInternationalWWWConference.SantaClaramUSA,April1997 [15)SougataMukhe 巧eaandJamesD.Foley.ShowingtheContextofNodesintheWorldWide Web.InProceedingsofACM CHI'95ConferenceonHumanFactorsin Computing Systems,volume2ofShortPapers:WebBrowsing.1995,326-327 致谢 在长达两年半的*敏*感*词*学习期间，我们将一个最初理论上的设想转化为工程上的初步 实现，并对运算性能进行了优化，为将来进一步展开研究奠定了基础。在此，我十分感谢我 的导师邵志清教授在研究过程中给予我悉心的指导、全力的支持和不断的鼓励. 在硕士*敏*感*词*的学习期间，我还十分感谢计算机系各位老师为我们创造的良好学习氛 围，多次的学术讨论会不仅让我们了解了其他同学的工作，也进一步扩宽了知识面，提高了 科研能力。