4.4 Web索引分析
- G% R9 ?+ D. k+ w2 ]
! A- e. C0 U( ?( S' b/ t8 J* ~任何运行在整个Web上的分析器必须能够处理可能包含错误的大型集合。范围从HTML标记到标记之间几K字节的0,非ASCII字符,几百层HTML标记的嵌套,各种各样令人难以想象的错误。为了获得最大的速度,我们没有采用YACC产生上下文无关文法CFG分析器,而是采用灵活的方式产生词汇分析器,它自己配有堆栈。分析器的改进大大提高了运行速度,它的精力如此充沛完成了大量工作。把文档装入barrel建立索引—分析完一篇文档,之后把该文档装入barrel中,用内存中的hash表—字典,每个词汇被转换成一个wordID。当hash表字典中加入新的项时,笨拙地存入文件。一旦词汇被转换成wordID,它们在当前文档的出现就转换成hitlist,被写进正向barrel。索引阶段并行的主要困难是字典需要共享。% v3 ?6 W: U+ b) j4 A1 u$ p' y
/ }$ @/ H, d7 R! I. M" h6 ]我们采用的方法是,基本字典中有140万个固定词汇,不在基本字典中的词汇写入日志,而不是共享字典。这种方法多个索引器可以并行工作,最后一个索引器只需处理一个较小的额外词汇日志。排序—为了建立反向索引,排序器读取每个正向barrel,以wordID排序,建立只有标题anchor hi t的反向索引barrel和全文反向索引barrel。这个过程一次只处理一个barrel,所以只需要少量暂存空间。排序阶段也是并行的,我们简单地同时运行尽可能多的排序器,不同的排序器处理不同的桶。由于barrel不适合装入主存,排序器进一步依据wordID和docID把它分成若干篮子,以便适合装入主存。然后排序器把每个篮子装入主存进行排序,并把它的内容写回到短反向barrel和全文反向barrel。
* a1 I6 y! I% e7 D+ E7 J' w7 Q* z- {5 u% W0 x5 }3 D$ f
4.5搜索
" U2 X* ]5 p3 K0 k4 O ?- f
$ @6 a; m2 B- o, h( p: B1 j6 K- s搜索的目标是提供有效的高质量的搜索结果。多数大型商业搜索引擎好像在效率方面花费了很大力气。因此我们的研究以搜索质量为重点,相信我们的解决方案也可以用到那些商业系统中。* \5 Z$ w+ A7 N$ V5 p( E
Google查询评价过程见图4。
2 i1 M7 S# F( D- z9 t
* J3 Y5 a, Z7 J: n% o# y1. 分析查询。 0 B0 Y! x* k/ d8 {$ |( H- J) w" q
2. 把词汇转换成wordID。
8 A+ M9 z/ P, l% y- c3. 在短barrel中查找每个词汇doclist的开头。& [6 |7 S8 }) ]8 P0 [
4. 扫描doclist直到找到一篇匹配所有关键词的文档
( A5 u# D& O4 m% S* V9 t5. 计算该文档的rank
5 S3 e9 {! T* ^0 [ Q& ]- }6. 如果我们在短barrel,并且在所有doclist的末尾,开始从全文barrel的doclist的开头查找每个词,goto 第四步
& P8 X/ L' m/ ~8 J- Y' ?+ Y0 C0 q: R7. 如果不在任何doclist的结尾,返回第四步。
* T$ Z3 j* Q2 C P. r8. 根据rank排序匹配文档,返回前k个。图4 Google查询评价在有限的响应时间内,一旦找到一定数量的匹配文档,搜索引擎自动执行步骤8。这意味着,返回的结果是子优化的。我们现在研究其它方法来解决这个问题。过去根据PageRank排序hit,看来能够改进这种状况。
8 i) \- W% y4 A- W: W/ \( A Y# ^$ H' M1 \
- P1 [, L4 ]. k# r. g6 E4.5.1 Ranking系统 : w; ]8 K' a" X, b0 w: T+ X. D, f
! ]& ^- e8 N& W3 A# X) W
Google比典型搜索引擎保存了更多的web信息。每个hitlist包括位置,字号,大小写。另外,我们还考虑了链接描述文字。Rank综合所有这些信息是困难的。ranking函数设计依据是没有某个因素对rank影响重大。首先,考虑最简单的情况—单个词查询。为了单个词查询中一个文档的rank,Goole在文档的hitlist中查找该词。Google认为每个hit是几种不同类型(标题,链接描述文字anchor,URL,普通大字号文本,普通小字号文本,……)之一,每种有它自己的类型权重。类型权重建立了一个类型索引向量。Google计算hitlist中每种hit的数量。然后每个hit数转换成count-weight。Count-weight开始随hit数线性增加,很快逐渐停止,以至于hit数与此不相关。我们计算count-weight向量和type-weight向量的标量积作为文档的IR值。最后IR值结合PageRank作为文档的最后rank。 对于多词查询,更复杂些。现在,多词hitlist必须同时扫描,以便关键词出现在同一文档中的权重比分别出现时高。相邻词的hit一起匹配。对每个匹配hit 的集合计算相邻度。相邻度基于hit在文档中的距离,分成10个不同的bin值,范围从短语匹配到根本不相关。不仅计算每类hit数,而且要计算每种类型的相邻度,每个类型相似度对,有一个类型相邻度权type-prox-weight。Count转换成count-weight,计算count-weight、 type-prox-weight的标量积作为IR值。应用某种debug mode所有这些数和矩阵与查询结果一起显示出来。这些显示有助于改进rank系统。
5 C0 X% r3 u8 ^) x ~. S1 F/ e
; f% d- T* j" h6 i* X0 ], y; e4.5.2 反馈 * s3 T1 t) o) u0 ?$ O5 i S) }4 @, a2 M, o
8 H& @3 B' `- _$ Drank函数有很多参数象type-weight和type-prox-weight。指明这些参数的正确值有点黑色艺术black art。为此,我们的搜索引擎有一个用户反馈机制。值得信任的用户可以随意地评价返回的结果。保存反馈。然后,当修改rank函数时,对比以前搜索的rank,我们可以看到修改带来的的影响。虽然不是十全十美,但是它给出了一些思路,当rank函数改变时对搜索结果的影响。
% p7 z& P% s- o8 d2 M0 K7 o6 U% s- D' d4 ^0 s2 w2 [
5 执行和结果
: G$ |3 a# U; t- ~7 L& Y; }9 }, `# c) A& N& z
搜索结果的质量是搜索引擎最重要的度量标准。完全用户评价体系超出了本文的论述范围,对于大多数搜索,我们的经验说明Google的搜索结果比那些主要的商业搜索引擎好。作为一个应用PageRank,链接描述文字,相邻度的例子,图4给出了Google搜索bill Clinton的结果。它说明了Google的一些特点。服务器对结果进行聚类。这对过滤结果集合相当有帮助。这个查询,相当一部分结果来自whitehouse.gov域,这正是我们所需要的。现在大多数商业搜索引擎不会返回任何来自whitehouse.gov的结果,这是相当不对的。注意第一个搜索结果没有标题。因为它不是被抓到的。Google是根据链接描述文字决定它是一个好的查询结果。同样地,第五个结果是一个Email地址,当然是不可能抓到的。也是链接描述文字的结果。所有这些结果质量都很高,最后检查没有死链接。因为它们中的大部分PageRank值较高。PageRank百分比用红色线条表示。没有结果只含Bill没有Clinton或只含Clinton没有Bill。因为词出现的相近性非常重要。当然搜索引擎质量的真实测试包含广泛的用户学习或结果分析,此处篇幅有限,请读者自己去体验Google,http://google.stanford.edu/。 9 m( w8 e1 g4 H4 K# Y
$ M% {5 J9 z8 I' ~! D2 i0 R1 t2 n5.1存储需求& J. a: R8 N( e) n1 B" {
3 a+ z4 A% n/ d) c( G
除了搜索质量,Google的设计可以随着Web规模的增大而有效地增大成本。一方面有效地利用存储空间。表1列出了一些统计数字的明细表和Google存储的需求。由于压缩技术的应用知识库只需53GB的存储空间。是所有要存储数据的三分之一。按当今磁盘价格,知识库相对于有用的数据来说比较便宜。搜索引擎需要的所有数据的存储空间大约55GB。大多数查询请求只需要短反向索引。文件索引应用先进的编码和压缩技术,一个高质量的搜索引擎可以运行在7GB的新PC。
4 X& Q" u" H6 `5 |2 A* D6 x! l% H
! h2 y7 d+ J0 C5 k5.2 系统执行
w" s; E1 r& p. t" u |* I+ a1 }& y7 [: ?% E+ [1 P( P+ e" b4 m
搜索引擎抓网页和建立索引的效率非常重要。Google的主要操作是抓网页,索引,排序。很难测试抓全部网页需要多少时间,因为磁盘满了,域名服务器崩溃,或者其它问题导致系统停止。总的来说,大约需要9天时间下载26000000网页(包括错误)。然而,一旦系统运行顺利,速度非常快,下载最后11000000网页只需要63小时,平均每天4000000网页,每秒48.5个网页。索引器和网络爬行机器人同步运行。索引器比网络爬行机器人快。因为我们花费了大量时间优化索引器,使它不是瓶颈。这些优化包括批量更新文档索引,本地磁盘数据结构的安排。索引器每秒处理54个网页。排序器完全并行,用4台机器,排序的整个过程大概需要24小时。( k# j. }% Y8 v3 ^; J' Z! g
& u: L8 y, X! U& h R/ P2 n- e5.3搜索执行改进3 c7 E# K; c- v+ ^" |; w& X
5 B. E! s6 t; B
搜索执行不是我们研究的重点。当前版本的Google可以在1到10秒间回答查询请求。时间大部分花费在NFS磁盘IO上(由于磁盘普遍比机器慢)。进一步说,Google没有做任何优化,例如查询缓冲区,常用词汇子索引,和其它常用的优化技术。我们倾向于通过分布式,硬件,软件,和算法的改进来提高Google的速度。我们的目标是每秒能处理几百个请求。表2有几个现在版本Google响应查询时间的例子。它们说明IO缓冲区对再次搜索速度的影响。
. i1 |+ y/ H! O) F+ O, ]) `% {* G; G* f
6 结论: z2 _" h7 I- @: x9 l
$ Y% r; S' L! r
Google设计成可伸缩的搜索引擎。主要目标是在快速发展的World Wide Web上提供高质量的搜索结果。Google应用了一些技术改进搜索质量包括PageRank,链接描述文字,相邻信息。进一步说,Google是一个收集网页,建立索引,执行搜索请求的完整的体系结构。
, ^+ N: L0 Q K% @% V+ Y% C, Q& j( @
6.1 未来的工作2 d4 Z4 P; L" z- {; ?5 c! J9 ^% r
+ i) v. J: N" ]8 \4 D7 D2 }大型Web搜索引擎是个复杂的系统,还有很多事情要做。我们直接的目标是提高搜索效率,覆盖大约100000000个网页。一些简单的改进提高了效率包括请求缓冲区,巧妙地分配磁盘空间,子索引。另一个需要研究的领域是更新。我们必须有一个巧妙的算法来决定哪些旧网页需要重新抓取,哪些新网页需要被抓取。这个目标已经由实现了。受需求驱动,用代理cache创建搜索数据库是一个有前途的研究领域。我们计划加一些简单的已经被商业搜索引擎支持的特征,例如布尔算术符号,否定,填充。然而另外一些应用刚刚开始探索,例如相关反馈,聚类(Google现在支持简单的基于主机名的聚类)。我们还计划支持用户上下文(象用户地址),结果摘要。我们正在扩大链接结构和链接文本的应用。简单的实验证明,通过增加用户主页的权重或书签,PageRank可以个性化。对于链接文本,我们正在试验用链接周围的文本加入到链接文本。Web搜索引擎提供了丰富的研究课题。如此之多以至于我们不能在此一一列举,因此在不久的将来,我们希望所做的工作不止本节提到的。+ ^& ^7 ?! |1 ?6 y+ f$ }) H
: P& s$ e& ]5 ]4 F) G
6.2 高质量搜索
. i9 T! S* Z: d
- V) l9 I, Z" ?+ v; `( D! B/ ?: k当今Web搜索引擎用户所面临的最大问题是搜索结果的质量。结果常常是好笑的,并且超出用户的眼界,他们常常灰心丧气浪费了宝贵的时间。例如,一个最流行的商业搜索引擎搜索“Bill Clillton”的结果是the Bill Clinton Joke of the Day: April 14, 1997。Google的 设计目标是随着Web的快速发展提供高质量的搜索结果,容易找到信息。为此,Google大量应用超文本信息包括链接结构和链接文本。Google还用到了相邻性和字号信息。评价搜索引擎是困难的,我们主观地发现Google的搜索质量比当今商业搜索引擎高。通过PageRank分析链接结构使Google能够评价网页的质量。用链接文本描述链接所指向的网页有助于搜索引擎返回相关的结果(某种程度上提高了质量)。最后,利用相邻性信息大大提高了很多搜索的相关性。 / |0 m; B, E/ t/ \ L) h+ d
( L. L5 r. {6 O$ W
6.3可升级的体系结构8 a# w' ^ q# |# h( F
) O# N8 L a& m
除了搜索质量,Google设计成可升级的。空间和时间必须高效,处理整个Web时固定的几个因素非常重要。实现Google系统,CPU、访存、内存容量、磁盘寻道时间、磁盘吞吐量、磁盘容量、网络IO都是瓶颈。在一些操作中,已经改进的Google克服了一些瓶颈。Google的主要数据结构能够有效利用存储空间。进一步,网页爬行,索引,排序已经足够建立大部分web索引,共24000000个网页,用时不到一星期。我们希望能在一个月内建立100000000网页的索引。 3 Q5 j$ R$ D! O. p
/ k/ D- W6 i! v" J0 h; F6.4 研究工具$ T5 Z) {) c0 A' f/ q( s4 Y
6 V3 T) f. ]0 Q+ R1 C$ r5 Q
Google不仅是高质量的搜索引擎,它还是研究工具。Google搜集的数据已经用在许多其它论文中,提交给学术会议和许多其它方式。最近的研究,例如,提出了Web查询的局限性,不需要网络就可以回答。这说明Google不仅是重要的研究工具,而且必不可少,应用广泛。我们希望Google是全世界研究者的资源,带动搜索引擎技术的更新换代。 2 v1 E+ ~2 |" X# f
+ p, _& R9 I8 r8 E3 |* q# w$ X5 R7 m7、致谢
/ P2 H! i( k8 T1 C2 y, T5 F, q" }- e6 C
Scott Hassan and Alan Steremberg评价了Google的改进。他们的才智无可替代,作者由衷地感谢他们。感谢Hector Garcia-Molina, Rajeev Motwani, Jeff Ullman, and Terry Winograd和全部WebBase开发组的支持和富有深刻见解的讨论。最后感谢IBM,Intel,Sun和投资者的慷慨支持,为我们提供设备。这里所描述的研究是Stanford综合数字图书馆计划的一部分,由国家科学自然基金支持,合作协议号IRI-9411306。DARPA ,NASA,Interva研究,Stanford数字图书馆计划的工业合作伙伴也为这项合作协议提供了资金。' ?, ?3 s2 W: V; R' B6 D7 w
A. _& A" b" |
参考文献。0 m9 L& f- I* u5 [
' d' r% J; o% ^4 q q
Best of the Web 1994 -- Navigators http://botw.org/1994/awards/navigators.html ! ]9 [7 y+ i. [% o1 u" `/ P3 n
Bill Clinton Joke of the Day: April 14, 1997. http://www.io.com/~cjburke/clinton/970414.html.
3 u4 L0 i+ N" f' J$ |: c4 C3 c/ @Bzip2 Homepage http://www.muraroa.demon.co.uk/
1 s; ]4 d. N! d8 R: _Google Search Engine http://google.stanford.edu/
0 H& r7 |6 G# h4 P# T' iHarvest http://harvest.transarc.com/
4 A5 `! m$ w t& {; f$ _, _Mauldin, Michael L. Lycos Design Choices in an Internet Search Service, IEEE Expert Interview http://www.computer.org/pubs/expert/1997/trends/x1008/mauldin.htm
4 n, u* ~0 G2 d0 x' ]% BThe Effect of Cellular Phone Use Upon Driver Attention http://www.webfirst.com/aaa/text/cell/cell0toc.htm
& _ H# P( w- }% r7 N2 TSearch Engine Watch http://www.searchenginewatch.com/ . C; U: A1 [) o$ r5 W8 ^1 U( `! c, Z
RFC 1950 (zlib) ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html
( I7 x& f U/ URobots Exclusion Protocol: http://info.webcrawler.com/mak/projects/robots/exclusion.htm T9 F5 W6 c; D, \6 i8 g6 A, W( y
Web Growth Summary: http://www.mit.edu/people/mkgray/net/web-growth-summary.html
9 L ^4 r2 T$ D3 ~Yahoo! http://www.yahoo.com/ 8 @- P$ |/ O) E! W8 q5 F/ w& U
[Abiteboul 97] Serge Abiteboul and Victor Vianu, Queries and Computation on the Web. Proceedings of the International Conference on Database Theory. Delphi, Greece 1997. : T6 v y4 E% \, C4 K4 \* g0 p) Q
[Bagdikian 97] Ben H. Bagdikian. The Media Monopoly. 5th Edition. Publisher: Beacon, ISBN: 0807061557
. L8 s3 R+ K! P* a" E[Chakrabarti 98] S.Chakrabarti, B.Dom, D.Gibson, J.Kleinberg, P. Raghavan and S. Rajagopalan. Automatic Resource Compilation by Analyzing Hyperlink Structure and Associated Text. Seventh International Web Conference (WWW 98). Brisbane, Australia, April 14-18, 1998.
8 z4 R# C6 I$ d* v2 k5 w[Cho 98] Junghoo Cho, Hector Garcia-Molina, Lawrence Page. Efficient Crawling Through URL Ordering. Seventh International Web Conference (WWW 98). Brisbane, Australia, April 14-18, 1998.
u) g- R e) s4 p0 U6 B3 @0 `4 U[Gravano 94] Luis Gravano, Hector Garcia-Molina, and A. Tomasic. The Effectiveness of GlOSS for the Text-Database Discovery Problem. Proc. of the 1994 ACM SIGMOD International Conference On Management Of Data, 1994.
7 Q5 f" ~& Q+ S' c[Kleinberg 98] Jon Kleinberg, Authoritative Sources in a Hyperlinked Environment, Proc. ACM-SIAM Symposium on Discrete Algorithms, 1998. ; e' s) |+ {/ K* u3 w/ [
[Marchiori 97] Massimo Marchiori. The Quest for Correct Information on the Web: Hyper Search Engines. The Sixth International WWW Conference (WWW 97). Santa Clara, USA, April 7-11, 1997. 7 S e+ B: u/ j! B I% |! A: W
[McBryan 94] Oliver A. McBryan. GENVL and WWWW: Tools for Taming the Web. First International Conference on the World Wide Web. CERN, Geneva (Switzerland), May 25-26-27 1994. http://www.cs.colorado.edu/home/mcbryan/mypapers/www94.ps
% P# r& Y) }5 A, S( d8 Z7 `[Page 98] Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd. The PageRank Citation Ranking: Bringing Order to the Web. Manuscript in progress. http://google.stanford.edu/~backrub/pageranksub.ps
( {) `4 G' r+ A/ O. f4 }[Pinkerton 94] Brian Pinkerton, Finding What People Want: Experiences with the WebCrawler. The Second International WWW Conference Chicago, USA, October 17-20, 1994. http://info.webcrawler.com/bp/WWW94.html 9 v7 z7 B) N. v! U) \
[Spertus 97] Ellen Spertus. ParaSite: Mining Structural Information on the Web. The Sixth International WWW Conference (WWW 97). Santa Clara, USA, April 7-11, 1997.
2 s; g" `+ U$ X3 N* r C. \[TREC 96] Proceedings of the fifth Text REtrieval Conference (TREC-5). Gaithersburg, Maryland, November 20-22, 1996. Publisher: Department of Commerce, National Institute of Standards and Technology. Editors: D. K. Harman and E. M. Voorhees. Full text at: http://trec.nist.gov/
4 H2 ]6 C% d; b [1 h: V6 g$ v[Witten 94] Ian H Witten, Alistair Moffat, and Timothy C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images. New York: Van Nostrand Reinhold, 1994.
# a* K8 G3 C+ A* z/ f[Weiss 96] Ron Weiss, Bienvenido Velez, Mark A. Sheldon, Chanathip Manprempre, Peter Szilagyi, Andrzej Duda, and David K. Gifford. HyPursuit: A Hierarchical Network Search Engine that Exploits Content-Link Hypertext Clustering. Proceedings of the 7th ACM Conference on Hypertext. New York, 1996.
& m" ^& L/ G3 ^8 M
1 L/ G6 ]. ]8 M" P7 s! M图1 Google系统的工作流程图2 ^# c% _9 q) } e9 N1 ~1 z2 `
(注:原图来自Sergey Brin and Lawrence Page, The Anatomy of a Large-Scale Hypertextual. Web Search Engine, 1998.http://www-db.stanford.edu/%7Ebackrub/Google.html)
. H+ @7 ?% a8 E- x
) p5 J$ z3 F4 N; [1 v①Google使用高速的分布式爬行器(Crawler)系统中的漫游遍历器(Googlebot)定时地遍历网页,将遍历到的网页送到存储服务器(Store Server)中。% F; f/ `1 C; R# {( J2 z# g/ ]" r
②存储服务器使用zlib格式压缩软件将这些网页进行无损压缩处理后存入数据库Repository中。Repository获得了每个网页的完全Html代码后,对其压缩后的网页及URL进行分析,记录下网页长度、URL、URL长度和网页内容,并赋予每个网页一个文档号(docID),以便当系统出现故障的时候,可以及时完整地进行网页的数据恢复。
3 ?. o; Q! R9 j: a* ?③索引器(Indexer)从Repository中读取数据,以后做以下四步工作:- {: L8 W& Y) O _1 o
④(a)将读取的数据解压缩后进行分析,它将网页中每个有意义的词进行统计后,转化为关键词(wordID)的若干索引项(Hits),生成索引项列表,该列表包括关键词、关键词的位置、关键词的大小和大小写状态等。索引项列表被存入到数据桶(Barrels)中,并生成以文档号(docID)部分排序的顺排档索引。
1 o# O' d2 c4 `3 V
$ j' ?% Y: A3 A- F6 q+ K索引项根据其重要程度分为两种:当索引项中的关键词出现在URL、标题、锚文本(Anchor Text)和标签中时,表示该索引项比较重要,称为特殊索引项(Fancy Hits);其余情况则称为普通索引项(Plain Hits)。在系统中每个Hit用两个字节(byte)存储结构表示:特殊索引项用1位(bit)表示大小写,用二进制代码111(占3位)表示是特殊索引项,其余12位有4位表示特殊索引项的类型(即hit是出现在URL、标题、链接结点还是标签中),剩下8位表示hit在网页中的具体位置;普通索引项是用1位表示大小写,3位表示字体大小,其余12位表示在网页中的具体位置。
4 Z: S7 A8 r' y; Q顺排档索引和Hit的存储结构如图3所示。5 S2 L8 C2 O- |4 D/ P
1 P" }$ r- g' j' l) W) K
& M q6 k/ e5 ^, d* B) J/ H
图3 顺排档索引和Hit的存储结构
& F: q* g. a! A$ O l
+ h* G+ @' n; I值得注意的是,当特殊索引项来自Anchor Text时,特殊索引项用来表示位置的信息(8位)将分为两部分:4位表示Anchor Text出现的具体位置,另4位则用来与表示Anchor Text所链接网页的docID相连接,这个docID是由URL Resolver经过转化存入顺排档索引的。& Q' r% E% K4 n' N0 d
(b)索引器除了对网页中有意义的词进行分析外,还分析网页的所有超文本链接,将其Anchor Text、URL指向等关键信息存入到Anchor文档库中。
" T6 }% J% y$ e/ |9 `1 Y(c)索引器生成一个索引词表(Lexicon),它包括两个部分:关键词的列表和指针列表,用于倒排档文档相连接(如图3所示)。
) c( _% [1 u* E& d) w' L! o(d)索引器还将分析过的网页编排成一个与Repository相连接的文档索引(Document Index),并记录下网页的URL和标题,以便可以准确查找出在Repository中存储的原网页内容。而且把没有分析的网页传给URL Server,以便在下一次工作流程中进行索引分析。7 D9 r7 T3 W% b/ b/ p8 U
⑤URL分析器(URL Resolver)读取Anchor文档中的信息,然后做⑥中的工作。- O, Q0 o, @& ~, P
⑥(a)将其锚文本(Anchor Text)所指向的URL转换成网页的docID;(b)将该docID与原网页的docID形成“链接对”,存入Link数据库中;(c)将Anchor Text指向的网页的docID与顺排档特殊索引项Anchor Hits相连接。
8 \* a( q# |3 M) F⑦数据库Link记录了网页的链接关系,用来计算网页的PageRank值。
# k, i e+ J2 d) z# R0 C, X7 r⑧文档索引(Document Index)把没有进行索引分析的网页传递给URL Server,URL Server则向Crawler提供待遍历的URL,这样,这些未被索引的网页在下一次工作流程中将被索引分析。
w. M3 s/ d6 I8 d+ b⑨排序器(Sorter)对数据桶(Barrels)的顺排档索引重新进行排序,生成以关键词(wordID)为索引的倒排档索引。倒排档索引结构如图4所示:
# \; ^/ N9 P) N9 O1 G. ?# S" \$ T( C* w0 q. `1 |5 O0 c0 e
图4 倒排档索引结构
2 a, Q7 v' g+ G. |3 O6 ^. N⑩将生成的倒排档索引与先前由索引器产生的索引词表(Lexicon)相连接产生一个新的索引词表供搜索器(Searcher)使用。搜索器的功能是由网页服务器实现的,根据新产生的索引词表结合上述的文档索引(Document Index)和Link数据库计算的网页PageRank值来匹配检索。2 Y* ?4 x5 E" y% r: ?
在执行检索时,Google通常遵循以下步骤(以下所指的是单个检索词的情况):% i" p% i9 @% o" g s- m
(1)将检索词转化成相应的wordID;( U/ n+ V# g& t* t0 A
(2)利用Lexicon,检索出包含该wordID的网页的docID;4 S1 M8 N) f. o' U
(3)根据与Lexicon相连的倒排档索引,分析各网页中的相关索引项的情况,计算各网页和检索词的匹配程度,必要时调用顺排档索引;
0 Y6 a. e; B" E(4)根据各网页的匹配程度,结合根据Link产生的相应网页的PageRank情况,对检索结果进行排序;
" V" q3 F8 \" l/ s8 t* K(5)调用Document Index中的docID及其相应的URL,将排序结果生成检索结果的最终列表,提供给检索用户。' b- y: _* e" j$ ~3 D- r+ r
用户检索包含多个检索词的情况与以上单个检索词的情况类似:先做单个检索词的检索,然后根据检索式中检索符号的要求进行必要的布尔操作或其他操作。5 N" S& J4 K: C7 {: Y7 c
& j% N; q) r/ g. Z( LFrom: http://www-db.stanford.edu/%7Ebackrub/google.html zhihere.com整理 2005-8-21 |