校园网搜索引擎的分析与设计Word格式文档下载.doc
《校园网搜索引擎的分析与设计Word格式文档下载.doc》由会员分享,可在线阅读,更多相关《校园网搜索引擎的分析与设计Word格式文档下载.doc(22页珍藏版)》请在冰点文库上搜索。
这种专业化的搜索引擎需要对专业知识专而精,并要求内容全面。
(2)个性化搜索:
提高搜索精确度的另一个途径是提供个性化搜索,也就是将搜索建立在个性化的搜索环境之下,通过对用户的不断了解、分析,使得个性化搜索更符合每个用户的需求。
2.搜索引擎的分类及工作原理
2.1搜索引擎的分类
当前搜索引擎的分类方法有很多,因此分类出来的搜索引擎也很多。
通常根据搜索引擎信息收集方法和工作方式的不同,现有的搜索引擎有以下三类:
1.机器人搜索引擎;
2.目录式搜索引擎;
3.元搜索引擎[3,6,21]。
2.1.1机器人搜索引擎
机器人搜索引擎它是将Web视作一个大型的全文数据库,利用几个关键词来表示一个网页,通过从互联网上提取的各个网站的信息(以网页文字为主)而建立的数据库中,检索与用户查询条件匹配的相关记录,返回查询结果一般包括Web页面标题和URL等信息,然后按一定的排列顺序将结果返回给用户,是真正的搜索引擎。
国外具有代表性的有Google、AllTheWeb等,国内著名的有百度(Baidu)。
这类搜索引擎的优点是信息量大,无需人工干预,但由于关键词是直接从原文中抽取的,每个人对于一个主题的描述存在着很大的随意性,而且关键词之间又是互相独立的,所以返回查询结果往往缺乏准确性。
机器人搜索引擎的自动信息搜集功能分两种:
一种是拥有自己的搜索程序,俗称“蜘蛛”(Spider)程序或“机器人”(Robot)程序,定期对一定IP地址范围的互联网站进行检索,一旦发现新的网站,它会自动提取网站的信息和网址加入自己的数据库,搜索结果直接从自身的数据库中调用;
另一种是由网站拥有者主动向搜索引擎网站提交网址。
2.1.2目录式搜索引擎
目录式搜索引擎是以人工方式或半自动方式搜集信息,由编辑员查看信息之后,人工编辑摘录核心信息,并将信息置于事先确定的分类框架中。
由于目录索引只是一个按目录分类的网站链接列表,因此目录式搜索引擎虽然有搜索功能,但严格意义上不能称为搜索引擎,仅仅是按目录分类的网站链接列表而已。
用户完全可以不用进行关键词查询,仅靠分类目录也可找到需要的信息。
它的优点在于:
目录清晰、内容较准确、有效价值较高;
缺点也比较明显:
分类体系不规范、不统一,交叉类目容易遗漏;
人工分类,效率比较低,速度比较慢,更新不及时。
目录搜索引擎中最具代表性的如Yahoo(雅虎)。
2.1.3元搜索引擎
元搜索引擎,即指在统一的用户查询界面与信息反馈的形式下,共享多个搜索引擎的资源库为用户提供信息服务的系统,又称作搜索引擎之上的搜索引擎。
元搜索引擎自身没有建立存储网页信息的数据库[7],而是将用户的查询请求同时传送至多个包含数据库的搜索引擎,并行地访问数个搜索引擎来查询这个关键词,然后对各搜索引擎返回的结果进行去重、排序等整理,最终响应给检索用户。
严格意义上来讲,元搜索引擎只能算是一种用户代理,而不是真正的搜索引擎。
目前,没有一个搜索引擎能涵盖整个Internet,各搜索引擎的收录范围又有所差异,因此这类元搜索受到了一定程度的关注,特别适合于对查全率要求高的查询。
但是,不同的搜索引擎之间,建立索引数据库和执行提交检索的具体方法或规则并不相同,因此,大大影响了元搜索的检索效果。
2.2搜索引擎工作原理
搜索引擎的工作原理基本都是一样的[10],利用一个叫网络蜘蛛的程序在网络上爬行,自动地遍历Web来获得的网络信息并保存到本地服务器中。
因此,我们通常所说的搜索引擎并不是真正的在搜索互联网,而是通过用户提供的关键词,搜索引擎再根据此关键词进行对其服务器的数据库进行搜索。
为了保证用户查找信息的精度和及时,搜索引擎需要建立并维护一个庞大的索引数据库,从而能够迅速的从中找到相关的信息。
搜索引擎的工作过程一般来说可以看作三大步:
从互联网上爬取网页->
预处理->
查询服务[23],如图1。
WWW
信息采集器
分析
索引排序
索引库
进行检索
分析查询
结果排序
用户
查询
返回
信息处理
建立索引
图1搜索引擎工作流程图
(1)从互联网上爬取网页
事先利用搜索引擎中的蜘蛛程序,自动地从一个种子URL集出发。
它能自动扫描与URL相对应的网页,它利用HTML语言的标记结构搜索信息和获取指向其他超文本的URL链接,通过一定搜索策略选择下一个要访问的页面,继而转向另一个链接的页面继续进行信息搜集,如此通过找到新的URL不断爬行,不断搜集页面。
从理论上讲,网络蜘蛛可以搜集Internet上所有信息。
(2)预处理(建立索引数据库)
由蜘蛛程序采集回来的信息,经分析索引系统程序对其进行分析处理,提取相关网页信息(包括网页筛选、页面内容包含的所有关键词、关键词位置、生成时间、大小、与其它网页的链接关系等),根据一定的相关度算法进行大量复杂计算,得到每一个网页针对页面文字中及超链中每一个关键词的相关度(或重要性),然后利用这些相关信息建立网页索引数据库。
(3)查询服务(在索引数据库中搜索排序)
经过以上两个步骤后,当用户输入关键词搜索后,由搜索系统程序从网页索引数据库中找到与该关键词所有相关的网页。
因为所有相关网页针对该关键词的相关度早已按照预设的算法算好,所以只需按照现成的相关度数值排序,相关度越高,排名越靠前。
最后,由页面生成系统将搜索结果的链接地址和页面内容摘要等内容组织起来返回给用户。
由以上简述可知,网络蜘蛛在整个搜索引擎中是核心组成部分之一。
3.网络蜘蛛简介
3.1网络蜘蛛
在搜索引擎原理中提到过,其数据库是通过网络蜘蛛搜集的网页。
那么在具体搜集过程中,如何爬取一篇篇网页,最常见的是通过爬取来找到网页[15,23,24]。
就是将Web上的网页集合看成一个有向图,搜集过程是从给定的起始URL集合S开始,沿着网页中的链接,按照一定的策略遍历,不停的从S中读取URL,下载相应的网页,并解析出网页中的超链接URL,看是否已经被访问过,将未访问过的那些URL加入集合S。
整个过程可以形象地想像为一个蜘蛛在蜘蛛网上爬行。
通过前面的描述,可知网络蜘蛛(Spider)它是一种功能很强的基于HTTP协议的网络应用程序。
它会定期根据预先设定的地址去查看对应的网页,如网页发生变化则重新获取该网页,否则根据该网页中的链接继续去访问其他页面,如此循环,理论上可以扫描互联网上的所有页面。
例如Google,就是利用网络蜘蛛程序来遍历Web站点,以创建并维护这些大型数据库。
3.2网络蜘蛛的工作原理及系统结构
网络蜘蛛是通过一个给定的初始URL集合[25,27],把这个初始URL集合放到URL处理器中;
网页读取器根据URL处理器提供的这个初始URL集合,解析URL中标明的Web服务器地址、建立连接、发送请求和接收数据,采集到相应的网页;
经过去重检测后,通过URL提取器从网页中提取出新的URL放入URL处理器;
并将其存入数据库中;
由标签信息获取器获取相应的标签,分两个方向分别将其存入URL处理器中和存入数据库中保存;
如此反复采集、处理数据,直到网页读取器要求停止(URL处理器中URL集合为空)为止。
一般来说网络蜘蛛采集是模拟人浏览网站的过程进行对网页采集的。
从网站某一个页面(通常是首页)开始,读取网页的内容,找到在网页中的其它链接地址,然后通过这些链接地址寻找下一个网页,这样一直循环下去,直到把这个网站所有的网页都爬取完为止。
按这个原理来,如果把整个互联网当成一个网站,那么网络蜘蛛就可以用这个原理把互联网上所有的网页都下载下来。
根据以上工作过程,可以得到网络蜘蛛的基本结构[22]如图2所示。
www
网页
读取器
URL处理器
初始URL
集合
标签信息
获取器
URL提取器
数据库
网页去重检测
图2网络蜘蛛的基本结构图
3.2.1URL处理器
URL处理器是根据先进先出的策略向网页读取器分配URL。
URL采取一个队列[11,13,16],以达到更快的处理速度。
URL处理器主要有两个数据来源:
1)初始的种子URL集,如图2所示;
2)从URL提取过来的URL集,它们是从已经读取到的页面中抽取出来并经过处理的。
页面的标题及摘要等信息,来自标签信息获取器,它们主要用来显示从URL提取器中传递过来的URL和重要性,为在队列中进行排序提供依据。
3.2.2网页读取器
通过各种Web协议来完成资料的采集。
一般来说协议包括http、ftp等。
但从主流上看,仍以http为主。
根据分配的URL通过各种Web协议来爬取页面并读取页面内容。
3.2.3网页去重检测
网络上的资源,网页中的内容经常被其他网站、网页引用,蜘蛛程序找到的网页有很多重复的,如不进行网页重复内容的检测过滤,将极大的浪费了网络带宽和系统的运行效率。
因此,重复内容检测是网络蜘蛛中的重要组成部分。
3.2.4URL提取器
在采集到的要读取的页面,通过网页去重检测后,需要分析其中的链接,进行抽取超链,这些任务由URL提取器来完成。
首先判别页面类型,对类型为“html和htm”等的页面进行链接分析。
页面的类型可在HTTP应答头的分析中得到,也可以通过分析URL中的文件扩展名来得到。
超链接的标记总共包括<
ahref=……>
、<
areahref=……>
basehref=……>
framesrc=……>
和<
imgsrc=……>
等。
总的来说,要提取页面的URL,主要是根据关键词href和src来提取即可[5,18,26]。
3.2.5标签信息获取器
标签信息获取,包括提取页面的标题、页面的摘要等。
主要目的是在没有对页面内容进行语义信息理解的前提下,尽可能多的挖掘出HTML标签、结构等信息,对从页面中提取出来的URL质量的好坏给出一个度量,并将其与已访问过的URL表进行比较,将未在表中出现的URL传输到URL处理器,对待提取URL队列进行排序。
3.2.6数据库
数据库中存储着采集下来的网页的URL、网页标题、网页摘要等,这些数据用于建立索引数据库时非常重要。
3.3网络蜘蛛的搜索策略
在网络蜘蛛进行爬取网页时,通用搜索引擎的网络蜘蛛将网络上的各个页面及各页面之间的链接看成一个有向图,每个页面作为图的节点,页面中的链接看成是图的有向边,这样就可以用一定的有向图遍历法对其进行遍历。
因此在设计通用搜索引擎时,常用的网络蜘蛛搜索策略有两种:
基于广度优先(BreadthFirst)和基于深度优先(DepthFirst)两种搜索策略[19]。
与通用搜索引擎不同的是,主题搜索引擎的网络蜘蛛是只服务于特定人群的搜索引擎,其索引的内容也只限于特定主题或专门领域,因而在搜索过程中不须对整个Web进行遍历,只需选择与主题相关的网页进行访问并建立索引数据库即可。
3.3.1广度优先策略
广度优先搜索策略是指在爬取过程中,先完成爬取起始网页中链接的所有网页,然后再选择其中的一个链接,继续爬取在此网页中链接的所有网页。
直到完成所有层的爬取。
在目前为覆盖尽可能多的网页,一般使用广度优先搜索方法。
因为这个方法可以让网络蜘蛛并行处理,提高其爬取速度。
同时也保证了对浅层的首先处理。
从而爬取相对来说更为重要的网页。
但是如果要遍历一个指定的站点或者深层嵌套的HTML文件集,用广度优先搜索策略这样一层一层爬取则需要花费比较长的时间才能到达深层的HTML文件。
3.3.2深度优先策略
深度优先策略是指网络蜘蛛从起始页开始,顺着HTML文件上的超链接直到不能再深入为止,然后返回到上一个接点的HTML文件,再继续选择该HTML文件中的其他超链接。
当不再有其他超链接可选择时,说明搜索已经结束。
深度优先搜索适宜遍历一个指定的站点或者深层嵌套的HTML文件集,但对于大规模的搜索,由于Web结构相当深,有可能永远也出不来了。
图3对这两种搜索策略作了更加直观的说明。
G
F
A
E
H
I
C
D
B
广度优先爬取顺序:
深度优先爬取顺序:
A-B.C.D.E.F-H.G-IA-F-G
E-H-I
图3两种算法的爬取顺序图
在搜索策略的选择上,MarcNajork等人研究证明,网络蜘蛛采用广度优先搜索策略爬行的网页质量要比采用深度优先搜索策略的要好[20,23],因此,大多数网络蜘蛛的设计采用广度优先搜索策略或者结合多种搜索策略的策略。
大型搜索引擎在设计网络蜘蛛时,像百度等其他一些通用搜索引擎,由于Internet上网页数量非常大,它的网络蜘蛛不可能爬取所有的网页,因此网络蜘蛛对一些不太重要的网站,限定了对网站访问的层数。
在图3中,设A为起始网页,属于0层,那么与A直接相连的B、C、D、E、F就属于第1层,依次类推G、H属于第2层,I属于第3层。
如果网络蜘蛛设置的访问层数为1的话,网页G、H、I就不会被访问到。
这也就是为什么有些网站上一部分网页能够在搜索引擎上搜索到,而网站中的另外一部分网页不能被搜索到。
但是即使这样设计了,其数据量级别还是很大,而且范围也很广,所以大型搜索引擎的网络蜘蛛设计都是采用分布式系统结构的[17]。
据有关研究表明[25],而采用分布式系统结构设计的网络蜘蛛其爬取得到的网页质量不如单一结构的网络蜘蛛所爬取得到的网页质量高。
校园网的数据量相比于亿量级的数据量,并不大,所以在本次设计中,没有采用分布式系统结构设计其网络蜘蛛。
3.3.3主题网络蜘蛛的搜索策略
主题搜索引擎的网络蜘蛛,它只服务于一定的人群,因此采集信息时也只采集与主题相关的信息。
主题搜索引擎其网络蜘蛛的搜索策略有很多种,以下简单介绍这些搜索策略。
基于内容评价的搜索策略[8,12,17,19],是由传统信息检索中的文本检索的思想转变过来的。
即利用文本相似度的计算方法评价页面文本与主题集(如关键词、主题相关文档)之间相似程度,再根据其相似程序确定访问页面的顺序。
基于链接结构评价的搜索策略,利用页面的结构特征和链接的重要性,来决定搜索顺序。
它有两种算法,分别是Page-Rank和HITS,前者原先用于对查询结果的排序,近几年被用于网络蜘蛛对链接重要性的评价;
后者根据网页出入度确定网页的重要性。
基于巩固学习的搜索策略,利用Web信息资源的相似性,先对网络蜘蛛进行一些训练,使其具备一些经验信息,再利用这些经验信息指导搜索。
4.平台选择与关键技术
4.1平台的选择
.NET平台与JAVA平台都是当前两大流行的设计平台。
这两大平台有各自的特点,都有非常强大的功能,都可以满足我们设计的需要。
JAVA平台提供给我们的是平台中立和可移植性,我们可以在WIN系统下或其他系统下开发项目,经过一次编译就可以在其他系统下运行;
而.NET平台提供给我们的是可视化的开发界面,使初学者较容易上手,丰富的组件库可以使开发者轻松许多。
考虑到初次设计这种要求较高的应用程序,我们这里选择.NET平台。
4.2语言的选择
前面讲到我们选择.NET作为我们的开发平台,在语言选择上,我们选择相对来说较为熟悉的C#语言作为本次设计的首选语言。
4.3I/O与数据流简介
I/O一般指输入(input)/输出(output)系统,它本身提供应用程序与外部沟通的一种方式。
数据流,是一个用于传输数据的对象,数据的传输也有两个方向:
(1)如果数据从外部源传输到程序中,这就是读取流。
(2)如果数据从程序传输到外部源,这就是写入流。
在C#语言中,它利用.NET的I/O系统,提供程序语言的I/O功能。
.NET以面向对象设计方式,处理I/O相关问题,所有与I/O有关的功能,被封装于各种不同形式的类,而其中主要的I/O类,集中于命名空间System.IO。
System.IO是非常大的命名空间,其中包含各种的类,提供不同格式数据流的处理功能。
4.4访问Internet介绍
C#可以通过.NET基类提供的方法和工具类,使用各种网络协议(如HTTP和TCP)访问网络和Internet。
在制作具备网络功能的应用程序时,我们要用到相应的类及方法,而这些类、方法都散布在System.Net.Sockets和Sytem.Net这两个命名空间。
其中,前者提供实现Sockets应用程序的相关类,它通常与较低层的操作有关;
后者提供开发因特网功能所需的应用程序接口,它通常与较高层的操作有关,例如使用HTTP等协议进行Web请求。
4.4.1命名空间System.Net.Sockets
System.Net.Sockets命名空间主要提供制作Sockets网络应用程序的相关类。
其中几个比较重要的类有Socket类、TcpClient类、TcpListener类,另外一个类ScoketException,则是当Sockets网络错误或使用DNS类存取网络主机信息产生错误时,系统所抛出的异常类。
使用Socket实现具备网络连接服务的应用程序,通常必需提供接受客户端应用程序连接的服务端应用程序,整个应用程序的运作过程如下几步:
(1)绑定至指定端点:
对一个特定主机的指定通信端口,等待连接的服务器端应用程序,进行联系的操作;
(2)完成服务器连接:
联系完成后,创建与主机服务器的连接;
(3)传送数据至Socket:
在客户端应用程序,将指定的数据传送至Socket对象上;
(4)从Socket上读取数据:
上述步骤的反向操作,在Socket读取所需的操作。
TcpClient类:
它提供TCP网络服务的Client连接,提供TCP网络服务的客户端应用程序与服务器连接,然后使用此连接发送和接收数据包。
通过指定的IP地址以及通信端口编号进行连接的。
其中IPEndPoint类代表网络终点,它是一种用以表示IP地址和通信端口编号的类。
IPAddress类代表IP地址。
TcpListener类:
提供制作相关功能所需的方法,分别接受IP地址以及所要倾听的通信端口编号参数。
NetworkStream类:
主要是提供用于网络访问的基础数据流。
它主要通过串接Socket对象,创建其对象实例,在使用前,需要创建Socket对象实例,并通过Socket.Connect方法建立与远程服务端的连接,而后才可以使用该方法得到网络传输流。
4.4.2System.Net命名空间
System.Net命名空间提供了一般性的网络资源存取,如下载网页、文件等。
有几个比较重要的类有WebRequest类、WebResponse类、HttpWebRequest类、HttpWebResponse类、WebClient类。
WebRequest类和WebResponse类是.NET要求/响应结构模型的核心类;
HttpWebRequest类和HttpWebResponse类让我们在使用HTTP协议完成网络的要求/响应等相关操作。
4.5多线程技术
线程可以视为一段独立执行的程序代码段,应用程序至少会于一个或一个以上的线程中执行,多线程可以让应用程序同时进行多项工作,提高执行性能。
多线程通常被应用在以下几种情形:
一种是耗时的运算工作,如进行复杂的数学运算,这时可以让应用程序进行运算的同时,进行其他工作。
另一种是等待响应信息,程序必须长时间等待响应时运用多线程技术。
如通过网络读取文件或下载大量数据时,可以通过使用多线程技术来提高工作效率。
4.5.1创建线程
想要在应用程序里使用线程,最简单的方式便是创建Thread类的实例对象,在此之前,先引用System.Threading命名空间。
以下为构造函数:
PublicThread(ThreadStartstartPoint);
//startPonit参数是一个ThreadStart委派,用以封装线程对象所要执行的方法。
此委派的定义如下:
PublicdelegatevoidThreadStart();
//ThreadStart委派不能有返回值,且不能接受任何参数。
在创建新线程对象后,要调用Thread类的Start方法,如此线程才会开始执行委派Thread所封装的方法,Start方法定义如下:
PublicvoidStart();
//启动线程;
程序首先声明一个实例对象,调用Start()方法,再通过声明一个Thread类的实例对象Threading,再调用线程的Start()方法来启动线程。
4.5.2线程的暂停与恢复
Thread类提供一组方法,允许一个线程启动后,能够暂停执行,在适当的时候恢复执行。
这里有几个方法可以达到此目的。
其定义如下:
PublicvoidSuspend();
//暂停线程;
PublicvoidResume();
//恢复线程;
PublicvoidJoin();
//将一个新的线程加入到目前正在执行的线程。
4.5.3终止线程
从创建线程、执行到暂停等,最终要终止线程。
这时可以调用方法Interrupt强制终止线程的执行。
PublicvoidInterrupt();
4.5.4线程管理
线程允许应用程序同时执行多个工作,但是不当的使用线程也会带来不利影响。
这时我们就可以用ThreadPool类来管理线程[9]。
其中比较重要的方法为QueneUserWorkItem方法。
5.程序实现
5.1设计思路
在理解本次设计原理的基础上,本程序主要功能就是分析URL并下载网页,那么在进行设计完整程序之前,可以对本程序的设计进行简化。
即把下载一个网站网页的设计简化为下载一个网页的设计。
这个问题相对来说就比较简单,我们可以利用.NET中的WebRequest/WebRe