一个大规模、高性能的搜索引擎系统

北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第1页摘要本文首先回顾了WWW的起源和发展。面对极其大量的信息，人们通常依靠搜索引擎来为他们在WWW上进行导航，这给搜索引擎技术带来了巨大的挑战。自1994年问世以来，搜索引擎的发展经历了四代。我们对每一代搜索引擎及其特色进行了简要的陈述。搜索引擎是一个集多种技术于一体的综合性系统。在本文的第二章，我们就搜索引擎涉及到的某些核心背景技术，如搜索技术、IR技术、超文本链分析技术、用户行为分析技术，进行了讨论，并说明了这些技术对搜索引擎发展的影响和作用。“天网”是国家“九五”攻关项目中的一个子专题。在借鉴和参考大量国内外相关研究的同时，根据中国WWW的特点，我们设计了一个大规模、高性能的搜索引擎系统。在第三章，我们根据WWW的特点和搜索引擎的功能，根据图论、集合论及关系模型构建了“天网”搜索引擎的理论模型，并且以理论模型为出发点，设计了整个系统的体系结构。在文章的主体部分，我们以搜索引擎中数据流程为主线，描述了搜索引擎的几个子系统搜集子系统、分析子系统、索引子系统、检索子系统以及用户界面和日志挖掘子系统。在这些章节中，特别强调“天网”所采用的相关技术和关键算法分布式并行搜集技术、启发式搜集策略、镜像消除技术、中英文特征项提取技术、高效索引技术、词典更新技术、超链分析技术、快速检索技术、相关度评价策略、HASH排序算法、CACHE策略、中文词汇学习技术和用户行为分析技术。最后，我们简要的介绍了系统的实现和性能，并对“天网”系统提出了一些今后的发展设想。关键词搜索引擎，WWW，信息提取，分布处理北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第2页ABSTRACTINTHISTHESISTHEORIGINANDEVOLVEMENTOFTHEWWWAREREVIEWEDFIRSTWITHTREMENDOUSINFORMATIONONTHEWEB,PEOPLEUSUALLYRELYONSEARCHENGINESTOLOCATETHEINFORMATIONTHEYNEED,WHICHCREATESCHALLENGESFORSEARCHENGINESFROMTHEAPPEARANCEIN1994,SEARCHENGINESHAVEEXPERIENCEDFOURGENERATIONSEACHGENERATIONANDITSCHARACTERISTICSAREBRIEFLYDESCRIBEDSEARCHENGINEISASYSTEMTHATINTEGRATESDIVERSETECHNOLOGIESINCHAPTER2,SOMECORETECHNOLOGIESCLOSELYRELATEDTOSEARCHENGINES,INCLUDINGEFFICIENTCRAWLINGTECHNOLOGY,INFORMATIONRETRIEVAL,HYPERLINKANALYSIS,ANDUSERBEHAVIORSMINING,AREINTRODUCEDTHEIRCONTRIBUTIONTOTHESEARCHENGINEISALSOEXPLAINED“WEBGATHER“ISARESEARCHTOPICOFNATIONAL9THFIVEKEYPROJECTSAFTERANALYZINGTHERELATEDRESEARCHWORKANDTHEKEYFEATURESOFWWWINCHINA,WEHAVEDESIGNEDALARGESCALESEARCHENGINESYSTEMWITHHIGHQUALITYOFSERVICEINTHETHIRDCHAPTER,WEPROPOSEATHEORETICALMODELFORWEBGATHERUSINGGRAPHTHEORY,SETTHEORYANDRELATIONMODEL,ANDDESIGNTHESYSTEMARCHITECTUREBASEDONTHISMODELINTHEFOLLOWINGCHAPTER,WEDESCRIBETHESUBSYSTEMSOFWEBGATHERTHEYARECRAWLINGSUBSYSTEM,ANALYZINGSUBSYSTEM,INDEXINGSUBSYSTEM,SEARCHINGSUBSYSTEM,USERINTERFACEANDLOGMININGSUBSYSTEMINTHEMEANTIME,SPECIALEMPHASESAREPLACEDONTHERELATEDKEYALGORITHMSANDTECHNOLOGIESUSEDINWEBGATHERDISTRIBUTEDANDPARALLELCRAWLING,HEURISTICCRAWLINGSTRATEGY,REPLICATEDPAGESERASING,CHINESEANDENGLISHFEATURESEXTRACTING,EFFICIENTINDEXINGTECHNOLOGY,DICTIONARYUPDATING,LINKSTRUCTUREANALYSIS,FASTSEARCHINGTECHNOLOGY,RELEVANCERANKINGSTRATEGY,HASHSORTINGALGORITHM,CACHINGSTRATEGY,CHINESEKEYWORDLEARNING,ANDUSERBEHAVIORANALYZINGTECHNOLOGYFINALLY,WEBRIEFLYINTRODUCETHEIMPLEMENTATIONANDPERFORMANCEOFTHESYSTEMANDCONCLUDEWITHSOMEFUTUREWORKSFORWEBGATHERKEYWORDSSEARCHENGINE,WWW,INFORMATIONRETRIEVAL,DISTRIBUTEDPROCESSING北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第3页目录摘要（中文）1摘要（英文）2目录3第一章引言511WWW的起源和发展512搜索引擎作用、起源和发展6第二章相关研究及技术821大规模的搜索技术研究822IR相关技术的研究1023超文本链相关的研究1124用户行为的分析研究14第三章天网搜索引擎的体系结构1631天网搜索引擎的理论模型16311搜集的定义16312搜索引擎索引系统的定义17313检索的定义18314搜索引擎系统的更新过程1832天网搜索引擎的系统结构和子系统划分19第四章系统剖析2241网页的获取22411WEB的组织结构和网页的发现和获取策略22412并行搜集23413分布式搜集系统24414应该首先去抓下哪个网页26北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第4页415镜像网页的消除2742网页的分析28421传统IR的方法28422中文的编码处理29423英文和中文特征项提取29424特征项的权值30425生成网页的描述信息3243索引的生成33431索引的结构33432索引系统的创建35433词典的结构和生成36434网页索引的生成37435超链分析3844检索39441找到相关网页40442相关度计算哪个网页用户最想得到41443HASH排序保持检索的复杂度在ON43444CACHE系统让大量的检索成为0时间检索4445用户界面和用户行为的跟踪学习46451用户的界面技术47452中文新词学习技术48453用户行为对网页权值的影响50第五章结论和展望5451系统的开发和实现5452系统的运行相关的数据和系统的性能5453系统发展的展望55参考文献56致谢58北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第5页第一章引言11WWW的起源和发展WWW（WORLDWIDEWEB）起源于1989年欧洲粒子物理研究室CERN。WWW的最初计划是由CERN的物理学家TIMBERNERSLEE于1989年3月提出的，第一个原型（基于文本）于18个月后运行。1991年12月在德克萨斯州的SANANTONIO91超文本会议上进行了一次演示，并于1993年2月，随着第一个图形界面MOSAIC的发布而达到了其发展的高峰。1WWW的核心技术是超文本和超媒体。通过将文本、图形、图象、音频、视频等信息的有机结合，给人们提供了丰富的信息表示空间。由于其界面友好、易学易用、内容丰富，很快便被政府机关、科研机构、商业企业和个人所接受，成为人们日常信息交流的一个简单易用的工具。在1993年下半年，WWW在不到三个月的时间里翻了一翻。在1995年4月，WWW在网上的流量超过了其它INTERNET上其它服务的流量，成为INTERNET上的第一大应用服务。到1997年12月，根据NEC研究院在科学杂志上发布的数据2，网上大约有3亿2000万网页。在最近两年里，WWW又得到了长足的发展，不仅成为企业必不可少的组成部分，并且开始走进千家万户。根据NEC研究院在自然上发布的数据3，截止到1999年2月，INTERNET上共有网站1600万个，其中公开提供WWW服务的网站280万个；共有WWW网页大约8亿页，这些网页包含了15T字节的数据。按照2000年4月在波士顿举行的第5届搜索引擎年会的会议报告4，我们可以知道现今的网页数目已经超过了10亿。WWW在1994年登陆中国，到现在仅仅6年的时间里发展速度惊人。根据CNNIC中国互联网络信息中心在2000年1月的统计信息表明5，中国已有上网计算机350万台，其中WWW站点15153个；上网人数890万。关于网页的北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第6页数目没有具体的统计数据，但根据科学杂志上提供的集合估计法2，通过中国几个主要搜索引擎获得的搜索数据（天网、新浪、搜狐、网易），我们可以估计到当前中国拥有的网页数已经超过1000万。12搜索引擎作用、起源和发展WWW的发展给人们带来了巨大的方便，使得人们可以跨越时间和空间的界限来共享大量的信息。我们可以直接到其它的科研机构阅读我们感兴趣的文献；我们可以不用出户购买我们需要的东西；我们可以实时的了解国内外的新闻焦点。但是，面对如此大量的信息，我们同时也开始感到无所适从。太多的信息使我们很难迅速定位我们真正需要的信息，而跟随超链在WWW上漫游则会浪费大量的时间，而且很可能徒劳无功。因此，人们迫切需要有效的信息发现工具来为他们在WWW上进行导航。网上出现了两大类提供WWW导航的系统。第一类是目录系统，它通过有专业知识的网页编辑人员对网上的网页进行精选，建立一个索引目录，来给用户提供服务。这类系统的优点是提供的网页准确率高，但覆盖的范围小，其典型代表是YAHOO。第二类是搜索引擎系统，它通过程序自动地从网上搜集和分析网页，建立索引，为用户服务。这类系统的的优点是涵盖的网页数量巨大，但搜索的准确率相对比较低，其典型代表是ALTAVISTA。下面我们主要进行搜索引擎相关的介绍和发现。搜索引擎面世后，虽然抱怨不断，但它迅速成为人们网上搜索的有效工具。根据统计，大约85的用户使用搜索引擎去定位他们需要的信息6；并且，几个著名的搜索引擎一直都稳定的处于全球访问量最大的10个网站之列7。搜索引擎出现于1994年，例如LYCOS,INFOSEEK,ALTAVISTA和EXITE。我们称这些搜索引擎为第0代搜索引擎。这些搜索引擎的目的是出于研究的目的，它们一般都索引少于100万个网页，极少重新搜集网页去发现新的网页并去刷新索引。这个时期的搜索引擎的检索速度非常之慢，一般都要等待10秒甚至更长的时间。北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第7页两年后，第1代搜索引擎出现了。这些搜索引擎一般每天能够接受1000万次检索，并保持一个大约5000万网页的索引为用户提供服务。这一代搜索引擎的先驱是ALTAVISTA和INKTOMI。而它们的实现方法也大不相同。ALTAVISTA采用大型的多处理器计算机来支持它们搜索引擎的运转；而INKTOMI则采用分布式方案来解决搜索引擎对计算能力的要求。大概又有两年的时间，开始了一个搜索引擎空前繁荣的时期，我们统称这一时期的搜索引擎为第2代搜索引擎。在这一时期，有几个发展的特点除了一般意义上的搜索以外，开始出现主题搜索和地域搜索。很多小型的垂直门户站点开始使用该技术。由于搜索返回数据量过大，检索结果相关度评价成为研究的焦点。相关的研究又可以分为两类一类是对超文本链的分析，在这方面STANFORD大学的GOOGLE系统和IBM的CLEVER系统作出了很大的贡献；另一类是用户信息的反馈，DIRECTHIT系统采用的就是这种方法。开始使用自动分类技术。NORTHERNLIGHT和INKTOMI的DIRECTORYENGINE都在一定程度上使用了该技术。这一阶段的发展为搜索引擎拓展了生存空间，同时提高了搜索的质量和效率，为以后的发展奠定了坚实的基础。现在我们正在进入第3代搜索引擎的发展时期。这一时期以尝试索引“整个WEB”为标志。几个主流的搜索引擎，如INKTOMI,FAST,NORTHERNLIGHT,GOOGLE，都不断扩展自己的搜集能力，企图将整个WEB上的数据都搜集到，建立索引并为用户提供服务。同时，第2代搜索引擎的相应技术进一步发展和完善，尤其是相关度评价技术。另外，个性化检索也成为研究的热点。根据用户注册的信息，以及用户日常检索的行为，为用户提供最适合他期望的检索结果已经越来越受到各个搜索引擎的关注。北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第8页第二章相关研究及技术搜索引擎是伴随WWW的发展而迅速发展的一种技术。在起先的阶段，大家主要的着眼点还在于科学研究，所以相关的技术和算法都是公开的，没有什么秘密可言。但一段时期以后，当搜索引擎的巨大商业利益被发现后，很多以搜索引擎的研制和运营为其主要业务的公司兴起了，如ALTAVISTA、EXITE。很多的研究项目，当发展到一定的阶段，也就是可以商业化运作时，就从项目中剥离出来，成立自己的品牌公司。STANFORD大学的GOOGLE就是典型的一例。在商业竞争中，技术手段就被作为公司的头等机密保护了起来。很显然，透露了核心技术就意味着丧失了公司的一部分优势，就会在激烈的竞争中处于劣势。公司的竞争对搜索引擎技术的发展产生了两个方面的影响一方面，竞争迫使每个搜索引擎公司都要投入大量的人力物力研究新的技术，促进了搜索引擎的发展；另一方面，由于各公司的技术相互保密，也导致了在研究上的大量的重复，而带来大量的人力物力上的浪费。虽然各个公司在其核心技术上严格保密，但幸运的是还有很多的大学、科研机构在从事这一方面的研究，这使得我们仍然可以找到有着很高学术价值的文章。另外各个公司虽然不透露核心技术，但是从它们对自己搜索引擎的宣传以及在一些国际会议上的演讲，我们仍然可以从大体上看到它们采用的核心技术的轮廓。在下面的篇幅里，我们就当前影响到搜索引擎发展的一些相关技术做以下简要的回顾。21大规模的搜索技术研究WEB数据最大的一个特点就是数据量巨大，数据增长速度快。所以搜索引擎北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第9页如何能够最大限度、最高效的获取网络上的网页，成为搜索引擎的一个研究热点。分布处理（DISTRIBUTEDPROCESSING）技术是一个研究的热点，并且被很多搜索引擎系统的应用证明是行之有效的技术。HARVEST系统是1994年美国UNIVERSITYOFCOLORADO和UNIVERSITYOFSOUTHCALIFORNIA在INTERNET信息资源发现服务领域开展的研究工作成果。作为INTERNETIRTF信息发现研究课题组的核心项目，HARVEST的设计目标是在国家信息基础设施上提供资源发现服务。考虑到大多数资源索引系统彼此间对信息收集缺乏协作，使它们对网络和服务器增加了不必要的负载。HARVEST设计了有效的收集和分布索引信息的方法。图21显示了HARVEST的整体结构8910。如图21所示，HARVEST由若干子系统组成。GATHERER从信息资源站点PROVIDER（如FTP，WWW服务器）上提供的资源中收集索引信息（如关键词，作者，标题等）。BROKER从一个或多个GATHERER中取回索引信息、去掉重复的信息、存储下来并提供一个WWW的查询界面。REPLICATOR（图21中REPLICATIONMANAGER）用于在INTERNET上复制BROKER的信息。CACHE是为了减少网络流量、加快用户访问INTERNET信息资源的缓冲。HARVEST有一个被称为HSR（HARVESTSERVERREGISTRY）的特殊BROKER来保存网上所有的BROKER、GATHERER、CACHE和REPLICATOR的有关信息。图21HARVEST的系统构成北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第10页HARVEST提出了一个广域网信息搜集、查询的分布式体系结构，有很多设计思想被以后的其它系统借鉴和利用。但是，HARVEST系统庞大、算法复杂、开销巨大，使得其仅仅停留在科学研究的阶段，而没有成为真正的INTERNET服务。为了对付网络上数以亿计的网页和36个月翻一翻的增长速度，各个搜索引擎公司基本上都采取了分布和集群的搜索策略。按照GOOGLE公司总裁LARRYPAGE在搜索引擎2000年大会上的演讲，GOOGLE正在用3,000台运行LINUX系统的个人电脑在搜集WEB上的网页，而且以每天30台的速度向这个微机集群里添加电脑，以保持与网络的发展相同步。INKTOMI公司也正在依赖强大的微机集群，逐步实现索引整个WEB的设想。22IR相关技术的研究搜索引擎最重要的作用就是从大量的网页中找到所需要的网页，笼统的讲，就是根据一些检索项找到相关信息的过程，这也正是IR（INFORMATIONRETRIEVAL）研究的核心内容。IR在计算机科学发展中是一个悠久历史的领域。从本世纪70年代起，基于图书馆、档案馆等地方对检索的需要，IR开始进入了一个蓬勃发展的时期。到90年代，IR的研究已经相对成熟，出现了很多成熟的模型和算法。其中的向量空间模型11和TFIDF算法12对搜索引擎的检索技术起到很大的影响。早期的搜索引擎（在第一章中我们提到的第0代搜索引擎）基本上采用IR的相应技术。但是，随着WEB的发展和人们对搜索引擎检索质量要求的不断提高，原有的仅仅依赖IR技术的搜索引擎检索策略已经不能满足人们的需要。其原因在于传统的IR方法有两个重要的内在假设1被索引的信息本身有着很高的质量，至少在信息的组织和内容上有着比较高的质量。在WEB出现以前，传统的IR之所以能够行之有效至少在部分上是依赖这一点的。很多的IR产品一般都是针对一个特定的领域，如北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第11页法律信息、医疗信息、环保信息等等。这样它们可以针对这个领域进行算法的优化，同时，也避免了对一词多义的处理。2检索信息的用户有一定的相关技能和知识。也就是说，当用户面对一个很大的信息源时，他知道通过什么样的手段去提高检索的准确率PRECISION，但同时又不降低系统的招回率RECALL。与此相对应的，传统的IR系统总是提供一套十分完善的复杂检索语法来满足用户的要求。但不幸的是，这些假设在WEB上都已不再成立1WEB上网页的质量参差不齐，大量的网页组织性、结构性比较差。同时，WEB又是一个无所不包的载体，它涉及到政治、经济、教育、生活等各个层面。这使得IR中的很多技术都没有了施展才能的余地。另外，网络上充斥着很多没有任何意义的网页，很多镜像的网页，如果不采取相应的技术处理，将会在很大程度上影响检索质量。2大部分检索用户是没有任何经验的。他们经常只输入一个或者两个检索词来检索他们需要的网页，但会得到大量的返回结果，很难达到满意的程度。很少的用户尝试使用逻辑运算来提高检索的质量。但遗憾的是，在这些用户输入中，很大一部分在表达上仍然存在各种各样的问题。基于以上的讨论，人们发现，原有的IR技术已经不能适应WEB的发展。必须改进原有的IR相应技术，研究新的适合WEB的技术的算法，提高WEB检索的质量。23超文本链相关的研究和传统IR面对的数据相比，人们发现WEB中的网页有一个极大的相异点超文本链。如果我们将每个网页认为是一个节点，每一条超文本链认为是一条有向边，那么整个WEB就构成了一个庞大的有向图。这给我们了一个重要的启发，到底我们能利用图论的相应理论，从这个有向图中得到什么有用的信息呢STANFORD大学的GOOGLE13研究小组和IBM的CLEVER1415系统开发小组同时注意到了这个问题。它们根据自己对这个有向图的理解，提出了自己各自的理论北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第12页模型。GOOGLE系统称它们的相应技术为PAGERANK16。它们提出了一个“随机冲浪”模型来描述网络用户对网页的访问行为。模型假设如下用户随机的选择一个网页作为上网的起始网页；看完这个网页后，从该网页内所含的超链内随机的选择一个页面继续进行浏览；沿着超链前进了一定数目的网页后，用户对这个主题感到厌倦，重新随机选择一个网页进行浏览，并重复2和3。按照以上的用户行为模型，每个网页可能被访问到的次数就是该网页的链接权值。如何计算这个权值呢PAGERANK采用以下公式进行计算NJIIIIJIJNWLDDW,1,1（21）其中WJ代表第J个网页的权值；LIJ只取0、1值，代表从网页I到网页J是否存在链接；NI代表网页I有多少个链向其它网页的链接；D代表“随机冲浪”中沿着链接访问网页的平均次数。选择合适的数值，递归的使用以上公式，即可得到理想的网页链接权值。GOOGLE对它们的系统进行了测试，认为该方法能够大幅度的提高简单检索返回结果的质量，同时能够有效的防止网页编写者对搜索引擎的欺骗。当GOOGLE系统获得学术界的一致好评后，旋即走出了大学，成立了GOOGLE公司，并且在竞争激烈的搜索引擎市场占有了一席之地，这也从另一个侧面反映了该技术的有效性。IBM研究院CLEVER系统中的相应技术称为HITS（HYPERLINKINDUCEDTOPICSEARCH）17。CLEVER选择两种类型的网页1权威型网页对于一个特定的检索，该网页提供最好的相关信息；2目录型网页该网页提供很多指向其它高质量权威型网页的超链。北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第13页当遇到一个检索时，CLEVER先利用检索的关键词得到一个网页的根集合。然后根据这个集合在整个网页有向图中位置来扩展这个根集合。具体办法是，将被链接的网页加入到这个根集合中，形成一个新的集合。重复上述步骤，使根集合扩展到一个包含1,000到5,000的网页集合。得到这个集合后，就开始计算集合中每个网页的目录型权值和权威型权值。CLEVER的做法是采用目录型网页和权威型网页相互评价的办法，采用递归的算法进行计算。对于一个网页P，用XP来表示网页P的权威型权值，用YP来表示它的目录型权值，并且用如下公式进行计算PQTHATSUCHQPPPQTHATSUCHQPPXYYX（22）下面讨论该公式的矩阵表示。令所有选出来的网页都进行标号，我们得到所有网页的编号集1,2,N。令相邻矩阵A为一个NN的矩阵，如果存在一个从网页I链接到网页J的超链，就令矩阵中的第（I,J）项置为1，其它各项置为0。同时，我们将所有网页的权威型权值X和目录型权值Y都表示成向量形式XX1,X2,XN，YY1,Y2,YN。由此我们可以得到计算X和Y的简单矩阵公式YAAAYAXAYXAAAXAYAXTTTTTT（23）经过一定次数的递归运算后，会得到集合中每个网页的权威型权值和目录型权值。按照这两个不同的权值，分别取出前K个返回个用户。根据CLEVER系统自己的测试数据，对于返回给用户的前10个检索结果，CLEVER系统在50的情况下获得了高于YAHOO和ALTAVISTA的用户评价。通过上面的分析，我们发现这两种方法有很多相似之处。它们都利用了网页和超链组成的有向图，根据相互链接的关系进行递归的运算。但是，两者又有很大的区别，主要在于运算的时机。GOOGLE是在网页搜集告一段落时，离线的使用一定的算法计算每个网页的链接权值，在检索时只需要从数据库中取出这些数据即可，而不用做额外的运算。这样做的好处是检索的速度快，但丧失了检索时北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第14页的灵活型。CLEVER使用即时分析运算策略，每得到一个检索，它都要从数据库中找到相应的网页，同时提取出这些网页和链接构成的有向子图，再运算获得各个网页的相应链接权值。这种方法虽然灵活性强，并且更加精确，但在用户检索时进行如此大量的运算，会导致检索效率的急剧下降。24用户行为的分析研究和传统IR的用户群相比，虽然搜索引擎的用户群的经验少，但他们的数量却十分巨大。（图22）。如ALTAVISTA和INKTOMI这种知名的搜索引擎，每天都有多于1000万次的用户检索。通过对这些用户检索行为的统计分析，我们可以从中获取大量的有用信息，这些信息可以大大提高搜索引擎的结果的准确率，提高检索的质量。DIRECTHIT18技术就是基于以上思想创立的。这项技术的主要特点是跟踪用户对检索结果的后继行为哪些站点被用户选择浏览了用户在这个站点上花费了多少时间通过对这些数据的统计，搜索引擎就可以提高那些经常被用户选择，而且花了大量时间去浏览的站点的权值，惩罚那些被用户忽略的站点的权值。对于新加入系统的网页，系统则先给它们一个缺省的权值，然后由用户来决定它们的重要性。另外，系统还可以利用以前的用户检索行为来对以后的相似检索进行优化，帮助用户尽快发现自己需要的信息。图22传统IR和INTERNETIR的用户群差别北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第15页这个技术的另一个优点就是可以对一个固定的用户的行为进行跟踪和统计，进而发现这个用户的喜好和对检索结果的期待，从而产生专门针对该用户的检索结果。这就是我们提到的个性化检索。例如，一个做建筑材料的工程师，当他检索“WINDOWS”，他最大的可能是关注有关窗户的问题；一个计算机工程师，同样的检索则更关心微软的WINDOWS产品。通过几次用户检索行为的跟踪学习，我们就可以获得这些信息，进而在以后的检索中，我们就对检索的输出结果进行针对用户的适应性调整。DIRECTHIT公司的总裁GARYCULLIS在搜索引擎1999年年会上对他们的技术进行了高度的评价，并且将搜索引擎使用的四种技术（1根据网页本身信息（AUTHOR）；2根据超链链接关系（OTHERAUTHOR）；3人工编辑产生的目录系统（EDITOR）；4根据用户行为（USER）进行了比较（图23），得出根据用户行为的技术比其它几种技术无论在准确率和招回率上都有相当的优势。另外值得一提的是微软的MSN搜索引擎。在1998年，MSN搜索引擎完全依赖于INKTOMI，仅仅是在INKTOMI的搜索引擎外加了一个MSN的界面。但这正是微软发展搜索引擎的策略。通过用户检索日志的积累，微软获得了大量的宝贵数据。进而对这些日志的统计分析，微软得到了例如用户检索的分布，用户检索的规律，热点站点的分布等重要的数据。依赖这些数据，微软在1999年3月发布了它们的第一个搜索引擎，并将其集成到IE中。图23INKTOMI提供的几种搜索引擎的比较北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第16页第三章天网搜索引擎的体系结构为了方便日益增多的国内用户，促进INTERNET上尤其是CERNET上中文信息的交流，增强全世界华人的凝聚力，CERNET在“九五”攻关项目“计算机信息网络及其应用关键技术研究”中设立了“中文编码和分布式中英文信息发现”子专题，北京大学网络研究室承担了该子专题的部分研究开发工作，设计开发了“天网”中英文搜索引擎（WEBGATHER）192021。1997年10月29日，天网搜索引擎正式在CERNET上提供查询服务，受到学术界广泛好评。软件世界（1998年7月）将天网评为国内最值得关注的搜索引擎，1998年12月，天网通过了CERNET的鉴定。之后，天网又进行了大量的技术创新和系统的完善。到目前为止，天网总访问量已经突破5,000,000，并且仍以每天大于30,000的访问量递增。31天网搜索引擎的理论模型311搜集的定义根据相关技术部分的讨论，我们在搜索引擎研究中可以将WEB抽象为一个有向图。我们定义整个WEB对应的有向图为。有了初始值，在函数35的作用下，搜索引擎就可以不停的从WEB上获取网页了。312搜索引擎索引系统的定义在搜索引擎的核心里，每篇文章被抽象成一些特征项的描述，即PW1,W2WN。从网页里提取特征项的过程就是文章分析，我们定义函数PEXTRACT来描述这个过程,21PPWWWPTEXTRACTN36我们令集合DW1,W2,WN代表系统的特征项词典，集合PP1,P2,PN代表系统当前保存的网页集合，系统的索引可表示为集合PPDWPWRPWR表示，其中JIJIJIDFTFW45WIJ表示特征项TJ在文档DI中的权重，TFIJ表示特征项TJ在文档DI中出现的频率，称为项频，IDFJ则表示文档集D中出现了特征项TJ的文档的数目，称为文档频率。北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第29页对用户的一个检索Q，按照和文档D相同的分析方法，可以获得这个检索的特征向量WQ。由于WI和WQ是M维特征项空间里的两个向量，就可以用M维空间的余弦公式来求的两个向量夹角得余弦值COSWQ,WI|,COSIQIQIQWWWWWW46定义一个阈值K，如果COSWQ,WIK，就得到文档DI为检索Q的相关文章。对所有的文档运算，获得D中所有的与检索Q相关的文章。422中文的编码处理中文编码处理是中文信息处理面临的一个特殊问题。中文是一种相形文字，其字符（汉字）个数太多，无法在ASCII字符集范围内表示，就出现了用两个ASCII字符来表示一个汉字的做法，这也就是汉字编码问题。当前国际上通用的汉字编码主要有三种国标码（GB）、大五码（BIG5）和汉字码（HZ）。其中GB和BIG5编码是8位编码，其特征是一个汉字对应两个ASCII字符，而且第一个ASCII字符的最高一位为1。而HZ编码为7位编码，它也是由两个ASCII字符组成，但这两个ASCII字符都是基本ASCII字符集中的字符，用特殊标志“和“来进行转义。三种编码的相互转换基于编码之间的内码转换表。天网将GB定义为系统的标准内码。其它两种编码BIG5和HZ都经过内码转化，在系统内部以GB的形式存在。423英文和中文特征项提取在提取特征项时，中文又面临了与英文处理不同的问题。对于英文而言，词和词之间有天然的空格作为间隔符，这样我们可以方便的提取英文词汇作为特征项。但是，中文则不然，对于一句话而言，在不遇到标点符号时没有分隔符。这北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第30页就遇到了一个问题，如何从连续的汉字中提取特征项当今的中文搜索引擎特征项提取技术主要分为两类1基于字的特征项提取方法在这一类系统中，主要的方法是以双字或多字为单位，提取搜索引擎的特征项。如在双字系统中，“中华人民共和国”会被分割为“中华华人人民民共共和和国”共6个特征项被提取出来。2基于词的特征项提取方法这类系统需要用到中文分词的相关技术。它的方法是按照一定的语法甚至语义将原有的句子切分为词汇。如上例，将会被切分为“中华人民共和国”共3个特征项。作为第一类技术，它确实无误的对“全文”进行了索引。但是，我们会发现如下问题首先，它提取的特征项过多，其中大量的特征项都没有意义，浪费了搜索引擎的存储空间，同时降低了搜索引擎的检索效率；其次，这些多余项还可能造成检索中的错误。例如我们在检索“华人”时，我们就会得到“中华人民共和国”这个结果，但这显然不是我们需要的结果。第二类技术基本上解决了上述问题。但是，它仍然有自己的问题，这就是词汇切分造成的问题。当前的词汇切分系统的切分效果仍有一些不足之处如对歧义语句的切分，对专业领域文档的切分都不尽人意。但是，随着词汇切分技术的提高，相信在搜索引擎领域处理的也会越来越好。天网采用了第二类技术。词汇切分部分采用北京大学语言所开发的相应软件，词汇切分的准确率达到95。根据天网的实际运行数据表示，这个准确率已经基本满足搜索引擎的使用。424特征项的权值前面我们提到了向量空间模型，但根据我们在第二章中的讨论，我们并不能北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第31页够将它完全照搬到我们的系统中来。网页信息和正文文本最重要的差别就是在网页中含有大量的HTML标签（TAG）。因此，我们在天网中提出了一个改进的TFXIDF检索和相关度评价算法。相对传统的IR而言，我们增加了对HTML标签和网页的可索引文本长度。可索引文本长度表示用户通过浏览器窗口看到的一个网页的文本内容长度。考虑被HTML标签包围的一段文本内容，到底这些标签应该如何影响这段内容呢天网将所有的标签分为两类一类是影响文本权值的标签，如、等；另一类是不影响文本权值的标签，如、等。在天网中，我们选择在表41中的标签作为影响文本权值的标签。表41影响权值的HTML标签TAGWTTAGTAGWTTAG4048424444162124812481411114对于一个网页，首先我们给予该网页中每个特征项一个缺省的权值W0。如果一个特征项还被其它的有权标签包围，这些标签的权值将会影响到这个特征项的权值。例如，“HELLO”在HELLO环境中的权值应该为0BWBIGWWWBTTT47通过公式47，我们可以获得每个特征项在网页中每次出现的权值。假设特征项T在网页中出现N次，每次出现的权值分别为WBT1,WBT2,WBTN，我们就可以得到特征项T在整篇网页中的权值北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第32页NIIWBTPTWBT1,48对于一个网页，应用公式48对每个特征项进行权值计算是公平的。但是，考虑到相同的特征项出现在不同的网页中，我们会发现，网页的长度越长，特征项可能获得的权值也就越高。所以，一个特征项的权值应该在某种程度上受到网页长度的影响。另外，为了区分高频词和低频词对网页的影响程度，我们沿用IR中的IDF项/LOGMAX/LOG,TTNPSSPTWBTTIDFPDSPTWBTPTWB49SMAX表示最大的网页可索引文本大小；SP代表网页P的可索引文本大小；N代表被索引网页的总量；TT是包含特征项T的网页的数量。通过以上的分析，我们可以清楚的看到一个特征项的权值由三部分组成第一部分是考虑了HTML标签影响的绝对权值；第二部分是考虑网页大小对权值的影响；第三部分是特征项出现频率对权值的影响。最后，我们对WBK,P进行归一化处理。其中WBMAX代表对于所有的K、P而言WBK,P的最大值。MAX,WBPKWBPKWB410在442节中我们将看到，WBK,P将作为基本权值来参与相关度评价的运算。425生成网页的描述信息最后，让我们来考虑所提取网页的描述信息。所谓描述信息，就是检索结果显示给用户的信息和高级用户检索的限制信息的总和。在天网中，一个网页的描述信息包括网页的标题、URL、摘要、大小、日期和编码类型。检索限制信息包括大小、日期、和编码类型。其中，URL、大小、日期可以通过HTTP协议中的相应数据得到；编码类型北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第33页可以通过网页正文中的编码属性域获得，或通过编码识别程序获得；标题的提取只需要获得网页中被和之间的文本；摘要则通过提取可显示正文中最重要的512字节获得。43索引的生成提到索引，就使人联想到数据库系统。不错，现有的数据库系统在效率、稳定性上都有不错的表现，而且支持的数据规模也在逐渐扩大。但是，它并不满足搜索引擎的特殊要求，就像IR不能照搬用来进行网页分析一样。首先，搜索引擎面对的是海量的数据。按照前面提供的数据，大型的商业搜索引擎一般都索引几千万个网页，有些甚至到几个亿。如此大型的数据量，使得数据库系统很难有效的管理。其次，搜索引擎使用的数据操作简单。一般而言，只需要增、删、改、查几个功能，而且数据都有特定的格式，可以针对这些应用设计出简单高效的应用程序。而一般的数据库系统则支持大而全的功能，同时损失了速度和空间。最后，搜索引擎面临大量的用户检索需求（1000万1亿/天），这要求搜索引擎在检索程序的设计上要分秒必争，尽可能的将大运算量的工作在索引建立时完成，使检索的运算尽量的少。一般的数据库系统很难承受如此大量的用户请求，而且在检索响应时间和检索并发度上都不及我们专门设计的索引系统。431索引的结构天网搜索引擎索引的设计主要围绕两个核心思想提高检索效率和节省系统资源。围绕这两点，天网设计了如图44的索引结构。北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第34页索引主要分为4个部分1词典词典是实现特征项、URL和其对应编码的工具。对于搜索引擎而言，特征项和URL是中文或英文的不定长字符串。显然这不利于系统的存储和运算。通过词典系统，将这些不定长的数据转换成系统唯一的整型编码，大大的节省了系统的存储空间，同时提高了检索中最常用的运算比较运算的运行效率。2一级网页索引通过词典，一个特征项被翻译为系统唯一的编码。利用这个编码，我们可以找到这个特征项对应的网页的一级索引的入口。一级索引中包含两个数据，一是该特征项对应的二级网页索引的入口地址偏移量，而是二级索引项的个数。3二级网页索引二级索引是一个索引项列表，它通过一级索引获得。二级索引表中每一项代表检索特征项对应的一个结果网页概要描述，包括该网页的编码，特征项与该网页的相关度权值以及用户的评价权值（参考453节）。4网页描述这就是检索到的信息，用户通过网页编码获得它。它的对应域基本上和网页分析时产生的网页描述相同，只有一个域链接权值，是在索引生成时通过对已搜集网页的链接关系生成。词典特征项特征项编码一级网页索引偏移量数目二级网页索引网页编码用户权值特征项权值网页描述URL标题摘要网页大小编码类型网页最后更新时间链接权值图44索引结构北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第35页432索引系统的创建结合42节的网页分析的相关内容，我们给出从搜集端数据库到检索端数据库的生成过程。如图45其中网页分析器的相关内容我们在上一部分已经详细的分析过，这里主要分析索引创建的具体实现。从图45上可以看到，索引创建主要由三个子模块构成，分别是索引生成器、词典生成器和超链分析器。从图中的两个反向流程线我们可以得知，应该首先生成检索端数据库的特征项词典和URL词典，然后再利用这两个词典生成网页索引和网页描述信息。网页数据库超链数据库网页分析器超链分析器索引生成器词典生成器特征项数据网页描述特征项词典URL词典网页索引网页描述搜集端数据库检索端数据库临时数据网页分析器索引创建器图45索引的创建北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第36页433词典的结构和生成词典的最简单的描述就是一个译码器，它分配给词典中的每一个条目一个唯一的整型编码。前面我们已经论述过词典的好处。在这里，我们从系统设计的高度再分析一下词典的用途。如图46所示，我们将系统分为核心和外围应用，我们就看到了词典的地位，它相当于系统核心和外围之间的一座桥梁。外围应用通常是和系统输入和输出（广义的）打交道的，它们面临的数据千差万别。如果让核心直接处理这些形态各异的数据，就会导致系统核心代码的急剧膨胀，系统运行效率迅速降低。通过词典的处理，将各种数据以统一的整型编码的形式交给系统内核，使得系统内核的处理简单，保证了系统的运行效率。既然词典处于桥梁的地位，那么词典的本身的设计就十分的关键。天网系统采取了HASH表的方法来实现系统的词典。对于每一个输入数据DINPUT，按照分布式搜集策略部分的分析，我们可以将其对应到一个大整数。我们选择HASH表的大小为H_SIZE，根据公式411，对任意一个输入数据，我们都可以获得它HASH表的入口地址SIZEHDDFADDRINPUTINPUTKEY_INT41其中的FKEY就是我们按照公式411得到的HASH的散列函数。任何值域小于定义域的散列函数，都不能保证没有冲突，这就要求我们的散列函数造成冲突的概率尽量的小。通过选择适当的H_SIZE和散列函数，我们可以控制HASH的平均拉链长度。对于散列函数FKEY，我们用593,286和特征项大小为100万的HASH中散列，得到的平均拉链长度为132。这意味着，我们对任何一个数据DINPUT操作时，需要的HASH相关的操作为132次。其它的相关操作，如FKEY的运算、HASH表的增删改查，都是常数复杂度。因此，我们可以获得词典的运算复杂度为O1。应用1应用1应用1词典层系统内核图46词典在系统中的地位北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第37页434网页索引的生成索引的生成相当于从正排表到倒排表的建立过程。当我们分析完网页时，得到的是以网页为主码的索引表，如图47A的表。当索引建立完成后，应该得到图47B的表。这就是一个表的重组的过程，时间复杂度为ON，但全过程需要在内存中完成。当面对小数据量时，我们有足够的内存保证该创建过程可以一次完成。但是，搜索引擎面对的是G级的数据，特别是当规模不断扩大时，我们根本不可能提供这么多的内存，这就要求我们采用其它的策略。天网搜索引擎采用分组索引，然后在归并索引的策略。如图48网页索引特征项词典特征项数据建立索引索引1索引2索引N归并索引图48分组索引生成策略特征项1特征项2特征项1特征项2特征项3网页1网页2网页K网页N网页1网页2网页1网页2网页3特征项1特征项2特征项K特征项N图47从正排表到倒排表AB北京大学硕士研究生学位论文一个大规模、高性能的搜索引擎系统第38页在该策略中，建立索引的模块根据当时运行系统所在的计算机的内存大小，将索引分为N组，使得每组都小于系统能够提供的最大使用内存大小。按照倒排表的相应生成算法，生成N个分组索引。然后将这N个索引归并，即将相同的主码对应的数据合并到一起，就得到了我们期望的以特征项为主码的倒排表，即网页索引。435超链分析在这部分，我们主要考虑WWW中超链的互链关系对一个网页权值的影响。WEB有两个基本的构成因素网页和超链。如果我们将网页认为是节点，超链是有向边的话，我们就可以将整个网络抽象为一个巨大的有向图（图49）。从图49中我们可以看到，每个网页的入度是不同的，我们称每个网页的入度为网页的链接命中数（LINKHITNUMBER,LHN）。为什么LHN应该影响一个网页的权值呢我们知道这些超链都是网页的编辑加入网页中的。他们之所以加入这些超链，是他们认为这些超链是有价值的，值得留恋他们网页的浏览者去继续阅读。如果一个网页被大量的其它网页所链接（也就是说，被大量的网页编辑推荐），我们可以确定，这个被链接的网页是相对重要的，它们会对上网浏览的用户有更大的帮助。所有的链接都应当按照如上所述的方法考虑吗经过认真的分