深圳SEO公司
欢迎您光临浏览!

搜索引擎数据规模的估计

深圳SEO在介绍索引系统主要概念后,通过索引数据规模估计的计算方法来体验索引系统设计中必须考虑的数据规模问题,我们首先从齐普夫法则(zipf law)开始说起。

齐普夫法则
齐普夫于1902年l月出生于一个德裔家庭(其祖父在19世纪中叶移居美国),1924年以优异成绩毕业于美国哈佛学院。1925年,齐普夫在德国波恩及柏林学习比较语文学专业。但是以其名字命名的定律却早已走出语言学,进入了信息学、计算机科学、经济学和社会学等众多研究领域,在学术界事有极高的声誉。

简单说来,齐普夫法则可以描述为第k个最经常出现的词,其词频(发生率)与1/k成正比。齐普夫是这样得到这个定律的,首先选用一个有关JamesJoyce Ulysses(不妨理解为一本中等篇幅的书籍)的用词数据,统计不同词汇的出现次数,并按照出现次数排序。他发现了一个惊人的现象,即一个词汇在词频上的排位(rank)乘以其出现的次数惊人地接近于一个常数,而这个常数即书籍的实际总词数260 430,如图5-7所示。
齐普夫法则
词频排名第10的词汇,在书中出现了2 653次,排名和出现次数的乘积为26 530。排名20的词汇,在书中出现了1 311次。排名和出现次数的乘积为26 220,可以看出它们的乘积是十分接近的.如果将其看做相等,得到以下公式:

词频排名
其中occurrence(T)表示词汇T的出现次数,rank(T)表示词汇在全部出现的词汇中词频排序,C为一个常效。上述公式同除以实际总词数(N),则有:回顾一下文档频率的计算,如果一个词汇在文档中出现l次以上,则在计算文档频率时该文档将被计数。文档频率的计算不考虑一个词在文档中出现多少次,而只需要出现即可。例如在4个文档中。“搜索引擎”出现在3个文档中,则“搜索引擎”的文档频率为3/4=0.75。第1个最经常使用的词汇在文档中出现了76次,从期望值的角度看,必定出现在所有的文档中;第2个最经常使用的词汇,在文档中平均出现76/2=38次,同理也几乎必然出现在所有的文档中。因此得出这样的结论,即在字典中词频排名1名一76名的词汇几乎出现在所有的文档中;词频排名77-152的词汇几乎出现在一半的文档中。这不难理解,如果将海量文档两份合为一份计算的话(每个文档的词汇数为2000),用前面方法不难得到词频排名77-152的词汇也是几乎必然出现,粗略地认为出现在一半的文档中。这样我们得到下面的一个关系,如图5-8所示。
词频排名
在图5-8中用6个文档代表全部文档,标“1”表示词汇在文档中出现。可以看出词频排名1-76的词汇出现在全部文档中,词频排名77-152的词汇出现在1/2的文档中,词频排名153-304的词汇出现在1/3的文档中。
对于共计500 000个词汇,则业有500 000/76=6 500这样的块。对于第i块,其出现在n/i个文档中。假定记录每个Docld需要k个字节,第i块(含76个词汇)需要的空间为76 kn/i,这样的块共有6 500个。不妨假设有100亿(10 GB)的网页,每个Docld的评价编码长度为1个字节(这里采用差分序列对Docld压缩编码,实际平均字节数略大于1),例如,在倒排索引中对词频排名为1-76的高频索引词,其倒排索引简化为如图5-9所示。
倒排索引
在图5-9中由于高频索引词(例如T1)几乎出现在所有的文档中,所以其指向的文档列(doclist)几乎为l ,2,3,4,…,,.变为理分序列得到1,1,1,1,…,1。由于序列间距足够小,因此对于大部分高频索引词,其所对应的每个Docid在压缩后所占的空间为一个字节。粗略地计算一下,采用Variable Byte Coding编码方式,小于128的数可用l个字节来表示。对于第1档高频词(共计76个),文档间距(gap)均为1,因此需要1个字节存储文档间距;第2档的高频词《共计76个》,文档间距为2。由于小于128,所以只需要1个字节存储文档间距。依次直到第127档的高频词,均采用1个字节来编码。这样共计127*76=9652个高频词,均用1个字节表示。剩余的低频词出现在极少的文档中。因此可以认为平均每个文档间距的存储接近l个字节。综上,在布尔位索模型下的倒排众引规模为:
布尔位索模型

情况下,我们可以得出这样的经验公式,即1MB的文档大约需要1GB的索引。为100亿(10 GB)网页创建倒排索引(不记录关键词出现的位置信息HitList,只记录是否出现),大约需要10TB(1TB=1024GB》的索引空间。如果还需要存储位置信息( HitList ),则需要的存储代价更加巨大。一般认为包含存储Docld和HitLis信息后,索引的大小依然是IOTB这个数量级。如果按一台100GB硬盘的服务器来计算,至少需要100台以上的服务器来做索引。而且为了一些安全稳定的因素,实际需要的服务器近千台。通过以上计算可以得出,索引主要面临的首要问题是“存得下”。下面我们将通过一些技巧来介绍如何存得下如此多的索引。
词汇T的词频
公式左边表示词汇T的词频,这样就得到了一开始提到的齐普夫定律。即第k个经常出现的词,其词频与1/k成比例,Zipf在(zipf 1949)中提出这是由于语言上的省力原则起作用的结果。有兴趣的读者可以进一步阅读文献(姜望琪2005)了解省力原则的社会学原理。

布尔检索模型下的索引规摸估计

通过学习齐普夫法则,接下来利用这个法则粗略地估计布尔检索棋型下的索引规模,从实践的角度体验一下索引的规模(Stanford IR)。首先,由齐普夫法则。第i个最经常使用词汇的频率和1/i成比率,因此第i个最经常用词汇的频率为c/i。

词频排序
综上,一个词频排序为i的词汇,它的实际词频大约是1/13i。这里的词频排序可以认为是海量数据中的排序,而不是局限于一本书。对于搜索引擎来说,一个词汇的词频就是它在全部网页中出现的实际次数除以全部网页实际出现的词汇数。例如一个词汇只在一个网页中出现,且出现了K次。所有网页为N个,平均每个网页长度为L个词。这样词颇为K/(NxL),文档频率为1/N,注意文档频率和词频在计算上的区别。
布尔检索模型在下一节详细介绍,这里认为一个关键词只记录是否出现在文档中,而不记录其出现的具体位置。即在如图5-6所示的倒排索引中,不考虑NHits和HitLis字段的信息。接下来对倒排索引长度的估计中,默认倒排索引不包含Nits和HitList字段。

在仅符合布尔检索的条件下,对倒排索引的长度进行粗略估计。假定每个文档的平均词汇数为1000,则第i个最经常使用的词汇在文档中期望出现的次数为1000*1/13i=76/i。

回顾一下文档频率的计算,如果一个词汇在文档中出现1次以上,则在计算文档频率时该文档将被计数.文档频率的计算不考虑一个词在文档中出现多少次,而只需要出现即可。例如在4个文档中。“搜索引擎”出现在3个文档中。则“搜索引擎”的文档频率为3/4=0.75,第1个最经常使用的词汇在文档中出现了76次,从期望值的角度看,必定出现在所有的文档中;第2个最经常使用的词汇,在文档中平均出现76/2=38次,同理也几乎必然出现在所有的文档中。因此得出这样的结论,即在字典中词频排名1名一76名的词汇几乎出现在所有的文档中;词频排名77-152的词汇几乎出现在一半的文档中。这不难理解,如果将海量文档两份合为一份计算的话(每个文档的词汇数为2000),用前面方法不难得到词频排名77-152的词汇也是几乎必然出现,粗略地认为出现在一半的文档中。这样我们得到下面的一个关系.如图5-8所示。
计算文档频率

在图5-8中用6个文档代表全部文档。标“1”表示词汇在文档中出现。可以看出词频排名1-76的词汇出现在全部文档中,词频排名77-152的词汇出现在1/2的文档中,词频排名153-304的词汇出现在1/3的文档中。
对于共计500000个词汇,则有500 000/76=6 500这样的块。对于第i块.其出现在n/i个文档中。假定记录每个Docld需要k个字节,第i块(含76个词汇)需要的空间为76kn/i ,这样的块共有6500个。不妨假设有100亿(10GB)的网页,每个Docld的评价编码长度为1个字节(这里采用差分序列对Docld压缩编码,实际平均字节数据略大于1),例如,在倒排索引中对词频排名为1-76的高频索引词,其倒排索引简化为如图5-9所示.

字节数据
在图5-9中由于高频索引词(例如T1)几乎出现在所有的文档中。所以其指向的文档列表(doclist)几乎为l,2,3,4,…,n.变为差分序列得 到1,1,1,1,…,1。由于序列间距足够小,因此对于大部分高频索引词,其所对应的每个Docid在压编后所占的空间为一个字节。粗略地计算一下,采用Variable Byte Coding编码方式,小于128的数可用l个字节来表示。对于第1档高频词(共计76个),文档间距( gap)均为1,因此需要一个字节存储文档间距;第2档的高频词《共计76个》,文档间距为2。由于小于128,所以只需要1个字节存储文档间距。依次直到第127档的高频词,均采用1个字节来编码。这样共计127*76=9652个高频词,均用1个字节表示。剩余的低频词出现在极少的文档中,因此可以认为平均每个文档间距的存储接近l个字节。综上,在布尔检索模型下的倒排众引规模为:
布尔检索模型

情况下,我们可以得出这样的经经公式,即1MB的文档大约需要1GB的索引。为100亿(10 GB)网页创建倒排索引(不记录关键词出现的位置信息HitList,只记录是否出现)。大约需要10TB(1TB-1024GB》的索引空间。如果还需要存储位置信息( HitList ),则需要的存储代价更加巨大。一般认为包含存储Docld和HitList信息后,索引的大小依然是10TB这个数量级。如果按一台100 GB硬盘的服务器来计算,至少需要100台以上的服务器来做索引。而且为了一些安全稳定的因康,实际需要的服务器近千台。通过以上计算可以得出,索引主要面临的首要问题是“存得下”。下面我们将通过一些技巧来介绍如何存得下如此多的索引。

本文出自深圳SEO公司,未经允许不得转载:深圳SEO-微笑SEO服务公司 » 搜索引擎数据规模的估计
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址