硕士学位论文-搜索引擎排序算法的分析与研究.doc

学校代码 10254 密级 论文编号 上海海事大学上海海事大学 SHANGHAI MARITIME UNIVERSITY 硕士学位论文硕士学位论文 MASTER DISSERTATION 论论文文题题目 目 搜索引擎排序算法的分析与研究搜索引擎排序算法的分析与研究 学科学科专业专业 计计算机算机应应用技用技术术 作者姓名 作者姓名 傅茂忠傅茂忠 指指导导教教师师 高茂庭高茂庭 副教授副教授 完成日期完成日期 二二 九年九年五五月月 论文独创性声明论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果 论文中除了特别加以标注和致谢的地方外 不包含其他人或其他机构已 经发表或撰写过的研究成果 其他同志对本研究的启发和所做的贡献均 已在论文中作了明确的声明并表示了谢意 作者签名 日期 论文使用授权声明论文使用授权声明 本人同意上海海事大学有关保留 使用学位论文的规定 即 学校 有权保留送交论文复印件 允许论文被查阅和借阅 学校可以上网公布 论文的全部或部分内容 也可以采用影印 缩印或者其他复印手段保留 论文 保密的论文在解密后遵守此规定 作者签名 导师签名 日期 摘 要 I 摘 要 随着现代科技的进步 互联网得到了飞速的发展 逐渐成为人们日常学习 生活 工作中最重要的获取知识和信息的工具 进入 21 世纪以来 网络信息成 几何级数的增长 快速精确查找需要的信息变得越来越难 这使得发展搜索引 擎技术成为一种必要 它能帮助人们快速有效地获取信息 本文介绍了搜索引擎的概念及其发展历史 搜索引擎的分类 结构与工作 原理 搜索引擎的评价标准 常用的中英文搜索引擎 以及搜索引擎排序算法 作了简单的介绍 如何使广大网民快速找到所要的知识和信息资源 成为搜索引擎技术研究 的重点 本文针对一些已有算法 PageRank 算法 HillTop 算法 Direct Hit 算 法等存在的不足 即 PageRank 算法平均分配权威值 Hilltop 中利用 专家页 面 不合理 容易产生 Spam Direct Hit 算法处理重复点击 与新页面不理想 的问题 提出改进算法的思路 针对 PageRank 算法权威值的计算 引入非均衡 分配的思想 改进 PageRank 算法平均分配权威值的问题 引入社区发现技术来 改进算法 该算法利用社区作为 专家页面 不仅可以改善 Hilltop 算法找 专家页面 不合理的现象 而且对于 Direct Hit 算法处理新页面不理想 用户 重复点击等问题也能起到一定的效果 关键词 搜索引擎 排序算法 社区发现技术 PageRank HillTop Direct Hit ABSTRACT II ABSTRACT With the progress of the information technology Internet develops fast and becomes an important means of obtained the knowledge and information which may be used in people s study daily life and work Since we enter into 21th century the information of internet increased at a geometric progression Querying information become more and more difficult it becomes a need of developing the search engine technologies It can help people acquire information quickly and effectively This paper introduce the conception and the developing history classify structure and operating principles of the search engine At the same time it describes the common Chinese and English the evaluation standard of the search engine and introduces the common algorithm step by step How to make the searching be quick is the main point of the search engine researching This paper according to some existing algorithm and puts forward improving ways to solve the shortcomings of the existing algorithms Such as the PageRank algorithm s PR values which is equal division HillTop algorithm easily generate the spam because of utilizing the expert pages illegitimacy and non ideal processing methods for repeat spot bowling of the Direct Hit algorithm We induct the unbalance idea for PageRank algorithm s problems of not equal division and the discovery technology of community to settle the standing problems of HillTop algorithm utilize the expert pages illegitimacy and non ideal processing methods for repeat spot bowling of the Direct Hit algorithm This algorithm could be help for reducing the adverse effects caused by these algorithms At last we summarize the work of this paper and predict the future development of the search engine algorithm Maozhong Fu Computer Application Directed by Prof Maoting Gao ABSTRACT III Keyword Search Engine sorting algorithm the technology of the community discovery PageRank HillTop Direct Hit 目 录 IV 目 录 第一章第一章 绪论绪论 1 1 1 研究背景和意义 1 1 2 搜索引擎的发展历史 2 1 2 1 搜索引擎的起源 2 1 2 2 搜索引擎的现状 3 1 2 3 搜索引擎的未来 4 1 3 搜索引擎排序算法的演进 6 1 3 1 搜索引擎排序算法的起源和现状 6 1 3 2 搜索引擎排序算法存在的问题 7 1 4 本文的组织框架及所做工作 7 第二章第二章 搜索引擎概述搜索引擎概述 9 2 1 搜索引擎的分类 9 2 1 1 按所覆盖内容 9 2 1 2 按是否有人参与 9 2 1 3 按检索层次 10 2 2 搜索引擎的结构及工作原理 12 2 2 1 搜索引擎组成结构 12 2 2 2 搜索引擎工作原理 14 2 3 常用搜索引擎 15 2 3 1 常用中文搜索引擎 15 2 3 2 常用英文搜索引擎 17 2 4 搜索引擎的评价标准 19 2 5 本章小节 20 第三章第三章 搜索引擎常用排序算法及相关技术搜索引擎常用排序算法及相关技术 21 3 1 搜索引擎常用的排序算法 21 3 1 1 词频位置加权排序算法 21 3 1 2 PageRank 算法 22 3 1 3 Direct hit 算法 24 3 1 4 Bayesian 算法 25 3 1 5 Web Query 算法 26 3 1 6 Hilltop 算法 26 3 1 7 HITS 算法 27 3 1 8 竞价排名 27 3 2 搜索引擎的相关技术 28 3 2 1 SEO 技术 28 3 2 2 Spam 作弊技术 31 3 3 本章小结 34 第四章第四章 利用社区发现技术改进排序算法利用社区发现技术改进排序算法 35 4 1 PAGERANK算法及其改进分析 35 目 录 V 4 1 1 PageRank 算法优缺点分析 35 4 1 2 PageRank 算法改进思路 36 4 2 另两种常用算法及其改进思路 38 4 2 1 HillTop 算法 38 4 2 2 Direct Hit 算法 40 4 3 利用社区发现技术改进排序算法 41 4 3 1 什么是社区发现技术 41 4 3 2 利用社区发现技术改进排序算法的过程 42 4 3 3 算法总结 44 4 4 实验过程 45 4 3 1 实验环境 45 4 3 2 过程描述 46 4 3 3 实验结果 46 4 3 4 实验评价 48 4 5 结果分析 50 4 6 本章小结 50 第五章第五章 工作总结与展望工作总结与展望 51 5 1 工作总结 51 5 2 展望 51 致致 谢谢 53 参考文献参考文献 54 攻读硕士期间发表论文和参加科研情况攻读硕士期间发表论文和参加科研情况 58 一 发表的论文 58 二 参加的科研项目 58 绪 论 1 第一章第一章 绪论绪论 本章首先介绍了本课题的研究背景和意义 其次论述了搜索引擎的发展及 其未来 以及搜索引擎排序算法发展过程以及存在的问题 最后对本文的工作 安排和论文结构做了详细的说明 1 1 研究背景和意义 随着信息技术的进步 互联网作为信息的载体得到了飞速的发展 成为人 们学习 工作 生活中获取知识和信息的主要来源 根据美国因特网监测公司 网器 Netcraft 28 日宣布 1 截止 2 月底 全球互联网网站数量超过 1 6 亿 较一个月前增加了 450 万 达 162662053 据国外权威通讯社报道 网站 数量在 2005 年增加了 1700 万 在 2006 年增加了 2740 万 美国 德国 中国 韩国和日本的网站发展速度最快 过去两年间 博客及网上购物的兴起和创建 网站操作的简单化等因素结合在一起 使得网站数量猛增 现有搜索引擎给人们带来了很多方便的同时 也逐渐暴露了自身的一些问 题 这些弊端主要表现在以下方面 1 网络信息量过于庞大 网络错综复杂 没有特定的网络模型 描述不便 2 检索结果信息过多 有用信息不全 3 检索结果缺乏个性化 不能满足不同用户的需求 4 不同国家的搜索引擎差别较大 对不同语言的适应性较差 5 多媒体信息检索还不完善 6 网页的更新速度远远快于索引数据库的更新 7 垃圾网页过多 许多虚假广告 不健康信息 错误信息充斥互联网 8 广告的比例较大 干扰正常的浏览 如何快速准确的查找用户所需的信息成为互联网急需解决的问题 这就为 搜索引擎技术的发展提供了土壤 现有的排序算法有很多 如 PageRank 算法 2 HillTop 算法 3 Direct Hit 算法 4 等 但是没有一个是完美无缺的 本文在介绍 搜索引擎及其相关技术的基础上 结合已有的排序算法 提出了自己的解决思 路 以改善搜索引擎排序算法的质量 使用户能够快速准确的找到所需信息 同时也为以后排序算法的研究提供一个有价值的参考 绪 论 2 本文是在上海市教委科研项目 基于统计学习的数据挖掘技术研究 项目 编号 06FZ007 的支持下 开展搜索引擎排序算法的分析与研究 1 2 搜索引擎的发展历史 搜索引擎是用于帮助互联网用户查询信息的搜索工具 它以一定的策略在 互联网中搜集 发现信息 对信息进行理解 提取 组织和处理 并为用户提 供检索服务 从而起到信息导航的作用 下面将介绍搜索引擎的发展历程 1 2 1 搜索引擎的起源 简单地说 搜索引擎起源于传统的信息全文检索理论 5 即计算机程序通 过扫描每一篇文章中的每一个词 建立以词为单位的排序文件 检索程序根据 检索词在每一篇文章中出现的频率和每一个检索词在一篇文章中出现的概率 对包含这些检索词的文章进行排序 最后输出排序的结果 在早期的时候 互 联网上面的搜索引擎和今天人们常用的搜索引擎有所不同 早期的搜索引擎更 像是如今很多中文的 ICP Internet Content Provider 网站 把因特网中的资源 服务器的地址收集起来 由其提供的资源类型的不同而分成不同的目录 再一 层层地进行分类 人们要找自己想要的信息可按他们的分类一层层进入 就能 最后到达目的地 找到自己想要的信息 这其实是最原始的方式 只适用于因 特网信息并不多的时候 因为如果信息一旦多起来 查找的时候所花费的时间 就很长了 1990 年 互联网还没有得到全面的推广 但是 通过网络传输文件已经比 较普遍 真正意义上的搜索引擎是 1994 年创立的 Lycos 他由 Michael Mauldin 将 John Leavitt 的 Spider 程序 6 接入其索引程序中产生的 互联网搜索引擎除了需要有全文检索系统之外 还要有所谓的 蜘蛛 Spider 系统 7 即能够从互联网上自动收集网页的数据搜集系统 蜘蛛 系 统是 John Leavitt 开发的 并且由 Michael Mauldin 将这个系统融合到了 Lycos 搜索引擎里面去 它能够将搜集所得的网页内容交给索引和检索系统处理 就 形成了现在常见的互联网搜索引擎系统 当然 一个完整的搜索引擎系统还需 要有一个检索结果的页面生成系统 也就是要把检索结果高效地组装成万维网 页面 概括起来说搜索引擎是为查询而生的 用户需求的不断更新 发展是搜索 绪 论 3 引擎技术不断进步的动力 1 2 2 搜索引擎的现状 经过了多年的发展 现在的搜索引擎功能越来越强大 提供的服务也越来 越全面 当你登录某一个网站 在互联网上搜索各个网站的某一类内容 比如 输入 猪流感 希望得到最新 最全面的信息 你需要等待多长时间 几年前 人们希望十几秒 最多 30 秒钟就能得到结果 而现在的期望值是 1 2 秒 也就 是说 伴随点击鼠标的 咔哒 一声 显示屏的页面已经变了 排在最前面的 十几 二十条信息的标题已经出现在你的面前 除了速度的不断提升之外 搜 索引擎目前的特点可概括为以下几个方面 1 目录型和检索型的搜索引擎相互结合 8 由于目录型和检索型的搜索引擎有各自的优点和缺点 目前它们谁也无法 完全取代谁 于是很多搜索站点都同时提供这两种类型的服务 例如 Yahoo 是 目录型搜索引擎的代表 但同时它也提供基于关键词的检索服务 而 Infoseek 则主要是一个检索型的搜索引擎 但它同时也建立了一个由人工编辑的小型目 录 2 多样化和个性化的服务 绝大多数搜索引擎现在都提供多样化的服务 以吸引更多的用户 商业搜 索引擎尤其注重这一点 以 Sohu 为例 用户可以从它的首页上查看新闻 理财 信息 公共交通 浏览黄页 可以进行网上购物 交易 交友 或者使用免费 E Mail 和网上聊天等服务 近期许多搜索引擎已开始提供个性化的服务 例如 Yahoo 的 My Yahoo Infoseek 9 的 Personalized start page Lycos 的 My Lycos 等 它们允许用户为自己定制起始页面 并选择感兴趣的内容和 经常使用的服务放在该页面上 3 强大的查询功能 与最早的搜索引擎相比 现在的搜索引攀在查询功能方面己经有了很大的 改进 除了简单的 AND OR 和 NOT 逻辑外 不少搜索引擎还支持相似查询 例如 AltaVista Northern light Lycos 等支持短语查询 AltaVista 的高级搜索功 能支持 NEAR 逻辑等 域搜索也是一项很实用的功能 它允许用户把查询范围 限制在网页的某个域中 例如标题 URL 图像标记或链接等 AltaVista Northern light Infoseek 和百度等搜索引擎都支持对网页的不同域进 行搜索 绪 论 4 但是在搜索引擎快速发展的同时 其自身也存在着一些问题 1 提供的查询方式相当有限 与用户的交互性差 信息检索质量不高 2 仅支持单个关键词或者一组关键词及其逻辑运算符组成的查询 而并不 支持自然语言搜索或语义搜索 3 不能利用历史信息进行搜索 用户的每次搜索都是从头开始 而不是从 原有的查询结果中作进一步选择 4 呈现方式单一 呆板 多数搜索引擎只返回一个长长的搜索结果列表 其中可能有数以万计的包含关键词的网页 但这些网页是否以及在多大程度上 与用户的搜索意图相关 则不得而知 1 2 3 搜索引擎的未来 互联网信息的快速发展促进了搜索引擎技术的不断进步 呈现出一个喜人 的应用前景 未来的搜索引擎不仅要满足用户简单的查询需求 更要能动态的 适应信息和用户不断改变所带来的更高的要求 搜索引擎以后的发展将致力于 以下几个方面 1 十分注意提高信息查询结果的精度 提高检索的有效性 用户在搜索引擎上进行信息查询时 并不十分关注返回结果的多少 而是 看结果是否和自己的需求吻合 对于一个查询 传统的搜索引擎动辄返回几十 万 几百万篇文档 用户不得不在结果中筛选 解决查询结果过多的现象目前 出现了几种方法 一是通过各种方法获得用户没有在查询语句中表达出来的真 正用途 包括使用智能代理跟踪用户检索行为 分析用户模型 使用相关度反 馈机制 使用户告诉搜索引擎哪些文档和自己的需求相关 及其相关的程度 哪些不相关 通过多次交互逐步求精 二是用正文分类 Text Categorization 技 术将结果分类 使用可视化技术显示分类结构 用户可以只浏览自己感兴趣的 类别 三是进行站点类聚或内容类聚 减少信息的总量 2 重视交叉语言检索的研究和开发 交叉语言信息检索是指用户用母语提交查询 搜索引擎在多种语言的数据 库中进行信息检索 返回能够回答用户问题的所有语言的文档 如果再加上机 器翻译 返回结果可以用母语显示 该技术目前还处于初步研究阶段 主要的 困难在于语言之间在表达方式和语义对应上的不确定性 但对于经济全球化 互联网跨越国界的今天 无疑具有很重要的意义 3 自然语言理解技术 绪 论 5 自然语言理解是计算机科学中的一个引人入胜的 富有挑战性的课题 从 计算机科学特别是从人工智能的观点看 自然语言理解的任务是建立一种计算 机模型 这种计算机模型能够像人那样理解 分析并回答自然语言 以自然语 言理解技术为基础的新一代搜索引擎 人们称之为智能搜索引擎 由于它将信 息检索从目前基于关键词层面提高到基于知识 或概念 层面 对知识有一定的 理解与处理能力 能够实现分词技术 同义词技术 概念搜索 短语识别以及 机器翻译技术等 因而这种搜索引擎具有信息服务的智能化 人性化特征 允 许网民采用自然语言进行信息的检索 为他们提供更方便 更确切的搜索服务 4 个性化的搜索 10 一种搜索引擎是否具有智能 是否能够满足用户的需求 要看它是否可以 分析用户的个人特点并制定相应的 对策 给出最合适的排序 个性化搜索 引擎很强大 对抓取和用户的搜索行为进行分析 通过他们的算法 可以实现 不同的人在搜索同样关键词的时候 根据不同人的各种属性 地域 年龄 性 别 爱好 职业 历史搜索等等 分别得到最适合他们的结果 可以根据用户 各自的差异和特点 提供最适合该用户的网页呈现 划分具有共同爱好 特性 的用户群体 浏览器可以在客户端自动获取分析用户各自感兴趣的信息 实现 个性化的搜索 如现在流行的Google为用户提供个性搜索 Individual Search 服务 用户在使 用高级搜索的时候可以设置检索词所在的位置 如正文 标题 仅在URL 或 者文本等等 还可以通过逻辑关系限制检索 如可以含有 一定含有 一定不 含有等等 以及对于检索的时间范围 地域范围做出限制 Baidu也提供了个性搜索功能 除Google所提供的功能外 用户还可以设置 检索结果的性质 可以设置只返回媒体类型 或者某些特定领域的页面 还可 以选择进行检索的数据库 以及结果的显示排列方式等等 然而这种定制服务 的方式 还是给用户增添了许多麻烦 它要求用户须按照指定的操作来进行搜 索才能获得更加满意的结果 然而即便是这样也无法实现真正的个性化服务 同样的操作下 仍然会给出相同结果集 5 P2P对等网络 P2P是peer to peer的缩写 意为对等网络 其在加强网络上人的交流 文 件交换 分布计算等方面大有前途 长久以来 人们习惯的互联网是以服务器 为中心 人们向服务器发送请求 然后浏览服务器回应的信息 而P2P所包含 的技术就是使联网电脑能够进行数据交换 但数据是存储在每台电脑里 而不 绪 论 6 是存储在既昂贵又容易受到攻击的服务器里 网络成员可以在网络数据库里自 由搜索 更新 回答和传送数据 所有人都共享了他们认为最有价值的东西 这将使互联网上信息的价值得到极大的提升 1 3 搜索引擎排序算法的演进过程 1 3 1 搜索引擎排序算法的起源和现状 从搜索引擎的发展历史可以看出其搜索结果是由一个从无序到有序 再到 按用户需要排序的过程 早期的搜索引擎只是简单地从数据库中取得数据 然 后按照数据被检索出的自然顺序返回给用户 之后的搜索引擎应用了关键词的 相关性 对于用户提交的关键词 如果它出现的位置越重要 在文档中的出现 频率越高 则认为此网页与检索词的相关性越高 越能满足用户的需求 这些 基本上是沿用了图书情报界的研究成果 而现在的搜索引擎大部分都用到了链 接分析技术 它是应用了文献引文索引机制的思想 即某个人的论文被别人引 用的次数越多 引用它的论文质量越高 那么 他的论文就是一篇好的论文 当前流行的搜索引擎如Google 百度都用到了链接分析 它的结果可以反映网 页的重要程度 但并不代表用户对网页的需求程度 对搜索引擎排序技术的研究有很多 1998年斯坦福大学的博士研究生 Sergey Brin 和 Lawrence Page提出了网络链接分析的一个新算法 PageRank 该 算法是建立在随机冲浪者模型上的 同年J Kleinberg提出了Hits算法 该算法专 注于改善泛指主题检索的结果 R Lempel和S Moran提出了SALSA 11 Stochastic Approach for Link Structure Analysis 算法 D Cohn和 H Chang 提出了Phits算 法 随后Hits的变种算法相继提出 如Monika R Henzinger 和 Krishna Bharat 提出了HillTop算法 IBM Almaden 研究中心的Clever工程组提出了ARC Automatic Resource Compilation 算法 Allan Borodin等提出Hub平均 Hub Averaging Kleinberg 算法 12 等 这两种算法都是基于概念模型的 2001年1月康柏系统研究中心的Krishna Bharat和多伦多大学的George A Mihaila提出了HillTop算法 该算法利用专家网页对网页进行评判 2004年10月 斯坦福大学的Z Gyongyi和Hector Garcia Mo lina提出了TrustRank算法 13 该算 法通过选择不可能作弊的站点 用这些站点对其他网页进行评判 2005年5月A Benczur和K Csalogany在第一届AIR Web 学术会议上提出 SpamRank 算法 14 绪 论 7 该算法判断出一些肯定是作弊的站点 与TrustRank算法思路正好相反 现代搜索引擎的搜索结果不仅仅考虑信息的本身 还融合了关键词和检索 出文档的相关性 使其更为贴近用户需求 另外 搜索引擎对排名采用了多因 素的融合 这些因素有域名因素 文档和页面信息 链接因素 搜索结果因素 用户数据因素等 1 3 2 搜索引擎排序算法存在的问题 上面提到了很多排序算法 但是没有一个是十全十美的 每个算法往往致 力于解决某个方面的问题 其他方面可能有所欠缺 现在也有很多综合的排序 算法方面的研究 但仍然难以达到预期的效果 虽然单一的网页排序已经有了 比较成熟的算法 但是 目前还没有一个搜索引擎的排序结果能完全符合用户 的需求 还存在以下方面的问题 1 一些网站在页面的标题 锚文本 正文或者Html中恶意堆砌关键词 而 没有用户所需的内容 搜索引擎分析网页的时候 会给这些关键词较高的权重 当用户搜索这些关键词的时候 这些页面就可能以高的排名返回给用户 目前 的搜索引擎虽然对此做出了相应对策 但从搜索结果来看 依然存在这个问题 2 链接分析出现以后 出现了很多作弊行为 网站管理员可以通过制造大 量虚假链接来提升其站点排名 他们还可以通过和其他网站交换链接来增加链 入的URL数目 人为提高了自己站点的反向链接数 3 尽管目前搜索引擎的排序方法在一定时间内都会更新一次 来防止一些 网站管理员的作弊 但目前Spam页面的大量存在使得搜索引擎往往不能返回相 关性比较好的结果 1 4 本文的主要工作及组织结构 本文首先介绍了搜索引擎的发展历史 排序算法的现状及存在的问题 其 次综述网络搜索引擎的工作原理 结构以及分类评价标准 在此基础上对现有的排序算法进行研究 发现不足之处如 PageRank 平均 分配权威值 Hilltop 中利用 专家页面 不合理 容易产生 Spam Direct Hit 算法不易处理重复点击的作弊行为 然后针对这些缺点引入非均衡分配的思想 来改进 PageRank 算法 利用社区发现技术来减少 HillTop 算法和 Direct Hit 算 法中不利因素对排序结果的影响 以此来改善排序的质量 有效降低 Spam 的 绪 论 8 在排名中的影响 防止网页作弊 使排序结果更合理 从而更好的满足用户的 需求 本文的结构按如下的方式进行组织 第一章 绪论 提出选题的意义和背景 介绍了搜索引擎的发展历史 然 后着重研究了互联网的信息特征和目前搜索引擎的不足之处 引出了本文将要 改善的地方 排序技术 简述了搜索引擎排序算法的现状 最后概括了本文 将要研究的内容 第二章 搜索引擎概述 本章主要介绍搜索引擎的分类方法 及其结构与 工作原理 然后综述了现在流行的中外搜索引擎 最后阐述了搜索引擎的评价 标准 如查全率和查准率 覆盖率 死链接率和响应时间等 第三章 搜索引擎常用排序算法及相关技术 主要分析了现在流行的排序 算法 如词频位置加权算法 PageRank 算法 Direct hit 算法 HillTop 算法等 其次介绍了搜索引擎的相关技术 包括 SEO 技术 15 与 Spam 作弊技术 16 第四章 利用社区发现技术改进排序算法 针对 PageRank 平均分配权威值 Hilltop 中提取 专家页面 不够合理 容易产生 Spam Direct Hit 算法重复点 击的问题 提出改进排序算法的思路 并加以比较 分析 第五章 总结展望 总结本文所做的工作 展望未来搜索引擎排序技术的 发展 提出下一步工作的思路 第二章 搜索引擎概述 9 第二章第二章 搜索引擎搜索引擎概述概述 本章首先概述了搜索引擎分类方法并作了简单的介绍 其次对搜索引擎工 作原理及结构 搜索引擎的每一个组成部分进行了详细的描述 最后阐述了搜 索引擎的评价标准 2 1 搜索引擎的分类 实际上 通常意义上的搜索引擎只是信息检索系统的前端 面向用户的一 端 而整个信息检索还包括后端的收集 索引信息等功能模块 由于 Web 信息 检索系统很多 功能上也有差异 人们在充分利用这些便利搜索工具的同时 也会感到无所适从 无从选择 据统计 各种各样的网络信息搜索工具已经有 上千种 从不同的角度 其分类也各不相同 2 1 1 按所覆盖内容 如果按搜索引擎所覆盖内容的范围来分 可分为通用型 专业型和特殊型 搜索引擎 1 通用型搜索引擎所采用的信息资源极为广泛 对资源的主题范围和数据 类型基本没有限制 所以它适用于各种用户 人们可以利用它来检索几乎任何 方面的内容 如 Google 就是这类工具 2 专业型搜索引擎 17 往往是着重某一主题范围内的信息资源 比如专门用 于收集医药的 Healthy Medical World Search 以及法律的搜索引擎 Law Crawler 等等 这类搜索引擎对于该专业信息的收集与查询 其查全率和查准率是极高 的 3 特殊型搜索引擎往往是指那些用来检索某一类型信息或数据的搜索工具 比如搜索电话号码的 Switchboard 查询地图的 Webseek 搜索 FTP 文件的 Archie 和 Files 等等 2 1 2 按是否有人参与 如果从是否有人参与来分 可分为人工搜索引擎和智能搜索引擎 1 人工搜索引擎主要是由人工来建立 主要依靠网络信息发布者的主动登 第二章 搜索引擎概述 10 记将要发布的信息按搜索引擎的主题树归类 填写信息源站点的地址 给出主 题关键词和摘要等等信息 由于个人的分类习惯和方法都难免带有主观性和片 面性 分类具有差异性 另外 主题分类树的形状 平衡性等都能直接影响信 息收集的质量和效果 其建立与维护也是一个难题 2 智能搜索引擎不需要人工登记信息 不需要人的主动参与 它依靠像 网络机器人 Robot 18 一样的程序在网络上不停地爬行和搜索 能够自动获 取网络上的信息 并自动进行分类 索引 摘要等 随着人工智能 机器学习 和其它智能信息处理技术的发展 智能搜索引擎对网络信息的分析和处理也越 来越准确 合理了 智能搜索引擎包括自动文摘 自动分类 自动索引等等技 术 在中文搜索引擎中还包括自动分词 2 1 3 按检索层次 如果按检索层次来分 可分为检索型搜索引擎 目录型搜索引擎 元搜索 引擎 信息代理 Agent 分布式搜索引擎和基于客户端的搜索引擎 1 检索型搜索引擎 Search Engine 检索型搜索引擎就是为用户提供输入关键词查找信息的搜索引擎 检索方 便直接 可以使用布尔逻辑查询 短语查询 邻近查询 模糊查询 自然语言 查询等等检索方式 Hotbot Infoseek Google 等就是这类检索工具的典型代表 它们有着自己的收益 组织资源的机制 通过对网页内容和特征的分析 建立 自己的索引数据库 为用户提供查询服务 2 目录型搜索引擎 Directory 除了基于网页分析建立索引的网页搜索引擎外 还有一种以人工方式或半 自动方式搜集信息的搜索引擎 目录型搜索引擎 目录型搜索引擎也称为分 类式搜索引擎 这种搜索引擎是由编辑人员根据信息资源的内容按一定的主题 进行分类组织 并形成信息摘要 将信息置于事先确定的分类框架中 组织成 一层一层的分类目录 目录下面有更具体的子目录 信息的类别也由大到小 由粗到细 整个搜索引擎形成了一个层次型的类别目录 用户可以逐层浏览 选择不同的主题对网络信息进行过滤 所选择的主题类别越小 信息的相关度 就越高 用户就越有可能找到自己所需要的信息 这类搜索引擎的性能主要取决于对获取网页的人工归类 或自动分类算法 的精确度如何 其代表有 Yahoo Look Smart Lycos Goto 等 比如中文 搜索引擎新浪 sina 的分类目录就有 15 大类目录 一万多个子目录 中文雅虎 第二章 搜索引擎概述 11 yahoo 也有 14 个一级目录 最深有 6 级子目录 目录之间还提供交叉访问 目录型搜索引擎的分类体系一般是根据所采集的资源范围来设计目录体系的 或者采用图书分类方法 所以不同的搜索引擎其分类也各不相同 目录型搜索引擎和检索型搜索引擎各自更适用于不同的搜索需求 两者可 以相互补充 但不可以相互替代 当用户需要查找关于某类内容的资料或某个 网站时 目录型搜索引擎是最适用的 而查询一些比较具体的资料时 用检索 型搜索更好 而现在的大多数搜索引擎都同时提供检索关键词和目录浏览两种 检索方式 这成为混合型搜索引擎 它可以借助于分类目录来缩小检索范围 达到更为精确和更高效的检索结果 3 元搜索引擎 Meta Search Engine 19 由于单个搜索引擎的覆盖范围往往不会太广 为了找到自己所需要的信息 用户常常需要使用多个搜索引擎 以期找到更多更全的信息 但由于不同的搜 索引擎其查询语法 接口界面往往不同 需要用户重新学习和适应不同的检索 方法 这给用户使用多个搜索引擎带来了极大的不便 为了解决这个问题 研 究人员开发了元搜索引擎 元搜索引擎是独立于索引系统的查询工具 它统一 了不同的搜索引擎的查询接口 用户面对的多个搜索引擎的界面是一样的 由 统一的元搜索引擎的接口对用户的查询请求进行处理 分别将其查询转换为符 合底层搜索引擎查询语法的子查询 同时向多个搜索引擎递交 由底层搜索引 擎在各自的索引数据库中进行查询 在各个搜索引擎返回检索结果后 元搜索 引擎将子查询结果进行汇总 去重 重新排序等处理 最后向用户返回搜索引 擎的检索结果 元搜索引擎一般都没有自己的数据库 而是利用其它的搜索引擎的数据库 来进行服务 在层次上 元搜索引擎要比检索型搜索引擎和目录型搜索引擎要 高 缺点是不能够充分使用下层搜索引擎的排序功能 用户需要做更多的筛选 这类搜索引擎的代表是 Meta Crawler Sary Search Informaker 等 例如 Meta Crawler 可以同时检索九个搜索引攀 有 Yahoo OpenText Lycos WebCrawler InfoSeek Excite Inktomi Galaxy Alta vista 等 4 信息检索代理 Agent 信息检索代理 Agent 是一种主动信息检索技术 它可以根据用户事先定义 的信息检索要求 甚至能从用户的日常检索行为 浏览行为中学习用户兴趣 推理用户隐含的需求 并利用已有的检索服务 如上述检索服务系统 主动从 Web 上检索相应的信息资源 实时监测信息源的动态变化等 并将有关信息以 电子邮件的方式或其它方式 及时主动地通知用户 如 Washington 大学开发 第二章 搜索引擎概述 12 的 ShopBot Canegie Mellon 大学开发的 Web Watcher 20 Standford 大学开发的 Fab 21 等代理系统 5 分布式搜索引擎 Distributed 分布式搜索引擎和集中式搜索引擎是相对而言的 集中式搜索引擎所有功 能都集中在一台服务器上 存在着数据库过大 维护困难 查询效率及可靠性 不高等缺点 而分布式搜索引擎从体系结构上解决了这个难题 它主要是根据 地域 主题或其它的划分标准建立分布的子检索服务器 索引数据库由分布的 数据库组成 因为扩充性较好 所以搜索引擎覆盖的范围可以变得很大 而且 各子服务器能够进行独立搜索 相互之间可以交换信息 如果一个检索服务器 上没有用户所需要的信息 查询请求将被重定向 被发送到别的子检索服务器 上继续查询 分布式搜索引擎的优点在于各个子服务器能协同工作 共享他们 所搜集的信息 从而具有较高的整体吞吐能力 划分之后的索引数据库各自索 引各自的区域 每个索引数据库较小 重复信息没有或很少 这大大提高了查 询的响应速度 各个子服务器同时进行收集工作 减少了获取信息的时间 像 Web Ants NWI 等就是这类搜索引擎 Inktomi 22 就是由 160 台 SUN 工作站构成 的分布式搜索引擎 每台工作站的索引数据库内容不同 这些工作站通过局域 网由专门的 Web 服务器向用户提供查询服务 6 基于客户端的搜索引擎 Client Based 基于客户端的搜索引擎将排序算法内嵌在 Web 客户程序 如浏览器 中 直 接在客户端执行 它的优势在于可以根据用户的不同情况分别进行搜索 对单 个用户具有很好的适应性 但是它必须下载每一篇文档 才能判断其相关与否 这样在找到文档以前就下载了很多无关的文档 占用了不应有的带宽 所以速 度较慢 而且如果每个客户程序都使用自己的内嵌程序来进行搜索的话 造成 的网络负担也是特别重的 难以在较大范围内推广使用 如 FishSearch 就是客 户端搜索引擎形式 虽然这种客户端搜索并不值得推广 但是其思想对于实现 搜索引擎的个性化机制却有很大的借鉴意义 要从一个统一的标准来对搜索引擎进行分类是一件困难的事情 不同的划 分方法差别较大 接下来将要介绍搜索引擎的结构与工作原理 第二章 搜索引擎概述 13 2 2 搜索引擎的结构及工作原理 2 2 1 搜索引擎组成结构 搜索引擎主要由搜集器 分析器 索引器 检索器 挖掘器和用以存储数 据的多个数据库组成 如图2 1所示便是搜索引擎的组成结构图 W WW WW W 搜集器 搜集 端数 据库 检索 端数 据库 分析器 索引器 检索器 挖掘器 用户 信息 库 搜索引擎 用户 图2 1 搜索引擎结构图 1 搜集器 搜集器主要完成从WWW上获取网页和超链结构信息的工作 WWW结构 是一个以网页为结点 超链为边的有向图 搜集器的工作可以抽象为一个有向 图的遍历过程 它从用户配置的一些 种子 网页出发 根据一定的算法 获 取新的网页和超链 从而实现从网上不停地获取网页的功能 2 分析器 分析器根据网上数据的特点 按照特定的算法 对己经搜集获得的网页和 超链信息进行分析 从中提取和用户检索相关的网页描述信息 例如 网页关 键词 编码类型 大小 被其他网页链接次数等 并将提取所得的信息交给索 第二章 搜索引擎概述 14 引器建立索引 3 索引器 分析器分析所得的网页描述信息 都是页面到页面描述数据的正排表 索 引器主要用于对这些已分析好的网页的抽象数据建立索引 索引器的核心工作 就是重新整理这些网页描述信息 对必要的数据项建立倒排表 包括关键词到 网页的倒排表 站点到网页的倒排表等 为用户的检索做准备 4 检索器 检索器的功能是根据用户的查询在索引库中快速检出文档 进行文档与查 询的相关度评价 对将要输出的结果进行排序 并实现某种用户相关性反馈机 制 检索器常用的信息检索模型有集合理论模型 代数模型 概率模型和混合 模型等多种 可以查询到文本信息中的任意字词 无论其出现在标题还是正文 中 检索器从索引中找出与用户查询请求相关的文档 采用与分析索引文档相 识的方法来处理用户查询请求 5 挖掘器 挖掘器提取用户相关信息 利用这些信息来提高检索服务的质量 它的主 要工作就是找出检索信息的相互关系 分析它们的特性 通过对用户行为的记 录来提高检索的质量 返回最期望的检索结果 2 2 2 搜索引擎工作原理 搜索引擎是一种特殊的计算机信息检索系统 Web信息检索系统 首先 从信息检索流程的角度来介绍计算机信息检索系统的工作原理 如图2 2所示即 为搜索引擎的工作原理图 文本数据库 数据库管理 模块 索引机制 查询处理文 本 处 理 用户界面 查找机制 排序机制 索引 逻辑视图 逻辑视图 查询 倒排文件 命中文献 文本 文本 用户需求 有 序 文 献 图2 2 搜索引擎工作原理图 在检索开始之前 搜索引擎必须对文本数据库进行定义 定义的内容包括 a 需要的文献 b 对文献进行的操作 c 文本模型 这个过程通常由数据库管 理员 DB Manager 来完成 文本操作 Text Operation 将原始文献转换为它们的逻 辑视图 Logical View 文献的逻辑视图一般是指文献经过去除停用词 Stop Words 如冠词和连词 进行截词 Stemming 如只保留词干 确定名词词组 消 去形容词 副词和动词 等文本操作之后 而得到的文献的主要内容 文献逻辑视图定义完毕之后 数据库管理员通过数据库管理模块 建立文 第二章 搜索引擎概述 15 本索引 Index 索引是一种非常重要的数据结构 检索系统通过它快速搜索大 量的数据 有很多种建立索引的方法 通常使用的是倒排文档 Inverted File 23 文本数据库建立好索引后 就可以开始检索过程 首先由用户给出用户需求 User Need 或者用户任务 User Task 该需求被相同的文本操作解析 再经过 查询操作 Query Operation 处理 形成系统可以识别的查询表达式 查找机制使 用查询和索引进行匹配处理 得到相关的文献 称作命中文献 命中文献在提交给用户之前 要按照相关度进行排序 以形成有序文献 Ranked Documents 当结果提交给用户之后 检索过程并没有结束 用户需要 从结果中查找有用信息 同时审查查询结果 指出哪些文献是真正感兴趣的 并反馈给检索系统 然后检索系统使用反馈的结果改进查询表达式 以期能获 得更好的查询结果 这个过程就叫做用户反馈 User Feedback 在整个信息检索过程中 用户和检索系统一直都通过用户界面 User Interface 来进行交流 用户界面 又称作用户接口 往往要求用户输入查询请 求 并显示检索的结果 通过对计算机信息检索系统工作流程的介绍 可以知 道完整的计算机信息检索技术涉及到文本处理技术 查询处理技术 查找匹配 技术 排序 等级评定 技术 用户接口技术以及索引技术 数据库技术等等 2 3 常用搜索引擎 上面介绍了搜索引擎的组成结构与工作原理 以及分类方法 下面就来看 看当代流行的搜索引擎 在这里主要介绍常用的中文和英文搜索引擎 2 3 1 常用中文搜索引擎 1 Yahoo 以雅虎 Yahoo 24 为代表 说到搜索引擎的历史 自然不能不说雅虎 Yahoo 了 正如计算机时代的很多新事物一样 Yahoo 起源于一个想法 随后变成一种业余爱好 最终成了使人全身心投入的一项事业 Yahoo 的两 位创始人大卫 费罗 David Filo 和杨致远 Jerry Yang 是美国斯坦福大学电机工程 系的博士生 于1994年4月建立了自己的网络指南信息库 将其作为记录他们个 人对互联网的兴趣的一种方式 但是不久 他们将Yahoo 变成了一个可定制 的数据库 旨在满足成千上万的 刚刚开始通过互联网社区使用网络服务的用 户的需要 他们开发了可定制的软件 帮助他们有效地查找 识别和编辑互联 网上存储的资料 最初Yahoo 存放在杨致远的学生工作站 akebono 上 而 第二章 搜索引擎概述 16 搜索引擎存放在Filo的计算机 konishiki 上 这些计算机的名称都来自于一些 具有传奇色彩的夏威夷摔跤手 结果令大家意想不到的是 Yahoo 大受欢迎 斯坦福大学的计算机网络由此受到来自外界的大浏览量的冲击 2 sohu 1996年8月 sohu 25 公司成