主题搜索引擎的设计与实现.doc

第四代搜索引擎 主题搜索引擎的设计与实现 Design and Implementation of Focused Search Engine 4th Generation Search Engine 北京大学计算机科学技术系计算机软件专业北京大学计算机科学技术系计算机软件专业 九七级学士毕业论文九七级学士毕业论文 指导教师 李晓明指导教师 李晓明 王建勇王建勇 作者 罗昶作者 罗昶 学号 学号 09708136 2001 年年 6 月月 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 1 指导老师对论文工作的评语指导老师对论文工作的评语 面向主题的搜索引擎 是我们 天网 搜索引擎下一步发展的重要方向 之一 罗昶同学的毕业论文 是这一新方向的良好开端 论文从系统实现的角度 较全面的阐述了实现一个高质量主题搜索引擎系 统的各个方面 着重分析了导向词 特征提取 权威和中心网页 超链分析以 及网页评分等多种搜集策略的运用 并提出了 主题度 的概念 用以衡量主 题搜索引擎的质量 意在指明一个搜索引擎在一个主题下的主题度越高 则它 越贴近这个主题 用户就越容易找到跟这个主题相关的资料 特别地 将上述 认识用于实践中 高质量地完成了一个面向影视主题的搜索引擎系统 搜集了 十多万影视信息 在影视信息方面提供着比 天网 通用搜索引擎更有效的服 务 论文内容丰富 所涉及的工作量很大 且有较强的系统性 是一篇很有参 考价值的论文 为 天网 的发展做出了贡献 老师签名 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 2 论文摘要论文摘要 互联网上的信息每天都以指数量级的速度爆炸性增长 面对如此浩瀚的资 源 搜索引擎为所有网上冲浪的用户提供了一个入口 毫不夸张的说 所有的 用户都可以从搜索引擎出发到达自己想去的网上任何一个地方 因此它也成为 除了电子邮件以外最多人使用的网上服务 但是 随着信息多元化的增长 千篇一律的给所有用户提供同一个入口显 然已经不能满足特定用户更深入的查询需求 同时 这样的通用搜索引擎在目 前的硬件条件下 要及时更新以得到互联网上较全面的信息是不太可能的 针 对这种情况 我们需要一个分类细致精确 对硬件要求低 数据全面深入 更 新及时的面向主题的搜索引擎 由于主题搜索运用了人工分类以及特征提取等 智能化策略 因此它比前三代的搜索引擎将更加有效和准确 我们将这类完善 的主题搜索引擎称为第四代搜索引擎 本文阐述了第四代搜索引擎天网主题搜索引擎的设计与实现 并着重分析 了导向词 特征提取 权威和中心网页 超链分析以及网页评分等多种搜集策 略的运用 论文最后定义了独创的 主题度 来衡量主题搜索引擎的性能 一 个搜索引擎在一个主题下的主题度越高 证明这个搜索引擎越贴近这个主题 用户就越容易找到跟这个主题相关的资料 有了 主题度 就可以很容易的 比较使用多种搜集策略以后的天网主题搜索引擎与原天网通用搜索引擎的差别 说明了前者在特定的主题下要比后者更准确贴切 关键词 关键词 互联网 万维网 搜索引擎 数据发掘 主题搜索 主题度互联网 万维网 搜索引擎 数据发掘 主题搜索 主题度 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 3 Abstract Information on the Internet grows explosively every day Search engine provides all the surfers on it with an entrance from which they can reach every corner of the web Therefore search engine becomes the most popular network service second to email With information continuing to explode in all directions however some specified kinds of users are not satisfied with only one entrance In the meanwhile due to current hardware conditions it is not likely to crawl full data on the Internet What we need is a focused search engine well classified requesting low hardware condition containing profound and entire data and updating in time Since it uses intelligent strategies such as human classification and sample extraction it is called the 4th generation search engine more efficient and accurate than the preceding ones In this paper described are the design and implementation of 4th generation search engine Webgather Focused Search Engine Mainly emphasized are its crawling strategies of orientation words sample extraction authority and hub pages anchor text analysis and page rank In the end Topic Approximation is defined for performance evaluation The higher the Topic Approximation is the more accurate the search engine is and the more easily users could find out what they really need With Topic Approximation it s easy to conclude that Webgather Focused Search Engine using intelligent strategies is more accurate than the original Webgather Search Engine without them Keyword Internet WWW Search Engine Data Mining Focused Crawling Topic Approximation 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 4 目录目录 指导老师对论文工作的评语指导老师对论文工作的评语 1 论文摘要论文摘要 2 ABSTRACT 3 目录目录 4 第一章第一章背景介绍背景介绍 7 1 1 INTERNET与 WWW 发展现状 7 1 1 1 Internet的发展历程 7 1 1 2 World wide web www 7 1 1 3 Internet的信息分布 8 1 2 搜索引擎简介 9 1 3 主题搜索引擎 第四代搜索引擎 10 1 4 小结 10 第二章第二章天网搜索引擎系统结构天网搜索引擎系统结构 12 2 1 系统简介 12 2 2 系统结构及各部分功能 12 2 2 1 WWW信息存取和分析子系统 主控程序 13 2 2 2 WWW信息收集控制子系统 搜索器 13 2 2 3 资源索引数据库 13 2 2 4 信息检索子系统 14 2 2 5 管理和监控子系统 14 2 3 主控程序及搜索器的实现 14 2 3 1 主控程序 14 2 3 2 搜索器 16 2 4 小结 17 第三章第三章主题搜索策略主题搜索策略 18 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 5 3 1 导向词 18 3 1 1 导向词及权值的配置 18 3 1 2 根据导向词及权值改变搜索顺序 19 3 2 网页评分 PAGERANK 19 3 2 1 引用计数 Hit Number 19 3 2 2 网页评分 Pagerank 20 3 3 权威网页 AUTHORITY 和中心网页 HUB 21 3 3 1 什么是权威网页和中心网页 21 3 3 2 发掘权威网页的难度 23 3 3 3 权威网页和中心网页的计算公式 23 3 3 4 计算权威网页和中心网页的算法 24 3 4 超链描述文本分析 HYPERLINK ANCHOR TEXT ANALYSIS 25 3 5 小结 25 第四章第四章天网主题搜索引擎的实现天网主题搜索引擎的实现 26 4 1 系统模块图 26 4 2 存储结构 27 4 2 1 系统数据库 27 4 2 2 搜索器和主控程序之间的通讯 扩展SOIF结构 30 4 2 3 导向词的存贮 33 4 3 搜索器的实现 34 4 3 1 导向词的加载分析 34 4 3 2 搜集策略的实现 35 4 4 小结 38 第五章第五章系统现状和性能系统现状和性能 39 5 1 天网主题搜索引擎系统现状 39 5 2 主题度的定义 39 5 3 天网主题搜索引擎与通用搜索引擎的比较 40 第六章第六章总结展望总结展望 42 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 6 致谢致谢 43 参考文献参考文献 44 参考参考 URL 45 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 7 第一章第一章 背景介绍背景介绍 1 1 Internet 与与 WWW 发展现状发展现状 1 1 1 1 1 1 INTERNETINTERNET 的发展历程的发展历程 Internet 的前身是美国国防部高级研究计划署的研究试验性网络 ARPANET 1983 年 TCP IP 成为 ARPANET 上唯一的正式协议 此后 ARPANET 上连接的网络 机器和用户快速增长 1988 年 NSFNET 和 ARPANET 互联 它的 规模以指数增长 很多地区网络开始加入 并且开始与加拿大 欧洲和太平洋 地区的网络连接 后来形成 Internet 90 年代初到现在 是 Internet 增长 最迅速的时期 1993 年 Internet 的增长速度是 341 截止到 1996 年 7 月 Internet 已连接了 134336 个网络 入网主机 1228 万台 以及数以亿计的用户 到 1998 年 7 月 Internet 已拥有 427 万个网址 4300 万个域名 3673 9 万台 主机和 3 2 亿个网页 其规模大概每年翻一番 1 1 2 1 1 2 WORLDWORLD WIDEWIDE WEB WWW WEB WWW World Wide Web WWW 是全球性的网络信息系统 一九八九年 位于瑞士的 European Laboratory for Particle Physics CERN 首先开始了 WWW 的研究工 作 随后 许多其他的研究机构 大学和公司也加入 WWW 研究者的行列 并相 继开发出各自的 WWW 软件 这些 WWW 软件的运行平台覆盖了目前主流的计算机 硬件和操作系统 在此过程中 WWW 也不断完善和发展 同时 为了保证不同 WWW 软件之间的互操作性 一系列 WWW 协议和标准也正在使用和完善之中 在最近几年里 WWW 得到了长足的发展 不仅成为企业必不可少的组成部分 并且开始走进千家万户 根据 NEC 研究院在 自然 上发布的数据 截止到 1999 年 2 月 Internet 上共有网站 1600 万个 其中公开提供 WWW 服务的网站 280 万个 共有 WWW 网页大约 8 亿页 这些网页包含了 15T 字节的数据 按照 2000 年 4 月在波士顿举行的第 5 届搜索引擎年会的会议报告 我们可以知道现 今的网页数目已经超过了 10 亿 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 8 WWW 在中国的发展速度也十分惊人 根据 CNNIC 中国互联网络信息中心 2001 年 1 月 17 日在京发布的最新的 中国互联网络发展状况统计报告 截止 到 2000 年 12 月 31 日止 我国上网计算机数有约 892 万台 我国上网用户人数 约 2250 万人 除计算机外同时使用其它设备 移动终端 信息家电等 上网的 用户人数为 92 万 CN 下注册的域名总数为 122099 个 WWW 站点数 包括 CN COM NET ORG 下的网站 约 265405 个 我国国际线路的总容量为 2799M 关于网页的数目没有具体的统计数据 但根据 科学 杂志上提供的集 合估计法 通过中国几个主要搜索引擎获得的搜索数据 天网 Chinaren 新 浪 搜狐 网易 我们可以估计到当前中国拥有的网页数已经超过 3000 万 1 1 3 1 1 3 INTERNETINTERNET 的信息分布的信息分布 Internet 上的信息资源随着 Internet 的发展而呈现出以下特点 信息量大而且分散 自治性强 信息资源多种多样 不一致和不完整性 这些特点对网络软件的性能提出了很高的要求 网络的快速发展给信息挖 掘带来了挑战 WWW 上信息呈现爆炸性的指数增长 同时伴随着上网经验不足 不太晓得如何查找信息的新用户的加入 用户很可能最大程度的运用超链来在 网上冲浪 他们通常从以下两类网站开始 第一类是目录系统 其典型代表是 Yahoo 它通 过有专业知识的网页编辑人员对网上的网页进行精选 建立一个索引目录 来 给用户提供服务 这类通过手工维护得很好的系统的优点是提供的网页准确率 高 可以有效的覆盖所有热门的主题 但它们的缺点是过于主观 而且需要高 昂的代价来建立和维护 更新改进的慢 同时不能很好的覆盖所有深奥的主题 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 9 第二类是搜索引擎系统 比如天网 它通过程序 自动地从网上搜集和分析网页 建立索引 为用户服务 这类通过关键词匹配 实现查找的自动更新的搜索引擎优点是涵盖的网页数量巨大 但通常返回太多 的低质量相关性不大的结果 1 2 搜索引擎简介搜索引擎简介 面对浩瀚的网络资源 搜索引擎为所有网上冲浪的用户提供了一个入口 毫不夸张的说 所有的用户都可以从搜索出发到达自己想去的网上任何一个地 方 因此它也成为除了电子邮件以外最多人使用的网上服务 搜索引擎技术伴随着 WWW 的发展是引人注目的 搜索引擎大约经历了三 代的更新发展 第一代搜索引擎出现于 1994 年 这类搜索引擎一般都索引少于 1 000 000 个网页 极少重新搜集网页并去刷新索引 而且其检索速度非常 慢 一般都要等待 10 秒甚至更长的时间 在实现技术上也基本沿用较为成熟的 IR Information Retrieval 网络 数据库等技术 相当于利用一些已有技术实 现的一个 WWW 上的应用 在 1994 年 3 月到 4 月 网络爬虫 World Web Worm WWWW 平均每天承受大约 1500 次查询 大约在 1996 年出现的第二代搜索引擎系统大多采用分布式方案 多个微型 计算机协同工作 来提高数据规模 响应速度和用户数量 它们一般都保持一 个大约 50 000 000 网页的索引数据库 每天能够响应 10 000 000 次用户 检索请求 1997 年 11 月 当时最先进的几个搜索引擎号称能建立从 2 000 000 到 100 000 000 的网页索引 Altavista 搜索引擎声称他们每天大 概要承受 20 000 000 次查询 自 1998 年到现在 出现了一个搜索引擎空前繁荣的时期 我们统称这一时 期的搜索引擎为第三代搜索引擎 第三代搜索引擎的发展有如下几个特点 1 索引数据库的规模继续增大 一般的商业搜索引擎都保持在几千万甚至 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 10 上亿个网页 2 除了一般意义上的搜索以外 开始出现主题搜索和地域搜索 很多小型 的垂直门户站点开始使用该技术 3 由于搜索返回数据量过大 检索结果相关度评价成为研究的焦点 相关 的研究又可以分为两类 一类是对超文本链的分析 在这方面 Stanford 大学的 Google 系统 7 和 IBM 的 Clever 系统 8 作出了很大的贡献 另 一类是用户信息的反馈 DirectHit 系统采用的就是这种方法 4 开始使用自动分类技术 Northern Light 和 Inktomi 的 Directory Engine 都在一定程度上使用了该技术 2000 年搜索引擎 2000 年大会上 按照 Google 公司总裁 Larry Page 的演讲 Google 正在用 3 000 台运行 Linux 系统的个人电脑在搜集 Web 上的网页 而且 以每天 30 台的速度向这个微机集群里添加电脑 以保持与网络的发展相同步 每台微机运行多个爬虫程序搜集网页的峰值速度是每秒 100 个网页 平均速度 是每秒 48 5 个网页 一天可以搜集超过 4 000 000 网页 1 3 主题搜索引擎主题搜索引擎 第四代搜索引擎第四代搜索引擎 随着信息多元化的增长 千篇一律的给所有用户同一个入口显然已经不能 满足特定用户更深入的查询需求 同时 这样的通用搜索引擎在目前的硬件条 件下 要及时更新以得到互联网上较全面的信息是不太可能的 针对这种情况 我们需要一个分类细致精确 数据全面深入 更新及时的面向主题的搜索引擎 由于主题搜索运用了人工分类以及特征提取等智能化策略 因此它比上面 提到的前三代的搜索引擎将更加有效和准确 我们将这类完善的主题搜索引擎 称为第四代搜索引擎 1 4 小结小结 这一章 概述了主题搜索引擎的产生背景以及它在搜索引擎历史上的地位 由于天网主题搜索是建立在原来天网搜索系统的基础上的 第二章将会介 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 11 绍天网搜索引擎的系统结构 并着重剖析搜索器和主控程序的设计实现 这是 因为主题搜索需要对这两部分做较大的改动 第三章将着重分析导向词 特征 提取 权威和中心网页 超链分析以及网页评分等多种主题搜集策略的运用 笔者将会在第四章详细介绍天网主题搜索引擎的设计与实现 最后是第五章的 系统现状性能以及第六章的总结展望 在这里笔者会比较一下使用了主题搜集 策略以后的天网主题搜索引擎与使用以前的天网通用搜索引擎的差别 并展望 以后的工作 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 12 第二章第二章 天网搜索引擎系统结构天网搜索引擎系统结构 2 1 系统简介系统简介 天网由于采用了可伸缩的分布式结构 查询 Cache 索引数据库和检索数据 库分开等先进 有效的技术 使得系统占用资源少 信息收集速度快 用户查 询响应时间快 系统对 96 7 以上的查询可在 1 秒钟之内作出响应 查准率和 查全率较高 基本达到了实用化程度 系统在设计和实现过程中 充分考虑到了用户和管理员的使用习惯 提供 了浏览器 电子邮件 中英文用户接口和方便使用 功能丰富的管理工具 因 而有很好的可用性和易用性 由于 天网 功能全面 性能突出 软件世界 杂志 年第 7 期将 天网 评价为国内最好的中英文搜索引擎 在 2001 年 4 月 天网累计访问量和索引网页数均突破了 10 000 000 天网 从 1997 年 10 月在 CERNET 上提供服务以来 得到了用户的欢迎和 好评 下面是不同时间统计的系统的使用情况 时间1998 年 9 月 1999 年 9 月2000 年 5 月2001 年 5 月 平均每天访问人 次 2200101133181751368 2 2 系统结构及各部分功能系统结构及各部分功能 天网系统主要由 WWW 信息存取和分析子系统 主控程序 WWW 信息收 集控制子系统 搜索器 资源索引数据库 信息检索子系统 管理和监控子系 统等几个部分组成 各个部分的功能如图 2 1 所示 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 13 2 2 1 2 2 1 WWWWWW 信息存取和分析子系统 主控程序 信息存取和分析子系统 主控程序 根据 WWW 信息收集控制子系统提供的 URL 和相关信息 使用 HTTP 协议 在 Internet 上获取相关资源 并能就对方主机返回的不同状态码作出相应处理 对取回的 Web 页面 主要是 HTML 格式 进行分析 自动对中文编码进行识别和 转化 对中文信息进行分词 提取页面的标题 关键词 摘要以及其中的超链 HyperLink 将分析的结果通过扩展 SOIF 接口提交给信息收集控制子系统 2 2 2 2 2 2 WWW 信息收集控制子系统 搜索器 信息收集控制子系统 搜索器 根据配置文件运用自然语言理解和知识获取技术 引导信息收集系统优先 访问特定知识领域和特定地域范围内的信息 向 HTML 存取分析进程发送需访 问的 URL 及相关信息 接收其发回的访问和分析结果 将相应的数据存入信息 数据库中 并对信息收集的频度和流量加以控制 HTML 文档 WWW 存取 分析 收集控制子系统 信息检索子系统 WWW 服务器 资源索引数据库 WWW 浏览器WWW 浏览器 WebGather 图 2 1 WebGather 系统总体结构 示意图 HTTP CGI 管理和监控子系统 WWW 存取 分析 WWW Server 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 14 2 2 3 2 2 3 资源索引数据库资源索引数据库 存储收集到的 WWW 信息 以及分析的结果 并对其重新进行基于词的分 级优化索引 以加快查询速度 2 2 4 2 2 4 信息检索子系统信息检索子系统 提供基于 WWW 方式的信息检索服务 用户通过任何标准的 WWW 浏览器 直接访问 检索系统可以支持在一次检索中使用多个检索词 中 英文 并支 持检索词之间的逻辑关系 与 或 还可以指定查询的范围和方式 精确 模 糊 检索结果以 HTML 形式返回给用户 各项结果的标题与它所对应的 URL 用超链连接起来 用户只需在浏览器中点中检索结果项的标题 就能马上取得 相应页面的实际内容 命中的 URL 页面按它与用户检索关键词的关联程度排序 使用户的检索更有效率 系统还支持在上一次返回的结果中进行查询 2 2 5 2 2 5 管理和监控子系统管理和监控子系统 提供系统配置 启动 停止 监控 统计等管理功能 信息收集控制子系统与 WWW 存取分析进程之间的信息交互是通过 TCP Socket 连接来实现的 因此各子系统可以分布运行于网络中不同的主机上 2 3 主控程序及搜索器的实现主控程序及搜索器的实现 2 3 1 2 3 1 主控程序主控程序 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 15 数数据据库库 H HT TM ML L 存存取取分分析析 H HT TM ML L 存存取取分分析析 主主进进程程 robots 存存取取分分析析进进程程 结结果果插插入入进进程程 URL 过过期期检检查查进进程程 SOCKET接口 SOIF数据格式 PIPE接口 SOIF数据格式 通过信号 SIGUSR1通知 Newurl 处处理理进进程程 未未访访问问 url 选选取取进进程程 Url Cache NewUrlCache 图图 2 2 主主控控的的系系统统结结构构 主控程序 主控程序的系统结构如图 2 2 所示 其中带阴影的模块是实现天网主题搜索 引擎时候需要改动的部分 在第四章将会详细介绍 原主控程序的流程如图 2 3 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 16 初初始始化化工工作作 1 根据命令行参数设置部分环境变量 包括初始目录 创建数据库 访问间隔 2 读配置文件 3 初始化运行信息 初始化共享内存 用于管理程序监控主控状态 初始化新url cache 及未访问 url cache 4 创建子进程 包括robot 存取分析进程 url选取进程 新url插入进程 4 个新 url 处理进程和过期 url检查进程等 daemon 5 设置初始 url 6 打开数据库 插入初始 url 设置信号函数 7 建立主控监听套接字 设置select 的描述符集和超时 时间 select 等待事件 超 时 检查是否有等待未访问 URL 的搜索器 若有则 选择并发送 URL 有新的连接到来 接受连接 分配一个 struct conn 的表项 有数据到来 调用函数 Process 处 理数据包 主主循循环环 图 2 3 主进程系统流程 2 3 2 2 3 2 搜索器搜索器 主控程序 搜索器搜索器 Restart 进程 共享内存 图 2 4 搜索器模块图 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 17 搜索器 负责收集主控进程指定的网页 分析网页 提取网页中的信息 将收 集的信息回送给主控进程 主控进程和收集分析进程之间通过扩展的 SOIF 接 口交换数据 搜索器在运行时会将它的进程号 正在收集的 URL 当前所处的 状态 如正在与目标主机建立连接 正在等待主控进程分发 URL 等 记录在共 享内存中 供管理程序使用 搜索器在分析一个网页的时候 可以得到这个网页上的所有超链接 URL 对于每一个 URL 搜索器都给它赋予一定的权值 才返回给主控程序 以便主 控程序按照一定的顺序在下一轮发给搜索器 下面这个公式用来计算 URL 的权值 未考虑导向词 Pirority URL a1 domain weight a2 link popularity a3 priority parent url a4 directory depth 其中domain weight 表示 URL 中各个域的权值 link popularity表示到 目前为止 这个超链接被其他网页引用的次数 parent url表示它的上一级双 亲 url 的权值 directory depth表示这个 url 中目录的深度 越深的目录 这个 url 的权值越低 2 4 小结小结 这一章 简单介绍了完整的天网搜索引擎的系统结构 并重点分析了其中 的主控程序和搜索器的实现流程和 URL 选择算法 在下面的两章笔者将会阐述 如何对这两部分修改以实现主题搜索功能 第三章将着重分析导向词 特征提 取 权威和中心网页 超链分析以及网页评分等多种主题搜集策略的运用 第 四章将会详细介绍这些方法在天网主题搜索引擎的实现上的具体应用 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 18 第三章第三章 主题搜索策略主题搜索策略 3 3 1 导向词导向词 3 1 1 3 1 1 导向词及权值的配置导向词及权值的配置 导向词就是一组关键词 它们会引导搜索器按照一定顺序搜索整个网络 使得搜索引擎可以在最短的时间里面得到最全面的跟某一个主题相关的信息 通过设置导向词以及它们对应的不同权值 所有标题 作者 正文或超连接文 本中含有某一导向词的网页都会被赋予较高的权值 在搜索的时候会优先考虑 搜索器在向主控程序获得 URL 的时候也是按照权值由高到低的顺序 反之 搜 索器在向主控程序提交新的 URL 和它的权值的时候 主控程序会按照权值预先 排序 以便下一次有序的发给搜索器 权值的设置有两种方法 第一种是根据管理员的经验手工设置 第二种是 给定一个跟主题有关的网页集合 由程序自动提取这些网页里面共同的特征 在这些网页里面都出现的很多的关键词 它就被选作导向词 我们把第二种方 法称为 特征提取 手工设置的好处是实现简单 同时人的经验一般比较准确 跟实际情况不会出现大的偏差 缺点是导向词可能有缺漏 权值的量化定义不 够精确 特征提取的优点是权值量化定义精确 但是它要求选取用来提取特征 的网页集合必须是非常有代表性而且是全面概括的 否则导向词就可能实现很 大的偏差 综合这两种方法的优缺点 我们的系统采用了这两种方法的结合策 略 1 手工设置好一组导向词和它们对应的权值 2 用这组导向词到原搜索引擎中查找出对应的网页 3 按权值的比例选取一定数量的网页 比如权值是 10 可以选 10n 个网页 4 用这些网页组成的集合作为特征提取程序的输入 得到一组新的导向词 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 19 以下是以 电影 为主题的一个例子的导向词及权值的配置 导向词权值 电影10 影视10 导演10 编剧10 监制10 主角8 配角8 奥斯卡5 影星9 3 1 2 3 1 2 根据导向词及权值改变搜索顺序根据导向词及权值改变搜索顺序 由上一章提到的 URL 优先级计算公式 Pirority URL a1 domain weight a2 link popularity a3 priority parent url a4 directory depth 将导向词及其权值考虑在内 可以得到新的 URL 优先级计算公式 Pirority URL a1 domain weight a2 link popularity a3 priority parent url a4 directory depth a5a5 Oi Oi 3 2 网页评分网页评分 PageRank 3 2 1 3 2 1 引用计数引用计数 HIT HIT NUMBER NUMBER 原系统中在搜索器搜集网页的时候 对于每一个网页数据库中都有一个指 向该网页的其他网页总数 称为 Hit Number 搜集器每访问一个新的网页 都 会逐一检查这个网页的所有超连接 如果发现这些超连接里面有指向已经访问 过的网页 那么这个已经访问过的网页的 Hit Number 将会被相应的加一 由此 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 20 可见 等到搜索器已经访问过的网页集合足够大的时候 理想情况是整个网络 Hit Number 越大 表示这个网页被别人引用得越多 由此可以估计这个网页也 越重要 这种网页不论是在搜索器抓取网页这方面 还是在检索器最终给用户 返回结构这方面 都应该放在优先处理的位置 但是 单纯比较两个网页的 Hit Number 有时候可能无法估计出这两个网 页正确的重要性排序 比如有两个网页 它们在 Internet 上同样只是被引用了一 次 一个是一份已经过时的个人简历 被一个个人网站所引用 除了作者以外 基本没有其他人关心 另外一个是当天发生的重大国际新闻 被 Yahoo 所引 用 每一秒钟都被世界各地不同肤色的数以百计的人浏览 这时候你不能由两 个网页的 Hit Number 一样 都是 1 就得出两个网页在 Internet 上一样重要的 结论 这样 我们需要一个更加深入的指标来评测 这就是下面提到的网页评分 PageRank 3 2 2 3 2 2 网页评分网页评分 PAGERANK PAGERANK 在考虑一个网页被另一个网页的引用时候 不是单纯的将被引用网页的 Hit Number 加一 而是将引用网页的连接数作为权 同时将该引用网页的重要性也 考虑进来 看看上面提到的例子 Yahoo 引用的网页显然比个人网站引用的 网页重要 因为 Yahoo 本身很重要 就可以得到扩展后的网页评分 最早提出网页评分的计算方法是 Google 它们提出了一个 随机冲浪 模 型来描述网络用户对网页的访问行为 模型假设如下 1 用户随机的选择一个网页作为上网的起始网页 2 看完这个网页后 从该网页内所含的超链内随机的选择一个页面继续进 行浏览 3 沿着超链前进了一定数目的网页后 用户对这个主题感到厌倦 重新随 机选择一个网页进行浏览 并重复 2 和 3 按照以上的用户行为模型 每个网页可能被访问到的次数就是该网页的链 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 21 接权值 如何计算这个权值呢 PageRank 采用以下公式进行计算 N jii i i jij n W lddW 1 1 其中 Wj代表第 j 个网页的权值 lij只取 0 1 值 代表从网页 i 到网页 j 是 否存在链接 ni代表网页 i 有多少个链向其它网页的链接 d 代表 随机冲浪 中沿着链接访问网页的平均次数 选择合适的数值 递归的使用以上公式 即 可得到理想的网页链接权值 该方法能够大幅度的提高简单检索返回结果的质量 同时能够有效的防止 网页编写者对搜索引擎的欺骗 因此可以将其广泛的应用在检索器提供给用户 的网页排序上 对于网页评分越高的网页 就排的越前 3 3 权威网页权威网页 Authority 和中心网页和中心网页 Hub 3 3 1 3 3 1 什么是权威网页和中心网页什么是权威网页和中心网页 权威网页权威网页 顾名思义 是给定主题底下的一系列重要的权威的网页 其重 要性和权威性主要体现在以下两点 第一点 从单个网页来看 它的网页内容本身对于这个给定主题来说是 重要的 第二点 从这个网页在整个互联网重的地位来看 这个网页是被其他网 页承认为权威的 这主要体现在跟这个主题相关的很多网页都 有链接指向这个网页 由此可见 权威网页对于主题搜索引擎的实现有很重大的意义 主题搜索 引擎一个很关键的任务就是从互联网上无数的网页之中最快最准的找出这些可 数的权威网页 并为他们建立索引 这也是有效区别主题搜索引擎和前三代传 统通用搜索引擎的重要特征 中心网页中心网页 是包含很多指向权威网页的超链接的网页 最典型中心网页的 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 22 一个例子是 Yahoo 它的目录结构指向了很多主题的权威网页 使得它兼任 了很多主题的中心网页 由中心网页出发 轻而易举的就会到达大量的权威网 页 因此 它对于主题搜索引擎的实现也起了很大的意义 权威网页和中心网页之间是一种互相促进互相促进的关系 一个好的中心网页必然 要有超链接指向多个权威网页 一个好的权威网页反过来也必然被多个中心网 页所链接 他们的关系如图 3 1 所示 权威网页权威网页 中心网页中心网页 图图 3 1 权威网页和中心网页权威网页和中心网页 权威网页权威网页 权威网页权威网页 中心网页中心网页 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 23 3 3 2 3 3 2 发掘权威网页的难度发掘权威网页的难度 前三代传统搜索引擎很大程度运用了单个网页内容 网页上出现的关键词 来发掘重要的网页 而忽略了网页在互联网中的地位 用这种方法要从互联网 上无数的网页之中找出这些可数的权威网页 有较大的难度 再看一下上面的 图 3 1 如果每一个权威网页都像图上那样写着 权威 两个字来让你发现 那 么我们的工作将会简单的多 可是现实却没有这么理想 首先 根据关键词出现的频率很难判定这个网页的权威性 考察一下这个 例子 比如你想找关于 北京大学 的权威网页 显然 北京大学的主页 是互联网上关于 北京大学 最权威的网页之一 用基于 关键词的传统的搜索引擎来查找 很自然的会输入 北京大学 或者 北大 这时候的查询效果不一定很理想 因为互联网上有成千上万包含 北京大学 或 北大 作为关键词的网页 如 北大方正 北大在线 北京大学网络 中心 等 而北大主页并不一定是 北京大学 或 北大 这两个关键词出现 的最多最显著的网页 这样 不禁令人猜想到 根本没有一种方法可以从网页 内在内容本身来判断这个网页的权威性 其次 很多权威网页本身并没有包含跟它所属主题相关的关键词 比如你 想找出网上 电脑销售 的大公司 如果你以 电脑销售 作为关键词 你很 难找到 联想 或 方正 公司的主页 因为他们的主页上根本不会出现 电 脑销售 的字眼 但他们的的确确是 电脑销售 的权威网页 由此我们可以得出结论 要找出权威网页 必须将该网页的内在因素和外 在因素都考虑在内 也就是说 除了要分析这个网页包含的关键词 还要分析 互联网上其他网页指向这个网页的超链接 3 3 3 3 3 3 权威网页和中心网页的计算公式权威网页和中心网页的计算公式 虽然上面提到了发掘权威网页的难度 但根据权威网页和中心网页互相促互相促 进进的关系 可用递推的方法循环计算出权威网页和中心网页 对于与某一个主 题相关的网页集合中的每一个网页 我们都给他们定义两个参数 A Authority 和 H Hub A 值越高表示网页的权威度越高 H 值越高表示 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 24 网页的中心度越高 将网页集合用有向图 G V E 表示 其中节点集 V 由网页组成 有向 边集合 E 表示网页间的超链接 对于 I V A I H I 分别表示 I 对应的网页的 权威度和中心度 为了控制 A H 的范围 我们将 A H 定义在 0 1 并且规格化 A H 使得 I V A I 2 1 I V H I 2 1 对于每一个节点 I 均有 A I i j E H J 3 1 H I i j E A J 3 2 本文只给出一个计算 A 值和 H 值的递推公式 有关该公式的收敛性证明 请参阅参考资料 5 3 3 4 3 3 4 计算权威网页和中心网页的算法计算权威网页和中心网页的算法 根据上面提供的公式 我们很容易就得到计算权威网页和中心网页的算法 计算权威网页和中心网页算法 G k G 网页集合对应的有向图 k 一个常数 定义 z 向量 1 1 1 1 R n X0 z Y0 z For i 1 2 k 用 Xi 1 Yi 1 代入公式 3 1 得到新的 Xi 用 Xi Yi 1 代入公式 3 2 得到新的 Xi 规格化 Xi 得到新的 Xi 规格化 Yi 得到新的 Yi 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 25 End Return Xk Yk 3 4 超链描述文本分析超链描述文本分析 Hyperlink Anchor Text Analysis 互联网的魅力在于 互联 从互联网上任何一 个地方出发 就可以轻而易举的到达世界上其它的 地方 实现互联是通过一系列的 超级文本链接 Hypertext Link 可以这样说 没有了 超级文本 链接 互联网会变得不名一文 每一个超级链接都 有一个描述文本 Anchor Text 这个文本反映了该 网页与该链接所至网页的某种关系 是互联的关键 所在 通过分析这个描述文本 就可以得到网页之 间重要的关系 原系统将这个描述文本与其所在的网页关联 我们在新系统的实现中 将 描述文本与其所指向的网页相关联 这样做会对程序的编写带来一定的复杂性 因为搜索器在处理当前网页的时候 会遇到这个网页上很多的超链接描述文本 如果将它们都与当前网页关联 处理起来就很简单 否则 如果对于每一个超 链接描述文本都将其与目标网页关联 就需要频繁的切换当前处理的网页 影 响到了搜索器处理网页的速度 虽然这样做增添了程序的复杂度 但是却有它 自身的很多好处 首先 描述文本通常比网页上的文本要更加精确的概括这个 网页 其次 基于文本切词的搜索引擎并不能处理网络上的所有格式 比如一 些图像 程序 数据库和多媒体等格式的文件 但是依靠超链接里面的描述文 本与其关联 即使搜索器本身并没有真的抓取这些格式的文件 也可以索引这 些搜索引擎无法直接索引的文件 但是这时候需要注意一个问题 就是通常说 的 死链 问题 因为搜索器本身并没有真的抓取这些格式的文件 而只是记 录了超链接描述文本 所以这些链接有可能只有描述文本 而它指向的文件根 本不存在 这就是 死链 3 5 小结小结 这一章从导向词 权威和中心网页 超链分析导向词 权威和中心网页 超链分析以及网页评分网页评分等多种搜集策 图 网页的互链结构图 网页的互链结构 A C D B 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 26 略入手 阐述了主题搜索引擎的关键设计思想 在这个基础上 笔者将在下一 章具体介绍天网主题搜索引擎的实现 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 27 第四章第四章 天网主题搜索引擎的实现天网主题搜索引擎的实现 4 1 系统模块图系统模块图 图 4 1 和图 4 2 对比了通用搜索引擎和主题搜索引擎的系统模块图 由上图 可以看出 主题搜索引擎需要建立多个面向不同主题的搜集数据库和检索数据 库 为了达到这个目的系统需要同时运行多个搜索器 分析器和检索器进程 并且允许不同主题对应的搜索器相互之间独立 更新数据允许不同步 主题搜索主题搜索 引擎引擎 Internet 通用搜集数据库通用搜集数据库 通用检索数据库通用检索数据库 索引器索引器 分析器分析器 搜索器搜索器 检索器检索器 图 4 1 通用搜索引擎系统模块图 Internet 索引器索引器 分析器分析器 搜索器搜索器 检索器检索器检索器检索器检索器检索器 搜索器搜索器搜索器搜索器 分析器分析器分析器分析器 主主题题库库据据数数集集搜搜 主主题题库库据据数数索索检检 图 4 2 主题搜索引擎系统模块图 第四代搜索引擎 天网主题搜索引擎的设计与实现北京大学学士论文 28 4 2 存储结构存储结构 4 2 1 4 2 1 系统数据库系统数据库 系统主数据库采用 Informix 数据库 由 visited tab unvisit tab newurl tab host tab dir tab delete tab filtered tab host2ip tab run info 等 9 个表构成 下面是几个主要表项的说明 visited tab 记录了已访问的 URL 的所有的信息 列 名类 型描 述 org urlchar 128 not null 是原URL的值 在数据库中有唯一的值 此org url中的主机部分是域名 检测重 复URL的方法是 url和org url在数据 库中都是唯一的 urlchar 128 not null 是URL的值 在数据库中有唯一的值 目前URL中的主机部分是IP 目的 是为了防止重复主机的出现 Urlnoint not null URL的序号 唯一存在 Resultint not null 存取分析进程返回的结果码 Hitnumint not null 此URL被别的文章引用的次数 code typechar 16 此URL对应的文章的汉字编码 Abstractchar 512 文章的摘要 Authorchar 32 文章的作者 Weightint 文章的权值 包含导向词信息 Discriptionchar 80 文章的描述 File Sizeint 文章的长度 Update Timeint 文章的索引 即本表项 信息插入的时 间 Keywordschar 256 文章的关键词 包含关键