索引系统-数据规模的估计

2019-12-12 10:39:56  浏览:221  作者:老王

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

  齐普夫法则


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

  简单说来,齐普夫法则可以描述为第k个最经常出现的词其词频(发生率)与1k成正比。

  齐普夫是这样得到这个定律的,首先选用一个有关 JamesJoyce Ulysses(不妨理解为一本中等篇幅的书籍)的用词数据,统计不同词汇的出现次数,并按照出现次数排序。他发现了一个惊人的现象,即一个词汇在词频上的排位(rank)乘以其出现的次数惊人地接近于一个常数,而这个常数即书籍的实际总词数260 430,如图5-7所示。

索引系统-数据规模的估计

  词频排名第10的词汇,在书中出现了2653次,排名和出现次数的乘积为26530。排名20的词汇,在书中出现了1311次。排名和出现次数的乘积为26220,可以看出它们的乘积是十分接近的。如果将其看做相等,得到以下公式:

图片.png

  其中 occurrence(表示词汇T的出现次数,rank(T)表示词汇在全部出现的词汇中词频排序,C为一个常数。上述公式同除以实际总词数(N),则有:

图片.png

  公式左边表示词汇T的词频,这样就得到了一开始提到的齐普夫定律。即第k个经常出现的词,其词频与1/k成比例,Zipf在 zipf1949]中提出这是由于语言上的省力原则起作用的结果。有兴趣的读者可以进一步阅读文献[姜望琪2005]了解省力原则的社会学原理。

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


  通过学习齐普夫法则,接下来利用这个法则粗略地估计布尔检索模型下的索引规模,从实践的角度体验一下索引的规模[ Stanford Ir]。

  首先,由齐普夫法则,第i个最经常使用词汇的频率和1i成比率,因此第i个最经常用词汇的频率为cli。

  接着,假定全部汉语词汇数目为50万,因此有∑C=1这不难理解在全世界所有中文书籍中取出50万个互不相同的词汇,并统计全部中文书籍的实际总词数。然后分别计算这50万的词汇各自出现的数目,用数目除以总词数即得到词频。这50万词汇的词频总和可以看做分母(总词数)不变,分子(各自出现的次数)相加。分子之和恰好为总词数,因此除的结果为1。

  在数学上,称图片.png为“调和级数”因此图片.png

  可以简化为:

  

图片.png

  调和级数的计算公式为:

  

图片.png

  这个常数c通过计算得到c=1/13。

  综上,一个词频排序为i的词汇,它的实际词频大约是1/13i这里的词频排序可以认为是海量数据中的排序,而不是局限于本书。对于搜索引擎来说,一个词汇的词频就是它在全部网页中出现的实际次数除以全部网页实际出现的词汇数。例如一个词汇只在一个网页中出现,且出现了K次。所有网页为N个,平均每个网页长度为L个词。这样词频为K/(NxL),文档频率为1/N,注意文档频率和词频在计算上的区别。

  布尔检索模型在下一节详细介绍,这里认为一个关键词只记录是否出现在文档中,而不记录其出现的具体位置。即在如图5-6所示的倒排索引中,不考虑 HIts和 HitList字段的信息。接下来对倒排索引长度的估计中,默认倒排索引不包含Nts和 Hitlist字段。

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

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

索引系统-数据规模的估计

  在图5-8中用6个文档代表全部文档,标“1”表示词汇在文档中出现。可以看出词频排名1-76的词汇出现在全部文档中,词频排名77-152的词汇出现在12的文档中,词频排名153-304的词汇出现在1/3的文档中。

  对于共计500000个词汇,则有500 00076=6 500这样的块。对于第i块,其出现在m个文档中。假定记录每个 DocId需要k个字节,第i块(含76个词汇)需要的空间为76 kn/i,这样的块共有6 500个。不妨假设有100亿(10GB)的网页,每个Docd的评价编码长度为1个字节(这里采用差分序列对 DocId压缩编码,实际平均字节数略大于1)例如,在倒排索引中对词频排名为1-76的高频索引词,其倒排索引简化为如图5-9所示。

索引系统-数据规模的估计

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

  综上,在布尔检索模型下的倒排索引规模为:

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

评论区

共0条评论
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~

【随机新闻】

返回顶部