网络搜索引擎的研究与实现

1、学校代码： 10254 密级： 论文编号： 上海海事大学上海海事大学 SHANGHAI MARITIME UNIVERSITY 硕士学位论文硕士学位论文 MASTER DISSERTATION 论文题目：论文题目： 学科专业：学科专业： 计算机应用技术计算机应用技术 作者姓名：作者姓名： 张东振张东振 指导教师：指导教师： 张明张明 教授教授 网络搜索引擎的研究和实现网络搜索引擎的研究和实现 完成日期：完成日期： 二二一一年五月年五月 论文独创性声明论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。 论文中除了特别加以标注和致谢的地方外，不包含其他人或其他机构已 经发表

2、或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均 已在论文中作了明确的声明并表示了谢意。 作者签名： 日期： 论文使用授权声明论文使用授权声明 本人同意上海海事大学有关保留、使用学位论文的规定，即：学校 有权保留送交论文复印件，允许论文被查阅和借阅；学校可以上网公布 论文的全部或部分内容，也可以采用影印、缩印或者其他复印手段保留 论文。保密的论文在解密后遵守此规定。 作者签名： 导师签名： 日期 摘 要 随着搜索经济的崛起，人们越来越关注全球各大搜索引擎的性能、技术和日 流量。搜索引擎的使用已经深入到各个行业和普通网民的日常生活。搜索引擎经 济的繁荣，又一次向人们展示了互联网所蕴含的巨

3、大商机。今日的互联网信息每 天以指数级别的速度增长，面对海量数据的处理和存储，集中式的搜索引擎显得 无能为力，大到整个互联网的搜索，小到本地文件的查找，都离不开搜索引擎技 术的支持。本文正是基于搜索引擎的普遍化，设计并实现了一个易扩展的分布式 搜索引擎的框架结构，能够满足于不同的搜索方案。 本文从研究和设计实现的角度出发，对网络搜索引擎的相关理论和技术进行 了详细的分析和讨论，以实现一个可分布式采集和查询，可以为某一行业以及相 关软件系统提供网络数据索引和检索的功能系统为目的。 论文主要研究的内容如下： 论述目前搜索引擎的国内外发展现状、存在的问题以及发展趋势；分析了搜 索引擎的工作原理以及各

4、部分的主要功能；系统介绍了搜索引擎内核实现的原理 和相关实现方法。 为了能高效、便捷地满足用户的信息需求，吸引用户访问。针对传统个性化 技术的不足,提出基于语义的自适应网页推荐模式,采用语义本体和用户查询倾向 机制构建自适应的语义用户模型,并采用语义质心聚类技术提高推荐的准确率。实 验结果表明,与其他推荐方法相比该算法具有更高的推荐准确率和召回率。 在插件机制的基础上，设计实现了一个可扩展，并且可以进行分布式查询的 搜索引擎体系结构。每一台索引机器负责特定域名信息的采集和索引，对于存储 在不同机器上的网页数据可以进行并行检索。重点阐述了搜索系统框架的实现， 不仅给出了系统各模块之间的关系，而且

5、还分析了各个模块的实现原理和思想。 总体上，本文论述了基于插件机制的可分布式查询和采集的完整的搜索引擎 的设计方法，并且改进了语义网页推荐模式。经验证，所实现的搜索引擎的架构 体系具有良好的实用性。 关键词： 网络搜索引擎，网络蜘蛛，中文分词,分布式搜索，推荐系统 Abstract With the economic rise of search，more people begin to concern the worlds major search engine performance，technology and daily flow. The use of the search engi

6、ne has extended to various industries and the daily lives of ordinary Internet users. The economic rise of search engines, to the people once again demonstrates the Internet by the tremendous business opportunities.Today,the information in the Internet is mounted up exponentially everyday, and in th

7、e face of massive data processing and storage，the traditional search engine appears to be powerless. They cant be run without the search engine such as searching the whole or even searching the local file. Because the search engine is wide spread，The main contributions in this dissertation are given

8、 below： Achieve from the perspective of research and design , the network search engine theories and techniques are analyzed and discussed in detail in order to achieve a may be distributed storage for a particular industry and related software systems to provide network data indexing and functional

9、 system for the purpose of retrieval. What this paper referring are as follows: The page recommendation can satisfy the users demand for information efficiently and conveniently. In consideration of the deficiencies of the traditional personalized technologies, this paper proposes a self-adaptive pe

10、rsonalized Web page recommendation method based on semantics. The method constructs a self-adaptive semantic user model by the use of semantic ontology and users interest drifting mechanism, and utilizes the centers of the semantic clusters to improve the precision of recommendation. Experimental re

11、sults show that the new method has a higher precision and recall compared with the other recommendation method. Discusses the current status of internal and external, the problems and trends of the search engines; what is the search engine working principle and the main functions of the various part

12、s; system introduces the search engine core principles and the implementation methods of it. Based on the plug-in mechanism, design and implement a scalable architecture which can be distributed on a search engine. Each machine is responsible for a specific domain index information collection and in

13、dex, for storage on different machines on the web page data can be retrieved in parallel. Search here focuses on the implementation of the framework, not only gives the relationship between each module, but also the realization of the principles of each module and ideas. Conclusively, this paper dis

14、cusses a search engines plug-in mechanism and a distributed query design methods, experience certificate, the implementation of the search engine system building skills good usability, Finally，give the summary of the search engine service based on the reality. Key words: Search engine , network spid

15、er , segment，distributed search，recommendation system 目 录 第一章第一章 绪论绪论.1 1.1 课题提出的背景 .1 1.1.1 搜索引擎的概念和及类型.1 1.1.2 现阶段中文搜索引擎存在的主要问题.2 1.2 主要研究的问题.3 1.2.1 网页搜集.3 1.2.2 预处理过程.3 1.2.3 查询服务.4 第二章第二章 数据搜集的协议数据搜集的协议.5 2.1HTTP 协议 .5 2.2HTTP 消息 .5 2.2.1 请求消息.5 2.2.2 响应消息.7 2.3 网页爬行过程中的正则规则 .8 2.4 本章小结 .9 第三章第

16、三章 搜索引擎相关技术搜索引擎相关技术.10 3.1 数据获取 .10 3.1.1 网络蜘蛛功能需求.10 3.1.2 网络蜘蛛实现原理.11 3.1.3 网络爬虫系统结构.12 3.1.4 网页采集程序设计和实现.13 3.2 信息索引.18 3.2.1 网页索引功能需求.19 3.2.2 网页索引实现原理.19 3.2.3 索引过程的设计与实现.22 3.3 查询处理.24 3.3.1 查询基本流程.24 3.4 结果排序.25 3.4.1 向量模型的排序局限性.27 3.4.2 搜索引擎相关性排序.28 3.4.3 链接分析 PageRank 原理.29 3.4.4 搜索排序的基本流程.

17、30 3.5 文档分析与中文分词.30 3.5.1 文档分析预处理过程.31 3.5.2 文档分析基本流程.31 3.5.3 中文分词技术.32 3.6 分布式搜索.33 3.6.1 搜索引擎分布式介绍.33 3.6.2 分布式搜索引擎原理.34 3.7 本章小结 .36 第四章第四章 基于传统搜索引擎的改进基于传统搜索引擎的改进.37 4.1 信息抓取算法的实现 .37 4.1.1 对基于超链接信息搜索策略的改进.37 4.1.2 DNS 转化实现.37 4.1.3 页面访问的实现.39 4.1.4 文件解析.39 4.1.5 分布式抓取的体系设计.39 4.2 索引算法的实现 .41 4.

18、3 检索算法的实现 .42 4.4 插件体系实现 .44 4.5 基于语义质心的推荐算法的实现 .47 4.5.1 构造语义连通图.47 4.5.2 基于语义质心的网页推荐模式.49 4.5.3 实验分析.50 4.6 本章小结 .52 第五章第五章 系统测试系统测试.53 5.1 系统测试环境 .53 5.2 系统测试用例 .53 5.2.1 爬行测试.53 5.2.2 查询测试.55 5.2.3 测试结果分析.57 5.3 分布式查询测试.58 5.3.1 查询服务器配置.58 5.3.2 数据服务器配置.58 5.3.3 查询过程.59 5.3.4 结果分析.59 5.4 分布式采集测试

19、 .62 5.4.1 结果分析 .62 5.5 搜索引擎服务网站的盈利模式 .62 5.6 本章小结 .63 第六章第六章 总结和展望总结和展望.64 6.1 对现有工作的总结 .64 6.2 进一步研究的地方 .66 参考文献参考文献.67 致致 谢谢.71 攻读硕士期间发表论文攻读硕士期间发表论文.72 第一章 绪论 1.1 课题提出的背景 在搜索引擎市场上，自 Google 和百度占领全球大部分搜索市场分额开始， 他们霸占整个市场的局面一直维持至今。人们在期待搜索领域的下一个大东西， 也乐见新的“Google”崛起。但对新兴的搜索引擎公司来说，挑战业已存在的 传统搜索引擎任务相当艰难。不

20、过这也正使搜索引擎初创企业看到利润的另一 面，在创业之初不得不避开谷歌等传统搜索引擎的锋芒而有所创新。 如何更好地找到信息、组织信息，这是新兴搜索公司的使命和努力的方向。 而在这些努力的过程中，隐约可见搜索引擎未来发展的新潮流。 在传统搜索市场，行业巨头发起一轮轮的大型搜索引擎争夺战。从被微软 追逐的雅虎表示，不会出售搜索引擎业务，并承诺增加搜索的研发费用，升级 产品的功能。同时，新兴搜索引擎大量涌现，大多拥有令人咋舌的 3 位数的增 长速度，并吸引了风险投资的目光。根据摇钱树公司 MoneyTree 的统计，去年 约有 50 家新的搜索引擎公司，总共获得超过 3.3 亿美元风险投资。 引领新

21、的搜索潮流绝非易事。新兴的小型搜索引擎如果不能迅速壮大，极 有可能在谷歌涉足这一领域后被淘汰，或者被谷歌等大型搜索引擎收购。 1.1.1 搜索引擎的概念及类型 搜索引擎是指以互联网为平台，以信息资源为对象，以信息检索的方式为 用户提供所需信息的服务系统，主要功能包括信息存取、信息管理和信息检索 三大部分。 目前，中文搜索引擎主要有三种类型：目录式搜索引擎、机器人搜索引擎 （又称全文搜索引擎）以及元搜索引擎14-17。 (1)目录式搜索引擎。目录式搜索引擎是以人工或半人工方式收集信息，建 立数据库，由编辑人员在访问了某个 web 站点后，对该站点进行描述，并根据 站点的内容和性质将其归为一个预先

22、分好的类别。由于目录式搜索引擎的信息 分类和信息搜集有人的参与，其搜索的准确度较高，导航质量也不错。但由于 其人工的介入，维护量大，信息量少，信息更新不及时都使得人们利用它的程 度有限。 (2)机器人搜索引擎。这是一种目前较流行的搜索引擎。目前以百度， Google 等为代表。它是使用自动爬行软件，搜集和发现信息，并下载到本地文 档库，再对文档内容进行自动分析并建立索引。对于用户提出的检索要求，通 过检索模块检索索引，找出匹配文档返回给用户。 机器人搜索引擎具有庞大的全文索引数据库。其优点是信息量大，范围广， 较适用于检索难以查找的信息或一些较模糊的主题。缺点是缺乏清晰的层次结 构，检索结果重

23、复较多，需要用户自己进行筛选。 (3)元搜索引擎。元搜索引擎是一种调用其他搜索引擎的引擎。它是通过一 个统一的用户界面，帮助用户在多个搜索引擎中选择和利用合适的搜索引擎来 实现检索。中文元搜索引擎开发较少，较成熟的则更少。 1.1.2 现阶段中文搜索引擎存在的主要问题 （1）信息覆盖面有限19。现阶段搜索引擎所覆盖的数据库的规模是非常有 限的，据美国科学期刊 Natures 一篇报告中称，全球最大的搜索引擎也只能覆 盖现有网页的 16%。中文搜索引擎因起步慢、中文信息所占互联网全部信息的 比例小（只占全部网络信息的 5%）等原因在这方面尤为突出。 （2）查全率不高。查全率是指检索出的相关信息量

24、与存储在检索系统中的 全部相关信息量的百分比，是判断检索系统质量的度量之一。 （3）查准率较低。查准率更是判断检索系统质量的重要尺度。是指系统所 检索到的真正与查询内容相关的文档占检索出的所有文档数的百分比。 造成查准率低的原因是，部分搜索引擎的分类体系与科学知识体系之间缺 乏内在联系；类目之间逻辑关系模糊，导致检索路径与搜索引擎类目错位；信 息加工深度不够；检索功能单一；检索词的专指性较差；大部分的检索结果是 题录式而非全文式，其内容简单等等。机器人搜索引擎的分类和索引缺乏人工 的参与，其查准率不如目录式搜索引擎，且检索结果中还含有大量的重复、虚 假的信息。 (4)专业性的搜索引擎发展迟缓。

25、专业性的搜索引擎是为专门收录某一行业， 某一主题的信息而建立，能够提供专题信息查询服务的搜索引擎。目前中文搜 索引擎大多是综合性的，能同时收录各行业、各学科的多种信息，但在反映某 一行业或某一专题的信息方面很难做到全面、精确，不能给用户提供特定的信 息服务。这就使得专业人员，特别是某一领域的学者、专家不愿意利用中文搜 索引擎去查询资料。 (5)检索功能方面存在缺陷。一是检索中符合布尔逻辑运算符的搜索引擎极 为有限；二是关键词检索输出的结果相关度排序方式杂乱，不能根据用户需要 来选择信息输出的方式；三是多数的搜索引擎是面向主题搜索不是面向用户搜 索，不能重复利用用户检索过的成果，更不能对特定的用

26、户进行定题跟踪服务； 四是检索网站的主页不规范，有些太简，有些又太繁，而且广告内容太多，无 法进行有效检索。 (6)缺乏语义处理技术的支撑 传统信息检索以关键词为基础的索引、匹配算法尽管简单易行，但毕竟停 留在语言的表层，而没有触及语义，因此检索效果差强人意，很难进一步提高。 1.2 主要研究的问题 1.2.1 网页搜集 (1) 是否支持并发的采集数据，如果要并发，要保证所有采集器能合作采 集，不会出现重复采集的情况。 (2) 采集的数据还要有一个去重的过程,只需要采集一个网站更新的数据。 (3) 网页 URL 信息的过滤，比如广告代码，重要性较低的 URL。 (4) DNS 信息的转化和缓存

27、。 (5) 一些网站对于高密度访问的请求会拒绝，如何设定合适的延迟又可以 保证效率不降低。 (6) 对于一些特殊网页的采集问题, 比如 flash 网页，一些游戏网页等，很 多网站会让采集程序陷入其中，采集数万无效数据，显然是浪费了采集程序的 精力。 1.2.2 预处理过程 (1)关键词的提取 作为预处理阶段的一个基本任务就是提取出网页源文件的内容部分所含的 关键词 。对于中文来说2，就是要根据一个词典 E，用一个所谓的“切词软件” ， 从网页文字中切出 E 所含的词语来 这样，一个网页主要就由一组词来近似代 表了，p=t1,t2,.,tn ,要去掉诸如“的” ， “在”等没有内容指示意义的词

28、，称 为“停用词”, 一篇网页有效的词语数量大约在 200 个左右 ，文档存储采用倒 排序文件索引对于中文分词方式为优先在待分析字符串中识别和切分出一些带 有明显特征的词，以这些词作为断点，可将原字符串分为较小的串再进行机械 分词。 (2)链接分析 词频 TF、文档频率 DF 之类的统计量能在一定程度上指示词语在一篇文档 中的相对重要性 h1 可能比 h4 的内容重要。 (3)网页重要程度的计算 被引用多的就是重要的，引用这个概念恰好可以通过 HTML 超链接在网页之 间体现得非常好，Google 创立核心技术的 PageRank 就是这种思路的成功体现。 1.2.3 查询服务 用户向搜索引擎

29、发出查询，搜索引擎接受查询并向用户返回资料。搜索引 擎每时每刻都要接到来自大量用户的几乎是同时发出的查询，它按照每个用户 的要求检查自己的索引，在极短时间内找到用户需要的资料，并返回给用户。 目前，搜索引擎返回主要是以网页链接的形式提供的，这些通过这些链接，用 户便能到达含有自己所需资料的网页。通常搜索引擎会在这些链接下提供一段 网页摘要信息以帮助用户判断此网页是否含有自己需要的信息。 1.3 本文结构 本文第 2 章介绍网络数据采集的协议基础，第 3 章阐述传统搜索引擎的原 理和技术。在第 4 章中介绍了基于传统搜索引擎的基础之上的进行的改进。主 要阐述了对基于超链接信息搜索策略的改进、分布

30、式爬行和查询体系的设计、 基于语义质心的网页推荐模式和整个体系架构的插件机制。在第 5 章中，对系 统实现的测试，主要进行了爬行测试，查询测试，分布式的采集和爬行测试。 最后第 6 章对全文工作进行总结，并展望了下一步的研究方向。 第二章 数据搜集的协议 2.1HTTP 协议 HTTP ：是超文本传输协议的缩写4，用于传送 WWW 方式的数据，关于 HTTP 协议的内容在 RFC2616 可以参考。 模型 ：请求/响应 客户端向服务器发送一个请求，服务器以一个状态行作为响应，客户端根 据此状态做出操作。 客户端请求消息： 请求的方法、URI、协议版本、以及包含请求修饰符、客户信息和内容的 类似

31、于 MIME 的消息结构。 服务器端响应消息： 协议的版本、成功或者错误编码、实体元信息以及可能的实体内容。 2.2HTTP 消息 http 消息组成： （1）请求消息： 请求头，通用头，实体头 （2）响应消息： 响应头，通用头，实体头 格式： 每个头域由一个域名，冒号（:）和域值三部分组成。 域名是大小写无关的，域值前可以添加任何数量的空格符，头域可以被扩 展为多行，在每行开始处，使用至少一个空格或制表符。 2.2.1 请求消息 第一行格式： MethodSPRequest-URLSPHTTP-VersionCRLF Method：表示对于 Request-URI 完成的方法，这个字段是大小

32、写敏感的， 包括 GET、HEAD、POST、PUT、DELETE、TRACE。其中，方法 GET 和 HEAD 应该被所有的通用 WEB 服务器支持，其他所有方法的实现是可选的。 GET 方法：取回由 Request-URI 标识的信息。 HEAD 方法：也是取回由 Request-URI 标识的信息，只是可以在响应时， 不返回资源数据。 POST：方法可以请求服务器接收包含在请求中的实体信息，可以用于提交 表单，向新闻组、BBS、邮件群组和数据库发送消息。 SP：表示空格。 Request-URI：遵循 URI 格式，在此字段为星号（*）时，说明请求并不用 于某个特定的资源地址，而是用于服

33、务器本身。 HTTP-Version：表示支持的 HTTP 版本，例如为 HTTP/1.1。 CRLF：表示换行回车符。 典型的请求消息： GET http:/ HTTP1.1 Host: :80 Cache-Control:no-cache Referer:http:/ User-Agent:Mozilla/4.04cn(Win xp; Nav) Range: bytes=255- Host 头域 Host 头域指定请求资源的 Internet 主机和端口号6，必须表示请求 URL 的 原始服务器或网关的位置。HTTP/1.1 请求必须包含主机头域，否则系统会以 400 状态

34、码返回。 Referrer 头域 Referrer 头域允许客户端指定请求 URL 的源资源地址，这可以允许服务器 生成回退链表，可用来 登陆、优化 cache 等。它也允许废除的或错误的连接由 于维护的目的被追踪。如果请求的 URL 没有自己的 URL 地址，Referrer 不能被 发送。如果指定的是部分 URL 地址，则此地址应该是一个相对地址。 Range 头域 Range 头域可以请求实体的一个或者多个子范围。 例如， 表示头 500 个字节：Bytes=0-499 表示第二个 500 字节：Bytes=500-999 表示最后 500 个字节：Byt

35、es=-500 表示 500 字节以后的范围：Bytes=500- 第一个和最后一个字节：Bytes=0-0,-1 同时指定几个范围：Bytes=500-600,601-999 但是服务器可以忽略此请求头 2.2.2 响应消息 第一行格式： HTTP-VersionSPStatus-CodeSPReason- PhraseCRLF Status-Code5： （1）是一个三位的数字结果代码，主要用于机器自动识别状态 （2）第一个数字定义响应的类别,第一个数字可能取 5 个不同的值 1xx:信息响应类，表示接收到请求并且继续处理 2xx:处理成功响应类，表示动作被成功接收、理解和接受 3xx:重

36、定向响应类，为了完成指定的动作，必须接受进一步处理 4xx:客户端错误，客户请求包含语法错误或者是不能正确执行 5xx:服务端错误，服务器不能正确执行一个正确的请求 Reason-Phrase： 对 Status-Code 提供一个简单的文本描述，用于帮助用户理解 其他： 响应头域允许服务器传递不能放在状态行的附加信息，这些域主要描述服 务器的信息和 Request-URI 进一步的信息。 典型的响应消息： HTTP/1.0 200 OK Date:Mon,31Dec:25:57GMT Server:Apache/1.3.14(Unix) Content-type: text/html Las

37、t-modified:Tue,17Apr:46:28GMT Etag:a030f020ac7c01 Content-length: Content-range: bytes=- Location 响应头： Location 响应头用于重定向接收者到一个新 URI 地址。 Server 响应头： Server 响应头包含处理请求的原始服务器的软件信息。此域能包含多个产 品识和注释，产品标识一般按照重要性排序。 实体头域 Content-Type 实体头： Content-Type 实体头用于向接收方指示实体的介质类型，指定 HEAD 方法 送到接收方的实体介质类型，或 GET 方法发送的请求介质

38、类型 Content-Range 实体头。 Last-modified 实体头 Last-modified 实体头指定服务器上保存内容的最后修订时间。 2.3 网页爬行过程中的正则规则 （1）得到网页上的链接地址： string matchString = +href=s*(?:(?+)|(?+) |(?s+)s*; （2）得到网页的标题： String matchString = .*; （3）去掉网页中的所有的 html 标记： String temp = Html.Replace( *, ); （4）js 去掉所有 html 标记的函数： str.replace(/g,);/去掉所有的

39、html 标记 2.4 本章小结 本章主要介绍了网络数据获取需要用到的协议，主要涉及 HTTP 协议、 HTTP 消息、请求消息、响应消息以及数据抽取的正则规则。数据采集是搜索 引擎的底层基础模块5，准确快速的获取到网络数据是搜索引擎成功的必备条 件。 第三章 搜索引擎相关技术 3.1 数据获取 数据的获取是搜索引擎赖以实现的基本条件，在网络搜索引擎中我们以 网 络爬虫实现数据获取的 功能。网络爬虫本质上是一个典型的网络应用程序，它 主要为搜索引擎完成信息抓取功能，实现技术主要通过 Socket 编程，实现 HTTP 协议的下载功能，完成网页信息的请求和下载。 3.1.1 网络蜘蛛功能需求 网

40、络蜘蛛作为流行的爬行工具，核心功能在于对网络的信息采集，作为比 较重要的一个功能模块需要重点设计。网络蜘蛛的设计开发总体上包括 5 方面 任务要求6。具体的内容描述如下： (1) 网络蜘蛛需要动态配置属性信息，设定需要抓取 URL 起始地址或者 URL 正则范围、爬行深度和爬行的域名范围。网络爬行的过程中需要配置采集 的线程数目以及爬行时间间隔等计划任务。 (2) 新网站和新链接的更新功能。网络蜘蛛需要简单分析下载的网页代码， 提取包含的新 URL。新增加的 URL 添加到等待采集队列，保证网络蜘蛛的自 我资源发更新能力。 (3) 下载网页的存储和管理。网络蜘蛛存储下载的网页内容，为网页分析

41、和索引提供数据依据。海量搜索引擎下载文档数量惊人，需要合理的管理策略。 存储策略的高效和健壮至关重要，甚至需要考虑分布式存储策略。 (4) 高效的网页更新、死链接判别方法。网络蜘蛛对历史下载的网页需要 定期检查，判断页面内容是否更换，确定网页是否已经被删除。这部分功能需 要网络蜘蛛通过多线程并发控制，控制对同一站点的访问并发访问数量和检查 周期。 (5) 域名解析缓存机制和己下载内容的本地代理缓存。网络蜘蛛需要经常 访问同一个域名下的网页内容。域名解析内容缓存能存储域名与 IP 地址的复杂 对应关系，减少域名查询次数，大大提高网络利用率。本地下载内容代理可以 避免重复下载，减少一定时期内对目标

42、站的冗余下载。 3.1.2 网络蜘蛛实现原理 从结构上来看，互联网其实就是一个大型的网状图。搜索引擎中可以把每 一个网页当作一个节点，把网页内的超链接(Hyperlinks)当作连接网页的弧7。 搜索引擎在进行信息抓取时，可以按照图论的相关算法进行处理。网络蜘蛛从 某个网站的首页进入，按照图论的相关遍历算法就可以访问这个网站所辖的所 有信息。 开发网络蜘蛛需要了解爬行过程所要涉及的 HTTP 等网络协议的内容。 HTTP 协议是用于从互联网 WWW 服务器传输起文本到本地浏览器的传送协议。 协议的目标是使浏览器更加高效，提高网络传输效率。HTTP 协议不仅可以正 确、快速地传输起文本文档，还可

43、以确定传输文档中的哪一部分首先显示。 HTTP 协议的基本结构如图 3-1 所示: HTTP解析www网页 HTTP请求 Http页面应答 图 3-1 HTTP 协议基本结构 HTTP 协议基于请求响应范式(相当于客户机服务器)。一个 HTTP 客户机 与服务器建立连接后，发送一个请求信息给服务器，服务器接到请求后，给予 相应的响应信息。HTTP 请求的格式为格式化文本，包括统一的资源标识符 (URL)、协议版本号、以及请求修饰符、客户机参数和其他参数内容的 MIME 信息。HTTP 应答的格式也是一个格式化状态行信息，包括信息的协议版本号、 一个成功或错误的代码，以及服务器信息、实体信息和其

44、他内容的 MIME 信息。 快速抓取的过程中，除了选择 HTTP 的 API 以外，也可以使用 Socket 的 API， socket 通信编程是网络编程中比较普遍的方法，Window 环境和 Linux 环 境下都有相应的接口。各种网络游戏的编程、QQ 等也是使用这种方法，上网 浏览网页使用的 IE 浏览器底层也是通过 socket 通信实现的。Socket 的基本通信 模式如图 3-2 所示: SOCKET下 载客户端 web网站服务 器 通讯请求协议 通讯应答协议 图 3-2 Socket 通信模式 3.1.3 网络爬虫系统结构 前面已经介绍了网络蜘蛛的基本结构和作用。实际的搜索引擎系

45、统实现过 程中，需要更加偏重网络蜘蛛的功能需求。搜索引擎的网络蜘蛛与普通的离线 阅读器比较类似。运行过程是先连接网络，抓取数据8，最后进行数据存储和 信息的抽取。网络蜘蛛通常需要设计一系列的具体框架结构，来完成一个功能 强大的网页采集程序。整体结构体系涉及协议编程下载模块、缓存队列管理、 策略控制模块等内容。功能结构如图 3-3 所示: URL数数 据据库库 下下载载网网页页提提取取URL URL增增加加待待 爬爬行行队队列列 请请求求URL 读读取取/写写入入URL 图 3-3 搜索引擎网络采集系统功能结构图 网络蜘蛛并不仅仅是基本的一些原理算法实现和单机下载系统。搜索引擎 需要考虑更复杂的

46、问题。谷歌、雅虎以及百度都拥有几十亿、上百亿的网页数 据，必须拥有强大的网络蜘蛛。假设网络蜘蛛每秒钟可以下载一篇文档，按照 100 亿的网页数量，单台服务器的爬行总需时间是 300 多年。真正商业化的网 络蜘蛛需要以大量的下载服务器的分布式运行为基础（图 3-4） ，在稳定良好的 宽带条件下运行。而这样复杂的网络蜘蛛系统的建立以及任务分配与协调都非 常的复杂。 网络蜘蛛是搜索引擎的信息采集模块。通过下载得到的数据通过海量存储 的原始网页库提交给后续模块处理。后续模块处理得到由一些链接地址信息会 反馈给网络蜘蛛继续下载。网络蜘蛛与搜索引擎其他模块的关系和联系如图 3- 5 所示: 主主控控服服务

47、务器器 采采集集器器采采集集器器采采集集器器 WEB 图 3-4 多服务器并行网络采集系统结构图 链链接接地地址址库库 网网络络蜘蜘蛛蛛文文本本预预处处理理 索索引引 检检索索 下下载载正正文文库库 索索引引和和正正文文库库 待下载地址列 表 获取的链接地址 下载到的网页 原始网页 纯文本 纯内容 检索结果 图 3-5 网络蜘蛛和其他模块之间的关系图 3.1.4 网页采集程序设计和实现 对于 java 语言开发的网络采集程序的设计和实现，java 提供了很多访问各 种标准 Internet 的协议类库，可以使网络编程人员很方便的编写 Internet 程序， 网页采集程序可以直接利用 Java

48、 的网络开发函数库 J.*函数调用来完成。 类库里包含了用于处理 socket 请求协议的方法，类库中的 .www.html 包 提供了处理 HTML 语言的功能方法，在 .www.http 包提供了处理 HTTP 协议的 API。 信息抽取的两种方式6：基于内嵌浏览器的 navigation 的抽取方式和 crawler 下网页进行离线抽取。第一种方式可以利用浏览器强大的功能 js,ajax 和 visual 方面的信息，来提高抽取的准确性。但效率比较低，js load 的时间比较长， 一些情况抽取的数据下无法满足实时性服务的需要。第二种方式有较高的效率， 但 web 的多样化，ajax、f

49、lex 等技术导致许多信息根本无法抽取。对于第一种 方法可以 hack 浏览器，添加 js 加载的缓存，从缓存中直接加载 js 的 url 对应的 js 文件，能够很大程度减少加载页面的时间。 网络采集程序的大致设计思路是首先确定需要下载的 URL，指定一个通信 端口，创建一个用于网络通信的 socket 对象。网员下载默认端口 80。采集结果 采用流式输出接口的对象。经过输入接口，向 socket 对象传入 HTTP 下载的请 求。远端的目标 Web 服务器得到请求后，发送回应消息。本地 socket 对象收到 消息后缓存并输出，完成整个网员下载过程。传输过程中使用默认的 HTTP 协 议进

50、行。 网页采集程序的各个模块之中11，核心模块是获取等待可以进行持续下载 的 URL 列表、创建下载的客户端、获取并存储得到的网页结果。实际上为了设 计方便还有很多重要的内容都被暂时简化掉，比如链接的发现、多线程的创建 和任务调度。简化的基本的网络采集程序流程图如图 3-6 所示: 准准备备 是是否否有有下下载载任任 务务 获获取取等等待待下下载载 的的URL列列表表 获获取取队队列列内内 下下载载地地址址 进进行行网网络络连连 接接 发发送送网网页页请请 求求 下下载载是是否否成成 功功？ 保保存存下下载载网网 页页 转转移移存存储储的的网网页页 提提交交解解析析和和索索引引 终终止止 是

51、否 是 获获取取下下一一任任务务 图 3-6 网页采集程序流程图 互联网上分布着大量网页，不同网页的访问速度差别较大。网页下载过程 中的网络延迟成为整个系统性能的须颈。为了提高效率，网络蜘蛛通常被设计 成队列缓冲、多线程并行结构。网络蜘蛛都具有 3 个主要模块：HTTP 下载模 块、链接分析模块和下载控制模块。3 个模块有机地组成一个高效功能体系。 各模块的作用如下： （1）HTTP 下载模块利用 HTTP 网络协议下载，获取并存储网页内容。 （2）链接分析模块能够提取网页内的超链接，用来获得后续页面入口。 （3）下载控制模块控制网页访问次序、更新策略、访问队列调度等工作。 网络蜘蛛的基本结构

52、和工作流程如图 3-7 所示。 (1)访问 URL 数据库，读取 URL 入口地址，生成内存访问队列。 (2)寻找空闲的 HTTP 下载模块，分配 URL，启动下载任务。 (3)HTTP 下载模块访问互联网，得到的网页内容放入结果队列。 (4)定期保存到网页数据库，为后续索引做准备。 (5)链接分析模块提取页面内的新链接，存入 URL 数据库等待下载。 (6)重复上述过程直到全部下载完成，等待新的任务。 下下载载控控制制 模模块块 URL数数据据 库库 下下载载模模块块 下下载载模模块块 下下载载模模块块 网网页页数数据据 库库 链链接接分分析析模模 块块 访访问问队队列列结结果果队队列列 图

53、 3-7 程序设计结构图 访问策略和算法 网络蜘蛛爬行某一个网站，需要从已知的入口 URL 开始。这个 URL 通常 选择是网站的首页或者网站 MAP12。从这个页面通过链接分析，寻找并访问后 续网页地址。 互联网的链接结构是一个典型的网状结构。在这个访问过程中需要遵循一 系列的算法。通常，网络蜘蛛对网站的访问有访问深度限制，一般在 35 层。 遍历策略多采用数据结构中典型的算法：广度优先和深度优先。网络蜘蛛访问 深度限制为二级情况下的访问过程，如图 3-8 所示: A导导入入页页面面 B一一级级页页面面 C一一级级页页面面 D一一级级页页面面 E二二级级页页面面 H三三级级页

54、页面面 F二二级级页页面面 G二二级级页页面面 图 3.8 网络访问策略 在模拟网络蜘蛛的访问过程中，由于访问深度限制为二级，网络蜘蛛始终 没有访问 H 页面。其中，广度优先搜索顺序：AB，C，DE，F，G；深度 优先搜索次序：ABECDF，G。 从应用角度来看，广度优先能尽快地比较平均的获取不同网站的内容10， 比较适合于大型搜索系统初期网页库的建立；深度优先在设计的时候比较容易， 对垂直搜索或者站内检索比较合适。实际的搜索引擎爬虫在设计时，还需要引 入对网站规模和机构的判断机制，根据实际情况采用相应的算法。 效率优化和更新 大型搜索引擎系统需要抓取海量数据。系统设计者必须有

55、效地提高网络蜘 蛛的性能和效率，才能满足系统数据下载需求。网络蜘蛛的设计通常包含以下 一系列优化策略和原则： （1）对已经下载过的 URL 进行标识和比对，避免重复下裁。 （2）增加多个工作队列，提高系统的并发能力。工件队列主要有 4 类：等 待队列、处理队列、成功队列、失败队列。 （3）利用网页 Proxy 缓冲检查是否有必要从远程下载，提高传输效率。 （4）同一站点的 URL 尽量交给同一线程处理，避免不同线程集中访问站 点带来的过度负载。 网络上的页面经常修改，网络蜘蛛需要定期更新自己存储的数据。这种更 新能解决内容过时、访问死链接的问题。搜索引擎会根据网站的特征、搜索系 统的目的来动态

56、改变更新周期。内容重要、更新频繁的网站会有比较短的更新 周期。长期不修改、不维护的网站会有比较长的更新周期。 蜘蛛访问需要遵守的规范 网络蜘蛛需要遵循 robots.txt 规范。Robots.txt 是一个存放在站点根目录朗 文本文件。这个文件用来告诉蜘蛛那些目录和文件不想被采集。这样，网络蜘 蛛在采集该网站内容时，就会只收录站长允许访问的内容。如果该文件不存在， 网络蜘蛛可以认为网站默认允许采集网站全部页面。 3.2 信息索引 网页索引实现的原理，类似于自己建立一个小型的数据库系统，或者建立 一个格式化文本文件。通常所说的网页索引库，并不一定是真正的存放在数据 库中，只是网

57、页文本中索引项的一种组织和存储方式。 索引是一种数据存储和组织结构。索引主要目的是可以从大量文件中快速 找到某个单词或词语。完成信息索引建立、维护和管理功能的模块是索引器。 索引器实际上是一个文本信息处理系统。通常采用倒排文件索引构造索引系统。 经过索引后的数据按照规范化的格式存放利于快速加载和检索。 查找信息的最传统的方法是顺序扫描每个文件，但是这种方法不适用于大 型文件系统和海量的数据系统。实际工作中通常对文档格式进行规则化，便于 快速查找和定位。 文本索引的实现方法很多，当前主流的索引技术有倒排索引、后缀数组和 签名文件 3 种。后缀数组技术比较适合于短语查询，签名文档技术目前使用也 比

58、较少。倒排索引是一种高效率的索引组织方式，能够很好地支持多种检索模 型，提供高性能的检索。倒排索引技术采用字或者词作为索引项，非常适合关 键词搜索。 搜索引擎的索引使用了传统信息检索中的索引模型。索引结构通常组织成 按照索引项排列的链表形式。在检索时，可以使用检索调和索引项进行匹配， 直接定位到检索结果所在的链表。根据实际需要获取检索列表内容。大型搜索 引擎一般也采用倒排索引，来满足海量数据的组织和高速检索的需要。索引结 构的选择和设计过程中需要考虑如何提高性能。对于搜索引擎的海量信息处理， 还需要考虑如何减少资源的消耗。 3.2.1 网页索引功能需求 网页搜索引擎的索引首要和最重要的目的就是

59、提供检索服务11，为了满足 实时响应要求，索引的查询和必须在可以忍受的时间内完成，这就要求索引器 能够生成一种数据存储和组织的结构规则体系。可以在大数据量的文本数据中 快速定位到某一个特定的单词或者词组。传统的顺序扫描每个文件的方法显然 在不适合，尤其是对于大型文件，或者是海量信息的环境。实际工作中通常对 文档格式进行规范化，形成可以满足快速检索的存储格式，便于快速查找和定 位。搜索引擎最常用的索引结构是倒排文档索引，用于快速响应关键词检索， 索引程序的基本思路很简单，目的也很明确，但是需要考虑的情况是数以亿计 的网页数据需要处理，并且查询用户在同一时间内有几千人的情况下，索引系 统的每一个细

60、节就成为了影响性能的关键问题，需要考虑的内容如下： 分布式的索引和查询都是在当前网络发展环境下的有利技术，并行的爬行 技术会成倍的提高数据采集速率，在查询模块中提供并行和分布式的功能无疑 大大提高检索性能。网页数据库中的数据需要定期的 UPDATE，以便于存储最 新信息和剔除死链接。 由于数据量庞大，为了能够保存上百亿、上千亿的网页，对索引进行一定 的压缩也是非常必要的。当数据量膨胀到无法直接索引，或者直接索引的时间 空间消耗巨大时，就必须要引入快表和缓存的机制来缓解这些矛盾。 3.2.2 网页索引实现原理 搜索引擎采用关键词匹配，核心算法上也采用倒排索引结构进行。虽然根 据实际情况，出现了各