网络蜘蛛的制作
简易网络蜘蛛的制作
1 绪论
1.1 目的和意义
互联网的飞速发展带来了网络上信息的飞速增长, 使得网络成为了人们获取信息的一个最重要的途径之一,然而面对如此海量的互联网信息,如何能够快速、准确地检索到用户需要的信息成为了一个重要的挑战,搜索引擎正是在此背景下产生的划时代技术产品。
1990年,加拿大麦吉尔大学(University of McGill)计算机学院的师生开发出Archie ,它能定期搜集并分析FTP 服务器上的文件名信息,提供查找分别在各个FTP 主机中的文件。用户必须输入精确的文件名进行搜索,Archie 告诉用户哪个FTP 服务器能下载该文件,被称为现代搜索引擎的鼻祖。随后出现的以雅虎为代表的网站分类目录查询等等,到至今很成熟的搜索引擎,如:百度、google 、新浪、搜狐、雅虎等等。为互联网用户检索提供了更方便、更快速、更准确的信息检索方法。
即便是当今较为成熟的百度搜索引擎,也会因为用户检索信息的输入,而检索到不同的结果。举一个很简单的例子,比如在百度里搜索:“计算机四级成绩查询”和“四级计算机成绩查询”,以下是搜索结果:
图1 计算机四级成绩查询搜索结果
图2 四级计算机成绩查询搜索结果
很显然,用户搜索的结果并不是完全一样,为什么会出现这种情况呢?这与搜索引擎的处理密切相关。
然而,据中国互联网络信息中心(CNNIC)发布的《第22次中国互联网络发展状况统计报告》[1]显示:截至2008年6月底,我国网民数量达2.53亿,这个数量只是中国互联网普及率的19.1%。统计表明,中国网站数量持续增长,共有191.9万个,年增长率为46.3%;其中CN 下的网站数为136.9万,占总网站数71.3%。还有世界诸多国家的互联网用户,随着互联网的广泛普及,平板电脑、手机用户越来越多,在信息海洋里搜索用户想要的信息,随着信息的增长,会变得越来越困难。因为当面对千千万万的互联网用户时,搜索引擎并不能预测用户的所有输入检索信息的方式,因此,了解搜索引擎的工作原理,能够帮助用户更精确、更快捷地检索到自己需要的信息。
1.2 国内外现状
第一代搜索引擎出现于1994年。这类搜索引擎一般都索引少于1,000,000个网页,极少重新搜集网页并去刷新索引。而且其检索速度非常慢,一般都要等待10秒甚至更长的时间。在实现技术上也基本沿用较为成熟的IR (Information Retrieval )、网络、数据库等技术,相当于利用一些已有技术实现的一个WWW 上的应用。在1994年3月到4月,网络爬虫World Wide 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) 索引数据库的规模继续增大,一般的商业搜索引擎都保持在几千万甚至 上亿个网页。
(2) 除了一般意义上的搜索以外,开始出现主题搜索和地域搜索。很多小型的垂直门户站点开始使用该技术。
(3) 由于搜索返回数据量过大,检索结果相关度评价成为研究的焦点。相关的研究又可以分为两类:一类是对超文本链的分析,在这方面Stanford 大学的Google 系统和IBM 的Clever 系统作出了很大的贡献;另一类是用户信息的反馈,Direct Hit系统采用的就是这种方法。
(4) 开始使用自动分类技术。Northern Light 和Inktomi 的Directory,Engine 都在一定程度上使用了该技术。
全文搜索引擎是目前广泛应用的主流搜索引擎,国外代表有Google ,国内则有著名的百度。它们从互联网提取各个网站的信息(以网页文字为主),建立起数据库,并能检索与用户查询条件相匹配的记录,按一定的排列顺序返回结果。
根据搜索结果来源的不同,全文搜索引擎可分为两类,一类拥有自己的检索程序(Indexer ),俗称“蜘蛛”(Spider )程序或“机器人”(Robot )程序,能自建网页数据库,搜索结果直接从自身的数据库中调用,上面提到的Google 和百度就属于此类;另一类则是租用其他搜索引擎的数据库,并按自定的格式排列搜索结果,如Lycos 搜索引擎。
目录索引,顾名思义就是将网站分门别类地存放在相应的目录中,因此用户在查询信息时,可选择关键词搜索,也可按分类目录逐层查找。如以关键词搜索,返回的结果跟搜索引擎一样,也是根据信息关联程度排列网站,只不过其中人为因素要多一些。如果按分层目录查找,某一目录中网站的排名则是由标题字母的先后顺序决定(也有例外)。
目前,搜索引擎与目录索引有相互融合渗透的趋势。原来一些纯粹的全文搜
索引擎现在也提供目录搜索,如Google 就借用Open Directory 目录提供分类查询。而象 Yahoo 这些老牌目录索引则通过与Google 等搜索引擎合作扩大搜索范围。在默认搜索模式下,一些目录类搜索引擎首先返回的是自己目录中匹配的网站,如中国的搜狐、新浪、网易等;而另外一些则默认的是网页搜索,如Yahoo 。这种引擎的特点是找的准确率比较高。
1.3 本文工作
本文从前面的分析可以发现搜索引擎受到越来越多的研究人员的关注,并且越来越多的相关研究成果被发表,成熟的商业运行模式也取得了成功。对搜索引擎研究的根本目的是为了能够自动地获取利用自由分布在整个互联网上的关于某一主题的丰富信息。
虽然整个Web 资源几乎包含了关于某一主题的全部信息,如数码产品类的主题网页,包括产品型号、价格、销售商、网友点评等,但要想以手工的方式对其进行抓取整理加以利用,在实际操作中是一件非常困难的事情。而对主题资源的有效搜索、整合正是为了以尽可能自动的方式来完成对Web 数据库中信息的有效利用。正是基于这种认识,本文在学习传统搜索引擎技术的基础上,对搜索引擎系统的关键技术进行了研究,并用C#语言模拟了蜘蛛系统,并将其应用于任何网站的信息搜索采集中。
通过本文,你可以初步了解搜索引擎的原理,搜索引擎的实现基本核心——网络蜘蛛,以及模拟的关键字搜索的实现信息检索。
本文的主要研究内容如下:
(1) 用C#编写一个蜘蛛程序,从指定蜘蛛程序入口的链接开始,检索指定网页中的所有的链接。
(2) 分析检索到的网页,解析出网页的内容,并将解析的内容和网页插入数据库。
(3) 提供搜索框,根据用户输入的关键字,从数据库中匹配,找到用户要搜索的信息的页面,加载到列表中供用户查阅。
1.4 本文组织
本文的内容共分为六章:
第1章 绪论包含四个部分,首先介绍了研究模拟搜索引擎的目的和意义,
然后介绍了国内外搜索引擎发展的状况并提出综合搜索引擎所面临的问题,然后总体介绍了下本文的研究工作内容,之后是本文的组织结构的描述。
第2章 本章节是开发环境的介绍。对开发环境进行了介绍,主要使用到的C#技术、LINQ To SQL 技术的简介和开发工具以及运行环境的详细介绍,以及为什么选择此类技术研究搜索引擎的设计与实现。
第3章 本章节是网络蜘蛛原理的介绍。主要介绍了搜索引擎核心蜘蛛程序的概念,为什么搜索引擎要使用网络蜘蛛来采集信息。详细的网络蜘蛛程序访问互联网的策略和原理。
第4章 本章节包括两个部分:首先是网络蜘蛛的关键技术;然后是数据库的结构设计。网络蜘蛛的关键技术部分包括三小节:蜘蛛程序的实现步骤,页面解析技术,为什么要使用多线程。
第一小节对搜索引擎核心算法——蜘蛛程序的实现步骤进行了详细的介绍,蜘蛛遍历网页的深度优先与广度优先算法的细致介绍。第二小节对采集的页面的信息进行解析的方法的介绍。第三小节回答了蜘蛛程序为什么要使用多线程。
第二部分介绍了数据库结构的设计,模拟搜索引擎的采集信息的存储结构表。
第5章 本章节涉及模拟搜索引擎的实现,主要包括四个部分:第一小节是搜索引擎的原理的介绍,主要介绍了搜索引擎的三个基本原理;第二小节是蜘蛛程序的实现;第三小节是使用LINQ 技术查询采集的和解析的数据信息;第四小节是模拟信息检索的实现。
第6章 本章节是模拟搜索引擎的结果以及总结,描述了模拟效果和设计的总结。
2 开发环境简介
2.1 C#技术
C sharp(又被简称为"C#")是微软公司在2OOO 年6月发布的一种新的编程语言, 并定于在微软职业开发者论坛(PDC)上登台亮相.C#是微软公司研究员Anders Hejlsberg 的最新成果.C#看起来与Java 有着惊人的相似; 它包括了诸如单一继承, 界面, 与Java 几乎同样的语法, 和编译成中间代码再运行的过程. 但是C#与Java 有着明显的不同, 它借鉴了Delphi 的一个特点, 与COM(组件对象模型) 是直接集成的, 而且它是微软公司.NET windows 网络框架的主要语言。微软c#语言定义主要是
从C 和C++继承而来的[2],而且语言中的许多元素也反映了这一点。C#在设计者从C++继承的可选选项方面比Java 要广泛一些(比如说structs) ,它还增加了自己新的特点(比方说源代码版本定义). 但它还太不成熟,C#还需要进化成一种开发者能够接受和采用的语言[3]。
C#有一个名叫object 的类是所有其他类的基类. 而一个名叫string 的类也象object 一样是这个语言的一部分. 作为语言的一部分存在意味着编译器有可能使用它--无论何时你在程序中写入一句带引号的字符串, 编译器会创建一个string 对象来保存它[4]。
2.2 LINQ to SQL简介
LINQ to SQL 全称基于关系数据的.NET 语言集成查询,用于以对象形式管理关系数据,并提供了丰富的查询功能。其建立于公共语言类型系统中的基于的SQL 模式定义的集成之上,当保持关系型模型表达能力和对底层存储的直接查询评测的性能时,这个集成在关系型数据之上提供强类型数据[5]。
LINQ To SQL 将关系数据库的数据模型映射开发人员所用的编程语言表示的对象模型[6]。当应用程序运行时,LINQ To SQL语言集成查询转换为 SQL ,然后将它们发送到数据库进行执行。当数据库返回执行结果时,LINQ To SQL 会将它们转换回您可以用您自己的编程语言处理的对象。使用Visual Studio 的开发人员通常使用对象关系设计器(O/R 设计器),LINQ To SQL提供了用于实现此转换的功能,使得对数据库的操作变得更加轻松简便。
2.3 开发工具的选择和运行环境介绍
2.3.1 开发工具的选择
C#多线程技术、Http 请求、网页解析等等技术特别适合模拟搜索引擎的核心——网络蜘蛛的实现,再结合ASP.NET 的优点,特别适合模拟搜索引擎的模拟与实现,而且C#用的是微软官方推出的Visual Studio 作为开发工具,有一个很方便、成熟的开发测试平台,再结合我自己的实际情况,我选择Visual Studio 2008作为开发工具,选择C#作为开发语言,开发蜘蛛程序和解析提取网络蜘蛛抓取的页面的信息,ASP.NET 作为模拟搜索引擎的界面及实现搜索。使用
SQLServer2005实现数据库应用和数据管理的设计方案。
2.3.2 运行环境介绍
Windows XP系统运行平台,IIS6.0WEB 服务器和脚本解释器,IE8.0浏览器,Visual Studio2008,.NET FrameWork 3.5和SQLServer2005企业版。
3 网络蜘蛛的原理
3.1 网络蜘蛛的概念
3.1.1 什么是网络蜘蛛
互联网由若干的网页传输数据,像一个巨大的网络,而通过网页的链接地址来寻找网页, 在这些网页间穿梭并提取信息的程序——网络蜘蛛即Web Spider 。是一个很形象的名字。把互联网比喻成一个蜘蛛网,那么Spider 就是在网上爬来爬去的蜘蛛。网络蜘蛛是通过网页的链接地址来寻找网页,从网站某一个页面(通常是首页)开始,读取网页的内容,找到在网页中的其它链接地址,然后通过这些链接地址寻找下一个网页,这样一直循环下去[7],直到把这个网站所有的网页都抓取完为止。如果把整个互联网当成一个网站,那么网络蜘蛛就可以用这个原理把互联网上所有的网页都抓取下来。这样看来,网络蜘蛛就是一个爬行程序,一个抓取网页的程序。网络蜘蛛(Spider) 因此得名[7]。
蜘蛛访问任何一个网站时,都会先访问网站根目录下的robots.txt 文件。如果robots.txt 文件禁止搜索引擎抓取某些文件或目录,蜘蛛将遵守协议,不抓取被禁止的网址。
和浏览器一样,搜索引擎蜘蛛也有标明自己身份的代理名称,站长可以在日志文件中看到搜索引擎的特定代理名称,从而辨识搜索引擎蜘蛛。
3.1.2 为什么要使用网络蜘蛛
为了方便互联网用户能够快捷搜索到想要的信息,必须对互联网上数以万计的信息做处理,如果人工处理的话,效率低下,远远赶不上信息的更新步伐,因此需要一种高效快捷的处理工具,网络蜘蛛正是处理互联网信息海洋的工具,它高效不知疲倦地在信息海洋里飞快地检索。而且,理论上,只要有足够的时间,网络蜘蛛会爬遍互联网上的每一个网站,抓取互联网上的所有的信息。网络蜘蛛是搜索引擎实现搜索功能的核心,通过网络蜘蛛在互联网上爬行,收集互联网上
的海量信息。
使用网络蜘蛛替代了大量的人工繁琐的体力劳动,而且只要网络畅通,服务器端硬件支持,就能够自动检索整理互联网上的大量的数据,所以搜索引擎使用网络蜘蛛,更能提高所搜引擎的信息存储量和更全面地服务互联网用户。
3.2 网络蜘蛛的访问策略
(1) 搜索策略
网络蜘蛛的搜索策略指的是如何根据抓取下来的URL 地址来选择访问地址先后的一种标准或规则。它将指导蜘蛛程序下一步的执行方向。搜索策略一般有深度优先的搜索策略和广度优先的搜索策略两种。
广度优先的搜索是最简便的图搜索算法,在数据结构上通常会以先进先出的队列结构为主,管理和实现起来都相当的简单,一般被认为是盲目的搜索。它是一种以搜索更多的网页为优先的一种贪婪的搜索策略。它会先读取一个文档,保存下文档上的所有链接,然后读取所有这些链接文档,并依次进行下去。这样做的好处是避免了在极短的时间内连续访问这台服务器上的文档的可能性,因为一个文档上的链接通常会有几个跳到别的服务器上,这样做十分有利于避免影响别的服务器工作。这种方法也通常被应用于聚焦爬虫中。其基本思想是认为与初始URL 在一定链接距离内的网页具有主题相关性的概率很大。同时它还可以使尽可能多的服务器有文档被索引服务器收集。它的缺点是很难深入到文档里面,而且随着抓取网页的增多,大量的无关网页将被下载并过滤,算法的效率变得十分的低下。
深度优先的搜索策略是以先进后出的栈方式来处理URL 地址的。网络蜘蛛程序分析一个文档,并取出它的第一个链接所指的文档继续分析,然后如此继续下去。它的优点就是能够较好的深入和发掘站点的结构,而且这种算法十分稳定,效率方面也是有所保障的。它对于搜索部分小的网站是有好处的。它的缺点是十分明显的,不断的短时间的访问同一台服务器的问题将非常的严重,而且它还容易陷入无限循环的文档树,这种算法处理这个问题的能力相当的有限。
将两种算法结合起来也是一种不错的办法,这两种算法互有长短,有些地方也可以形成互补。以一种算法为主,一种算法相辅的办法可以达到取长补短的效果。除了以上的算法之外,最好优先算法也经常被采用,它通过对采集的链接通
过一些关于网页质量和效率的算法来排序,优秀者将优先被抓取。但是这个关于质量和效率的算法则又有许多不同的版本,在这里就不作详细的展开了。除去这些常用的算法,还有一些不常被人采用的优秀算法,如Hash 算法,遗传算法等。
(2) 更新策略
索引中大量的网页是很少变化的,对所有的网页按照同一频率统一更新是完全没有必要的。因而以网页变化的周期为依据,只对那些经常变化的网页做更新操作也是一些小型的搜索引擎常采用的方法。但是只对部分网页做更新可能会漏掉一些重要网页的更新工作,所以网络爬虫也经常采用个体更新的策略。它是以个别网页的变化频率来决定对网页的更新频率,这样一来基本上每个网页都会有一个独立的更新频率。
4 网络蜘蛛算法与数据库的设计
4.1 网络蜘蛛的关键技术
4.1.1 蜘蛛程序的实现步骤
C#蜘蛛程序主要用到Http 协议从互联网上请求信息,并进行以下操作:
(1) 通过一个链接地址进入网站,查找网站内部的链接;
(2) 判断每一个查找到的链接,并判断该链接是否应经被蜘蛛程序遍历处理过,如果被蜘蛛遍历过则进行第三步,如果未被蜘蛛遍历过,则进行第四步;
(3) 根据遍历的算法解析该网页中的链接,获得URL 链接进行第一步;
(4) 蜘蛛程序从此链接进入,解析HTML ,根据解析到的href 属性获得页面链接,然后查找页面的URL 进行第一步;把解析到的页面内容插入数据库,建立搜索的数据库。
(5) 从数据库中提取URL 链接,判断是否被处理过,如果被处理过,则进行第三步;
主要操作流程图3如下所示:
图3 Spider工作流程
蜘蛛爬行互联网网页有两种方式:广度优先和深度优先。
广度优先是指网络蜘蛛会先抓取起始网页中链接的所有网页,然后再选择其中的一个链接网页,继续抓取在此网页中链接的所有网页。这是最常用的方式,因为这个方法可以让网络蜘蛛并行处理,提高其抓取速度。
深度优先是指网络蜘蛛会从起始页开始,一个友情链接一个链接跟踪下去,处理完这条线路之后再转入下一个起始页,继续跟踪链接。这个方法有个优点是网络蜘蛛在设计的时候比较容易。由于不可能抓取所有的网页,有些网络蜘蛛对一些不太重要的网站,设置了访问的层数。这也让有些网站上一部分网页能够在搜索引擎上搜索到,另外一部分不能被搜索到。对于网站设计者来说,扁平化的网站结构设计有助于搜索引擎抓取其更多的网页。
图4 网络蜘蛛遍历
如上图所示:
广度优先的遍历顺序是:A —B 、C 、D 、E 、F —G 、H —I 。
即蜘蛛按层次进行网页的遍历,先爬行完每一层次的网页的链接,在进行下一层次的网页信息的检索。
深度优先的遍历顺序是:
(1) A—B
(2) A—C
(3) A —D
(4) A—F —G
(5) A—E —H —I
即蜘蛛跟踪找到的每一个链接,直至此链接没有链接了,再回到原来的起始位置,继续跟踪下一个链接,跟踪至没有链接时,再切换到下一个链接,如此往复地检索互联网上网站的信息。
4.1.2 页面解析技术
在研究搜索引擎的开发中,对于HTML 网页的处理是核心的一个环节。 对于网络蜘蛛来说。网页信息中最有价值的信息是网页的链接和网页的内容。网页的链接(Intemal Links) ,关系到网络蜘蛛下一步爬行的页面,网页内容则是网络蜘蛛获取的网页所显示的文字或图像内容。
对于网络蜘蛛来说,如何分析、获得网页信息是很重要的一环。对于C#提供两种分析页面的方法:
(1) 在C#中可以用正则表达式来获得网页的内容,正则表达式去掉页面的脚本和HTML 标签,提取页面的内容。然后使用URL 正则表达式分析Html 中的链接。用这种方法来获取网页的链接信息,网页的链接信息是网络蜘蛛进行判断下一步遍历目标,选择遍历路径的重要已知条件。
(2) 而另一种方法就是谢用.NET 的—个类库——HtmlParser 这个开源类库可以解析几乎所有的HTML 标签。HtrmlParser 对HTML 进行了4级封装.从低级到高级的顺序为:ParserStream 、Source 、Page 、Lexer 其中ParserStream 负责从文件中获取二进制数据,但不做任何处理。Source 把二进制文件转换成相应的字符序列。存储一组未加工的字符序列。网上有很多开源的代码,HTMLParser 是比较著名并且得到广泛应用的一个。对于HTML 的内容HTMLParser 处理起来基本没有任何问题。HTMLParser 具有小巧,快速的优点,缺点是相关文档比较少(英文的也少),很多功能需要自己摸索。对于初学者还是要费一些功夫的,而一旦上手以后,会发现HTMLParser 的结构设计很巧妙,非常实用,基本你的各种需求都可以满足。
4.1.3 使用多线程技术
蜘蛛程序为什么要使用多线程?因为单线程存在以下问题:
(1) 分析和下载不能同步进行。在单线程的程序中,两者是无法同时进行的。也就是说,分析时会造成网络空闲,分析的时间越长,下载的效率越低。反之也是一样,下载时无法同时进行分析,只有停下下载后才能进行下一步的分析。怎样才能做到充分利用资源呢?如果能够把分析和下载用不同的线程进行,能够提高蜘蛛的效率。
(2) 只是单线程下载。相信大家都有用过电驴等下载资源的经历,它里面下载时可以看见文件被分成了很多小窄条,这就是多线程的分配下载的例子。它会将文件分成与线程数相同的部分,然后每个线程下载自己的那一部分,这样下载效率就有可能提高。但是,在带宽一定的情况下,并不是线程越多,速度越快,而是在某一点达到峰值。爬虫作为特殊的下载工具,不具备多线程的能力何以有效率可谈?爬虫在信息时代的目的,就是为了快速获取信息,所以,爬虫需要有多线程(可控数量)同时下载网页,才能提升从互联网里提取信息的能力。
4.2 数据库结构设计
存储网络蜘蛛程序采集信息的数据库服务器使用SQLSERVER2005,数据库名
为SpiderMsg ,其中包括一个表:PageInLocal(存储解析程序提取的网页的信息) ,具体设计如下:
表1:蜘蛛程序抓取页面的内容表
说明: PageInLocal 表存储从页面中找到的URL 链接,并记录是否被解析和解析后的提取信息。
5 模拟搜索引擎的实现
5.1 搜索引擎的原理
搜索引擎的三个基本原理:
(1) 利用蜘蛛系统程序,自动访问互联网,并沿着任何网页中的所有URL 爬到其它网页,重复这过程,并把爬过的所有网页收集回来。
(2) 由分析索引系统程序对收集回来的网页进行分析,提取相关网页信息,得到每一个网页针对页面内容中及超链中每一个关键词,然后用这些相关信息建立网页索引数据库。
(3) 当用户输入关键词搜索后,由搜索系统程序从网页索引数据库中找到符合该关键词的所有相关网页。最后,由页面生成系统将搜索结果的链接地址和页面内容摘要等内容组织起来返回给用户。
用户输入关键搜索关键词后,搜索引擎的主要工作:
找到包含所有关键词的匹配文件后,还不能进行相关性计算,因为找到的文件经常会有几十万几百万,甚至上千万个。要对这么多文件实时进行相关性计算,需要的时间还是比较长的。
实际上用户并不需要知道所有匹配的几十万、几百万个页面,绝大部分用户只会查看前两页,也就是前20个结果。搜索引擎也并不需要计算这么多页面的相关性,而只要计算最重要的一部分页面就可以了。常用搜索引擎的人都会注意到,搜索结果页面通常最多显示100个。用户点击搜索结果页面底部的“下一页”
链接,最多也只能看到第100页,也就是1000个搜索结果。
搜索引擎又怎么知道哪一千个文件是最相关的?所以用于最后相关性计算的初始页面子集的选择,必须依靠其他特征而不是相关性,其中最主要的就是页面权重。由于所有匹配文件都已经具备了最基本的相关性(这些文件都包含所有查询关键词),搜索引擎通常会用非相关性的页面特征选出一个初始子集。初始子集的数目是多少?几万个?或许更多,外人并不知道。不过可以肯定的是,当匹配页面数目巨大时,搜索引擎不会对这么多页面进行计算,而必须选出页面权重较高的一个子集,再对子集中的页面进行相关性计算。
5.2 蜘蛛程序的实现
5.2.1 多线程的实现
多线程在C#中有一个命名空间:System.Threading ,提供了多线程的支持。 要开启一个新线程,需要以下的初始化:
//当前线程数(用户指定)
public static int threadCounts;
//线程数组
public static Thread[] theads;
ThreadStart start = new ThreadStart(StartSpider);//线程起始设置:即每个线程都执行启动蜘蛛程序的方法,注意:StartSpider ()必须为不带有参数的方法
theads[i] = new Thread(start);//实例化要开启的新类
theads[i].Start();//开启线程
由于线程起始时启动的方法不能带有参数,这就为多线程共享资源添加了麻烦。不过我们可以用类级变量(当然也可以使用其它方法)来解决这个问题。知道开启多线程下载的方法后,可能还会有以下几个问题:
(1) 如何控制线程的数量?
线程数量我们可以通过for 循环来实现,就如同初学编程的打点程序一样。 比如已知用户指定了n (它是一个int 型变量)个线程,可以用如下方法开启五个线程。
Thread[] downloadThread;//声名下载线程数组
ThreadStart startDownload = new ThreadStart( DownLoad );//线程起始设置:即每个线程都执行DownLoad()
downloadThread = new Thread[ n ];//为线程申请资源,确定线程总数
for( int i = 0; i
{
downloadThread[i] = new Thread( startDownload );//指定线程起始设置
downloadThread[i].Start();//逐个开启线程
}
这样就实现了控制开启多线程数来启动蜘蛛程序下载网页的方法。
(2) 如何防止多线程解析同一网页?
下面出现的一个问题:所有的线程都调用DonwLoad()方法,这样如何避免它们同时解析同一个网页呢?
这个问题也好解决,只要建立一下Url 地址表,表中的每个地址只允许被一个线程申请即可,具体实现可以为每个Url 设定一个State 状态,被请求下载后,设置其状态为true ,否则其状态为false ,线程只执行状态为false 的Url 的请求。具体实现如下:
可以利用数据库,建立一个表,表中有四列,其中一列专门用于存储Url 地址,另外两列分别存放地址对应的线程以及该地址被申请的次数,最后一列存放下载的内容。(当然,对应线程一列不是必要的)。当有线程申请后,将对应线程一列是否被请求的状态设为true(即已经被请求过) ,这样,别的线程就无法申请该页。如果下载成功,则将内容存入内容列。如果不成功,内容列仍为空,作为是否再次解析的依据之一,如果反复不成功,则进程将于达到重试次数(对应该地址被申请的次数,用户可设)后,申请下一个Url 地址。主要的代码如下(以VFP 为例):
CREATE TABLE (PageInLocal) (LocalID , DownUrl , Title , Contents, State )建立一个表PageInLocal.dbf ,含有URL 地址、页面标题、页面解析内容、是否被解析的状态(初值为0,线程标志是从1开始的整数)四个字段,如果URL 对应的页面已经被解析过了,则URL 后面对应的State 被设置为True ,其他线程不会再去解析此URL ;如果URL 对应的State 为false ,则是其他线程作为解析的标记。
好了,这样就解决了多线程中线程的冲突问题。当然,去重问题也可以在C#语言内解决,建立一个PageFromInt 表,将蜘蛛查找到的所有的链接地址保存到表中,以后请求时,可以根据表中Url 来判断遇到的Url 是否被请求过,差对
它们设置相应的属性即可。
(3) 如何判断线程结束?
线程结束是很难判断的,因为它总是在查找新的链接。认为可以假设:当所有的线程都没有可以查到的Url 和被解析的Url 时候,那么可以认为它已经解析完了所有链接。主要代码如下:
string url = "";
int times = 0;
while ( url == "" )//如果没有找到符合条件的记录,则不断地寻找符合条件的记录
{
url = getUrl.GetAUrl( „„ );//调用GetAUrl 方法,试图得到一个url 值 if ( url == "" )//如果没有找到
{
times ++;//尝试次数自增continue; //进行下一次尝试
}
if ( times > N ) //如果已经尝试够了次数,则退出进程
{
downloadThread[i].Abort; //退出线程
}
else//如果没有尝试够次数
{
Times = 0; //尝试次数归零处理
}//进行下一步针对得到的Url 的处理
}
(4) 如何控制线程结束?
这个问题相对简单,因为在问题一中已经建议,将线程声名为类级数组,这样就很易于控制。只要用一个for 循环即可结束。代码如下:
for( int i = 0; i
{
downloadThread[i].Abort();//逐个关闭线程
}
5.2.2 解析下载的html
搜索引擎蜘蛛的采集信息是实现检索前提的重要步骤,实现了信息的检索后,对采集到的html 页面的内容处理也是不可或缺的部分,要实现页面内容的处理,得去除页面不用的html 标签,这个可以用到开源组件HtmlParser ——专门处理Html 页面的标签,提取页面信息。先引用Winista.HtmlParser.dll 组件,从PageInLocal 表中查找未被解析的网页,然后专门针对互联网上的页面,进行页面解析。
本解析模拟实现蜘蛛程序查找网络链接后,根据URL 进入网页,通过HtmlParser 和正则表达式相互配合,提取网页的有效信息。首先,使用开源组件HtmlParser ,分析页面的标签,提取页面超链接的Html 标签,然后提取出超链接的地址,将提取的超链接地址插入数据库SpiderMsg 中的表PageInLocal ,通过解析出HTML 页面的Title 和页面内容。HtmlParser 组件定义了html 解析的方法,可以根据它得到page 中的所有节点,然后查找链接的节点,提取链接的地址。页面的内容可以根据正则表达式除去所有的html 标签和标签里的内容、JavaScript 标签和标签里的内容以及CSS 样式,提取文本内容的信息,将提取到的信息插入建立的数据库的表中。
在进行数据采集显示文章摘要,内容计数等情况下,需要清除源代码中的html 标签、空格、style 、script 等标签,处理这些标签内容时,主要
(1) styleReg:清除样式,如。全部替换为空。
(2) scriptReg 和styleReg 同样的道理。
(3) htmlReg :清除html 标签的输入为
aaa
,结果为:aaa
(4) htmlSpaceReg :html 空格 ;替换为空格
(5) spaceReg :把一个以上的空格替换为一个空格
public string RemoveHtml(string src)
{
Regex htmlReg = new Regex(@"]+>", RegexOptions.Compiled |
RegexOptions.IgnoreCase);
Regex htmlSpaceReg = new Regex("\\ \\;", RegexOptions.Compiled | RegexOptions.IgnoreCase);
Regex spaceReg = new Regex("\\s{2,}|\\ \\;", RegexOptions.Compiled |
RegexOptions.IgnoreCase);
Regex styleReg = new Regex(@"", RegexOptions.Compiled | RegexOptions.IgnoreCase);
Regex scriptReg = new Regex(@"",
RegexOptions.Compiled | RegexOptions.IgnoreCase);
src = styleReg.Replace(src, string.Empty);
src = scriptReg.Replace(src, string.Empty);
src = htmlReg.Replace(src, string.Empty);
src = htmlSpaceReg.Replace(src, " ");
src = spaceReg.Replace(src, " ");
return src.Trim();
}
想去掉除了段落标记之外的所有html 标记,只要页面的文字,也就是只要标签中包含的内容,使用HtmlParser 组件分析页面的结构的话,可能不太方便,然而使用正则表达式能够更好地实现除去样式、脚本信息,能够更好地提取页面的信息。必要时,再结合HtmlParser 处理指定的标签,这样就实现了从html 页面中提取文本信息的功能。
5.2.3 Spider程序结构
网络机器人必须从一个网页迁移到另一个网页,所以必须找到该页面上的超连接。程序首先解析网页的HTML 代码,查找该页面内的超连接然后通过递归和非递归两种结构来实现Spider 程序。
(1) 递归结构
递归是在一个方法中调用自己本身的程序设计技术。虽然比较容易实现但耗费内存且不能使用多线程技术,故不适合大型项目。
(2) 非递归结构
这种方法使用队列的数据结构,当Spider 程序发现超连接后并不调用自己本身而是把超连接加入到等待队列中。当Spider 程序扫描完当前页面后会根据制定的策略访问队列中的下一个超连接地址。
虽然这里只描述了一个队列,但在实际编程中用到了四个队列,他们每个队列都保存着同一处理状态的URL 。
在同一时间,一个URL 只能在一个线程中,我们把它称为URL 的状态。
图5 Spider处理网站URL 的详细过程
以上的图表示了线程处理Url 的过程,在这个过程中,当一个URL 被加入到等待处理的线程中时Spider 程序就会开始运行。只要等待线程中有一个网页或Spider 程序正在处理一个网页,程序就会继续其它的工作。当等待线程执行的对Url 的处理为空并且当前没有任何网页时,Spider 程序就会停止它的工作,否则Spider 会一直执行下去。
5.2.4 Spider 模拟程序的代码结构图
这个是网络蜘蛛模拟的项目结构图:
图6 简易网络蜘蛛制作的项目结构
主要包括两个部分:第一部分是C/S结构;第二部分是B/S结构。第一部分是WinForm 项目,主要包括一个启动蜘蛛程序采集信息的窗体界面、App_Data提供的LINQ to SQL 数据源和实现Spider 的相关的方法的封装。启动后,用户可以输入指定的网址和线程数,然后开始检索网络蜘蛛的提取信息过程。第二部
分是ASP.NET 项目,主要包括两个页面Search.aspx 和SearchResult.aspx 和配置文件,这部分主要实现了对网络蜘蛛提取的信息的模拟检索功能,在Search.aspx 页面的输入框中输入关键字,然后点击搜索按钮,进入SearchResult.aspx 页面,并向用户展示搜索的结果。
5.2.5 如何提高程序性能
Internet 中拥有海量的Web 页面,如果开发出高效的Spider 程序是非常重要的。下面就来介绍下几种提高性能的技术:
(1) C#多线程技术
线程是通过程序的一条执行路线。多线程是一个程序同时运行多个任务的能力。它是在一个程序的内部进行分工合作。
优化程序的通常方法是确定瓶颈并改进他。瓶颈是一个程序中最慢的部分,他限制了其他任务的运行。据个例子说明:一个Spider 程序需要下载十个页面,要完成这一任务,程序必须向服务器发出请求然后接受这些网页。当程序等待响应的时候其他任务不能执行,这就影响了程序的效率。如果用多线程技术可以让这些网页的等待时间合在一起,不用互相影响,这就可以极大的改进程序性能。
(2) 数据库技术
当Spider 程序访问一个大型Web 站点时,必须使用一种有效的方法来存储站点队列。这些队列管理Spider 程序必须维护大型网页的列表。如果把他们放在内存中将会是性能下降,所以我们可以把他们放在数据库中减少系统资源的消耗。
5.3 模拟搜索结果的实现
使用蜘蛛程序提取到互联网信息,并且建立信息检索库后,用户就可以在搜索输入框内输入搜索的关键字,如:腾讯网,点击“搜索一下”按钮,检索关键字相关的信息。本部分如下图所示:
图7 模拟搜索蜘蛛提取的信息
在Search.aspx 页面中,提供了关键字输入框,后台取到用户输入的关键字,将关键字作为搜索匹配数据库中结果的条件,然后当用户点击“搜索一下”按钮
时,同时将关键字存入Session 中,然后在用户搜索结果呈现的页面——SearchResult.aspx 页面里,以分页列表的形式展现用户搜索到的结果。并取出Session 里面的值,填充搜索结果页面上的页面顶部和底部的关键字输入框,在搜索结果展现页面的上下关键字输入框里,用户还可以输入关键字,然后点击“搜索一下”按钮,可以在本页面里检索信息。
如果没有检索到和关键字相对应的搜索结果记录,搜索界面给出有好提示:抱歉,您输入的“XXX ”不在搜索范围内。
在考虑一个网页被另一个网页的引用时候,不是单纯的将被引用网页的Hit Number 加一,而是将引用网页的连接数作为权,同时将该引用网页的重要性也考虑进来(看看上面提到的例子,Yahoo !引用的网页显然比个人网站引用的网页重要,因为Yahoo !本身很重要),就可以得到扩展后的网页评分。
最早提出网页评分的计算方法是Google 。它们提出了一个“随机冲浪”模型来描述网络用户对网页的访问行为。模型假设如下:
用户随机的选择一个网页作为上网的起始网页;
看完这个网页后,从该网页内所含的超链内随机的选择一个页面继续进行浏览;
沿着超链前进了一定数目的网页后,用户对这个主题感到厌倦,重新随机选择一个网页进行浏览,并重复2和3。
按照以上的用户行为模型,每个网页可能被访问到的次数就是该网页的链接权值。如何计算这个权值呢?PageRank 采用以下公式进行计算:
其中Wj 代表第j 个网页的权值;lij 只取0、1值,代表从网页i 到网页j 是否存在链接;ni 代表网页i 有多少个链向其它网页的链接;d 代表“随机冲浪”中沿着链接访问网页的平均次数。选择合适的数值,递归的使用以上公式,即可得到理想的网页链接权值。该方法能够大幅度的提高简单检索返回结果的质量,同时能够有效的防止网页编写者对搜索引擎的欺骗。因此可以将其广泛的应用在检索器提供给用户的网页排序上,对于网页评分越高的网页,就排的越前。
5.4 使用LINQ 查询数据
打开Visual Studio 2008自带的命令提示工具,输入SqlMetal 命令,连接SQLSERVER 数据库,然后输入生成数据库文件SpiderMsg.dbml 命令和生成代码文件UrlMsg.cs 文件的命令,操作命令如下图所示:
图8 LINQ生成数据文件命令
将生成的数据库文件和代码文件添加到项目中的App_Data文件夹下面,然后根据LINQ to SQL的语法,先创建连接对象,然后操作数据表映射到实体对象的对象和对应的属性。
这是LINQ 从数据库检索Url 的过程,可以完全实现对对象的操作: var localUrlMsg = (from p in sMsg.PageInLocal
where p.DownUrl == downLoadUrl
select p).Single();
localUrlMsg.State = true;
localUrlMsg.Title = title;
sMsg.SubmitChanges();
其它的增、改、查功能的实现都可以针对实体的操作来实现,操作完成后,调用对象的SubmitChanges 方法将更改的数据提交回数据库即可。
6 搜索引擎的模拟结果及总结
6.1 蜘蛛程序启动页面
蜘蛛程序提取信息,可以输入URL 链接和线程数,然后单击开始,进入蜘蛛抓取分析页面、提取页面内容、建立数据库。
图9 蜘蛛程序启动示例
如图9所示,运行网络蜘蛛程序后,在起始的URL 输入框内输入蜘蛛程序起始访问的地址和线程数量,比如:起始URL 是http://www.qq.com/,线程数是8,然后单击“启动”按钮,便可实现向指定的URL 发送http 请求,在界面下方的多行文本框中就可以看到蜘蛛程序处理URL 的请求记录,单击“停止”按钮,就可以停止蜘蛛程序的执行。
在蜘蛛程序处理URL 请求的过程中,使用多线程一边进行URL 的访问,一边不断获取新的URL 作为下一次解析的起始URL 并一边提取解析的页面信息,插入数据库中,建立检索的数据库信息表。
6.2 蜘蛛程序模拟搜索
检索完网站的信息后,可以根据模拟的搜索引擎界面,根据用户输入的关键字从数据库中进行信息的检索匹配,并把包含相关信息的网页的信息以列表的形式罗列出来,用户点击相应的链接,就可以浏览搜索结果对应的信息。
在罗列匹配的搜索结果时,根据匹配结果的先后顺序依次罗列出来,达到模拟搜索引擎的效果,这里并没有研究搜索引擎计算相关结果与搜索的相似度,根据相似度排名的方法。以下是搜索关键字输入框:
图10 模拟关键字检索
图10是模拟的搜索引擎输入关键字的搜索输入框,用户输入关键字,然后点击“搜索一下”,根据匹配结果的情况,就有可能搜索到相关的结果。(因为检索的信息和本地硬件设施有限,模拟的搜索引擎并不能达到用户所有搜索都能匹配的效果) 。比如:输入关键字“腾讯网”,点击搜索一下,便可实现检索包含“腾讯网”关键字的搜索结果记录。
图11 根据关键字检索的结果
图11是根据关键字“腾讯网”搜索到蜘蛛程序采集的包含相关信息的结果记录,结果记录很多,采用分页,每页10条记录的形式显示。在保持网络连接的条件下,点击相应的链接,就可以实现访问相应的页面。
图12 搜索结果底部分页显示
首页显示“下一页”按钮,可以查看其他分页信息。
如果没有匹配的结果,显示一下提示信息:
图13 没有匹配的搜索结果
图13是用户输入关键字“很划算的”,在数据库中没有检索到相关的信息时,友情提示页面。
以下是使用蜘蛛程序抓取“四川省图书馆”的测试,开启蜘蛛程序,花了5个小时,抓取到“四川省图书馆”主页上的200000条记录数据。以下是蜘蛛程序抓取的页面数据。
图14 蜘蛛程序抓取数据的页面
图14是使用完成的蜘蛛程序采集四川省图书馆的示例,输入四川省图书馆的URL ,启动蜘蛛后,花费了5个小时,采集到了200000条相关的数据记录。
模拟搜索引擎的实现,可以帮助互联网用户了解搜索引擎的基本工作原理,了解搜索引擎搜索技术的实现过程,匹配关键字的搜索方法,方便用户如何更有效更简洁地搜索自己想要的信息。另一方面,发布网站的用户知道搜索引擎的原理后,可以做出更容易被蜘蛛程序抓取到的网站。
7 结束语
对搜索引擎的模拟,初步认识了搜索引擎的运行及检索信息的方式。在本次设计中,我完成了使用蜘蛛程序对指定链接网页的信息提取与分析,然后根据分析的URL 链接,继续分析检索页面,在这个过程中,为了提高蜘蛛程序的速度,使用了多线程技术,最后将提取的信息插入数据库,建立检索的数据库;在实现搜索的部分,根据输入的关键字,从数据库中匹配到包含关键字的网页的信息,然后提取页面信息和超链接,以列表的形式展现用户搜索的结果和搜索结果页面的部分描述信息,以每页10条记录的形式显示分页的搜索记录结果。
本次毕业设计《简易网络蜘蛛的制作》,实现了基本的蜘蛛爬行网页,抓取链接,然后使用自己的HtmlParser 分析提取页面的内容信息,建立起提供检索的数据库。根据用户输入的关键字,匹配到检索的结果信息。
通过本次毕业设计,初步了解了搜索引擎核心算法——网络蜘蛛的实现,了解了搜索引擎的搜索原理,在蜘蛛提取信息过程中,效率比一般的蜘蛛较慢,在以后的工作学习中,不断学习提高。
参考文献
[1]第二十二届互联网调查报告,http://news.ccidnet.com/zhuanti/2008cnnic
[2]作者:Karli Watson Nagel,C #入门经典,清华大学出版社,2006年5月
[3]作者:王超,Visual C#通用范例开发金典,电子工业出版社,2008年6月
[4]作者:瑞奇特,框架设计(第二版),清华大学出版社,2006年11月
[5]作者:黎晓冬, 精通C #编程,科学出版社,2003年1月
[6]郑阿奇,SQLServer 实用教程,北京:电子工业出版社,2003
[7]作者:Zac SEOer,了解搜索引擎
[8]作者:王小科, C#程序开发范例宝典,人民邮电出版社,2011
[9]作者:梁斌,走进搜索引擎[M】,北京:电子工业出版社,2007
[10] 作者:夏普,Visual C# 2005 从入门到精通,清华大学出版社,2006年6月
[11]作者:(美)沃尔瑟,ASP.NET.3.5揭秘,人民邮电出版社,2009年12月
[12]作者:刘浩,ASP.NET+SQLServer网络应用系统开发与实例,人民邮电出版社,2005-2
[13]http://social.msdn.microsoft.com/search/zh-cn?query=%E5%A4%9A%E7%BA%BF%E7%A8%8B,MSDN 官方网站.NET 多线程开发
[14]网站SEO 优化前的那些准备, http://www.seowhy.com/u/budongseo/4018.html
[15] Author: Christian Nagel,Bill Evjen,Jay Glynn,Karli Watson,Margan Skinner,Professional C# 2008,Publisher: John Wiley & Sons,Publication Date: 2011-01-28
致谢
用了将近一个月的时间将这篇论文写完,在写作的过程中遇到了许多的困难和障碍,在同学和老师的帮助下解决了这些问题,首先,我要真诚的感谢指导老师魏登峰老师,本设计在选题和完成都是在他的悉心指导下完成的。魏老师平日里工作蛮忙,不过在我做毕业设计的每个阶段,从查阅资料到设计草案,再到后来的项目实施,其中包括中期检查、进度询问调度、技术的指导、后期详细设计等等工作都给予了很大的指点,不厌其烦的帮助进行论文的修改和改进。同时非常感谢所有任课老师和亲爱的同学们给予的帮助与关怀,以及答辩小组老师们、测试小组老师们的辛苦批阅。另外,我还要感谢我的母校——长江大学,是母校给我们提供了优良的学习环境。
感谢这篇论文所涉及到的各位学者。本文引用了数位学者的研究文献,如果没有各位学者的研究成果的帮助和启发,我将很难完成本篇论文的写作。
最后要感谢的是我的父母和家人,我永远都不会忘记你们的良苦用心和一如既往的支持与鼓励。四年来,快乐的事情有你们一起分享,失意的日子有你们的默默关怀。无论我成功与否,你们总以鼓励的言语告诉我很棒,谢谢你们,我会继续努力。
四年的磨砺让我成熟了不少,即将踏入社会开始工作的我,面临的抉择和困难也非常多,但是不管前途多么的艰难,因为有你们大家的支持,我会毫无畏惧地前行。在论文即将完成之际,我的心情无法平静,从开始进入课题到论文的顺利完成,有多少可敬的师长、同学、朋友给了我无言的帮助,在这里请接受我诚挚的谢意!
在实际完成论文的过程中,由于受个人的知识、经验和能力的限制,论文肯定存在不足之处,我恳请各位老师提出批评和指正。我也会悉心听取各位老师及同学们的指导与意见,并在以后学习工作中努力提高自己的专业水平,以不辜负老师对我的期望。
杨玉瓶
2012年6月