Google搜索引擎剖析

唐培和;杨新论;刘浩

【摘 要】详细分析了Google搜索引擎的体系结构、数据结构、索引及其过程搜索步骤,提出了需加强的方面.

【期刊名称】《情报杂志》

【年(卷),期】2004(023)008

【总页数】3页(P88-90)

【关键词】Google 搜索引擎 体系结构 数据结构

【作 者】唐培和;杨新论;刘浩

【作者单位】广西工学院计算机系,柳州,545006;广西工学院计算机系,柳州,545006;广西工学院计算机系,柳州,545006

【正文语种】中 文

【中图分类】教科文艺

G。。gle 搜索引擎剖析唐培和杨新论刘浩 （广西工学院计算机系柳州 545006) 摘 要 详细分析了 Gαigle 搜索引擎的体系结构、数据结构 、 索引及其过程搜索步骤，提出了需加强的方面。关键词Google搜索引擎体系结构数据结构随着因特网的迅猛发展、Web 信息的增加，用户要在信息 海洋里查找信息，就象大海捞针一样，而搜索引擎技术恰好解 决了这一难题。因此，搜索引擎技术正成为计算机工业界和学 术界争相研究、开发的对象。提起搜索，全球网民很少有不知道 Google 的，它拥有多项 创新的技术，并多次为公司夺得业界殊荣。被英国品牌经济公 司lnterbrand 评为 2002 年的“年度品牌”，超越了苹果、可口可 乐以及 IBM 等。目前，在搜索引擎市场，α增e 以 32% 的市场 份额高居第一，雅虎则以 25% 排名第二。如果将所有利用 Gαigle 服务的合作伙伴如雅虎、AOL 和 MSN 计算在内， Gαigle 的市场份额超过了 70% 。 Gαigle 的成功在于迅速地完成了囱.到质的转变，它以其高质量的搜索服务及用户的普遍认可取 得了巨大的成功，已成为互联网行业成功的典范之一。1 Gα:igle 的体系结构搜索引擎根据用户的查询请求，按照一定的算法从索引数 据库中查找相应的信息并返回给用户。为了保证用户查找信 息的精度和新鲜度，搜索引擎儒要建立并维护一个庞大的索引 数据库。 Gα哥拉e 搜索引擎主要由网络蜘蛛、索引（库）与搜索引 擎软件等部分组成，如图 1 所示。圈 1 位吨le ’事禀籁掏·广西自然科学基金资助项目（桂科自∞“006)圆l.1 网络蜘蛛（αawler) 搜索引擎需要定期收集信息。 Gα,gle 定期地（一般是 28 天）派出网络蜘蛛（也称 crawl筐，即 “爬行者”）根据预先设定的 IP 地址范围遍历对应的网页，如果 网页发生变化或者发现新的网页，则获取该网页，传回服务棍， 然后继续沿网络遍历，直至访问完所有的链接。因此，网络蜘 蛛访问页丽的过程就是对互联网上信息遍历的过程。为了保 证网络蜘蛛遍历信息的广度，Gα,gle 事先设定了一些重要的链 接。Gα,gle 可同时运行 3 个 αawler，当服务摞把 URL 列表提 供给 crawler 后，每个 crawler 可同时保持大约 300 个网络连接。 高峰时，通过 crawler,Gα,gle 每秒钟获取的网页可超过 100 个。 影响爬行速度的一个重要因素是 DNS 查询，为此，每个 crawler 都要维护一个自己的 DNS 缓冲。这样每个连接都处于不同的 状态，包括 DNS 查询 3连接主机、发送请求、得到响应。这些因 素综合起来使得 crawler 变成一个非常复杂的系统。 1.2 索引（库）网络蜘蛛将遍历时所获得的页面存放在数据库中。为了提高检索的效率，情要按照一定的规则建立索引。Goe雹le 索引时，采用的是“倒排文件”技水。很显然，如果 索引不能及时更新，网络蜘蛛带回的新信息就不能被使用索引 引擎的用户查到了。也就是说，新信息更新周期等于网络蜘蛛 停止工作的时间加上遍历的时间再加上索引建立的时间。 l.3搜索引擎搜索引擎负责筛选索引库中元数的网页信 息，挑选出符合查询要求的网页，然后对它们进行分级排序，与 查询关键字关联度较大的排在前面，最后把排序后的结果返回 给用户。2 Google 的鼓据结构由于搜索引擎面对的是海量信息，并且用户对检索信息的 速度又很敏感，因此，数据结构和算法的设计就变得非常关键。 为了采用紧凑的数据结构和达到离效的检索能力，Gα划e 在数 据结构方面尽量进行优化，以便用较低的代价实现对大文本集 合进行获取、索引和搜索。另外，由于磁盘存取的速度没有取 得突破性的提高， Gα,gle 就尽量减少对磁盘的操作，显然对数 据结构的设计也有影响。唐培和杨新论刘浩（广西工学院计算机系柳州 545006) 摘要详细分析了 Gαigle 搜索引擎的体系结构、数据结构 、 索引及其过程搜索步骤，提出了需加强的方面。随着因特网的迅猛发展、Web 信息的增加，用户要在信息海洋里查找信息，就象大海捞针一样，而搜索引擎技术恰好解决了这一难题。因此，搜索引擎技术正成为计算机工业界和学术界争相研究、开发的对象。提起搜索，全球网民很少有不知道 Google 的，它拥有多项创新的技术，并多次为公司夺得业界殊荣。被英国品牌经济公司lnterbrand 评为 2002 年的“年度品牌”，超越了苹果、可口可乐以及 IBM 等。目前，在搜索引擎市场，α增e 以 32% 的市场份额高居第一，雅虎则以 25% 排名第二。如果将所有利用Gαigle 服务的合作伙伴如雅虎、AOL 和 MSN 计算在内， Gαigle的市场份额超过了 70% 。 Gαigle 的成功在于迅速地完成了囱.到质的转变，它以其高质量的搜索服务及用户的普遍认可取得了巨大的成功，已成为互联网行业成功的典范之一。搜索引擎根据用户的查询请求，按照一定的算法从索引数据库中查找相应的信息并返回给用户。为了保证用户查找信息的精度和新鲜度，搜索引擎儒要建立并维护一个庞大的索引数据库。 Gα哥拉e 搜索引擎主要由网络蜘蛛、索引（库）与搜索引擎软件等部分组成，如图 1 所示。圈1位吨le ’事禀籁掏网络蜘蛛（αawler) 搜索引擎需要定期收集信息。Gα,gle 定期地（一般是 28 天）派出网络蜘蛛（也称 crawl筐，即“爬行者”）根据预先设定的 IP 地址范围遍历对应的网页，如果网页发生变化或者发现新的网页，则获取该网页，传回服务棍，然后继续沿网络遍历，直至访问完所有的链接。因此，网络蜘蛛访问页丽的过程就是对互联网上信息遍历的过程。为了保证网络蜘蛛遍历信息的广度，Gα,gle 事先设定了一些重要的链接。Gα,gle 可同时运行 3 个 αawler，当服务摞把 URL 列表提供给 crawler 后，每个 crawler 可同时保持大约 300 个网络连接。高峰时，通过 crawler,Gα,gle 每秒钟获取的网页可超过 100 个。影响爬行速度的一个重要因素是 DNS 查询，为此，每个 crawler都要维护一个自己的 DNS 缓冲。这样每个连接都处于不同的状态，包括 DNS 查询 3连接主机、发送请求、得到响应。这些因素综合起来使得 crawler 变成一个非常复杂的系统。1.2 Goe雹le 索引时，采用的是“倒排文件”技水。很显然，如果索引不能及时更新，网络蜘蛛带回的新信息就不能被使用索引引擎的用户查到了。也就是说，新信息更新周期等于网络蜘蛛停止工作的时间加上遍历的时间再加上索引建立的时间。l.3搜索引擎搜索引擎负责筛选索引库中元数的网页信息，挑选出符合查询要求的网页，然后对它们进行分级排序，与查询关键字关联度较大的排在前面，最后把排序后的结果返回给用户。由于搜索引擎面对的是海量信息，并且用户对检索信息的速度又很敏感，因此，数据结构和算法的设计就变得非常关键。为了采用紧凑的数据结构和达到离效的检索能力，Gα划e 在数据结构方面尽量进行优化，以便用较低的代价实现对大文本集合进行获取、索引和搜索。另外，由于磁盘存取的速度没有取得突破性的提高， Gα,gle 就尽量减少对磁盘的操作，显然对数据结构的设计也有影响。2.1 Bigfile 文件系统 在 Gα惠le 中 ， 为了便于对数据的管 理和访问，采用了 Bigfile 文件系统 ， 它是一种基于其他多种文 件系统之上的 、以 64 位整数来存取文件的虚拟文件系统。 Big­ file文件系统能够自动地获知如何在多个文件系统中进行存储 空间分配。 Bigfile 文件系统还直接支持文件的压缩功能。 2.2 信息库 信息库用来存放网络蜘蛛获取的网页 6 在Gα划恒的信息库中包含了每个网页的 ITTML 文档，为节省存储 空间，对每个网页都用 zlib 算法进行了压缩。 之所以采用 zlib 压缩算法，是综合考虑了速度与压缩率的因素，而不是一咪地 追求压缩率。信息库中的文档按照如图 2 所示的格式存放。 | 也ID ｜配呻｜ urllen ｜附1回｜ur1I附 |回2惰息库的’直据篇掏其中，docID 为文档的标识，enrode 表示存放文档时所采用 的编码方式， urll四表示该文档来源的 URL 地址的长度，阿萨 l四表示文档的长度， url 表示文档来源的 URL，阳ge 存放该文 档的内容 。 该结构充分考虑了 ITTML 的特点 ，而且存取方便。 2.3 文本余号r文本索引需要饺照一定的次序来保存每个文挡的信息 ， 以便于信息的查找。 在 Google 中利用了固定长度的ISAM（索引序列访问模式）进行索引，该索引按照 docID 进 行排序。在每个索引条目中包含当前文本的状态、一个指向信 息库的指针、一个文本的检验值和一些统计信息。如果文本已 经被取囚，则该条目还包含指向一个可变长度文件的指针，该 文件包含文本的 URL 和标题：否则 ， 该指针指向一个 URLlist （只包含 URL） 。 这种数据结构可以保证数据的紧凑性和在搜 索过程中能够通过一次查找就能取回记录 。另外，还有一个用来将 URL 转换成 docID 的对照文件。 该文件包含了 URL 校验值和它相应的优ID。 该文件按照 URL 的校验值排序。为了能够方便地根据 URL 找到对应的 cloclD，首先计算该 URL 的校验值，然后根据二分查找法在校 验值文件中查找对应的优IDo 2.4词典在 Google 中，词典全部存放在内存之中，大约占 256M 内存。该词典包含大约 1400 万个词 。 Google 的词典由 两部分组成：一部分是一个通过空格分隔的词表；另一部分是 由指针组成的散列表。示在文档中的位置 。 对于锚采样来说 ， 8 位被分成两部分 ， 其中 4 位表示在锚信息中的位置，另 4 位表示出现该锚信息的文档的优ID 的散列值。普通采样：｜大小写：1字体大小：3 I 位置：12特定采样 g｜大小写：1 I 1｜类型，4 I 位置：8锚21 大小写：1 I1 ｜类型，4 I 散列值，4 I 位置：4困 3 果串串的结构 为了节省存储空间，在前向索引中 ，采样表的长度和 wor­dID 结合起来存放；在倒排序索引中，采样表的长度和 docID 结合起来存放。 2.6 前向余引 前向索引是文档到词的索引 ， 在处理文挡的时候以文档为单位建立这种索引比较方便 。 在 G吨le 中 ，前 肉索引存放在 64 个存储桶中，每个桶容纳一定范围内的 wor­ dID.~日图 4 所示。如果一个文档包含的单词属于某个桶的话， 那么该桶首先记录该文档的 docID，后面跟随 wordID 和对应的 采样表。这种方法将导敦同一个伽ID 出现在不同的桶中，从 而造成一定程度的空间膨胀。这种空间膨胀对于一定数量的 存储桶来说不会太大，但是却可以大大提高索引阶段的效率和 减少编码的复杂性。由于各个桶存放一定范围之内的明rd田， 为节省存储空间，只存储 wordID 相对于该桶中最小明rdID 的 相对值，这种相对值可以用 24 位数据表示 。｜邮DW时哇ID: 24来样的个数2 8来样来样来样来样word!D:24 来样的个数2 8 来样采样采样采样word!D:24 ｜ 邮P W田咀ID,24采样的个数： 8采样采样采样采样word!D,24 采样的个数， B来样采样采样来样w。rd!D, 24 采样的个数a 8 来样 采样采梓采样 空word!D 回 4 前向’l 吉I戴帽绩掏2.7 后向索引 前向索引便于建立，但是在信息查找过程中，是根据词来找文档的，因此为了提高文档检索的速度，必须 建立词到文档的知｜，即后向索引。在 Google 的后向索引中也 包含了与前向索引类似的存储桶，如图 5 所示 。 不同的是后向 索引经过排序处理。对于每个有效的 wordID，词典也包含一个 指向该 wordID 所在桶的指针。 该指针指向一个 cloclD 的列表 2.5 采样农在Gα>gle 中，文档中的每个词对应一个采样 ， 和与该 wordID 相关的采样表。该 clocID 的列表包含所有出现采样包含该词在该文裆中的位置、字体和大小写信息。 采样表 该明，rdID 所对应的词的文挡。在前向和后向索引中占据主要的存储空间 。 因此高效编码D田ID: 27采样的个数， sI 来样 采样来样来样采样采样是必须的。在这里， Google 选择了既节省存储空间，速度又比较快的紧凑编码法。程｜去D。cID: 27DocID,27D四ID: 27 来样的个数， sI 采样来样来样来样采样 来样的个数， sI 来样来样来样来样采样采样 采样的个数： s I 果样采样采样 在紧凑编码法中，每个采样占用两个字节，如图 3 所示 。采样分为特定采样和普通采样 。 特定采样包括出现在 URL、标题 、锚点文本和 Meta 标记中的采样 ， 其他采样统称为 普通采样 。 在普通采样中 ，包含一个大小写位 、3 个字体大小 位和用 12 位表示的文档位置（对于所有超过 4096 的位置都记图 5 后向’E冒l戴揭结构在后向索引中，一个主要的问题是如何对 cloclD 列表中的 doc ID 进行排序。一种方法是简单地按照伽ID 进行排序，该 方法可以与实现多词查询时的 cloclD 列表的合并。 另一种方 成4096） 。字体通过相对表示法（相对其他的文本）表示 ， 占据 法是按照每个文档中该词出现的频率对 clocID 列表进行排序，3位（由于 111 表示该采样为普通采样，因此字体大小只有 7 种 该方法便于单个词的查询 ， 而且在多词查询时很容易在 docID 选择） 。在特定采样中，包含一个大小写位、字体位设为 7 表示 列表的头部找到结果，但却不利于多个 clocID 列表的合并。 该采样为特定采样，用 4 位表示该特定采样的类型，用 8 位表 Google 采取了折中的办法，将后向索引桶分成两类：一个存放． 囱Bigfile 文件系统 在 Gα惠le 中 ， 为了便于对数据的管理和访问，采用了 Bigfile 文件系统 ， 它是一种基于其他多种文件系统之上的 、以 64 位整数来存取文件的虚拟文件系统。 Big­file文件系统能够自动地获知如何在多个文件系统中进行存储空间分配。 Bigfile 文件系统还直接支持文件的压缩功能。.信息库信息库用来存放网络蜘蛛获取的网页 6 在Gα划恒的信息库中包含了每个网页的 ITTML 文档，为节省存储空间，对每个网页都用 zlib 算法进行了压缩。 之所以采用 zlib压缩算法，是综合考虑了速度与压缩率的因素，而不是一咪地追求压缩率。信息库中的文档按照如图 2 所示的格式存放。| 也ID｜配呻｜urllen ur1 I 附回其中，docID 为文档的标识，enrode 表示存放文档时所采用的编码方式， urll四表示该文档来源的 URL 地址的长度，阿萨l四表示文档的长度， url 表示文档来源的 URL，阳ge 存放该文档的内容 。 该结构充分考虑了 ITTML 的特点 ，而且存取方便。2.3 ISAM（索引序列访问模式）进行索引，该索引按照 docID 进行排序。在每个索引条目中包含当前文本的状态、一个指向信息库的指针、一个文本的检验值和一些统计信息。如果文本已经被取囚，则该条目还包含指向一个可变长度文件的指针，该文件包含文本的 URL 和标题：否则 ， 该指针指向一个 URLlist（只包含 URL） 。 这种数据结构可以保证数据的紧凑性和在搜索过程中能够通过一次查找就能取回记录 。另外，还有一个用来将 URL 转换成 docID 的对照文件。该文件包含了 URL 校验值和它相应的优ID。 该文件按照URL 的校验值排序。为了能够方便地根据 URL 找到对应的cloclD，首先计算该 URL 的校验值，然后根据二分查找法在校验值文件中查找对应的优IDo 词典在 Google 中，词典全部存放在内存之中，大约占256M 内存。该词典包含大约 1400 万个词 。 Google 的词典由两部分组成：一部分是一个通过空格分隔的词表；另一部分是由指针组成的散列表。中4位表示在锚信息中的位置，另 4 位表示出现该锚信息的文｜类型，4 I位置：8大小写：1 I 困果串串的结构为了节省存储空间，在前向索引中 ，采样表的长度和 wor­合起来存放。2.6前向余引前向索引是文档到词的索引 ， 在处理文挡的时候以文档为单位建立这种索引比较方便 。 在 G吨le 中 ，前肉索引存放在 64 个存储桶中，每个桶容纳一定范围内的 wor­dID.~日图 4 所示。如果一个文档包含的单词属于某个桶的话，那么该桶首先记录该文档的 docID，后面跟随 wordID 和对应的采样表。这种方法将导敦同一个伽ID 出现在不同的桶中，从而造成一定程度的空间膨胀。这种空间膨胀对于一定数量的存储桶来说不会太大，但是却可以大大提高索引阶段的效率和减少编码的复杂性。由于各个桶存放一定范围之内的明rd田，为节省存储空间，只存储 wordID 相对于该桶中最小明rdID 的相对值，这种相对值可以用 24 位数据表示 。W时哇ID:24 来样来样来样来样word!D:24 word!D:24 ｜邮PW田咀ID,采样的个数： 8 采样采样采样采样word!D,24 来样采样采梓采样空word!D前向’l 吉I戴帽绩掏2.7后向索引前向索引便于建立，但是在信息查找过程中，是根据词来找文档的，因此为了提高文档检索的速度，必须建立词到文档的知｜，即后向索引。在 Google 的后向索引中也包含了与前向索引类似的存储桶，如图 5 所示 。 不同的是后向索引经过排序处理。对于每个有效的 wordID，词典也包含一个指向该 wordID 所在桶的指针。 该指针指向一个 cloclD 的列表2.5 D田ID:27 采样的个数， sI 来样 采样来样来样采样采样D。cID:DocID,27 D四ID:来样的个数， sI 采样来样来样来样采样来样的个数， sI 来样来样来样来样采样采样采样的个数： s I 果样采样采样在紧凑编码法中，每个采样占用两个字节，如图 3 所采样分为特定采样和普通采样 。 特定采样包括出现在URL、标题 、锚点文本和 Meta 标记中的采样 ， 其他采样统称为普通采样 。 在普通采样中 ，包含一个大小写位 、3 个字体大小位和用 12 位表示的文档位置（对于所有超过 4096 的位置都记图5后向’E冒l戴揭结构在后向索引中，一个主要的问题是如何对 cloclD 列表中的doc ID 进行排序。一种方法是简单地按照伽ID 进行排序，该方法可以与实现多词查询时的 cloclD 列表的合并。 另一种方成在特定采样中，包含一个大小写位、字体位设为 7 表示 列表的头部找到结果，但却不利于多个 clocID 列表的合并。该采样为特定采样，用 4 位表示该特定采样的类型，用 8 位表 Google 采取了折中的办法，将后向索引桶分成两类：一个存放．囱标题或者锚信息的采样表，另一个存放所有的采样表。 如果在 第一类桶中没有足够匹配结果的话，再在第二类桶中进行匹 配。2.8 其它方面 与其它搜索引擎相比， G吨le 的信息库中保存了更多的有用信息。每个采样表包含位置、字体和大小写信息 。之外，Google 还利用了 PageRank 技术［4］：如果一个页面 被多次引用，那么这个页面很可能是重要的 ；如果一个页面尽 管没有被多次引用，但却被一个重要的页面引用，那么这个页 面很可能是重要的；一个页面的重要性被均匀并传递到它所引 用的页面。另外， Google 在计算查询串与文档相似度时，还充 分利用了所保存的文档信息，比如对于出在标题、锚点和正文 中的词条均赋予不同的位置的权重，而对于不同的字体大小也 赋予了不同的权重 。 结果表明， PageRank 技术与相似度函数相 综合来对文档进行评价可以获得比较满意的结果 。3 Goc-gle 索引及其过程3.1 Google 索引方法 为了加快信息检索的速度，G吨le 对 信息库建立倒排索引 。在建立倒派索引时，着重考虑了以下几 个方面的问题：a.全文索引 。 Gα冻le 对信息库中的页面建立了全文索引， 并且在建立索引时 ，还同时考虑了超文本的不同标记所表示的 不同含义，如粗体、大字体显示的内容往往比较重要；放在铺链 中的信息往往是它所指向页面的信息的概括 ，所以用它来作为 它所指向的页面的重要信息。 Google 还在建立索引的过程中 收集页面中的超链接，这些超链接反映了收集到的信息之间的 空间结构，利用这些信息可以提高页面相关度判别的准确度 。 b.过滤无用词汇。 网页中存在着许多对信息检索没有什 么实际意义的词汇，如英文中的“a”、“an”、“the”等，以及中文中 的“的”、“啊”等，它们不能明确表达网页的主题信息，因此没有 必要对它们进行索引 。 G吨le 在建立索引时，依据事先保存的 一张无用词汇表，对网页中的元用词汇进行过滤。c.对图像标记的处理。 网页中存在着大量的图像信息，而 图像检索技术目前还不是很成熟。 网页中的图像标记往往存 放着图像的替换信息 ，这些信息对相应的图像有一个基本的描 述。Google 就专门针对这些图像的替换信息建立了索引，以支持某种程度上的图像检索 。3.2 Google 索引过程 Google 具体建立索引的过程，可分为以下三个阶段：a.分析过程。 该过程主要处理文档中可能出现的错误。这些错误包括：错误的 HTML 标记 、 非 ASCII 码字符、标记嵌套层次过深等。b.对文档进行索引 。 经过分析的文档经编码后被存进一 个个存储桶中 。 根据存放在内存中的词典（散列表），文档中的 每个词都被转换成对应的 wordID，然后将它们在文档中的出 现情况转换成采样表，存放于前向桶中 。 我们知道，并行索引 可以提高索引的速度，但并行索引的困难在于索引需要共享同一词典．而由于外来词的存在，索引过程中需要对词典进行一 定的修正 。 在 G吨le 中，先不对外来词汇进行索引，而是把它 们记录在一个日志中，从而实现多个索引器的并行处理，在所 有的索引完成后，再对这些外来词汇建立索引。c.排序过程。 为了生成最后的便于索引的后向索引，需要将前向索引存储中的信息按照 wordID 排序，最后生成标题和 锚点信息的后向桶以及一个全文的后向桶。可以对桶逐个地 进行排序，也可以并行处理，具体视系统资源而定 。 由于一个 桶不能全部存放于内存，Google 就按照明时ID 和 docID 适当地 对桶进行分割，然后进行排序，最后生成后向索引桶。4 Google 搜索步’EGoc-gle 在建立好索引后就可以对用户的查询做出响应，该 响应过程通过搜索过程来实现。搜索的目标就是要为用户提 供高效、高质量的搜索结果 。 在 Go:唱：le 中，搜索过程通过如下 步骤来实现：step!Par曾出e q田町； step2 Convert words into wordlDs;step3 Seekto 出e Stan of 吐、e doclist inthe 址lOrt bon哩l f。r every W四d;step4 ScBll thro.毡h d、e docli凶届四til t阳10isadoc田nent that mate!回 all the 晒rcht臼ms, st叩5 Com阳te 由e rank 。f 出at 企irument forthe 申JCI)';step6If 响 are in the 如，rt barrels and at the end of BllY 也list, seek to the 回art ol 吐，edoclist in the fullb8rrel for every w田-d and go to st，叩 4;st叩7 If 飞回 are notat 吐回 erd of any dochst go to step 4 ; step8 Sort the 仗>ruments 出at h四 matched by =k 阳、d return the t叩 k.为了缩短搜索引擎的响应时间，一旦获得一定数量的匹配 文档后，搜索程序就自动转向 step 8。 也就是说只能返回部分 最优的结果。5 总结Google 的设计与实现确实有很多过人之处，并因此确定了 它牢固的地位。但从发展的角度来看，它也有需要加强的方 面，比如：从页面收集到生成索引之间的时间延迟较长，被检索 信息的时效性尚待改善；信息的“质”会因场合的不同而不同， 不可能像 PageRank 技术所描述的那样一成不变；应考虑增加 智能代理信息过滤和个性化服务；采用分布式体系结构以提高 系统规模和性能 ；用户母语化问题等等 。，考文献Google inc.http.//wwwg,:吨le corn 险inS,P吨！＂ Lη、e Anat西ny of a U事－ Scale H川ierte盯咀l Web S国rch E咱ine.Proc of 7由 World Wide Web 臼u(WWW'98），副如re,A回时ia,19983 徐保文．张卫丰．搜索引擎与信息获取技术．北京．清华大学出版社，20034 曹 军 Google 的 P啡Rank 技术剖析情报杂志 ，2002;(10)李晓明 ．刘建国搜索引擎技术及趋势 http: //www.目－ express.com/,e/se07.hun ｛资篇 ：钩细’自）标题或者锚信息的采样表，另一个存放所有的采样表。 如果在第一类桶中没有足够匹配结果的话，再在第二类桶中进行匹配。2.8其它方面与其它搜索引擎相比， G吨le 的信息库中之外，Google 还利用了 PageRank 技术［4］：如果一个页面被多次引用，那么这个页面很可能是重要的 ；如果一个页面尽管没有被多次引用，但却被一个重要的页面引用，那么这个页面很可能是重要的；一个页面的重要性被均匀并传递到它所引用的页面。另外， Google 在计算查询串与文档相似度时，还充分利用了所保存的文档信息，比如对于出在标题、锚点和正文中的词条均赋予不同的位置的权重，而对于不同的字体大小也赋予了不同的权重 。 结果表明， PageRank 技术与相似度函数相综合来对文档进行评价可以获得比较满意的结果 。Google 索引方法 为了加快信息检索的速度，G吨le 对信息库建立倒排索引 。在建立倒派索引时，着重考虑了以下几个方面的问题：全文索引 。 Gα冻le 对信息库中的页面建立了全文索引，并且在建立索引时 ，还同时考虑了超文本的不同标记所表示的不同含义，如粗体、大字体显示的内容往往比较重要；放在铺链中的信息往往是它所指向页面的信息的概括 ，所以用它来作为它所指向的页面的重要信息。 Google 还在建立索引的过程中收集页面中的超链接，这些超链接反映了收集到的信息之间的空间结构，利用这些信息可以提高页面相关度判别的准确度 。过滤无用词汇。 网页中存在着许多对信息检索没有什么实际意义的词汇，如英文中的“a”、“an”、“the”等，以及中文中的“的”、“啊”等，它们不能明确表达网页的主题信息，因此没有必要对它们进行索引 。 G吨le 在建立索引时，依据事先保存的一张无用词汇表，对网页中的元用词汇进行过滤。对图像标记的处理。 网页中存在着大量的图像信息，而图像检索技术目前还不是很成熟。 网页中的图像标记往往存放着图像的替换信息 ，这些信息对相应的图像有一个基本的描述。a分析过程。 该过程主要处理文档中可能出现的错误。对文档进行索引 。 经过分析的文档经编码后被存进一个个存储桶中 。 根据存放在内存中的词典（散列表），文档中的每个词都被转换成对应的 wordID，然后将它们在文档中的出现情况转换成采样表，存放于前向桶中 。 我们知道，并行索引可以提高索引的速度，但并行索引的困难在于索引需要共享同一词典．而由于外来词的存在，索引过程中需要对词典进行一定的修正 。 在 G吨le 中，先不对外来词汇进行索引，而是把它们记录在一个日志中，从而实现多个索引器的并行处理，在所有的索引完成后，再对这些外来词汇建立索引。c排序过程。 为了生成最后的便于索引的后向索引，需要将前向索引存储中的信息按照 wordID 排序，最后生成标题和锚点信息的后向桶以及一个全文的后向桶。可以对桶逐个地进行排序，也可以并行处理，具体视系统资源而定 。 由于一个桶不能全部存放于内存，Google 就按照明时ID 和 docID 适当地对桶进行分割，然后进行排序，最后生成后向索引桶。Goc-gle 在建立好索引后就可以对用户的查询做出响应，该响应过程通过搜索过程来实现。搜索的目标就是要为用户提供高效、高质量的搜索结果 。 在 Go:唱：le 中，搜索过程通过如下步骤来实现：step!Par曾出e q田町；step2 Convert words into wordlDs; step3 Seekto 出e Stan of 吐、e doclist inthe 址lOrt bon哩l f。r every W四d;t臼ms,st叩5Com阳te 由e rank 。f 出at 企irument forthe 申JCI)';step6If 响 are in the 如，rt barrels and at the end of BllY 也list, seek to the 回art ol doclist in the fullb8rrel for every w田-d and go to st，叩 4;st叩7If飞回arenotat 吐回 erd of any dochst go to step 4 ; step8 Sort the 仗>ruments 出at h四 matched by =k 阳、d return the t叩 k.为了缩短搜索引擎的响应时间，一旦获得一定数量的匹配文档后，搜索程序就自动转向 step 8。 也就是说只能返回部分最优的结果。总结Google 的设计与实现确实有很多过人之处，并因此确定了它牢固的地位。但从发展的角度来看，它也有需要加强的方面，比如：从页面收集到生成索引之间的时间延迟较长，被检索信息的时效性尚待改善；信息的“质”会因场合的不同而不同，不可能像 PageRank 技术所描述的那样一成不变；应考虑增加智能代理信息过滤和个性化服务；采用分布式体系结构以提高系统规模和性能 ；用户母语化问题等等 。Google inc.http.//wwwg,:吨le corn 险inS,P吨！＂ Lη、e Anat西ny of a U事－ Scale H川ierte盯咀l Web S国rch E咱ine.Proc of 7由 World Wide Web 臼u(WWW'98），副如re,A回时ia,1998 曹军 Google 的 P啡Rank 技术剖析情报杂志 ，2002;(10)