课程设计 互联网搜索引擎的关键技术.doc

互联网搜索引擎的关键技术信息工程学院中文摘要现在互联网的迅猛发展，网络信息逐渐增加，用户想要在互联网上查找到自己需要的信息犹如大海捞针。而现在正有一种技术正好解决这样的问题，那就是搜索引擎技术。搜索引擎是指互联网上专门提供检索服务的一类网站，这些站点的服务器通过网络搜索软件(例如网络蜘蛛)或网络登录等方式，将Intemet上大量网站的页面信息收集到本地，经过加工处理建立信息数据库和索引数据库，从而对用户提出的各种检索作出响应，提供用户所需的信息或相关指针。用户的检索途径主要包括自由词全文检索、关键词检索、分类检索及其他特殊信息的检索(如企业、人名、电话黄页等)。关键词：搜索引擎 中文分词 搜集器 建立索引 搜索结果显示 目录1引言- 3 -2网络数据的搜集- 4 -2.1网络蜘蛛- 4 -2.2抓取策略- 5 -2.3网络蜘蛛示例- 6 -3.建立索引- 8 -3.1索引- 8 -3.2搜索引擎分类- 9 -3.3索引主流技术- 10 -4中文分词技术- 11 -4.1基于字符串匹配的分词方法- 11 -4.2基于理解的分词方法- 13 -4.3基于统计的分词方法- 14 -5搜索结果的显示- 14 -5.1 PageRank算法- 14 -5.2 HillTop算法- 15 -6中国搜索引擎市场规模和预测- 15 -个人感受：- 16 -参考文献：- 16 -1引言从基本架构来说，一个网络搜索引擎是运行在计算机上面的，这台计算机就称作搜索引擎服务器。搜索引擎会使用网络蜘蛛到互联网上爬行，抓取数据回来，存入本机，建立索引及副本，这样就形成了索引库。然后用户在搜索引擎客户端输入要搜索的条件，搜索引擎处理用的输入，将结果显示出来，这就完成了搜索。网络蜘蛛爬行过程可见图1.1：人工干预系统互联网蜘蛛群抓取信息处理系统检索索引数据库指令搜索指定连接报告连接数 据 图1.1蜘蛛群抓取信息全过程而在整个搜索过程中，涉及的技术包括了搜索引擎服务器的假设、网络蜘蛛、建立索引、建立副本和处理用户请求等方面，而对于如何抓去网络数据 、解析不同格式的数据、如何建立索引，以及对中文的支持等内容是搜索引擎关注的核心问题，而搜索引擎的关键技术包括了网络数据的搜集、建立索引、中文分词技术和搜索结果的显示。12网络数据的搜集2.1网络蜘蛛执行网络数据搜集的功能模块称为搜集器。网络蜘蛛就是搜集器，搜集器的功能实在互联网中漫游，发现并搜集信息，它搜集的信息类型多种多样，包括HTML页面、XML文档、Newsgroup文章、FTP文件、字处理文档、多媒体信息等。搜集器是一个计算机程序，其实现场常采用分布式和并行处理技术，以提高信息发现和更新的效率。商业搜索引擎的搜集器每天可以搜集几百万甚至更多的网页。搜索器一般要不停地运行，要尽可能多、尽可能快地搜集互联网上的各种类型的新信息。因为互联网上的信息更新很快，所以还要定期更新已经搜集过的旧信息，以避免死链接和无效链接。另外，因为Web信息是动态变化的，因此搜集器、分析器和索引器要定期更新数据库，更新周期通常约为几周甚至几个月。索引数据库越大，更新也越困难。在搜集器实现时，系统中维护一个超链队列，或者堆栈，其中包含一些起始URL，搜集器从这些URL出发，下载相应的页面，并从中抽取出新的超链接加入到队列或者堆栈中，上述过程不断重复队列直到堆栈为空。为提高效率，搜索引擎将Web空间按照域名、IP地址或国家域名进行划分，使用多个搜集器并行工作，让每个搜索器负责一个子空间的搜索。为了便于将来扩展服务，搜集器应能改变搜索范围。9网络蜘蛛是通过网页的链接地址来寻找网页，从网站某一个页面（通常是首页）开始，读取网页的内容，找到在网页中的其他链接地址，然后通过这些链接地址寻找下一个网页。这样一直循环下去，知道把这个网站所有的网页都抓取完为止。如果把整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上所有的网页都抓取下来。在抓取过程中，蜘蛛主要分为三个功能模块， 一个是网页读取模块主要是用来读取远程 Web 服 务器上的网页内容，另一个是超链分析模块，这个 模块主要是分析网页中的超链接，将网页上的所有 超链接提取出来，放入到待抓取 URL 列表中，再一 个模块就是内容分析模块，这个模块主要是对网页 内容进行分析，将网页中所有超标志去掉只留下网 页文字内容。为了提高网络蜘蛛的抓取效率，需要引入以下 技术。1）、 多线程技术：由于抓取的站点 URL 相当多，采用单线程蜘蛛抓取时速度不够，也不能满足实 际的需要。因而需要多线程技术来创建多个蜘蛛线程来同时抓取，以提高速度。2）、 网页抓取：网页抓取是基于 HTTP 协议之上的， 网页上的资源有多种，有网页，有 Word 文档也 有其他类型的文件，这样抓取时需要判断 URL 所指向资源的类型。3）、 超链分析：超链分析是一个比较重要的环节，需要对 HTML 的各种标志（tag）有一个很全面 的了解。需要反复测试，考虑各种情形的发生。超链分析时从网页里提取出来的是相对于当前 页的相对 URL，因而需要根据当前页的绝对 URL 将提取的这个 URL 转换成绝对 URL。在 此过程中需要根据 ParentURL（就是当前页的 URL）作出各种判断。82.2抓取策略由于互联网上的信息在爆炸式的增长，所以搜集器需要采用一定的搜索策略来对互联网进行遍历并下载文档。网页的抓取策略可以分为深度优先、广度优先和最佳优先三种。深度优先在很多情况下会导致爬虫的陷入(trapped)问题，目前常见的是广度优先和最佳优先方法。广度优先搜索策略是指在抓取过程中，在完成当前层次的搜索后，才进行下一层次的搜索。该算法的设计和实现相对简单。在目前为覆盖尽可能多的网页，一般使用广度优先搜索方法。也有很多研究将广度优先搜索策略应用于聚焦爬虫中。其基本思想是认为与初始URL在一定链接距离内的网页具有主题相关性的概率很大。另外一种方法是将广度优先搜索与网页过滤技术结合使用，先用广度优先策略抓取网页，再将其中无关的网页过滤掉。这些方法的缺点在于，随着抓取网页的增多，大量的无关网页将被下载并过滤，算法的效率将变低。最佳优先搜索策略按照一定的网页分析算法，预测候选URL与目标网页的相似度，或与主题的相关性，并选取评价最好的一个或几个URL进行抓取。它只访问经过网页分析算法预测为“有用”的网页。存在的一个问题是，在爬虫抓取路径上的很多相关网页可能被忽略，因为最佳优先策略是一种局部最优搜索算法。因此需要将最佳优先结合具体的应用进行改进，以跳出局部最优点。将在第4节中结合网页分析算法作具体的讨论。研究表明，这样的闭环调整可以将无关网页数量降低30%90%。最大的搜索引擎Google（ ）从2002年的10亿网页增加到现在近40亿网页；最近雅虎搜索引擎（ / ）号称收录了45亿个网页；国内的中文搜索引擎百度（ ）的中文页面从两年前的七千万页增加到了现在的两亿多。据估计，整个互联网的网页数达到100多亿，而且每年还在快速增长。因此一个优秀的搜索引擎，需要不断的优化网络蜘蛛的算法，提升其性能。 2.3网络蜘蛛示例网络蜘蛛的软件现在有不少，下面是一个名叫JOC Web Spider的软件，方便了解网络蜘蛛抓取网页的过程：打开软件后，新建工程，在工程中添加条目如图2.1：添加条目 图2.1新建工程在Starting Address窗口中填入目标地址1如图2.2：目标网址1 图2.2添加目标网址1再添加一个目标网址如图2.3：目标网址2 图2.3添加目标网址2目标条目添加完毕如图2.4： 图2.4添加完毕点击Update，开始抓取工作如图2.5： 图2.5抓取进行中抓取结束如图2.6： 图2.6结束抓取抓取到的数据如图2.7：（其中包括的信息类型多种多样，包括HTML页面、图片、字处理文档等）。 图2.7抓取结果每个网络蜘蛛都有自己的名字，在抓取网页的时候，都会向网站标明自己的身份。网络蜘蛛在抓取网页的时候会发送一个请求，这个请求中就有一个字段为User agent，用于标识此网络蜘蛛的身份。例如Google网络蜘蛛的标识为GoogleBot，Baidu网络蜘蛛的标识为BaiDuSpider， Yahoo网络蜘蛛的标识为Inktomi Slurp。如果在网站上有访问日志记录，网站管理员就能知道，哪些搜索引擎的网络蜘蛛过来过，什么时候过来的，以及读了多少数据等等。如果网站管理员发 现某个蜘蛛有问题，就通过其标识来和其所有者联系。3.建立索引3.1索引索引是将一种或多种书看文献中有关信息的名称（如字、词、人名、书名、刊名、篇名等）分别摘录，分类或按主题编排起来，或成册，或附在一书之后，注明出处，用以检索文献信息的工具，它能够提供信息的线索。索引是目录的延续和深化。当用网络蜘蛛在互联网中爬完后，需要对所获得的网页信息进行预处理，即根据网页结构去掉网页控制代码及无用信息，提取出有用的信息，并把信息用一定的模型表示，使查询结果更为准确。其中信息的表示模型一般有布尔模型、向量模型、概率模型和神经网络模型等。模型化的信息将存放在临时数据库中，由于Web数据的数据量极为庞大，为了提高检索效率，应该按照一定规则建立索引。索引文件一般是按照倒排文件的格式存放的，索引的建立包括：1）分析过程处理文件中可能的错误；2）文件索引完成分析的文件被编码存进索引数据库，有些搜索引擎还会使用并行索引；3）排序将索引数据库按照一定的规则排序，产生全文索引。不同的搜索引擎在建立索引时会考虑不同的选项，比如是否建立全文索引、是否过滤无用词汇、是否使用META信息等（META标签是内嵌在网页中的特殊HTML标签，作用是向搜索引擎解释网页是有关哪方面信息）。23.2搜索引擎分类搜索引擎按其工作方式主要可分为三种，分别是全文索引类引擎（Full Text Search Engine）、目录索引类搜索引擎（Search Index/Directory）和元搜索引擎（META Search Engine）。全文索引类引擎是从互联网上提取各个网站的信息（以网页文字为主），建立起数据库，并能检索与用户查询条件相匹配的记录，按一定的排列顺序返回结果。全文索引类引擎是名副其实的搜索引擎，国外有代表性的是Google，国内有百度。根据搜索结果来源的不同，全文搜索引擎可分为两类：一类拥有自己的检索程序（Indexer），俗称“蜘蛛”（Spider）程序或“机器人”（Robot）程序，能自建网页数据库，搜索结果直接从自身的数据库中调用，Google和百度就属于此类；另一类则是租用其他搜索引擎的数据库，并按自定的格式排列搜索结果，如Lycos搜索引擎。目录索引类搜索引擎虽然有搜索功能，但严格意义上不能称为真正的搜索引擎，只是按目录分类的网站链接列表而已。用户完全可以按照分类目录找到所需要的信息，不依靠关键字（Keywords）进行查询。目录索引类搜索引擎中最具代表性的莫过于大名鼎鼎的Yahoo和新浪分类目录搜索。元搜索引擎（META Search Engine）接受用户查询请求后，同时在多个搜索引擎上搜索，并将结果返回给用户。著名的元搜索引擎有InfoSpace、Dogpile、Vivisimo等，中文元搜索引擎中具有代表性的是搜星搜索引擎。在搜索结果排列方面，有的直接按来源排列搜索结果，如Dogpile；有的则按自定的规则将结果重新排列组合，如Vivisimo。在以上三种主要搜索引擎中，全文搜索引擎是应用最广泛的一种，一般所说的搜索引擎指的都是全文搜索引擎。建立索引是搜索引擎核心技术之一，建立索引的目的是能够快速地响应用户的查询。搜索引擎一般由搜索器、所引起、检索器和查询器4个部分组成。各部分的功能如下：1）搜索器在互联网中发现并且取回尽量多的网页信息；2）索引器将搜索器所搜索到的网页信息切分成多个关键字，以关键字作为索引项，用于表示文件以及生成文件库的索引表；3）检索器根据用户的查询在索引库中快速检索文件，进行相关度匹配，对检索到的结果进行排序，返回相应的网页给用户；4）查询器的作用是接纳用户查询，显示查询结果，提供个性化查询项。3.3索引主流技术索引器的好坏直接影响到搜索引擎的质量，索引器从搜索器获取的资源中抽取信息，并建立利于检索的索引表。目前搜索引擎中最流行也最有效的索引方式是倒排文件，先将分词形成的倒排文件组织成索引数据，然后在进行倒排处理。目前主流的索引技术有三种：倒排文件、后缀数组和签名： 倒排索引文件是一种面向单词的索引机制，每个文件都可以用一系列关键字来表示。一个典型的倒排索引主要由词汇表（也叫索引项）和事件表（也叫文件链表）两部分组成。词汇表是用来存放分词词典的，通常称存放词汇表的文件为索引文件；事件表是用来存放这个文件中对应词汇表中词汇出现的位置和次数的，通常称存放出现位置的文件为位置文件。倒排文件的优点是：实现简单，响应时间快，支持复杂查询，适合商用搜索引擎。缺点是：建立索引要消耗很大的磁盘、内存空间；当网页更新后，索引的维护代价也比较大。2倒排文件索引的例子Lucene倒排索引。Lucene是一个高性能的Java全文检索工具包，它使用的是倒排文件索引结构。Lucene是一个开放源代码的全文索引库。经过十多年的发展，Lucene拥有了大量的用户和活跃的开发团队。如果说Google是拥有最多用户访问的搜索引擎网站，那么拥有最多开发人员支持的搜索包也许是Lucene。它最初由Java开发而成，现在有了C#和C+等移植版本。Lucene中的API相对于数据库来说比较灵活，没有类似数据库先定义表结构后使用的过程。如果前后两次写索引时定义的列名称不一样，Lucene会自动创建新的列，所以field的一致性需要我们自己掌握。10 后缀是指从某个位置i 开始到整个串末尾结束的一个特殊子串。字符串S 的从i开头的后缀表示为Suffix(S,i)，也就是Suffix(S,i)=Si.len(S)。关于字符串的大小比较，是指通常所说的“字典顺序”比较，也就是对于两个字符串u、v，令i 从1 开始顺次比较ui和vi，如果ui=vi则令i 加1，否则若uivi则认为uvi则认为uv（也就是vlen(u)或者ilen(v)仍比较出结果，那么若len(u)len(v)则认为ulen(v)则uv。从字符串的大小比较的定义来看，S 的两个开头位置不同的后缀u 和v 进行比较的结果不可能是相等，因为u=v 的必要条件len(u)=len(v)在这里不可能满足。下面我们约定一个字符集和一个字符串S，设len(S)=n，且Sn=$，也就是说S 以一个特殊字符$结尾，并且$小于中的任何一个字符。除了Sn之外，S 中的其他字符都属于。对于约定的字符串S，从位置i 开头的后缀直接写成Suffix(i)，省去参数S。后缀数组SA 是一个一维数组，它保存1.n 的某个排列SA1,SA2,.SAn，并且保证 Suffix(SAi)Suffix(SAi+1),1in。也就是将S 的n 个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入SA中。12作为一种常用的索引组织方式，它在很多领域得到了应用。下面从存储和查询两个阶段对它进行介绍。1）存储阶段：对于每个关键字，分配一个固定大小的向量（k-bit），这个向量叫做签名（Signature）；对于一个网页文件，经过词典切分后，形成由对应关键字序列构成的向量，即P=，对这些关键字的签名做OR运算，就形成了网页文件的签名。这个过程也被称为重叠编码（Superimposed Coding），然后把网页文件的签名结果依次存入一个个独立的文件中，形成对应的签名文件，这样形成的签名文件比原文件小很多。例如：有一页网页分词后有这样一些关键字“文本”、“英语”、“单词”、“信件”，假设将这些关键字经某哈希表散列成固定位的数字向量（以6位为例），分别为hash(文本)=000110，hash(英语)= 110001，hash(单词)= 001101，hash(信件)=000111，这些数字向量即为关键字的签名，然后将这些签名做OR运算，得到网页文件的签名。2）查询阶段：接受用户查询语句A，首先把用户查询串字符串切分成关键字序列，形成查询向量，即A=。然后把关键字映射成相应的向量签名，再与网页签名文件进行按位与运算，得到最后的匹配结果。3）优缺点：签名文件索引方式是一种比较有效的索引机制，文件组织简单，基本和原文件顺序一致；维护容易，生成、插入、删除都很方便；所需空间小，特别是采用重叠编码之后；实现比较简单，更新比较容易；适合并行处理和分布式存储。但是签名向量的大小选择是一个需要研究的问题，而且对于大的文本文件，必须进行分块处理，检索速度慢，需要顺序扫描。后缀数组的方法虽然快，但是其维护困难，代价相当高，不适合做引擎的索引。签名是一种很好的索引方式，但倒排文件的速度和性能已经超过了签名。倒排文件是一种在各大搜索引擎中被主要使用的索引的方式，并且它也是搜索引擎中一个核心的技术。124中文分词技术分词就是将连续德兹序列按照一定的规范重新组合成词序列的过程。搜索引擎技术的研究，国外比中国要早近十年，从最早的Archie，到后来的Excite，以及altvista、overture、google等搜索引擎面世，搜索引擎发展至今，已经有十几年的历史，而国内开始研究搜索引擎是在上世纪末本世纪初。目前在中文搜索引擎领域，国内的搜索引擎已经和国外的搜索引擎效果上相差不远。3之所以能形成这样的局面，有一个重要的原因就在于中文和英文两种语言自身的书写方式不同，在英文中单词之间是以空格作为自然分界符的，如“I am a Chinese”，计算机很容易就把句子分词成为“I，Chinese”，但中文的“我是中国人”， 中文分词技术比英文要复杂得多，计算机不能简单的将句子分词，因此中文分词是一项专门的技术，而计算机将一句话分词的处理过程就是分词算法。现有的分词算法可分为三大类：基于字符串匹配的分词方法（又称机械分词方法）、基于理解的分词方法和基于统计的分词方法。4.1基于字符串匹配的分词方法这种方法又称为机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行区配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短）匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下：1）正向最大匹配法（由左到右的方向）；2）逆向最大匹配法（由右到左的方向）；3）最少切分（使每一句中切出的词数最小）。4这几种分词方法的基本原理相同，基于字符串匹配的分词算法用得很多的是正向最大匹配和逆向最大匹配。其实这两种算法是大同小异的，只不过扫描的方向不同而已，但是逆向匹配的准确率会稍微高一些。据网上的统计数据表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245。最少切分的方法就是在在前两种方法的结果基础上用统计方法找出切出词最小的匹配方法。 1下面是一个小型中文分词器的使用介绍：这个分词器采用的正是使用的机械分词方法，只实现了两个最简单的分词算法：正向最大匹配（FMM）和逆向最大匹配（BMM）。除此之外，分词器还实现了语料训练功能。首先选择分词算法，如图4.1。 图4.1选择分词算法用这个分词器将“他喜欢美丽的鲜花。”分词，最后分词结果是： “他 喜欢 美丽 的 鲜花 。”如图4.2。这个句子的逆向最大匹配分词也是相同的结果。 图4.2输入句子分词器中的训练词典功能：训练语料必须是已经分过词的纯文本文件，文件编码方式为ANSI/ASCII，词与词之间用一个空格分开。训练语料格式可以参考文件“语料示例.txt”训练完成后请选择保存词典将训练好的词典保存到硬盘上。 如图4.3。 图4.3载入训练文件机械分词从切分程度或切分策略上看可以分为部分切分和全切分两种。部分切分只取得输入序列的一种或几种可接受的切分形式，全切分则要求获得所有可接受的切分形式。3由于部分切分忽略了可能的其他切分形式，所以建立在部分切分基础上的分词方法不管采取何种歧义纠正策略，都可能会遗漏正确的切分，造成分次错误或失败。而建立在全切分基础上的分词方法，由于全切分取得了所有可能的切分形式，因为从根本上避免了可能切分形式的遗漏，克服了部分切分方法的缺陷。但最终分词结果的正确和完全性依赖于其一处理方法的选择，如果评测有误，也会造成错误的结果。基于字符串匹配的分词算法都是依赖于词典的，但是不管再怎么大的词典也未必能完全收录所有词汇，况且不断的有新词出现，还有就是人名的识别，因此分词程序如果能够识别出一些词典中所没有的新词的话，有助于提高分词的准确率。54.2基于理解的分词方法这种方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这是一种理想的分词方法,但这类分词方案的算法复杂度高,其有效性与可行性尚需在实际工作中得到进一步的验证。知识分词利用有关词、句子等的句法和语义信息或者从大量语料中找出汉字组词的结合特点来进行评价,以期找到最贴近于原句语义的分词结果。4.3基于统计的分词方法这种方法是基于(两个或多个) 汉字同时出现的概率,通过对语料库(经过处理的大量领域文本的集合)中的文本进行有监督或无监督的学习可以获取该类文本的某些整体特征或规律。如果 能够充分地利用这些统计现象、规律 就可以构造基于语料 库的统计学信息抽取算法统计的分析方法多种多样近来研究的热点主要集中于由随机过程发展而来的理论和方法，其中最重要的是应用隐马尔科夫模型(HMM)进行自然语言处理的方法。隐马尔科夫模型,在语音识别领域已经取得了很好的成效,在信息抽取领域的应用也正在不断的尝试和推广中 。15搜索结果的显示解决了抓取数据、存储副本和建立索引的问题后，剩下的就是接受用户的检索条件并进行处理，将搜索结果显示出来。处理检索条件的基本过程就是从倒排索引总读取关键词对应的记录。至于现实搜索结果的过程，并没有一个统一的算法。可以依据信息发布的时间顺序逆向排列，也可以根据信息被搜索殷勤收录的先后顺序，或者先计算每条记录中关键词出现的频率，然后按照出现频率实现排序等。5.1 PageRank算法著名的Google的成功有许多因素，最重要的是Google对搜索结果的排序比其他搜索引擎都要好。Google保证让绝大部分用搜索的人，都能在搜索结果的第一页就找到他想要的结果。所以Google在没有做任何广告的前提下，让自己成为了全球最大的搜索品牌。Google采用的排序技术叫做PageRank，也就是网页级别。PageRank算法是由Google公司两个创始人Sergey及Larry Page提出的一种搜索引擎排序算法。这个算法是献给每个网页赋予一个PageRank值，那么对于用户查询传粉伺候得到关键字的集合，通过搜索引擎中的索引器，得到一个匹配的网页集合，然后对这个集合中的网页按照PageRank值高低进行排序，把排序高的前面K个网页返回给用户。目前主流搜索引擎一般都会计算这个网页排序值。PageRank是个别网页价值的指示器，透过庞大的连接架构来信赖网站独特的民主性质。简单来说，Google说明网页A连接至网页B时，则是为网页A投给网页B一票。当然，Google会查看票数来源，或链接网页接受的票数；同时它也会分析参与投票的网页。通过“重要的”网页来参与投票，并且帮助其他的网页也成为“重要的”网页数据。PageRank是基于一个这样的假设：从许多优质的网页上连接来的网页，必定也是优质网页。它的特点跟用户的查询过程是不相关的，而跟网页之间的连接结构相关，这个值一般是预先计算好的。通过“重要的”网页来参与投票，并且帮助其他的网页也成为“重要的”网页数据。PageRank是基于这样一个假设：从许多优质的网页上链接过来的网页，必定也是优质网页。它的特点跟用户的查询过程是不相关的，而跟网页之间的链接结构相关，这个值一般是预先计算好的。它赋予每一个网页p一个特定的Rank值，记为PageRank(p)，计算公式为：由此可见，某个网页文件的PageRank值为所有链入该网页的其他网页的PageRank值除以它们各自的链出网页个数（网页出度）的和。A表示所有指向网页p的网页集合，|P|表示网页p的链出网页个数。PageRank(p)的值跟网页p链入网页个数、网页p链入网页的链出网页个数以及网页p链入网页的质量（重要性）这三个因素有关。但由于存在一些出度为0，也就是那些不链接任何其他网页的网页（也称为孤立网页），使得很多网页不能被访问到，因此需要对PageRank矩阵进行修正。基于这样一个假设：一个用户随机地访问网络，该用户到达一个随机网页文件的概率为c，或者随机地沿着一个链接返回到已访问网页文件的概率为1-c，同时假设该用户不会沿着刚才的访问网页链接返回到已访问过的网页文件。2 PageRank算法也有不足之处。因为重要、优质的网站会得到较高的Rank，同时Google会记住每次所处理的查询情况。当然，如果查询出来的网页结果并不符合用户的需求，重要的网页对用户也不具有任何意义。因此，Google将PageRank和精密的内文比对技术结合，来找出重要并且与用户的查询相关的网页。Google会将出现于网页上的字词显示出来，并且检查所有的网页内容（以及连接到此网页的其他网页内容），以决定这样的查询结果是否最符合用户的需求。5.2 HillTop算法HillTop也是一种搜索引擎网页排序算法，是Google的一位工程师Bharat在2001年提出来的。HillTop算法基于这样一个假设：主题相关网页之间的链接对于网页权重计算的贡献优于主题不相关的链接对网页权重计算。该算法的基本思想是：在PageRank基础上，对PageRank计算公式进行改进，在计算网页文件的Rank（重要程度）时，重点计算链接该网页文件的所有网页中跟该网页文件同一主题分类的网页对它的贡献。这种算法跟PageRank算法结合，可以给用户提供更好的排序结果，在一定程度上改进了目前只使用PageRank算法而存在的用户作弊行为，它的缺点是实现起来比较复杂，同时该算法的假设在特定环境下并不成立。6中国搜索引擎市场规模和预测 根据iResearch艾瑞市场咨询2003年中国搜索引擎研究报告的研究数据显示，中国的搜索引擎市场2003年达到了5.2亿元人民币，比2002年的2.3亿一年增长了127%，显示了搜索引擎市场的强劲增长。iResearch研究的搜索引擎市场包括IE地址栏搜索、网站登陆/固