【毕业学位论文】（Word原稿）第四代搜索引擎——主题搜索引擎的设计与实现

第四代搜索引擎 主题搜索引擎的设计与实现 4四代搜索引擎 天网主题搜索引擎的设计与实现 北京大学学士论文 1 指导老师对论文工作的评语 “面向主题的搜索引擎”，是我们“天网”搜索引擎下一步发展的重要方向之一。罗昶同学的毕业论文，是这一新方向的良好开端。 论文从系统实现的角度，较全面的阐述了实现一个高质量主题搜索引擎系统的各个方面，着重分析了导向词 、特征提取、权威和中心网页、超链分析以及网页评分等多种搜集策略的运用，并提出了“主题度”的概念，用以衡量主题搜索引擎的质量，意在指明一个搜索引擎在一个主题下的主题度越高，则它越贴近这个主题，用户就越容易找到跟这个主题相关的资料。特别地，将上述认识用于实践中，高质量地完成了一个面向影视主题的搜索引擎系统，搜集了十多万影视信息，在影视信息方面提供着比“天网”通用搜索引擎更有效的服务；论文内容丰富，所涉及的工作量很大，且有较强的系统性，是一篇很有参考价值的论文，为“天网”的发展做出了贡献。 老师签名 :_ 第四代搜索引擎 天网主题搜索引擎的设计与实现 北京大学学士论文 2 论文摘要 互联网上的信息每天都以指数量级的速度爆炸性增长，面对如此浩瀚的资源，搜索引擎为所有网上冲浪的用户提供了一个入口，毫不夸张的说，所有的用户都可以从搜索引擎出发到达自己想去的网上任何一个地方。因此它也成为除了电子邮件以外最多人使用的网上服务。 但是，随着信息多元化的增长，千篇一律的给 所有用户提供同一个入口显然已经不能满足特定用户更深入的查询需求。同时，这样的通用搜索引擎在目前的硬件条件下，要及时更新以得到互联网上较全面的信息是不太可能的。针对这种情况，我们需要一个分类细致精确、对硬件要求低，数据全面深入、更新及时的面向主题的搜索引擎。由于主题搜索运用了人工分类以及特征提取等智能化策略，因此它比前三代的搜索引擎将更加有效和准确，我们将这类完善的主题搜索引擎称为第四代搜索引擎。 本文阐述了第四代搜索引擎天网主题搜索引擎的设计与实现，并着重分析了导向词、特征提取、权威和中心网页、超链分析以及 网页评分等多种搜集策略的运用。论文最后定义了独创的“主题度”来衡量主题搜索引擎的性能，一个搜索引擎在一个主题下的主题度越高，证明这个搜索引擎越贴近这个主题，用户就越容易找到跟这个主题相关的资料。 有了“主题度”，就可以很容易的比较使用多种搜集策略以后的天网主题搜索引擎与原天网通用搜索引擎的差别，说明了前者在特定的主题下要比后者更准确贴切。 关键词： 互联网、万维网、搜索引擎、数据发掘、主题搜索、主题度 第四代搜索引擎 天网主题搜索引擎的设计与实现 北京大学学士论文 3 on on it an of to to in of In to it is to on we is a in it as it is th In th of In is is its to is 四代搜索引擎 天网主题搜索引擎的设计与实现 北京大学学士论文 4 目录 指导老师对论文工作的评语 . 1 论文摘要 . 2 . 3 目录 . 4 第一章 背景介绍 . 7 展现状 . 7 发展历程 . 7 . 7 信息分布 . 8 索引擎简介 . 9 题搜索引擎 第四代搜索引擎 . 10 结 . 10 第二章 天网搜索引擎系统结构 . 12 统简介 . 12 统结构及各部分功能 . 12 息存取和分析子系统（主控程序） . 13 息收集控制子系统（搜索器） . 13 源索引数据库 . 13 息检索子系统 . 14 理和监控子系统 . 14 控程序及搜索器的实现 . 14 控程序 . 14 索器 . 16 结 . 17 第三章 主题搜索策略 . 18 第四代搜索引擎 天网主题搜索引擎的设计与实现 北京大学学士论文 5 向词 . 18 向词及权值的配置 . 18 据导向词及权值改变搜索顺序 . 19 页评分 (. 19 用计数 (. 19 页评分 (. 20 威网页 (中心网页 (. 21 么是权威网页和中心网页 . 21 掘权威网页的难度 . 23 威网页和中心网页的计算公式 . 23 算权威网页和中心网页的算法 . 24 链描述文本分析 (. 25 结 . 25 第四章 天网主题搜索引擎的实现 . 26 统模块图 . 26 储结构 . 27 统数据库 . 27 索器和主控程序之间的通讯 扩展 构 . 30 向词的存贮 . 33 索器的实现 . 34 向词的加载分析 . 34 集策略的实现 . 35 结 . 38 第五章 系统现状和性能 . 39 网主题搜索引擎系统现状 . 39 题度的定义 . 39 网主题搜索引擎与通用搜索引擎的比较 . 40 第六章 总结展望 . 42 第四代搜索引擎 天网主题搜索引擎的设计与实现 北京大学学士论文 6 致谢 . 43 参考文献 . 44 参考 . 45 第四代搜索引擎 天网主题搜索引擎的设计与实现 北京大学学士论文 7 第一章 背景介绍 展现状 发展历程 1983 年 P 成为 唯一的正式协议。 此后， 连接的网络、机器和用户快速增长。 1988 年 联，它的规模以指数增长，很多地区网络开始加入，并且开始与加拿大、欧洲和太平洋地区的网络连接。 后来形成 90年代初到现在，是 993 年， 增长速度是 341%。截止到 1996 年 7 月， 连接了 134336个网络，入网主机 1228万台，以及数以亿计的用户。到 1998 年 7月，27 万个网址， 4300万个域名， 个网页，其规模大概每年翻一番。 全球性的网络信息系统。一九八九年，位于瑞士的先开始了 后，许多其他的研究机构、大学和公司也加入 相继开发出各自的 些 此过程中， 时，为了保证不同 件之间的互操作性，一系列 善之中。 在最近几年里， 到了长足的发展，不仅成为企业必不可少的组成部分，并且开始走进千家万户。根据 然上发布的数据，截止到 1999年 2月， 600万个，其中公开提供 80万个；共有 页大约 8 亿页，这些网页包含了 15T 字节的数据。按照 2000 年4月在波士顿举行的第 5届搜索引擎年会的会议报告，我们可以知道现今的网页数目已经超过了 10亿。 第四代搜索引擎 天网主题搜索引擎的设计与实现 北京大学学士论文 8 据 国互联网络信息中心 )2001年 1月 17日在京 发布的最新的中国互联网络发展状况统计报告，截止到 2000年 12 月 31 日止，我国上网计算机数有约 892 万台。我国上网用户人数约 2250万人，除计算机外同时使用其它设备（移动终端、信息家电等）上网的用户人数为 92 万。 注 册 的 域 名 总 数 为 122099 个， 点数（包括 的网站）约 265405 个，我国国际线路的总容量为2799M。关于网页的数目没有具体的统计数据，但根据科学杂志上提供的集合估计法，通过中国几个主要搜索引擎获得的搜索数据（天网、 浪、搜狐、网易），我们可以估计到当前中国拥有的网页数已经超过 3000万。 信息分布 信息量大而且分散 自治性强 信息资源多种多样 不一致和不完整性 这些特点对网络软件的性能提出了很高的要求。网络的快速发展给信息挖掘带来了挑战。 时伴随着上网经验不足、不太晓得如何查找信息的新用户的加入。用户很可能最大程度的运用超链来在网上冲浪，他们通常从以下两类网站开始： 第一类是目录 系统，其典型代表是 ）， 它通过有专业知识的网页编辑人员对网上的网页进行精选，建立一个索引目录，来给用户提供服务。这类 通过手工维护得很好的 系统的优点是提供的网页准确率高，可以有效的覆盖所有热门的主题，但它们的缺点是过于主观，而且需要高昂的代价来建立和维护，更新改进的慢，同时不能很好的覆盖所有深奥的主题 。 第四代搜索引擎 天网主题搜索引擎的设计与实现 北京大学学士论文 9 第二类是搜索引擎系统， 比如天网（ ）， 它通过程序自动地从网上搜集和分析网页，建立索引，为用户服务。这类 通过关键词匹配实现查找的自动更新的搜索引擎 优点是涵盖的网页数量巨大，但 通常返回太多的低质量相关性不大的结果。 索引擎简介 面对浩瀚的网络资源，搜索引擎为所有网上冲浪的用户提供了一个入口，毫不夸张的说，所有的用户都可以从搜索出发到达自己想去的网上任何一个地方。因此它也成为除了电子邮件以外最多人使用的网上服务。 搜索引擎技术伴随着 发展是引人注目的。搜索引 擎大约经历了三代的更新发展： 第一代搜索引擎出现于 1994 年。这类搜索引擎一般都索引少于 1， 000， 000个网页，极少重新搜集网页并去刷新索引。而且其检索速度非常慢，一般都要等待 10 秒甚至更长的时间。在实现技术上也基本沿用较为成熟的 网络、数据库等技术，相当于利用一些已有技术实现的一个 1994 年 3 月到 4 月，网络爬虫 均每天承受大约 1500 次查询。 大约在 1996 年出现的第二代搜索引擎系统大多采用分 布式方案（多个微型计算机协同工作）来提高数据规模、响应速度和用户数量，它们一般都保持一个大约 50， 000， 000 网页的索引数据库，每天能够响应 10， 000， 000 次用户检索请求。 1997 年 11 月，当时最先进的几个搜索引擎号称能建立从 2， 000， 000 到100， 000， 000 的网页索引。 索引擎声称他们每天大概要承受 20， 000，000 次查询。 自 1998 年到现在，出现了一个搜索引擎空前繁荣的时期，我们统称这一时期的搜索引擎为第三代搜索引擎。第三代搜索引擎的发展有如下几个特点： 1. 索引数据库 的规模继续增大，一般的商业搜索引擎都保持在几千万甚至上亿个网页。 第四代搜索引擎 天网主题搜索引擎的设计与实现 北京大学学士论文 10 2. 除了一般意义上的搜索以外，开始出现主题搜索和地域搜索。很多小型的垂直门户站点开始使用该技术。 3. 由于搜索返回数据量过大，检索结果相关度评价成为研究的焦点。相关的研究又可以分为两类：一类是对超文本链的分析，在这方面 统 7和 统 8作出了很大的贡献；另一类是用户信息的反馈， 统采用的就是这种方法。 4. 开始使用自动分类技术。 在一定程度上使用了该技术。 2000 年搜索引擎 2000 年大会上，按照 司总裁 演讲，在用 3,000 台运行 统的个人电脑在搜集 的网页，而且以每天 30 台的速度向这个微机集群里添加电脑，以保持与网络的发展相同步。每台微机运行多个爬虫程序搜集网页的峰值速度是每秒 100 个网页，平均速度是每秒 网页，一天可以搜集超过 4， 000， 000 网页。 题搜索引擎 第四代搜索引擎 随着信息多元化的增长，千篇一律的给所有 用户同一个入口显然已经不能满足特定用户更深入的查询需求。同时，这样的通用搜索引擎在目前的硬件条件下，要及时更新以得到互联网上较全面的信息是不太可能的。针对这种情况，我们需要一个分类细致精确、数据全面深入、更新及时的面向主题的搜索引擎。 由于主题搜索运用了人工分类以及特征提取等智能化策略，因此它比上面提到的前三代的搜索引擎将更加有效和准确，我们将这类完善的主题搜索引擎称为第四代搜索引擎。 结 这一章，概述了主题搜索引擎的产生背景以及它在搜索引擎历史上的地位。 由于天网主题搜索是建立在原来天网搜 索系统的基础上的，第二章将会介绍天网搜索引擎的系统结构，并着重剖析搜索器和主控程序的设计实现，这是因为主题搜索需要对这两部分做较大的改动。第三章将着重分析导向词、特征提取、权威和中心网页、超链分析以及网页评分等多种主题搜集策略的运用。笔者将会第四代搜索引擎 天网主题搜索引擎的设计与实现 北京大学学士论文 11 在第四章详细介绍天网主题搜索引擎的设计与实现。最后是第五章的系统现状性能以及第六章的总结展望，在这里笔者会比较一下使用了主题搜集策略以后的天网主题搜索引擎与使用以前的天网通用搜索引擎的差别，并展望以后的工作。 第四代搜索引擎 天网主题搜索引擎的设计与实现 北京大学学士论文 12 第二章 天网搜索引擎系统结构 统简介 天网由于采用了可 伸缩的分布式结构、查询 引数据库和检索数据库分开等先进、有效的技术，使得系统占用资源少、信息收集速度快、用户查询响应时间快（系统对 上的查询可在 1 秒钟之内作出响应）、查准率和查全率较高，基本达到了实用化程度。 系统在设计和实现过程中，充分考虑到了用户和管理员的使用习惯，提供了浏览器、电子邮件、中英文用户接口和方便使用、功能丰富的管理工具，因而有很好的可用性和易用性。 由于“天网”功能全面、性能突出，软件世界杂志年第 7 期将“天网”评价为国内最好的中英文搜索引擎。 在 2001 年 4 月，天网累计访问量和索引网页数均突破了 10， 000， 000。 “天网 ”从 1997 年 10 月在 提供服务以来，得到了用户的欢迎和好评。下面是不同时间统计的系统的使用情况： 时间 1998年 9月 1999 年 9 月 2000 年 5 月 2001 年 5 月 平均每天访问人次 2200 10113 31817 51368 统结构及各部分功能 天网系统主要由 息存取和分析子系统 (主控程序 )、 息收集控制子系统 (搜索器 )、资源索引数据库、信息检索子系统、管理和监控子系统等几个部分组成。各 个部分的功能如 图 第四代搜索引擎 天网主题搜索引擎的设计与实现 北京大学学士论文 13 息存取和分析子系统（主控程序） 根据 息收集控制子系统提供的 相关信息，使用 议，在 获取相关资源，并能就对方主机返回的不同状态码作出相应处理。对取回的 面 (主要是 式 )进行分析，自动对中文编码进行识别和转化，对中文信息进行分词、提取页面的标题、关键词、摘要以及其中的超链（ 将分析的结果通过扩展 口提交给信息收集控制子系统。 息收集控制子系统 （搜索器） 根据配置文件运用自然语言理解和知识获取技术、引导信息收集系统优先访问特定知识领域和特定地域范围内的信息，向 取分析进程发送需访问的 相关信息，接收其发回的访问和分析结果。将相应的数据存入信息数据库中。并对信息收集的频度和流量加以控制。 源索引数据库 存储收集到的 息，以及分析的结果。并对其重新进行基于词的分级档 取、分析 收集控制子系统 信息检索子系统 务器 资源索引数据库 览器 览器 统总体结构示意图 理和监控子系统 取、分析 四代搜索引擎 天网主题搜索引擎的设计与实现 北京大学学士论文 14 优化索引，以加快查询速度 息检索子系统 提供基于 式的信息检索服务。用户通过任何标准的 览器直接访问。检索系统可以支持在一次检索中使用多个检索词 (中、英文 )，并支持检索词之间的逻辑关系（与、或）。还可以指定查询的范围和方式（精确、模糊）。检索结果以 式返回给用户。各项结果的标题与它所对应的 超链连接起来。用户只需在浏览器中点中检索结果项的标题，就能马上取得相应页面的实际内容。命中的 面按它与用户检索关键词的关联程度排序，使用户的检索更有效率。系统还支持在上一次返回的结果中进行查询。 理和监控子系统 提供系统配置，启动、停止、监控、统计等管理功能。 信息收集控制 子系统与 取分析进程之间的信息交互是通过 接来实现的，因此各子系统可以分布运行于网络中不同的主机上。 控程序及搜索器的实现 控程序 第四代搜索引擎 天网主题搜索引擎的设计与实现 北京大学学士论文 15 数据库 取分析 取分析 主进程 . . . r o b o t s 存取分析进程 结果插入进程 期检查进程 S O C K E T 接口 S O I F 数据格式 P I P E 接口 S O I F 数据格式 通过信号 S I G U S R 1 通知 N e w u r l 处理进程 未访问 u r l 选取进程 U r l C a c h e N e w U r l C a c h e 图 2 . 2 主控的系统结构 主控程序 主控程序的系统结构如图 示，其中带阴影的模块是实现天网主题搜索引擎时候需要改动的部分，在第四章将会详细介绍。 原主控程序的流程如图 第四代搜索引擎 天网主题搜索引擎的设计与实现 北京大学学士论文 16 初始化工作 : 1 、 根据命令行参数设置部分环境变量，包括初始目录、创建数据库、访问间隔； 2 、 读配置文件； 3 、 初始化运行信息、 初始化共享内存 （用于管理程序监控主控状态） 、 初 始 化 新 u r l c a c h e 及未访问 u r l c a c h e ； 4 、 创 建 子 进 程 ，包 括 r o b o t 存取分析进程、 u r l 选 取 进 程 、新 u r l 插入进程、 4 个新 u r u r l 检查进程等 d a e m o n ; 5 、 设置初始 u r l ; 6 、 打开数据库、插入初始 u r l 、设置信号函数； 7 、 建立主控监听套接字； 设置 s e l e c t ( ) 的描述符集和超时时间， s e l e c t ( ) 等待事件 超 时？ 检查是否有等待未访问U R L 的搜索器，若有则选择并发送 U R L 。 有新的连接到来？ 接 受 连 接 ， 分 配 一 个s t r u c t c o n n 的表项。 有数据到来？ 调用函数 P r o c e s s ( ) 处理数据包。 主循环： 图 2 . 3 主进程系统流程 索器 主控程序 搜索器 搜索器 程 共享内存 图 索器模块图 第四代搜索引擎 天网主题搜索引擎的设计与实现 北京大学学士论文 17 搜索器，负责收集主控进程指定的网页， 分析网页，提取网页中的信息，将收集的信息回送给主控进程。主控进程和收集分析进程之间通过扩展的 口交换数据。搜索器在运行时会将它的进程号，正在收集的 前所处的状态，如正在与目标主机建立连接、正在等待主控进程分发 ，记录在共享内存中，供管理程序使用。 搜索器在分析一个网页的时候，可以得到这个网页上的所有超链接 于每一个 索器都给它赋予一定的权值，才返回给主控程序，以便主控程序按照一定的顺序在下一轮发给搜索器。 下面这个公式用来计算 权值（未考虑导向词）： = + 其中 示 各个域的权值。 示到目前为止，这个超链接被其他网页引用的次数。 示它的上一级双亲 示这个 目录的深度，越深的目录，这个 结 这一章，简单介绍了完整的天网搜索引擎的系统结构，并重点分析了其中的主控程序和搜索器的实现流程和 择算法。在下面的两章笔者将会阐述如何对这两部分修改以实现主题搜索功能。第三章将着重分析导向词、特征提取、权威和中心网页、超链分析以及网页评分等多种主题搜集策略的运用。第四章将会详细介绍这些方法在天网主题搜索引擎的实现上的具体应用。 第四代搜索引擎 天网主题搜索引擎的设计与实现 北京大学学士论文 18 第三章 主题搜索策略 向词 向词及权值的配置 导向词就是一组关键词，它们会引导搜索器按照一定顺序搜索整个网络，使得搜索引擎可以在最短的时 间里面得到最全面的跟某一个主题相关的信息。通过设置导向词以及它们对应的不同权值，所有标题、作者、正文或超连接文本中含有某一导向词的网页都会被赋予较高的权值，在搜索的时候会优先考虑。搜索器在向主控程序获得 时候也是按照权值由高到低的顺序。反之，搜索器在向主控程序提交新的 它的权值的时候，主控程序会按照权值预先排序，以便下一次有序的发给搜索器。 权值的设置有两种方法，第一种是根据管理员的经验手工设置，第二种是给定一个跟主题有关的网页集合，由程序自动提取这些网页里面共同的特征，在这些网页里面都出现 的很多的关键词，它就被选作导向词。我们把第二种方法称为“特征提取”。手工设置的好处是实现简单，同时人的经验一般比较准确，跟实际情况不会出现大的偏差，缺点是导向词可能有缺漏，权值的量化定义不够精确；特征提取的优点是权值量化定义精确，但是它要求选取用来提取特征的网页集合必须是非常有代表性而且是全面概括的，否则导向词就可能实现很大的偏差。综合这两种方法的优缺点，我们的系统采用了这两种方法的结合策略： 1 手工设置好一组导向词和它们对应的权值； 2 用这组导向词到原搜索引擎中查找出对应的网页； 3 按权值的比例选取一定数量的网 页