（计算机软件与理论专业论文）搜索引擎的研究与实现(1).pdf

摘要 面对互联网信息量爆炸式的增长，让人们越来越对搜索引擎产生需求和依赖，对 搜索引擎技术的研究具有非常重要的理论意义和实用价值本文对搜索引擎系统结构 及其工作原理进行了系统论述，在理论研究的基础上，还利用j a v a 技术对新闻搜索引 擎的核心部分进行了实现，并对网页搜索算法和搜索结果排序算法提出改进 本文在分析现有网页搜集技术的基础上，提出一种基于非贪婪策略的启发式搜索 算法，给出详细的算法过程和性能分析，并采用基于索引页的增量式网页搜集策略以 提高索引数据库维护效率，确保网页索引数据的及时更新；针对目前普遍采用的基于 链接分析的网页排序算法的缺陷，提出综合考虑网站性能、网页内容、页面更新时间 和用户点击率多种因素的网页捧序改进算法，以过滤垃圾网站提高搜索性能；最后就 基于j a v a 技术的新闻搜索引擎的实现机制进行了介绍。 关键词：搜索引擎网络蜘蛛页面分析索引页 f a c i n gt h ee x p l o s i v eg r o w t ho f t h ei n t e r n e tn e t w o r ki n f o r m a t i o n , p e o p l ed e p e n do nt h e s e a r c he n g i n em o l ea n dm o r e ，s or e s e a r c hf o rt h es e a r c he n g i n eh a st h ev e r yi m p o r t a n t l y t h e o r e t i c a lm e a n i n g sa n dp r a c t i c a lv a l u e s 隘p a p e rs y s t e m a t i c a l l yd i s c u s s e st h es y s t e m s t r u c t u r ee n dw o r kt e n e to ft h es e a r c he n g i n e ，o nt h eb a s i so ft h er e l e v a n tt h e o r y , m a k i n g u s eo ft h ej a v at e c h n i q u et o a l i z ct h en u c l e a rp a r t so ft h en e w ss e a r c he n g i n e , a n dp u t t i n g f o r w a r dt h ei m p r o v e m e n to nw e b p a g es e a r c ha l g o r i t h me n ds e a r c hr e s u l t r a n k i n g a l g o r i t h m o nt h eb a s i so fa n a l y z i n gt h ee x i s t i n gw e bc r a w l i n g , t h ea r t i c l ep u t sf o r w a r da h e u r i s t i c ss e a r c h i n ga l g o r i t h mb a s e do nn o n - g r e e d yp o f i c ya n di n t r o d u c e st h ep r o c e s so f a l g o r i t h me n dp e r f o r m a n c ea n a l y s i s i n d e t a i l ，a d o p t t i n ga l li n c r e m e n t a li n f o r m a t i o n e x t r a c t i o ns t r a t e g yb a s e do ni n d e xp a g et oi m p r o v et h ee f f i c i e n c yo fi n d e x e dd a t a b a s e m a i n t e n a n c ee n di n s u r et h er e f r e s h m e n to fw e b p a g ei n d e x e dd a t ai nt i m e a i m m i n ga tt h e c u r r e n t l yw i d e s p r e a d l ya d o p t t e dt h ew e a k n e s so fp a g cr a n k i n ga l g o r i t h m b a s e do nl j l 止 a n a l y g ；s ，p u tf o r w a r da ni m p r o v e m e n ti np a g er a n k i n ga l g o r i t h mo fc o m p r e h e n s i v e l y c o n s i d e r a t t e dv a r i o u sf a c t o r sc 孚，w e b s i t ep e r f o r m a n c e ，w e b p a g ea 加蜘坞，w e b p a g er e f r e s h t i m ea n dt h ev i s i t i n gr a t e so fc u s t o m e r se t c ，t of i l t e rt h er u b b i s hw e b s i t ee n di m p r o v et h e s e a r c hp e r f o r m e n c e ；f i n a l l y , t h er e a l i z i n gs y s t e mo ft h en e w ss e a r c he n g i n eb a s e do nj a v a t e c h n o l o g yi si n t r o d u c e d k e y w o r d ：s e a r c he n g i n ow e bs p i d e rp a g ea n a l y s ioi n d e xp a g e 长春理工大学硕士学位论文原创性声明 本人郑重声明：所呈交的硕士学位论文， 搜索引擎的研究与实现是本人在指导 教师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的作品成果对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结 果由本人承担 作者签名：g 毪缝缝坌墅墨年互月三丘日 长春理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“长春理工大学硕士、博士学位论文版权使 用规定”，同意长春理工大学保留并向国家有关部门或机构送交学位论文的复印件和电 子版，允许论文被查阅和借阅。本人授权长春理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编 学位论文。 作者签名：么缝缝迦旺月翌日 指导导师签名： 年至月冱日 第一章绪论 搜索引擎( s e a r c he n g i n e ) 是利用信息挖掘系统在网际空间寻找和挖掘相关或有 用信息，在此基础上建立检索数据库，并通过提供简单友好的查询界面帮助用户进行 网络信息检索的信息服务系统或工具“】搜索引擎实际是i n t e r n e t 上的一类网站，这 类网站与一般的网站不同，其主要工作是自动搜寻w e b 服务器的信息，将信息进行分 类、建立索引，然后把索引的内容存放到数据库中，便于以查询和利用的方式提交给 用户本章主要对课题研究的意义、搜索引擎的发展现状、本文主要研究内容等问题 进行阐述。 1 1 题目研究的意义 几年前全球式搜索引擎收录的网页量只有几千万页，而现在已经达到几十亿页。面 对互联网信息量爆炸式的增长，一方面极大满足了人的无限求知欲望，另一方面又使 时间资源越来越稀缺，这种情况也让人们越来越对搜索引擎产生需求和依赖。据c h i c ( 中国互联网网络信息中心) 第十四次互联网调查显示，搜索以7 1 9 的绝对优势成 为用户从互联网上获得信息的主要方式。几乎在全球所有的调查中，搜索引擎都是互 联网上使用程度仅次于电子邮箱的服务。有需求就要有供给，就会有市场，也就具有 发展的强劲动力。因此对搜索引擎技术的研究吸引了众多商家和学者的目光。 然而，目前搜索引擎技术同样遇到了一系列的困难，根据c n n i c 的报告称，用户认 为在互联网上查询信息时遇到的最大问题是重复信息太多( 4 4 麟) 、信息太陈旧更新 缓慢( 2 7 骗) 、得到的有用信息太少( 1 0 7 ) 、信息查找不方便( 1 0 2 ) 。目前普遍 采用的搜索引擎技术一般是对网页建立索引，根据关键字检索索引，最后返回指向目 标网页的指针“1 。这种传统的搜索技术存在着以下缺陷： 1 ) 随着信息的增多，索引会变得极为庞大而且，网上的内容随时都在更新，索 引信息随时会变得过时： 2 ) 基于关键字的检索方式使得检索结果返回成千上万条符合关键字查询条件的记 录，而其中绝大部分不满足用户的真正需要，用户不得不自行花费大量时间进行筛选； 3 ) 基于按u r l 来寻址的传统查询方式，使得如果搜索目标网页被移动到别的目录 结构后，与改变前相同的查询条件输入会导致搜索失败。1 。 针对以上缺陷，许多研究者就如何突破现有的传统搜索技术开展了研究工作，结 合数据挖掘、自然语言理解、神经网络等技术提出许多新的研究方向，涌现出许多热 点问题，因此对搜索引擎技术的研究工作具有非常重要的理论意义和实用价值。 1 2 搜索引擎的发展现状 1 2 1 搜索引擎分类 搜索引擎按其工作方式主要可分为三种，分别是目录索引类搜索引擎( s e a r c h i n d e x d i r e c t o r y ) 、全文搜索引擎( f u l l t e x t s e a r c h e n g i n e ) 和元搜索引擎( m e t a s e a r c h e n g i n e ) 啪 1 ) 目录索引类搜索引擎：目录索引是第一代搜索引擎的基本特点，其技术路线主 要受传统的图书情报管理方法的影响。我们知道，传统的图书馆面对大量的文献资源， 采用的办法是首先建立套图书文献分类标准，然后将文献按照分类标准手工或者计 算机辅助地进行分类，这样用户就可以按照这个分类进行文献的检索了目录索引类 搜索引擎就是将网站分门别类地存放在相应的目录中，因此用户在查询信息时，可按 分类目录逐层查找，某一目录中网站的排名通常是由标题字母的先后顺序决定( 也有 例外) 。这种搜索引擎的弊端和传统图书馆文献管理方法的弊端是一样的，首先，这个 分类体系是由文献的管理者人为的给出来的，用户并不一定清楚，或者说普通用户并 不一定理解，这样就有可能找不到想要的信息。其次，手工分类的成本太大、效率太 低，不能适应快速增长的网上信息资源管理的需要蛐 2 ) 全文搜索引擎：全文搜索引擎是目前主流的搜索引擎技术，国外具代表性的有 g , o o g l e 、f a s t ，a l 埘h e w c b 、a l t a v i s t a 、i n k t o m i 、t e o m a 、w i s e n u t 等，并不对文献进行 分类，而是从文献中识别出“关键字”来，然后建立索引，也就是说文献是用一组关 键字列表来表示的，这就是网络资源的数据模型这一模型的好处就是计算机可以自 动地完成，无需人工干预，这使得大规模的搜索成为可能。根据用户提交的查询关键 字，然后对出现这些关键字的页面按照确定的方法对其进行捧序，并按照得分的高低 顺序呈现给用户。这种方法的最大好处是用户不需要额外的负担，只需要敲入适当的 关键字就可以了。然而，在这里“关键字”仅仅是出现在网页中的符号而已，它所指 代的语义并没有被使用。页面分析所依据的也是存在于页面之间的链接关系，它不能 表示这些页面本身包含什么信息。这就决定了搜索引擎还不能很好地处理页面信息的 语义。 3 ) 元搜索引擎：据分析，任何一个搜索引擎索引的w e b 页面实际上都不到页面总 数的三分之一，而且由于检索机制、范围、算法等的不同，导致同样一个检索请求在不同 搜索引擎中的查询结果的重复率不足3 4 。因此，要想获得一个比较全面、准确的结果， 就必须反复调用多个搜索引擎，这无疑增加了用户的负担。元搜索引擎的出现，在一定程 度上解决了这些问题。元搜索引擎被称为搜索引擎之上的搜索引擎，它自己并不收集网 站或网页信息，通常也没有自己的资源库和r o b o t 。当用户查询一个关键词时，它把用户 的查询请求转换成其他搜索引擎能够接受的命令格式。并行地访问多个传统的搜索引擎 来查询这个关键词，然后将返回的结果进行合并、重新排序等处理后，作为自己的结果返 回给用户，严格地讲，元搜索引擎只是一个搜索代理程序，算不上一个真正独立的搜索引 擎“。 上述三种不同的搜索引擎分别可以用于不同的场合，有着自己的优缺点。全文搜 索引擎一般用于综合性的搜索，它的优点是信息量大，更新及时，不需要人工干预， 缺点是处理的信息量大，信息筛选困难。目录搜索引擎大多是面向网站，提供目录浏 2 览服务和直接检索服务，它的优点是人工的干预有利于提高信息搜索的准确度，缺点 是需要人工介入，维护成本高，更新慢，信息量小。元搜索引擎由于可以查询多个其 它的搜索引擎，所以特别适合于要求查全率高的场合，但是目前不同的搜索引擎之间， 建立索引数据库和执行提问检索的具体方法或规则并不相同，大大影响了元搜索工具 的检索效果。 1 2 2 专题搜索引擎 搜索引擎按收录范围可以将其分为综合类搜索引擎与专题类搜索引擎。综合类搜 索引擎又称为通用搜索引擎，收录的网络信息涉及多个主题及多种信息类型，在网上 可以搜索包括科学、人文、生活、新闻、休闲娱乐等多种信息。上文提到的全文搜索 引擎与元搜索引擎都是综合类搜索引擎；专题类搜索引擎亦称垂直搜索引擎，专门搜 某一类或某一主题的网络信息以满足用户查询某一类网络信息的需要。比如股票、天 气、新闻、人物、旅行路线等类的搜索引擎，具有很高的针对性，用户对查询结果的 满意度较高。图行天下( h t t p ：a v w w g 0 2 m a p t o m ) 、城市交通旅游电子地图0 l t p ：w w w a 血a p t o m 饥) 等属于垂直搜索引擎。 专题性搜索引擎是为了进一步满足某一专业领域在查全率和准确率上的搜索要求 而提出的。专题性搜索引擎通过编制一个按照预先己定义好的专题，来有选择性地收 集相关的网页的地址。首先分析它的搜集范围，再找到最相关的链接，避免不相关的 w e b 页。由于它涉及的信息范围要小得多，所以可以节省大量的硬件设备，可以提高信 息利用价值，并有能力跟踪每个相关网页，迅速发现和收集网上新加入的信息和被删 除的信息，使得信息保持定时更新此外专题性搜索引擎索引器因为涉及的领域小， 信息量相对少，所以完全可以在自动分类标引的过程中加入人工智能，利用专家的智 能对信息进行分类标引，提高信息的质量。 目前对于搜索引擎的首要关注点己经从如何找到更多的信息转移到如何找到准确、 有用的信息，查准率己经成为众多搜索引擎的首要目标。专题性搜索引擎是一种专用 领域的搜索引擎，它从某一专题出发，有针对性的搜索网上某一专题信息，采取优化 后台信息集合、优化用户查询界面等措旌，从而能够高效检索到所需的专题信息。研 究它可以方便用户更有效的发掘网上的信息资源，提高用户的信息查询效率，使之不 至于被信息海洋淹没。专题性搜索引擎具有广阔的应用前景和实用意义。 1 3 论文主要研究内容 互联网发展到今天，己经成为能够和报纸、电视以及广播齐名的四大媒体之一， 获取新闻也成为互联网的主要功能之一。无论哪一家媒体，拥有一个好的新闻栏目无 疑对吸引读者和观众至关重要，与传统媒体相比，互联网新闻在时效性上有着不言而 喻的优势，如何有效综合利用网络新闻资源，创办有特色的新闻栏目是目前各种传媒 在竞争中都面临的问题，新闻搜索引擎正是为了满足这一需求而开发的产品。它采用 中文搜索核心技术，针对新闻报道的特点进行专门的设计，从而可以帮助用户以较少 3 的花费建立独具特色、内容丰富、功能强大的新闻栏目。本论文在对搜索引擎的工作 原理和关键技术进行研究的基础上，详细论述如何利用j a v a 技术实现新闻搜索引擎的 功能。主要研究内容包括以下几个方面： 1 搜索引擎系统结构及其工作原理剖析。 2 在分析现有网页搜集技术的基础上，针对目前普遍采用的启发式搜索策略对信 息资源分布情况的估计存在明显的。近视性”( 只能近似反映未搜索空间边缘而不是内 部的分布情况) ，提出一种基于非贪婪策略的启发式搜索算法，给出详细的算法过程和 性能分析，与广度优先搜索算法和基于最好优先策略的搜索算法进行比较 3 采用基于索引页的增量式网页搜集策略以提高索引数据库维护效率，确保网页索 引数据的及时更新。 4 分析目前普遍采用的基于链接分析的网页排序算法的缺陷，提出综合考虑网站性 能、网页内容、页面更新时间和用户点击率多种因素的网页排序改进算法，以过滤垃 圾网站提高搜索性能 5 利用j a v a 多线程机制，结合l u c e n e 、j s p 等开发工具完成新闻搜索引擎的实现， 论文第五章给出具体实现机制。 4 第二章搜索引擎系统结构及关键技术 2 1 搜索引擎系统结构 搜索引擎并不真正搜索互联网，它搜索的实际上是预先整理好的网页索引数据库。 即根据用户的查询请求，按照一定算法从索引数据中查找信息返回给用户。通常真正 意义上的搜索引擎，通常指的是收集了因特网上几千万到几十亿个网页并对网页中的 每一个词( 即关键词) 进行索引，建立索引数据库的全文搜索引擎。当用户查找某个 关键词的时候，所有在页面内容中包含了该关键词的网页都将作为搜索结果被搜出来 在经过复杂的算法进行捧序后，这些结果将按照与搜索关键词的相关度高低，依次排 列显然，为了保证用户查找信息的精度和新鲜度，搜索引擎需要建立并维护一个庞 大的索引数据库”， 图2 1 搜索引擎系统结构 一般的搜索引擎由网络机器人程序、索引数据库、查询服务等部分组成。如图2 1 所示，搜索引擎的工作过程基本分为四个步骤：首先从互联网上抓取网页，利用能够 从互联网上自动收集网页的网络机器人程序( 又称网络蜘蛛) ，自动访问互联网，并 沿着任何网页中的所有u r l 爬到其它网页，重复这过程，并把爬过的所有网页收集回 5 来，由控制程序存入网页数据库；其次，由网页分析程序对收集回来的网页进行分析， 提取相关网页信息( 包括网页所在u r l 、编码类型、页面内容包含的关键词、关键词位 置、生成时间、大小、与其它网页的链接关系等) ，根据一定的相关度算法进行大量 复杂计算，得到每一个网页针对页面内容中及超链中每一个关键词的相关度( 或重要 性) ，然后用这些相关信息建立网页索引数据库：第三步是用户通过查询接口输入查 询条件，检索程序在索引数据库中检索，从网页索引数据库中找到符合该关键词的所 有相关网页。最后，由页面生成系统将搜索结果的链接地址和页面内容摘要等内容组 织起来返回给用户，因为所有相关网页针对该关键词的相关度早已算好，所以只需按 照现成的相关度数值排序，相关度越高，排名越靠前。图中用户的行为日志和日志分 析器部分的功能是将用户对搜索结果的操作反馈给网页数据库和索引数据库，为搜索 结果的捧序和网页内容分析提供依据 2 2 搜索引擎的关键技术 2 2 1 网络机器人 以w e b 网页为对象的搜索引擎利用h t 札文档之间的链接关系，在w e b 上一个网 页、一个网页的“爬取”( c r a w l ) ，将那些网页“抓”到本地后进行分析，因此如何在 w e b 上“爬取”，就是搜索引擎要解决的一个基本问题。在这方面，1 9 9 3 年m a t t h e wg r a y 开发了w o r l dw i d ew e bw a n d e r e r 是世界上第一个利用h t m l 网页之间的链接关系来监 测w e b 发展规模的“机器人”( r o b o t ) 程序。鉴于其在w e b 上沿超链“爬行”的工 作方式，这种程序也被称为“蜘蛛”( s p i d e r ) 。因此，在文献中c r a w l e r ，s p i d e r ，r o b o t 一般都指的是相同的事物，即在w e b 上依照网页之间的超链接关系一个个抓取网页的 程序，通常在搜索引擎系统中也称为网页搜集子系统嗍。 2 2 1 1 网页刷新策略 面对大量的用户查询，不可能想象每一个查询，系统就到网上。搜索”一次，网 络比较畅通的情况下，从网上下载一篇网页大约需要1 秒钟左右，因此如果在用户查 询的时候实时去网上抓来成千上万的网页，一个个分析处理，和用户的查询匹配，不 可能满足搜索引擎的响应时间要求。不仅如此，这样做会重复抓取太多的网页，无法 在效率上满足用户的要求，因此我们看到，大规模搜索引擎服务的基础应该是一批预 先搜集好的网页。这批预先搜集好的网页如何维护? 有两种基本的方法： 1 ) 定期搜集，每次搜集替换上一次的内容，我们称之为“批量搜集”。由于每次 都是重新来一次，对于大规模搜索引擎来说，每次搜集的时间通常会花几周。这样做 的好处是系统实现比较简单，缺点是“时新性”( f r e s h n e s s ) 不高，还有重复搜集所 带来的额外带宽的消耗。 2 ) 增量搜集，开始时搜集一批，往后只搜集新出现的网页，由于除新闻网站外， 许多网页的内容变化并不是很经常的更新，这样做每次搜集的网页量不会很大，于是 可以经常启动搜集过程，这样的系统表现出来的信息时新性就会比较高，但是系统实 6 现比较复杂”。 对于已提取页面的刷新问题，一般有周期性刷新、随机刷新和纯随机的刷新等三 种刷新机制以供选择，也有人尝试提出使用泊松分布对页面的变化过程进行建模。在 页面刷新的频度控制上，直觉上认为那些更新更快的页面在随后的一段时间内倾向于 发生改变。但是有研究表明，使用较高的刷新频率刷新更新快的页面并非总是正确的， 在有些时候，对各种页面采取相同的刷新周期反而在总体上来说刷新效果更好因为 假如以相对较高的频率刷新更新快的页面，这将使得其它页面的刷新机会减少，而当 那些更新快的页面在网络蜘蛛在刷新时并没有发生改变的情况下，这就造成了总体刷 新质量的下降。 2 2 1 2 网页搜索策略 在具体搜集过程中，如何抓取一篇篇的网页，也可以有不同的考虑。最常见的一种 是所谓“爬取”：将w e b 上的网页集合看成是一个有向图，搜集过程从给定起始u r l 开 始，沿着网页中的链接，按照某种策略遍历，下载相应的网页，解析出网页中的超链 接u r l ，整个过程可以形象地想象为一个蜘蛛( s p i d e r ) 在蜘蛛网( w e b ) 上爬行( c r a w l ) 。 对于搜索引擎来说，要抓取互联网上所有的网页几乎是不可能的，从目前公布的数据 来看，容量最大的搜索引擎也不过是抓取了整个网页数量的百分之四十左右这其中 的原因一方面是抓取技术的瓶颈，无法遍历所有的网页，有许多网页无法从其它网页 的链接中找到：另一个原因是存储技术和处理技术的问题，如果按照每个页面的平均 大小为2 0 k 计算( 包含图片) ，1 0 0 亿网页的容量是1 0 0x2 0 0 0 g 字节，即使能够存储， 下载也存在问题。同时，由于数据量太大，在提供搜索时也会有效率方面的影响。因 此，搜索引擎的网络蜘蛛只是抓取那些重要的网页，而在抓取的时候评价重要性主要 的依据是某个网页的链接深度。 本文第三章详细阐述了网页抓取的实现机制，对搜索算法的改进以及实验性能分 析。 2 2 1 3 搜索中的权限问题 据估计，整个互联网的网页数达到1 0 0 多亿，而且每年还在快速增长。因此一个 优秀的搜索引擎，需要不断的优化网络蜘蛛的算法，提升其性能。网络蜘蛛在访问网 站网页的时候，经常会遇到加密数据和网页权限的问题，有些网页是需要会员权限才 能访问。当然，网站的所有者可以通过协议让网络蜘蛛不去抓取，但对于一些出售报 告的网站，他们希望搜索引擎能搜索到他们的报告，但又不能完全免费的让搜索者查 看，这样就需要给网络蜘蛛提供相应的用户名和密码。网络蜘蛛可以通过所给的权限 对这些网页进行网页抓取，从而提供搜索。而当搜索者点击查看该网页的时候，同样 需要搜索者提供相应的权限验证。 网络蜘蛛需要爬取网页，不同于一般的访问，如果控制不好，则会引起网站服务 器负担过重。有多种方法可以让网站和网络蜘蛛进行交流。一方面让网站管理员了解 网络蜘蛛都来自哪几，做了些什么，另一方面也告诉网络蜘蛛哪些网页不应该抓取， 7 哪些网页应该更新。每个网络蜘蛛都有自己的名字，在抓取网页的时候，都会向网站 标明自己的身份。网络蜘蛛在抓取网页的时候会发送一个请求，这个请求中就有一个 字段为u s e r - a g e n t ，用于标识此网络蜘蛛的身份例如g o o g l e 网络蜘蛛的标识为 g o o g l e b o t 。b a i d u 网络蜘蛛的标识为b a i d u s p i d e r ，y a h o o 网络蜘蛛的标识为i n k t o m i s l u r p 。如果在网站上有访问日志记录，网站管理员就能知道，哪些搜索引擎的网络蜘 蛛过来过，什么时候过来的，以及读了多少数据等等“”。 2 2 2 网页内容分析 搜索引擎建立网页索引，处理的对象是文本文件。对于网络蜘蛛来说，爬取下来 的网页包括各种格式，包括盯儿、图片、d o c ( 惦霄0 r d 文档) 、p d f ( a d o b ep o r t a b l e d o c u m e n tf o r m a t ) 、多媒体、动态网页及其它格式等。这些文件抓取下来后，需要把 这些文件中的文本信息提取出来。准确提取这些文档的信息，一方面对搜索引擎的搜 索准确性有重要作用，另一方面对于网络蜘蛛正确跟踪其它链接有一定影响。 1 ) d o c ，p d f 等文档：这种由专业厂商提供的软件生成的文档，厂商都会提供相应 的文本提取接口。网络蜘蛛只需要调用这些插件的接口，就可以轻松的提取文档中的 文本信息和文件其它相关的信息。 2 ) h t m l 文档：h t m l 有一套自己的语法，通过不同的命令标识符来表示不同的字 体、颜色、位置等版式。提取文本信息时需要把这些标识符都过滤掉。这些标识符都 有一定的规则，只要按照不同的标识符取得相应的信息即可。但在识别这些信息的时 候，需要同步记录许多版式信息，例如文字的字体大小、是否是标题、是否是加粗显 示、是否是页面的关键词等，这些信息有助于计算单词在网页中的重要程度。同时， 对于哪札网页来说，除了标题和正文以外，会有许多广告链接以及公共的频道链接， 这些链接和文本正文一点关系也没有，在提取网页内容的时候，也需要过滤这些无用 的链接。过滤这些无效链接需要统计大量的网页结构规律，抽取一些共性，统一过滤： 对于一些重要而结果特殊的网站，还需要个别处理。 3 ) 多媒体文件：图片、声音等多媒体文件一般是通过链接的锚文本( 即链接文本) 和相关的文件注释来判断这些文件的内容。另外，许多多媒体文件中有文件属性，考 虑这些属性也可以更好的了解文件的内容。 4 ) 动态网页：动态网页一直是网络蜘蛛面l 临的难题，所谓动态网页，是相对于静 态网页而言，是由程序自动生成的页面，这样的好处是可以快速统一更改网页风格， 也可以减少网页所占服务器的空间，但同样给网络蜘蛛的爬取带来一些麻烦。由于开 发语言不断的增多，动态网页的类型也越来越多，如：a s p ( a c t i v es e r v e rp a g e ) 、j s p ( j a v as e r v e r p a g e s ) 。p h p ( h y p e r t e x tp r e p r o c e s s o r ) 等。这些类型的网页对于网络 蜘蛛来说，可能还稍微容易一些。网络蜘蛛更难于处理的是一些脚本语言( 如v b s c r i p t 和j a v a s c r i p t ) 生成的网页，如果要完善的处理好这些网页，网络蜘蛛需要有自己的脚 本语言解释程序。对于许多数据是放在数据库的网站，需要通过本网站的数据库搜索 才能获得信息，这些也给网络蜘蛛的爬取带来很大的困难。对于这类网站，如果网站 8 设计者希望这些数据能被搜索引擎搜索，则需要提供一种可以遍历整个数据库内容的 方法。 对于网页内容的抓取，系统一般采用插件的形式，通过一个插件管理服务程序， 遇到不同格式的网页采用不同的插件处理。这种方式的好处在于扩充性好，以后每发 现一种新的类型，就可以把其处理方式做成一个插件补充到插件管理服务程序之中” 2 2 3 索引数据库 搜索引擎不可能在搜索时实时去检查每个网页，而是需要把网页先抓取下来，按 照关键词建立好索引，每次搜索的结果都会直接从搜索引擎建立好索引的数据库中查 找，然后把结果返回给访问者。在目前磁盘容量已经不是瓶颈的时候，搜索引擎一直 在扩大自己的网页数量。最大的搜索引擎g o o g l e ( h t t p ：w w w g o o g l e c o m ) 从2 0 0 2 年的1 0 亿网页增加到现在近4 0 亿网页；最近雅虎搜索引擎 ( h t t p ：s e a r c h y a h o o c o m ) 号称收录了4 5 亿个网页；国内的中文搜索引擎百度 ( h t t p ：w w w b a i d u c o m ) 的中文页面从两年前的七千万页增加到了现在的两亿多。 对如此巨大的网页数据，索引的创建不仅仅只是一个高效的倒捧算法，它还包含许多 重要的方面：索引词的选择、中文分词、编码识别与转换、网页净化、强健的页面分析 等。 2 2 3 1 索引词选择 索引词的选择是检索系统实现的一个重要环节。搜索引擎普遍使用全文索引技术， 即网页文档中所有词都参与索引。理想的索引词应该是表达文档内容的语义单位，即 语言学里的词汇词，是那此专指义而实际意义无法由组合成分相加得到的最小语言单 位。实际系统中的中文文本必须通过自动分词程序的处理而分割成为独立的分词中一 位，再从分词结果中选择索引词。中文自动分词普遍采用基于分词词典的机械型分词 方法，这一方法主要难点在于分词歧义处理和未登录词识别：同时，词典规模是制约分 词精度的重要因素，中文自动分词软件使用的词典选词十分严格，随意加入新词将影响 分词软件的歧义处理过程，导致分词精度下降。而基本词典的规模对处理w e b 数据来 说是远远不够的，目前的检索系统普遍采用了一种混合索引的技术，这一技术首先用 统计方法对索引文档中的未登录词进行识别，把识别出的新词放入扩展词典。由于统 计方法的错误率高，扩展词典里面存在不少被错误识别的词，总规模在5 0 万词。在索 引创建过程中，使用两趟分词，先后根据基本词典的分词结果和使用扩展词典的分词 结果建立混合索引。例如，基本词典有“北京”、“大学”两词，无“北京大学”：扩展 词典中有“北京大学”，对文档中的“北京大学”字串，基本分词分为“北京”、“大 学”，扩展分词再切分为“北京大学”，索引按“北京”、“大学”、“北京大学”这样三 个单位建立。混合索引是索引大小与检索效率间的一种折衷，文档中的词被重复索引 导致索引文件增大：同时，因为更多可能成词或短语的字串被索引，可以大大提高对它 们的检索效率。实际系统中，存储开销相对于检索效率并不重要。所以，混合索引成 为一项可用技术。 9 2 2 3 2 网页预处理 在索引创建过程的网页分析中，编码转换是一个重要步骤。由于w e b 上的网页有 各种编码和字符集，搜索引擎索引系统必须对它们转换，采用统一字符集和编码方案 u n i c o d e 是一种兼容性较好的字符集选择，而且可以使用不同的编码方案，比如u t f - 8 ， u t f - 1 6 等。但是，由于程序移植和编程习惯上的困难，仍然使用g b k 为系统的字符集， 这对于中文的搜索引擎实现基本已经足够。但是，如果进一步考虑国际化，u n i c o d e 是更好的选择。常见的中文编码包括简体中文的g b k 、g b 2 3 1 2 、i s 0 - 2 0 2 2 - c n 、g b l 8 0 3 0 ， 还有繁体中文的b i g 5 ，b i g 5 h k s c s 和e u c t l r ：在g n u 的g l i b c 中有对这种编码的转换支 持，但对于简体、繁体转换是简单的基于字一字映射，准确度不高在网页分析中，识 别网页的编码方式也比较繁琐。按h t m l 的标准，页面内容编码依次由w e b 服务器返回 的h t t p 头中的c h a r s e t 字段、网页中m e t a 标签里的c h a r s e t 属性以及每个网页元索 的c h a r s e t 属性决定。而对中文网页存在许多编码设置错误的情况，尤其是大量简体、 繁体自动转换的网页，这时需要有一个自动识别编码的模块，按统计的方法自动识别 网页的正确编码“町 大量网页中存在不符合h t m l 标准的错误，这要求网页分析模块十分健壮。同时， 许多网页中存在大量无用信息，比如广告、导航条等，这一现象在大型网站使用相同 模板的网页中普遍存在。这些信息被称为网页噪音，它们对用户检索没有价值，不被 包含到索引范围内 2 2 3 3 索引的创建 检索系统可以采用词级带位置信息的全文索引。因为系统采取了按站点划分网页 数据的分布式方案，各个索引节点相互独立，索引创建过程在每个节点上独立进行 创建采用两趟的内存倒排创建算法，依次为每个小文档集倒排，最后执行多路合并， 生成总的倒排文件，主要步骤如下： ( 1 ) 页面分析。分析网页标签结构，调用中文分词和英文词法分析器提取索引词分 析过程中记录每个索引词的文档频率d f 和文档内的词频t f 通过散列表转换为索引词 编码，生成词典文件( f e x i c o nl i l e ) 。 ( 2 ) 按统计得到的索引词的t f 、d f 属性，可以估计出对应倒排项长度，以此预申 请空间。再次对文档集进行页面分析，同时在内存中执行倒排，把结果保存到临时文 件。 ( 3 ) 对生成的多个临时倒排文件执行多路合并，压缩编码输出，得到最终的倒排文 件( i n v e r t e df i l e ) 。 在索引创建过程中，页面分析特别是中文分词为主要的时间开销。算法的后两步 相对很快。这样，创建算法的优化集中在中文分词效率上，而没有采用倒排生成效率 更高的方法。 2 2 4 查询结果的组织 客户一般通过浏览器进行查询，这就需要系统提供w e b 服务器并且与索引数据库 进行连接。客户在浏览器中输入查询条件，w e b 服务器接收到客户的查询条件后在索引 数据库中进行查询、排列然后返回给客户端。 2 2 4 1 搜索结果的摔序 搜索引擎返回给用户的，是一个和用户查询相关的结果列表。列表中条目的顺序是 很重要的一个问题。如何对查询结果进行捧序有很多因素需要考虑，人们参照科技文 献重要性的评估方式，核心想法就是“被引用多的就是重要的”。引用”这个概念恰 好可以通过h t m l 超链在网页之间体现得非常好，作为g o o g l e 创立核心技术的p a g e r a n k 就是这种思路的成功体现。除此以外，人们还注意到网页和文献的不同特点，即一些 网页主要是大量对外的链接，其本身基本没有一个明确的主题内容，而另外有些网页 则被大量的其他网页链接。从某种意义上讲，这形成了一种对偶的关系，这种关系使 得人们可以在网页上建立另外一些重要性指标，这些指标有的可以在预处理阶段计算， 有的则要在查询阶段计算，但都是作为在查询服务阶段最终形成结果捧序的部分参数。 各种搜索引擎的技术改进和优化，都直接反应到搜索结果的捧序上。许多搜索引 擎都在进一步研究新的排序方法，来提升客户的满意度。专业人士认为，目前的搜索 引擎捧序算法上还存在两大不足 1 ) 没有真正解决相关性：相关性是指搜索词和页面的相关程度仅仅通过链接、 字体、位置等表面特征，不能真正判断搜索词和文章的相关性，更何况许多时候这些 特征不会都同时存在。这也是许多对搜索引擎做弊方法能有效的原因另外，有些文 章中没有出现搜索词，但说的就是和搜索词十分相关的内容，搜索引擎就无法搜索到 该网页表面特征只能治标，不能治本。治本的方法应该是增加语意理解，例如主题 词和关键词的提取，从语意上分析，得出搜索词和网页的相关程度，分析的越准，效 果就会越好“。 2 ) 搜索结果的单一化：在搜索引擎上，任何人搜索同一个词的结果都是一样。这 样明显不能满足访问者。科学家搜索“星球”，可能是希望了解星球的知识，但普通 人可能是想找“星球大战”电影，但搜索引擎所给的都是一样的结果。如何满足这些 不同类型的访问者，需要对搜索结果的个性化，最理想的结果应该是针对每个访问者， 排序结果直接和他们的搜索习惯和意愿有关。搜索“体育”，对喜欢足球的人应该把 足球的相关结果排在前面，对喜欢篮球的人应该把篮球的相关结果排在前面“” 2 2 4 2 搜索结果的表现方式 搜索引擎给出的结果是一个有序的条目列表，每一个条目有三个基本的元素：标 题，网址和摘要。其中的摘要需要从网页正文中生成。一般来讲，从一篇文字中生成 一个恰当的摘要是自然语言理解领域的一个重要课题，人们已经做了多年的工作并取 得了一些成果。但相关的技术用到网络搜索引擎有两个基本困难。一是网页的写作通 常不规范，文字比较随意，因此从语言理解的角度难以做好；二是复杂的语言理解算 法耗时太多，不适应搜索引擎要高效处理海量网页信息的需求。因此搜索引擎在生成 摘要时要简便许多，基本上可以归纳为两种方式，一是静态方式，即独立于查询，按 1 1 照某种规则，事先在预处理阶段从网页内容提取出一些文字，形成的摘要存放在查询 子系统中，一旦相关文档被选中与查询项匹配，就读出返回给用户。显然，这种方式 对查询予系统来说是最轻松的，不需要做另外的处理工作。但这种方式的一个最大的 缺点是摘要和查询无关。另一种方式是“动态摘要”方式，即在响应查询的时候，根 据查询词在文档中的位置，提取出周围的文字来，在显示时将查询词标亮。这是目前 大多数搜索引擎采用的方式。为了保证查询的效率，需要在预处理阶段分词的时候记 住每个关键词在文档中出现的位置。此外，对应一个查询往往会有成千上万的结果， 返回给用户的内容通常都是按页组织的，网络用户一般没有耐心一页页看下去，因此， 如果希望用户多用搜索引擎，就要让第一页的内容尽量有吸引力“l 】 2 3 搜索引擎评价指标 在传统信息检索中，衡量系统的基本指标：查全率( r e c a l l ) 和查准率( p r i c i s i o n ) ， 查全率是检索出的相关文档数和文档库中所有的相关文档数的比率；查准率是检索出 的相关文档数与检索出的文档总数的比率。对于一个检索系统来讲，查全率和精度不 可能两全其美：查全率高时，精度低，精度高时，查全率低。对于搜索引擎系统来讲， 因为没有一个搜索引擎系统能够搜集到所有的w e b 网页，所以查全率很难计算。由于 互联网海量信息的特征，查询返回的结果大都非常多，因此目前的搜索引擎系统都非 常关心精度。同时，互联网的信息是动态变化的，搜索引擎必须反映这种变化。 简单来讲，搜索引擎要满足用户对信息查询的需求，提高用户的搜索体验。以下 是几个比较重要的指标： 1 ) 网页覆盖率。提高查全率，是保证查准率的基础。 2 ) 返回结果的准确性，主要是第一页结果的准确性。大部分用户仅仅察看搜索结 果的第一页。 3 ) 重复信息返回的过滤。返回结果应该尽可能不出现重复、类似的结果。 4 ) 网页更新速度。取决于新网页的发现，和死链( 指无法访问网页) 的及时删除。 结果中大量的死链和过时信息的链接，将会降低用户体验。 5 ) 搜索服务的相应时间，也就是用户提交检索后得到结果返回的等待时间，一般 要低于一秒即可。 6 ) 搜索服务的系统稳定性。 第三章网页搜集技术 搜索引擎的第一步工作是在w e b 上收集网页并将其存入页面存储库，即网页抓取。 目前搜索引擎都采用一个叫做网络蜘蛛( w e b s p i d e r ) 的机器人程序来完成网页抓取的 工作。网络蜘蛛是一个很形象的名字，把互联网比喻成一个蜘蛛网，那么w e bs p i d e r 就是在网上爬来爬去的蜘蛛。网络蜘蛛是通过网页的链接地址来寻找网页，从网站某 一个页面( 通常是首页) 开始，读取网页的内容，找到在网页中的其它链接地址，然后 通过这些链接地址寻找下一个网页，这样一直循环下去，直到把这个网站所有的网页 都抓取完为止。如果把整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把 互联网上所有的网页都抓取下来。 3 1 抓取技术的协议分析 3 1 1 通信协议 超文本传输协议( h y p e r t e x tt r a n s f e rp r o t o c 0 1 ) ，简称f f r r p ，是面向分布式和 协同式超媒体信息系统的应用层协议，是胛w 发布信息的主要通信协议。h t t p 是建立 在t c p i p 之上的协议，同时也是一种套接字协议，事实上w e b 就是建立在i w r p 之上 的协议。要从w e b 上抓取网页，也就是通过h t t p 协议与w e b 服务器之间进行数据通信， 所以在研究网页抓取技术之前要对用到的通信协议即h r t p 协议做一个简要介绍“。 h t t p 是一个请求响应方式工作的协议( 相当于客户机服务器) 。 1 h t t p 请求行 一个h t t p 请求行由请求行、可选个数的请求首标和一个空行组成，使用p o s t 方 法时还允许有一些附加数据。请求行格式如下： 请求方法u r ih n p 版本号 请求方法是一个单词，h t t p1 0 中使用g e t 、h e a d 与p o s t 这几种请求方法。不过 现在越来越多的服务器开始