本章要点
本章介绍搜索引擎的原理和相关技术。从信息检索谈起,逐步阐述蜘蛛、索引等概念,并介绍搜索引擎涉及的一些数学算法。
2.1现代的信息检索技术
现在的时代被一些人称为信息时代,信息时代自然以信息为核心。在这个时代里,由于计算机技术的不断发展,信息技术逐渐成为了一门重要的学问。信息技术包含的门类很多,比如:信息存储、信息识别、信息检索、信息还原等。
信息检索是什么意思?
“检索”,就是“找”的意思。信息检索,就是找信息。比如:清晨起床,你发现袜子不见了,于是去寻找它,这就是一个信息检索的过程。你想要得到的信息是“袜子的位置”,在找袜子的过程中,你可能会钻到床底下,爬到衣柜上,或者转过身去照镜子看看袜子是不是粘到了你的毛衣上面。你所做的这些事情,就是你所采用的信息检索方法。
上面讲的是广义的信息检索,在计算机技术领域所研究的信息检索是狭义的,比如:把信息录入数据库中,然后在数据库中执行查询从而把符合需要的数据显示出来。
为什么要研究信息检索呢?
在德国柏林图书馆门前有这样一段话:“这里是知识的宝库,你若掌握了它的钥匙,这里的全部知识都是属于你的。”这里所说的“钥匙”即是指信息检索的方法。
至于信息检索技术有什么意义,读者大可发挥想像,笔者在这里仅举几个现实的例子,管中窥豹,可见一斑。
戴维曾经非常高兴地告诉牛顿,说他悟出了万有引力定律,而牛顿却很从容地拉开抽屉,里面正是他两个月前写好的万有引力定律的资料,戴维因此很气愤。如果当时有学术期刊互联网,戴维有了想法之后只需上网搜索一下,就知道自己的想法是不是新的,也就不会浪费时间了。
笔者的一个朋友对《庄子》很感兴趣,到书店去买,需要30块钱。于是他上网搜索,下载了一本电子书,两天就看完了,加了批注并打印了下来。这件事以后他就经常看电子书,认为“的确很合算”。
通过在网上搜索信息进行学习,通常是一件很轻松,很省钱的事情。
总之,信息检索之所以成为一门技术,其原因在于信息太多了,找起来太麻烦。越来越多的人都希望有一些方法可以实现快速而准确地找到自己想要的信息,信息检索技术就应运而生了。
这正如鲁迅说的那样:“世上本没有路,走的人多了,也便成了路。”对于信息检索,世上本没有这技术,检索的人多了,技术也就产生了。
本书介绍的网络搜索技术,正是信息检索技术的一部分。
2.2搜索引擎的原理
2.2.1古代的搜索引擎
既然提到“现代搜索引擎”,就不能不说“古代搜索引擎”。搜索引擎,是用来进行信息检索的工具,古人也要进行信息检索,当然也需要搜索引擎。
笔者曾经在古书上看到一个搜索引擎的案例,那是公元前238年,22岁的秦王政加冕亲政。这年,宦官嫪毐发动宫廷政变,秦始皇派昌平君、昌文君率兵围剿长信侯嫪毐,并悬赏说:“有生得毐,赐钱百万;杀之,五十万。”(《史记·秦始皇本纪》)这里,秦始皇为了找到嫪毐,用了昌平君、昌文君两个人及大量的兵马,这就是他的搜索引擎。
古时候并没有计算机技术,不论做什么事情对人力的依赖都很大,搜索也是如此。据史书记载,我国很久以前就有了图书馆,图书馆的工作人员把图书按照不同的分类放到架子上,然后挂上竹板作标记,再将书的内容和排列次序写到簿册上,以便于查阅。这其实就是索引技术。而且,在计算机技术发展起来之前,原始的纸本索引技术一直都使用着,直到现在,许多小型的图书馆仍然采用纸本索引技术来进行图书的检索和维护。
2.2.2现代搜索引擎的原理
在第1章中简单地提到了现代搜索引擎的分类,即:目录索引(或目录式搜索引擎)、全文搜索引擎和元搜索引擎。这里对搜索引擎的原理细致地介绍一下。
从技术上讲,目录索引并不能算是搜索引擎,因为它不能“搜索”。它只是人工地把网页进行归类,分成一层层的目录,让人去查找。比如,要查找“蔡依林”,可能需要这样做:
①进入“人类”目录,它包含着“男人”,“女人”,“太监”等子目录;②然后,选择“女人”目录进入,它下面又有“年轻的”,“中年的”,“老年的”等子目录;③选择“年轻的”进入,它下面有“美女”,“看得过去的女人”,“恐龙女”等子目录;④这时,选择“美女”目录,它包含“中国的”,“美国的”,“俄罗斯的”等子目录;⑤然后,选择“中国的”目录,进入,应该就可以看到“蔡依林”的名字排在第二或第三的位置上,这时,单击“蔡依林”链接,就可以看到与她相关的网页了。
不要以为目录索引很慢,应该退休。事实上它还是很有用处的。
真正的网络搜索引擎是全文搜索引擎。它基于对原数据的捕捉、分析和存储、索引等技术。它用网络蜘蛛从互联网或局域网中获取数据,然后对数据进行解析,在服务器中建立索引,存储副本,以供检索。
元搜索引擎是基于全文搜索引擎技术的,它将用户提交的检索请求发送到多个独立的搜索引擎上去搜索,并将检索结果集中统一处理,以统一的格式提供给用户,因此有搜索引擎之上的搜索引擎之称。元搜索的主要精力放在提高搜索速度、智能化处理搜索结果、个性化搜索功能的设置和用户检索界面的友好性上,查全率和查准率都比较高。
所以,从本质上讲,只有一种搜索引擎,虽然从技术上有不同的实现方式,但它们都属于全文搜索引擎。如果细分,全文搜索引擎可以分成本机搜索和互联网搜索。但是,从广义上讲,本机也可以称为独立网络节点,所以,从这个意义上讲,本机搜索和互联网搜索都属于网络搜索。网络搜索不只不含全文搜索一种,还有FTP搜索等形式,这不是本书要着重讲的内容,这部分知识也非常简单。
2.3网络搜索引擎的相关技术
2.3.1网络搜索引擎的架构
从基本架构谈起,一个网络搜索引擎是运行在计算机上面的,这台计算机就称作搜索引擎服务器。搜索引擎会使用蜘蛛程序到互联网上爬行,抓取数据回来,存入本机,建立索引及副本,这样就形成了索引库。然后用户在搜索引擎客户端输入要搜索的条件,搜索引擎处理用户的输入,将结果显示出来,这就完成了搜索。
分隔线以上就是搜索引擎的结构。这里的搜索界面包含了两部分:一部分是接受用户输入搜索条件的界面,数据来自用户;另一部分是显示搜索结果的界面,数据来自搜索引擎。
在这个搜索过程中,涉及了哪些技术呢?
(1)搜索引擎服务器的架设
直接地讲就是服务器计算机上的软硬件配置问题:要用什么型号的硬盘?硬盘容量多大?
硬盘之间如何协调?只用一台机器够吗?是不是要用一个服务器组?机器的内存多大?最多能支持多少个并发请求?……
类似的问题还有很多。在大型互联网搜索引擎的数据中心里,一般运行数千台甚至数十万台计算机,而且每天向计算机集群里添加数十台机器,以保持与网络发展的同步。
关于搜索引擎服务器的优化,已经是一门单独的学问。
(2)网络蜘蛛
搜索引擎要通过网络蜘蛛的爬行来寻找数据,蜘蛛首先定位数据的位置,然后建立连接,将数据抓取回来。那么,网络蜘蛛的原理是什么?怎样能使蜘蛛的效率更高?这也是一个问题。通常自动搜集网页信息的平均速度是每秒数十个网页,网络蜘蛛的优化也是一门学问。
(3)建立索引
数据抓取回来之后,存储在本机,对其建立索引。这个索引是如何建立的?又如何存储?
是不是对任何格式的数据都能建立索引?为什么这种索引相对于人工索引要快、智能?如何进行索引优化?这是一个重要的问题,直接影响到搜索效率。
(4)建立副本
对抓取来的数据建立副本,以实现快照,这些数据存在哪里?是存在文件系统中还是存在数据库里?应该选用哪种数据库来存储?快照的信息多久进行一次更新?
(5)处理用户请求
搜索引擎如何分析用户的请求?用户的语言搜索引擎能否读懂?是不是同时支持中文和英文?搜索引擎一次可以处理多少个并发用户请求?返回的结果按照什么标准进行排序?
这五个方面,是搜索引擎架设需要考虑的基本问题。在此之外,还有其他的问题需要考虑,比如服务器的安全、防黑客、防毒、防感应雷等,任何一方面考虑不周都会造成隐患。本书不分析服务器的配置、文件系统和数据库的性能及如何防黑客等问题,这些问题是建立任何的网络应用程序都需要考虑的问题,并不专属于搜索引擎。而对于如何抓取网络数据、解析不同各式的数据、如何建立索引,以及对中文(由这里可见搜索引擎对多国语言的支持)的支持等内容,是搜索引擎关注的核心问题,也正是本书要详解的知识。
2.3.2网络数据的搜集
1.搜集器的概念
执行网络数据搜集的功能模块称为搜集器。前面提及的网络蜘蛛就是搜集器。搜集器的功能是在互联网中漫游,发现并搜集信息,它搜集的信息类型多种多样,包括HTML页面、XML文档、Newsgroup文章、FTP文件、字处理文档、多媒体信息等。搜集器是一个计算机程序,其实现常常采用分布式和并行处理技术,以提高信息发现和更新的效率。
网络蜘蛛是一个很形象的名字。网络蜘蛛是通过网页的链接地址来寻找网页,从网站某一个页面(通常是首页)开始,读取网页的内容,找到在网页中的其他链接地址,然后通过这些链接地址寻找下一个网页。这样一直循环下去,直到把这个网站所有的网页都抓取完为止。
如果把整个互联网当成一个网站,那么网络蜘蛛就可以用这个原理把互联网上所有的网页都抓取下来。
对于搜索引擎来说,要抓取互联网上所有的网页几乎是不可能的,从目前公布的数据来看,容量最大的搜索引擎也不过是抓取了整个网页数量的百分之四十左右。这其中的原因一方面是抓取技术的瓶颈,无法遍历所有的网页,有许多网页无法从其他网页的链接中找到;另一个原因是存储技术和处理技术的问题,如果按照每个页面的平均大小为20KB计算(包含图片),100亿网页的容量是100×2000GB,即使能够存储,下载也存在问题(按照一台机器每秒下载20KB计算,需要340台机器不停地下载一年时间,才能把所有网页下载完毕)。同时,由于数据量太大,在提供搜索时也会有效率方面的影响。因此,许多搜索引擎的网络蜘蛛只是抓取那些重要的网页,而在抓取的时候评价重要性的主要依据是某个网页的链接深度。
2.抓取网页的策略
在抓取网页的时候,网络蜘蛛一般有两种策略:广度优先和深度优先。广度优先是指网络蜘蛛会先抓取起始网页中链接的所有网页,然后再选择其中的一个链接网页,继续抓取在此网页中链接的所有网页。这是最常用的方式,因为这个方法可以让网络蜘蛛并行处理,提高其抓取速度。深度优先是指网络蜘蛛会从起始页开始,一个链接一个链接地跟踪下去,处理完这条线路之后再转入下一个起始页,继续跟踪链接。这个方法的一个优点是,网络蜘蛛在设计的时候比较容易。
在这里,简要介绍一下深度优先和广度优先策略。
这两种策略都是搜索策略,打个比方来说,就是这样:一块地,下面某一处藏着一箱子钻石。不知在地下多少米的地方,也不知所处的方位。现在你很想把它挖出来,应该用什么方法呢?基本上有两种方法,一种是在一个地方挖洞,一直挖下去,挖到底,如果没有就换个地方挖,继续挖洞,挖到底,一步一步地往前挖,直到挖到宝藏为止。这就是深度优先策略。另一种方法是,一层一层地挖。先把这块地整体铲平一米,看看有没有,没有就继续铲平,再整体向下推一米,直到挖到宝藏为止。
这两种策略各有优劣,策略的好坏是由结果来定的。
如果这宝藏埋得很深,使用广度优先策略,几乎要把所有的土地都挖光才能挖到它,而使用深度优先策略,可能一不小心就碰上了,只挖了几个坑就找到了宝藏。
如果这宝藏埋得很浅,但地点隐秘。使用深度优先策略,是难以发现它的,盲目性太大。
而如果用了广度优先策略,把地皮向下铲一米,就找到了宝藏。
由于我们事先并不知道宝藏在什么地方,所以不能说采用哪个策略更好。
综合两个策略,有这样一个概念“启发式搜索”。这是什么意思呢?同样打个比方,现在你使用“挖洞”策略,已经挖了三个洞,忽然,从洞里跳出了土地老,他告诉你“宝藏在西南方向的大树下”,于是你得到了这个信息,立即赶到西南方大树下,挖了一个洞,把宝藏找出来了。或者,你现在使用“铲平”策略,把地皮铲去了一米,忽然发现了某处有一本藏宝图,恰恰写着宝藏的埋藏地点,于是你按照图找到了宝藏。
在启发式搜索中,强调了“启发”。这就是说,在搜索的过程中,要根据每个阶段搜索到的结果去做进一步的思考,从而使搜索的策略得到优化,以尽快得到搜索结果。