这里是一点我在学习和开发搜索引擎过程中的一点学习和经验总结,文中讲述了蜘蛛、切词、索引、查询器等名模块的一些概述和细节,希望能给搜索引擎中的初学点的一点帮助,对于那些高手也能够带来一点点启发的帮助!这是我在2004年学习和开发搜索引擎相关东西时的一点总结,可能比较肤浅,最近还是一直在搞这方面的研究,相对于这篇文章又有了一些新的总结,等以后有时间再写一篇和大家分享!
(有些图是没有办法显示的,因为从Word里拷不过来)
若想下载Word文档请到这里下载:
http://www.vchelp.net/itbookreview/view_paper.asp?paper_id=1539
目 录
在互联网发展初期,网站相对较少,信息查找比较容易。然而伴随互联网爆炸性的发展,普通网络用户想找到所需的资料简直如同大海捞针,这时为满足大众信息检索需求的专业搜索网站便应运而生了。
现代意义上的搜索引擎的祖先,是
1990
年由蒙特利尔大学学生
Alan Emtage
发明的
Archie
。虽然当时
World Wide Web
还未出现,但网络中文件传输还是相当频繁的,而且由于大量的文件散布在各个分散的
FTP
主机中,查询起来非常不便,因此
Alan Emtage
想到了开发一个可以以文件名查找文件的系统,于是便有了
Archie
。
Archie
工作原理与现在的搜索引擎已经很接近,它依靠脚本程序自动搜索网上的文件,然后对有关信息进行索引,供使用者以一定的表达式查询。由于
Archie
深受用户欢迎,受其启发,美国内华达
System Computing Services
大学于
1993
年开发了另一个与之非常相似的搜索工具,不过此时的搜索工具除了索引文件外,已能检索网页。
当时,“机器人”一词在编程者中十分流行。电脑“机器人”(
Computer Robot
)是指某个能以人类无法达到的速度不间断地执行某项任务的软件程序。由于专门用于检索信息的“机器人”程序象蜘蛛一样在网络间爬来爬去,因此,搜索引擎的“机器人”程序就被称为“蜘蛛”程序。
世界上第一个用于监测互联网发展规模的“机器人”程序是
Matthew Gray
开发的
World wide Web Wanderer
。刚开始它只用来统计互联网上的服务器数量,后来则发展为能够检索网站域名。
与
Wanderer
相对应,
Martin Koster
于
1993
年
10
月创建了
ALIWEB
,它是
Archie
的
HTTP
版本。
ALIWEB
不使用“机器人”程序,而是靠网站主动提交信息来建立自己的链接索引,类似于现在我们熟知的
Yahoo
。
随着互联网的迅速发展,使得检索所有新出现的网页变得越来越困难,因此,在
Matthew Gray
的
Wanderer
基础上,一些编程者将传统的“蜘蛛”程序工作原理作了些改进。其设想是,既然所有网页都可能有连向其他网站的链接,那么从跟踪一个网站的链接开始,就有可能检索整个互联网。到
1993
年底,一些基于此原理的搜索引擎开始纷纷涌现,其中以
JumpStation
、
The World Wide Web Worm
(
Goto
的前身,也就是今天
Overture
),和
Repository-Based Software Engineering (RBSE) spider
最负盛名。
然而
JumpStation
和
WWW Worm
只是以搜索工具在数据库中找到匹配信息的先后次序排列搜索结果,因此毫无信息关联度可言。而
RBSE
是第一个在搜索结果排列中引入关键字串匹配程度概念的引擎。
最早现代意义上的搜索引擎出现于
1994
年
7
月。当时
Michael Mauldin
将
John Leavitt
的蜘蛛程序接入到其索引程序中,创建了大家现在熟知的
Lycos
。同年
4
月,斯坦福(
Stanford
)大学的两名博士生,
David Filo
和美籍华人杨致远(
Gerry Yang
)共同创办了超级目录索引
Yahoo
,并成功地使搜索引擎的概念深入人心。从此搜索引擎进入了高速发展时期。目前,互联网上有名有姓的搜索引擎已达数百家,其检索的信息量也与从前不可同日而语。比如最近风头正劲的
,其数据库中存放的网页已达
30
亿之巨!还有百度其存放的网页也有
6
亿多。
随着互联网规模的急剧膨胀,一家搜索引擎光靠自己单打独斗已无法适应目前的市场状况,因此现在搜索引擎之间开始出现了分工协作,并有了专业的搜索引擎技术和搜索数据库服务提供商。象国外的Inktomi(已被Yahoo收购),它本身并不是直接面向用户的搜索引擎,但向包括Overture(原GoTo,已被Yahoo收购)、LookSmart、MSN、HotBot等在内的其他搜索引擎提供全文网页搜索服务。国内的百度也属于这一类,搜狐和新浪用的就是它的技术。因此从这个意义上说,它们是搜索引擎的搜索引擎。
现在一提到搜索引擎,人们往往想到的是Google、百度、雅虎、搜狐等。那么究竟什么是搜索引擎呢?“搜索引擎”实际上是为人们提供在internet网上利用关键词来进行全文检索的一种网页检索工具。
搜索引擎按其工作方式主要可分为三种,分别是全文搜索引擎(Full Text Search Engine)、目录索引类搜索引擎(Search Index/Directory)和元搜索引擎(Meta Search Engine)。全文搜索引擎是最广泛也是用得最多的一种,一般所说的搜索引擎都指的是全文搜索引擎。
全文搜索引擎
全文搜索引擎是名副其实的搜索引擎,国外具代表性的有
、
Fast/AllTheWeb
、
AltaVista
、
Inktomi
、
Teoma
、
WiseNut
等,国内著名的有百度(
Baidu
)、中国搜索等。它们都是通过从互联网上提取的各个网站的信息(以网页文字为主)而建立的数据库中,检索与用户查询条件匹配的相关记录,然后按一定的排列顺序将结果返回给用户,因此他们是真正的搜索引擎。
从搜索结果来源的角度,全文搜索引擎又可细分为两种,一种是拥有自己的检索程序(
Indexer
),俗称“蜘蛛”(
Spider
)程序或“机器人”(
Robot
)程序,并自建网页数据库,搜索结果直接从自身的数据库中调用,如上面提到的
7
家引擎;另一种则是租用其他引擎的数据库,并按自定的格式排列搜索结果,如
Lycos
引擎。
目录索引
目录索引虽然有搜索功能,但在严格意义上算不上是真正的搜索引擎,仅仅是按目录分类的网站链接列表而已。用户完全可以不用进行关键词(
Keywords
)查询,仅靠分类目录也可找到需要的信息。目录索引中最具代表性的莫过于大名鼎鼎的
Yahoo
雅虎。其他著名的还有
Open Directory Project
(
DMOZ
)、
LookSmart
、
About
等。国内的搜狐、新浪、网易搜索也都属于这一类。
元搜索引擎
(META Search Engine)
元搜索引擎在接受用户查询请求时,同时在其他多个引擎上进行搜索,并将结果返回给用户。著名的元搜索引擎有InfoSpace、Dogpile、Vivisimo等(元搜索引擎列表),中文元搜索引擎中具代表性的有搜星搜索引擎。在搜索结果排列方面,有的直接按来源引擎排列搜索结果,如Dogpile,有的则按自定的规则将结果重新排列组合,如Vivisimo。
除上述三大类引擎外,还有以下几种非主流形式:
1、集合式搜索引擎:如HotBot在2002年底推出的引擎。该引擎类似META搜索引擎,但区别在于不是同时调用多个引擎进行搜索,而是由用户从提供的4个引擎当中选择,因此叫它“集合式”搜索引擎更确切些。
2、门户搜索引擎:如AOL Search、MSN Search等虽然提供搜索服务,但自身即没有分类目录也没有网页数据库,其搜索结果完全来自其他引擎。
3、免费链接列表(Free For All Links,简称FFA):这类网站一般只简单地滚动排列链接条目,少部分有简单的分类目录,不过规模比起Yahoo等目录索引来要小得多。
由于上述网站都为用户提供搜索查询服务,为方便起见,我们通常将其统称为搜索引擎。
搜索引擎系统一般由蜘蛛(也叫网页爬行器)、切词器、索引器、查询器几部分组成。蜘蛛负责网页信息的抓取工作,一般情况下切词器和索引器一起使用,它们负责将抓取的网页内容进行切词处理并自动进行标引,建立索引数据库。查询器根据用户查询条件检索索引数据库并对检索结果进行排序和集合运算,如并集、交集运算,再提取网页简单摘要信息反馈给查询用户。
搜索引擎从功能上同样分为三大部分:网页爬行、标引入库和用户查询。网页爬行主要负责网页的抓取,由
URL
服务器、爬行器、存储器、分析器和
URL
解析器组成
,
爬行器是该部分的核心;标引入库主要负责对网页内容进行分析,对文档进行标引并存储到数据库里,由标引器和分类器组成,该模块涉及许多文件和数据,有关于桶的操作是该部分的核心;用户查询主要负责分析用户输入的检索表达式,匹配相关文档,把检索结果返回给用户,由查询器和网页级别评定器组成,其中网页等级的计算是该部分的核心。其总体系统结构下图所示。
搜索引擎的主要工作流程是:首先从蜘蛛开始,蜘蛛程序每隔一定的时间(象google一般是28天)自动启动并读取网页URL服务器上的URL列表,按深度优先或广度优先算法,抓取各URL所指定的网站,将抓取的网页分配一个唯一文档ID(DocId),存入文档数据库。一般在存入文档数据库之前进行一定的压缩处理。并将当前页上的所的超连接存入到URL服务器中。在进行抓取的同时,切词器和索引器将已经抓取的网页文档进行切词处理,并按词在网页中出现的位置和频率计算权值,然后将切词结果存入索引数据库。整个抓取工作和索引工作完成后更新整个索引数据库和文档数据库,这样用户就可以查询最新的网页信息。查询器首先对用户输入的信息进行切词处理,并检索出所有包含检索词的记录,通过计算网页权重和级别对查询记录进行排序并进行集合运算,最后从文档数据库中提取各网页的摘要信息反馈给查询用户。
蜘蛛(即Web Spider),实际上是一个基于HTTP协议的网络应用程序。网络蜘蛛是通过网页的链接地址来寻找网页,从网站某一个页面(通常是首页)开始,读取网页的内容,并抽取出网页中的其它超链接地址,然后通过这些链接地址寻找下一个网页,这样一直循环下去,直到把这个网站所有的网页都抓取完为止。
在抓取网页的时候,网络蜘蛛一般有两种策略:广度优先和深度优先。广度优先是指网络蜘蛛会先抓取起始网页中链接的所有网页,然后再选择其中的一个链接网页,继续抓取在此网页中链接的所有网页。这是最常用的方式,因为这个方法可以让网络蜘蛛并行处理,提高其抓取速度。深度优先是指网络蜘蛛会从起始页开始,一个链接一个链接跟踪下去,处理完这条线路之后再转入下一个起始页,继续跟踪链接。这个方法有个优点是网络蜘蛛在设计的时候比较容易。
根据抓取过程蜘蛛主要分为三个功能模块,一个是网页读取模块主要是用来读取远程
Web
服务器上的网页内容,另一个是超链分析模块,这个模块主要是分析网页中的超链接,将网页上的所有超链接提取出来,放入到待抓取
URL
列表中,再一个模块就是内容分析模块,这个模块主要是对网页内容进行分析,将网页中所有超标志去掉只留下网页文字内容。蜘蛛的主要工作流程如下图所示:
首先蜘蛛读取抓取站点的
URL
列表,取出一个站点
URL
,将其放入未访问的
URL
列表(
UVURL
列表)中,如果
UVURL
不为空刚从中取出一个
URL
判断是否已经访问过,若没有访问过则读取此网页,并进行超链分析及内容分析,并将些页存入文档数据库,并将些
URL
放入已访问
URL
列表(
VURL
列表),直到
UVRL
为空为止,此时再抓取其他站点,依次循环直到所有的站点
URL
列表都抓取完为止。
创建蜘蛛 |
读取站点 URL 列表 |
站点 URL 列表是否空 |
结束 |
是 |
否 |
将 URL 放入 UVURL 列表 |
UVURL 为空? |
读取此 URL 网页 |
超链分析 |
内容分析 |
存入文档库 |
删除此 URL 并加入 VURL |
取出一 URL |
是否已访问? |
否 |
否 |
版权声明:本文为xsc2001原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。