硕士学位论文-网络搜索引擎的研究与实现.doc

学校代码：10254 密级： 论文编号： 上海海事大学上海海事大学 SHANGHAI MARITIME UNIVERSITY 硕士学位论文硕士学位论文 MASTER DISSERTATION 论论文文题题目：目： 学科学科专业专业： ： 计计算机算机应应用技用技术术 作者姓名：作者姓名： 张东张东振振 指指导导教教师师： ： 张张明明 教授教授 完成日期：完成日期： 二二一一年五月年五月 网网络络搜索引擎的研究和搜索引擎的研究和实现实现 论文独创性声明论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。 论文中除了特别加以标注和致谢的地方外，不包含其他人或其他机构已 经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均 已在论文中作了明确的声明并表示了谢意。 作者签名： 日期： 论文使用授权声明论文使用授权声明 本人同意上海海事大学有关保留、使用学位论文的规定，即：学校 有权保留送交论文复印件，允许论文被查阅和借阅；学校可以上网公布 论文的全部或部分内容，也可以采用影印、缩印或者其他复印手段保留 论文。保密的论文在解密后遵守此规定。 作者签名： 导师签名： 日期 摘要 摘 要 随着搜索经济的崛起，人们越来越关注全球各大搜索引擎的性能、技术和日 流量。搜索引擎的使用已经深入到各个行业和普通网民的日常生活。搜索引擎经 济的繁荣，又一次向人们展示了互联网所蕴含的巨大商机。今日的互联网信息每 天以指数级别的速度增长，面对海量数据的处理和存储，集中式的搜索引擎显得 无能为力，大到整个互联网的搜索，小到本地文件的查找，都离不开搜索引擎技 术的支持。本文正是基于搜索引擎的普遍化，设计并实现了一个易扩展的分布式 搜索引擎的框架结构，能够满足于不同的搜索方案。 本文从研究和设计实现的角度出发，对网络搜索引擎的相关理论和技术进行 了详细的分析和讨论，以实现一个可分布式采集和查询，可以为某一行业以及相 关软件系统提供网络数据索引和检索的功能系统为目的。 论文主要研究的内容如下： 论述目前搜索引擎的国内外发展现状、存在的问题以及发展趋势；分析了搜 索引擎的工作原理以及各部分的主要功能；系统介绍了搜索引擎内核实现的原理 和相关实现方法。 为了能高效、便捷地满足用户的信息需求，吸引用户访问。针对传统个性化 技术的不足,提出基于语义的自适应网页推荐模式,采用语义本体和用户查询倾向 机制构建自适应的语义用户模型,并采用语义质心聚类技术提高推荐的准确率。实 验结果表明,与其他推荐方法相比该算法具有更高的推荐准确率和召回率。 在插件机制的基础上，设计实现了一个可扩展，并且可以进行分布式查询的 搜索引擎体系结构。每一台索引机器负责特定域名信息的采集和索引，对于存储 在不同机器上的网页数据可以进行并行检索。重点阐述了搜索系统框架的实现， 不仅给出了系统各模块之间的关系，而且还分析了各个模块的实现原理和思想。 总体上，本文论述了基于插件机制的可分布式查询和采集的完整的搜索引擎 的设计方法，并且改进了语义网页推荐模式。经验证，所实现的搜索引擎的架构 体系具有良好的实用性。 关键词： 网络搜索引擎，网络蜘蛛，中文分词,分布式搜索，推荐系统 ABSTRACT 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 engine 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 the 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 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 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 personalized 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 results 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 parts; system introduces the search engine core principles and the ABSTRACT 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 index, 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 discusses 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 spider , 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 第三章第三章 搜索引擎相关技术搜索引擎相关技术.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 搜索排序的基本流程.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.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 分布式采集测试 .62 5.4.1 结果分析 .62 5.5 搜索引擎服务网站的盈利模式 .62 5.6 本章小结 .63 第六章第六章 总结和展望总结和展望.64 6.1 对现有工作的总结 .64 6.2 进一步研究的地方 .66 参考文献参考文献.67 致致 谢谢.71 攻读硕士期间发表论文攻读硕士期间发表论文.72 第一章 绪论 1 第一章 绪论 1.1 课题提出的背景 在搜索引擎市场上，自 Google 和百度占领全球大部分搜索市场分额开始， 他们霸占整个市场的局面一直维持至今。人们在期待搜索领域的下一个大东西， 也乐见新的“Google”崛起。但对新兴的搜索引擎公司来说，挑战业已存在的 传统搜索引擎任务相当艰难。不过这也正使搜索引擎初创企业看到利润的另一 面，在创业之初不得不避开谷歌等传统搜索引擎的锋芒而有所创新。 如何更好地找到信息、组织信息，这是新兴搜索公司的使命和努力的方向。 而在这些努力的过程中，隐约可见搜索引擎未来发展的新潮流。 在传统搜索市场，行业巨头发起一轮轮的大型搜索引擎争夺战。从被微软 追逐的雅虎表示，不会出售搜索引擎业务，并承诺增加搜索的研发费用，升级 产品的功能。同时，新兴搜索引擎大量涌现，大多拥有令人咋舌的 3 位数的增 长速度，并吸引了风险投资的目光。根据摇钱树公司 MoneyTree 的统计，去年 约有 50 家新的搜索引擎公司，总共获得超过 3.3 亿美元风险投资。 引领新的搜索潮流绝非易事。新兴的小型搜索引擎如果不能迅速壮大，极 有可能在谷歌涉足这一领域后被淘汰，或者被谷歌等大型搜索引擎收购。 1.1.1 搜索引擎的概念及类型 搜索引擎是指以互联网为平台，以信息资源为对象，以信息检索的方式为 用户提供所需信息的服务系统，主要功能包括信息存取、信息管理和信息检索 三大部分。 目前，中文搜索引擎主要有三种类型：目录式搜索引擎、机器人搜索引擎 （又称全文搜索引擎）以及元搜索引擎14-17。 (1)目录式搜索引擎。目录式搜索引擎是以人工或半人工方式收集信息，建 立数据库，由编辑人员在访问了某个 web 站点后，对该站点进行描述，并根据 站点的内容和性质将其归为一个预先分好的类别。由于目录式搜索引擎的信息 分类和信息搜集有人的参与，其搜索的准确度较高，导航质量也不错。但由于 第一章 绪论 2 其人工的介入，维护量大，信息量少，信息更新不及时都使得人们利用它的程 度有限。 (2)机器人搜索引擎。这是一种目前较流行的搜索引擎。目前以百度， Google 等为代表。它是使用自动爬行软件，搜集和发现信息，并下载到本地文 档库，再对文档内容进行自动分析并建立索引。对于用户提出的检索要求，通 过检索模块检索索引，找出匹配文档返回给用户。 机器人搜索引擎具有庞大的全文索引数据库。其优点是信息量大，范围广， 较适用于检索难以查找的信息或一些较模糊的主题。缺点是缺乏清晰的层次结 构，检索结果重复较多，需要用户自己进行筛选。 (3)元搜索引擎。元搜索引擎是一种调用其他搜索引擎的引擎。它是通过一 个统一的用户界面，帮助用户在多个搜索引擎中选择和利用合适的搜索引擎来 实现检索。中文元搜索引擎开发较少，较成熟的则更少。 1.1.2 现阶段中文搜索引擎存在的主要问题 （1）信息覆盖面有限19。现阶段搜索引擎所覆盖的数据库的规模是非常有 限的，据美国科学期刊 Natures 一篇报告中称，全球最大的搜索引擎也只能覆 盖现有网页的 16%。中文搜索引擎因起步慢、中文信息所占互联网全部信息的 比例小（只占全部网络信息的 5%）等原因在这方面尤为突出。 （2）查全率不高。查全率是指检索出的相关信息量与存储在检索系统中的 全部相关信息量的百分比，是判断检索系统质量的度量之一。 （3）查准率较低。查准率更是判断检索系统质量的重要尺度。是指系统所 检索到的真正与查询内容相关的文档占检索出的所有文档数的百分比。 造成查准率低的原因是，部分搜索引擎的分类体系与科学知识体系之间缺 乏内在联系；类目之间逻辑关系模糊，导致检索路径与搜索引擎类目错位；信 息加工深度不够；检索功能单一；检索词的专指性较差；大部分的检索结果是 题录式而非全文式，其内容简单等等。机器人搜索引擎的分类和索引缺乏人工 的参与，其查准率不如目录式搜索引擎，且检索结果中还含有大量的重复、虚 假的信息。 (4)专业性的搜索引擎发展迟缓。专业性的搜索引擎是为专门收录某一行业， 第一章 绪论 3 某一主题的信息而建立，能够提供专题信息查询服务的搜索引擎。目前中文搜 索引擎大多是综合性的，能同时收录各行业、各学科的多种信息，但在反映某 一行业或某一专题的信息方面很难做到全面、精确，不能给用户提供特定的信 息服务。这就使得专业人员，特别是某一领域的学者、专家不愿意利用中文搜 索引擎去查询资料。 (5)检索功能方面存在缺陷。一是检索中符合布尔逻辑运算符的搜索引擎极 为有限；二是关键词检索输出的结果相关度排序方式杂乱，不能根据用户需要 来选择信息输出的方式；三是多数的搜索引擎是面向主题搜索不是面向用户搜 索，不能重复利用用户检索过的成果，更不能对特定的用户进行定题跟踪服务； 四是检索网站的主页不规范，有些太简，有些又太繁，而且广告内容太多，无 法进行有效检索。 (6)缺乏语义处理技术的支撑 传统信息检索以关键词为基础的索引、匹配算法尽管简单易行，但毕竟停 留在语言的表层，而没有触及语义，因此检索效果差强人意，很难进一步提高。 1.2 主要研究的问题 1.2.1 网页搜集 (1) 是否支持并发的采集数据，如果要并发，要保证所有采集器能合作采 集，不会出现重复采集的情况。 (2) 采集的数据还要有一个去重的过程,只需要采集一个网站更新的数据。 (3) 网页 URL 信息的过滤，比如广告代码，重要性较低的 URL。 (4) DNS 信息的转化和缓存。 (5) 一些网站对于高密度访问的请求会拒绝，如何设定合适的延迟又可以 保证效率不降低。 (6) 对于一些特殊网页的采集问题, 比如 flash 网页，一些游戏网页等，很 多网站会让采集程序陷入其中，采集数万无效数据，显然是浪费了采集程序的 精力。 第一章 绪论 4 1.2.2 预处理过程 (1)关键词的提取 作为预处理阶段的一个基本任务就是提取出网页源文件的内容部分所含的 关键词 。对于中文来说2，就是要根据一个词典 E，用一个所谓的“切词软件” ， 从网页文字中切出 E 所含的词语来 这样，一个网页主要就由一组词来近似代 表了，p=t1,t2,.,tn ,要去掉诸如“的” ， “在”等没有内容指示意义的词，称 为“停用词”, 一篇网页有效的词语数量大约在 200 个左右 ，文档存储采用倒 排序文件索引对于中文分词方式为优先在待分析字符串中识别和切分出一些带 有明显特征的词，以这些词作为断点，可将原字符串分为较小的串再进行机械 分词。 (2)链接分析 词频 TF、文档频率 DF 之类的统计量能在一定程度上指示词语在一篇文档 中的相对重要性 h1 可能比 h4 的内容重要。 (3)网页重要程度的计算 被引用多的就是重要的，引用这个概念恰好可以通过 HTML 超链接在网页之 间体现得非常好，Google 创立核心技术的 PageRank 就是这种思路的成功体现。 1.2.3 查询服务 用户向搜索引擎发出查询，搜索引擎接受查询并向用户返回资料。搜索引 擎每时每刻都要接到来自大量用户的几乎是同时发出的查询，它按照每个用户 的要求检查自己的索引，在极短时间内找到用户需要的资料，并返回给用户。 目前，搜索引擎返回主要是以网页链接的形式提供的，这些通过这些链接，用 户便能到达含有自己所需资料的网页。通常搜索引擎会在这些链接下提供一段 网页摘要信息以帮助用户判断此网页是否含有自己需要的信息。 1.3 本文结构 本文第 2 章介绍网络数据采集的协议基础，第 3 章阐述传统搜索引擎的原 理和技术。在第 4 章中介绍了基于传统搜索引擎的基础之上的进行的改进。主 第一章 绪论 5 要阐述了对基于超链接信息搜索策略的改进、分布式爬行和查询体系的设计、 基于语义质心的网页推荐模式和整个体系架构的插件机制。在第 5 章中，对系 统实现的测试，主要进行了爬行测试，查询测试，分布式的采集和爬行测试。 最后第 6 章对全文工作进行总结，并展望了下一步的研究方向。 第二章 数据采集的协议 6 第二章 数据搜集的协议 2.1HTTP 协议 HTTP ：是超文本传输协议的缩写4，用于传送 WWW 方式的数据，关于 HTTP 协议的内容在 RFC2616 可以参考。 模型 ：请求/响应 客户端向服务器发送一个请求，服务器以一个状态行作为响应，客户端根 据此状态做出操作。 客户端请求消息： 请求的方法、URI、协议版本、以及包含请求修饰符、客户信息和内容的 类似于 MIME 的消息结构。 服务器端响应消息： 协议的版本、成功或者错误编码、实体元信息以及可能的实体内容。 2.2HTTP 消息 http 消息组成： （1）请求消息： 请求头，通用头，实体头 （2）响应消息： 响应头，通用头，实体头 格式： 每个头域由一个域名，冒号（:）和域值三部分组成。 域名是大小写无关的，域值前可以添加任何数量的空格符，头域可以被扩 展为多行，在每行开始处，使用至少一个空格或制表符。 2.2.1 请求消息 第一行格式： 第二章 数据采集的协议 7 MethodSPRequest-URLSPHTTP-VersionCRLF Method：表示对于 Request-URI 完成的方法，这个字段是大小写敏感的， 包括 GET、HEAD、POST、PUT、DELETE、TRACE。其中，方法 GET 和 HEAD 应该被所有的通用 WEB 服务器支持，其他所有方法的实现是可选的。 GET 方法：取回由 Request-URI 标识的信息。 HEAD 方法：也是取回由 Request-URI 标识的信息，只是可以在响应时， 不返回资源数据。 POST：方法可以请求服务器接收包含在请求中的实体信息，可以用于提交 表单，向新闻组