搜索引擎中网络蜘蛛的设计与实现

I湖南师范大学计算机科学与技术专业优秀本科毕业论文搜索引擎中网络蜘蛛的设计与实现于 力 超二七年五月II目 录摘 要 .11 绪论 .31.1 课题背景 .31.2 搜索引擎的定义与发展历史 .31.3 现代搜索引擎的结构与原理 .51.4 本文研究的主要内容 .62 网络蜘蛛系统的分析与设计 .72.1 网络蜘蛛的功能分析与设计要求 .72.2 系统结构与工作原理 .82.3 基于线程池技术的线程管理 .102.4 基于广度优先的 URL Server .122.4.1 页面爬取策略 广度优先算法 .122.4.2 如何避免重复工作 .132.5 HTML 的解析 .142.6 页面的存储与更新策略 .163 基于 Java 的面向对象设计与实现 .183.1 Java 技术简介 .183.2 网络蜘蛛的面向对象设计 .193.3 线程池的实现 .213.3.1 工作线程 Spider 类 .213.3.2 线程池 SpiderPool .22III3.4 基于哈希表的 URL Server .233.4.1 数据结构 .233.4.2 如何通知线程停止 .243.5 Java Socket 与页面请求 .263.6 用正则表达式解析页面 .273.7 网络蜘蛛的控制 .293.8 程序运行结果的分析 .30结 论 .33参考文献 .35致 谢 .361搜索引擎中网络蜘蛛的设计与实现计算机科学与技术 2003 级 于力超摘 要：在互联网蓬勃发展的今天，信息浩如烟海。人们在享受互连网带来的便利的同时，却面临着一个如何在如此海量的内容中准确、快捷地找到自己所需要的信息的问题，由此互 联网搜索引擎应运而生。当前对于搜索引擎是互联网中最热门的研究领域，以提供原料为主的网络蜘蛛正是搜索引擎性能的关键所在。性能是网络蜘蛛的关键，采用多线程并发页面请求的方式可以大大提高网络蜘蛛的性能。此外，爬取策略，即优先爬取哪些网页也是影响网络蜘蛛高效性的关键因素，广度优先遍历 算法是是解决这一问题的合理答案。本文首先从搜索引擎出发，对搜索引擎的发展历史、系统结构和工作原理做了初步了解，然后探讨了网 络蜘蛛在搜索引擎中的作用和地位，进而提出了网络蜘蛛的功能和设计要求。接着，在对网络蜘蛛系统结构和工作原理所作分析的基础上，研究了线程调度、页面爬取、解析等策略和算法。并使用 Java 给出了一个网络蜘蛛的实现程序，对其运行结果做了分析。最后，本文总结了实现程序的不足和优点，并展望了下一步的研究方向。关键词：搜索引擎；网络蜘蛛；线程池；哈希表；广度优先Design and Implementation of Web Spider in Search EngineAbstract: The contents on the web are increasing exponentially as the rapid development of the Internet. A problem how to obtain the useful information from vast contents quickly and accurately is facing us while people are enjoying the 2convenience of the Internet. The solver of this problem is Web Search Engine. Nowadays, search engine is one of the hottest topics in the field of Internet technology. To provide raw materials, Web Spider is the key to the performance of Search Engine.Performance is the key to Web Spider. Using multithreading to send request concurrently can improve the performance of Web Spider. In addition, crawling strategy that which pages should be downloaded first is also the key factor of performance. Breadth-first traversal is the reasonable answer to solve this problem.This text first from search engine to set out, did first step understanding to development history, system structure and work principle of Search Engine, then searched the function and the position of Web Spider in the Search Engine, then put forward the function and design request of Web Spider.Then, through the study of the system structure and work principle, this paper studied thread scheduling, pages crawling, analytical strategies and algorithms and make one realization with Java.Finally, the paper summarized the shortcomings and advantages of the procedures, and looked forward to the next step in the direction of research.Key Words: Search Engine; Web Spider; Thread Pool; Hash Table; Breadth First31 绪论1.1 课题背景中国互联网络信息中心（CNNIC ）于 2007 年 1 月 23 日发布的第 19 次中国互联网络发展状况统计报告显示：截至 2006 年底，全国网页数和网页字节总数分别为 44.7 亿个和 122,306GB。全球范围内，据美国 IDC 调查，全球网站数量已超过 1 亿，网页数量预计已达到 150 亿个。互联网已经成为人类有史以来最大的信息源，在如此浩瀚的信息海洋中寻找自己想要的信息无异于大海捞针。搜索引擎正是为了解决这个“信息迷航” 问题 而出现的技术。它提供给用户一个接口，通过一定的技术手段，帮助用户在互联网的信息海洋中提取自己需要的信息。因此，搜索引擎站点也被誉为“ 网络门户” ，搜索引擎技术成为计算机工业界和学术 界争相研究、开 发的对象。1.2 搜索引擎的定义与发展历史搜索引擎（Search Engine）是一个对互联网信息进行搜集整理，为用户提供信息检索服务的系统。网络搜索引擎的历史可以追溯到 1991 年。最早的搜索引擎是麦吉尔大学（McGill University）开发的“ 亚奇” （Archie）。“亚奇”允许对网站上的文件名进行关键词搜索。1994 年，雅虎（Yahoo）的出现使搜索引擎的概念深入人心。然而，事实上 Yahoo 只是一个手动更新的可搜索网站目录。同样在 1994 年4第一个支持搜索文件全部文字的全文搜索引擎 WebCrawler 诞生。从此，全文搜索成为了搜索引擎的一个基本特征。WebCrawler 同时还引入另一项技术，意在为全文搜索提供“原料” 的网络机器人（Web Robot，又称网络蜘蛛，Web Spider）。网 络机器人的出现，使得搜索引擎可以以自动、海量的方式搜集信息，后来的搜索引擎大多都基于此项技术。1995 年 12 月，AltaVista 永远改变了搜索引擎的定义。 AltaVista是第一个支持自然语言搜索的搜索引擎，A1taVista 是第一个实现高级搜索语法的搜索引擎 (如 AND, OR, NOT 等) 。用户可以用A1taVista 搜索 Newsgroups(新闻组) 的内容并从互联网上获得文章，还可以搜索图片名称中的文字、搜索 Titles 等超文本元素。AltaVista提供的细致的信息搜索将 Web 虚拟成为了一个巨大的数据 库，用户输入的信息则类似于 SQL 语言，搜索引擎向智能化、个性化迈进了一大步。1998 年诞生的 Google 在后来的崛起使搜索引擎成为了互联网真正的门户和明星。它利用更加高效抓取、索引技术和排名算法使搜索引擎具备了更高的使用价值，并且逐渐改变了每个人网络生活方式。自 Google 诞 生以来，主流搜索引擎始 终以页面迭代抓取、全文索引、关键词 搜索等技术为基本特征，并没有大的发展和变化。展望未来，随着互联网信息量的持续地高速增长，以及用户对信息质量要求的不断提高，搜索引擎将朝着个性化、智能化方向发展。未来的搜5索引擎将是已用户为中心的信息服务提供商，用户可以从搜索引擎得到适合自己的、准确的信息。1.3 现代搜索引擎的结构与原理前面提到，目前主流的搜索引擎主要以页面迭代抓取、全文索引以及关键词搜索为基本特征，其内部结构如图 1.1：WWW 网络蜘蛛页面库全文索引器关键词索引库用户接口关键词分析器结果排序器搜索器图 1.1 搜索引擎内部结构图其中，用户接口是用户所接触的使用界面，用户通过用户接口输入关键词组后，关键词组将被发送到关键词分析器进行分析，一般是进行分词操作。经过分析的关键词将被送往搜索器，搜索器将从关键词索引库中提取关键词的信息，即关键词所在页面的 URL 及相关信息等。搜索到的页面往往有成千上万条之多，所以要经过结果排序器进行排序， 这个模块也是商业搜索引擎进行盈利所利用的主要工具，通过竞价排名等手段，搜索引擎将结果中付费用户的页面链接排在前面，以此来盈利。排序结果最后以 HTML 或 XML 形式发送往用户接6口，一个搜索过程到此完成。每个搜索引擎都对其关键词索引库日夜不停地进行更新、维护。通过若干只网络蜘蛛在互联网上不断“漫游 ”，来下载大量网页并存储到页面库中。全文索引器再对这些页面进行全文索引来更新关键词索引库。在页 面库与关键词索引库之间可能还会存在一个页面资源处理器，来对网 页超文本进行解析，记录其中的图像、视频、文件等资源，以此来实现搜索引擎的图片、视频、文件搜索功能。1.4 本文研究的主要内容评判搜索引擎的优劣主要从两个标准出发：结果的有效性和高效性。有效性指的是结果是否是用户想要的，好的搜索引擎返回的结果会列出对用户有用的链接；而差的则返回无用链接。高效性是指用户进行一次搜索所使用的时间是否足够短。随着计算机技术的飞速发展，借助分布式计算技术、硬件水平的提升，大多数搜索引擎在高效性方面做的不错。提高信息的有效性成为了各大搜索引擎发展的主要技术目标。信息的有效性主要取决于信息的查全率和查准率。关键词的分析、搜索、结果的排序共同决定着查准率。决定查全率的则是搜索引擎与WWW（World Wide Web 万维网）的接口网络蜘蛛。好的网络蜘蛛高效、完整、全面地爬取网页， 为索引器提供更多更好的原料。而差的网络蜘蛛将导致索引器没有足够全、足够好的页面进行索引，从而严重影响索引库的更新、维护，降低搜索引擎整体的有效性。本文以网络蜘蛛为研究对象。通过对其内部结构、工作原理进行7分析，进而使用 Java 语言对其进行技术实现，从而对搜索引擎中的网络蜘蛛有一个深刻全面的理解。2 网络蜘蛛系统的分析与设计2.1 网络蜘蛛的功能分析与设计要求对于搜索引擎来说，网络蜘蛛是最底层的原料提供者。对网络蜘蛛的需求主要来自索引器。索引器一般为全文索引器，它并不能干预网络蜘蛛的行为，因此，网络蜘蛛必须可以自动不停地运行。索引器要求网络蜘蛛爬取并保存一定字符集范围内的文本文件。保存形式可以是一个大文件也可以是文件夹或数据库。同时，由于互联网是一个全天候开放的系统，网络上的资源随时都有可能已被更新。网络蜘蛛要尽量做到下载的网页保持最