欢迎光临本站!

索引系统-文档编号

来源:技术探讨    更新时间:2019-12-12 09:58:14    编辑:老王    浏览:278

  个惟一的编号是描述一个复杂事物最好的方法,每一个文档赋予一个惟一的编号后,这个编号就能代表这个文档。

  编号的本质


  编号的历史能够追溯到古老的时代。部队有番号、单位职工有工作证号、大中专院校学生有学号,以及公民有身份证号。从各种各样的编号中不难发现这样的规律,即凡是需要区别大量个体的情况就会用到编号。一个家庭成员之间不会用编号来区分因为用姓名更加自然并亲切。然而,如果某个家庭成员来到学校读书,因为可能存在同名同姓的同学。因此采用姓名就不能有效地区分,使用学号就成为必然的手段。这样通过一定的编码方式可以保证某个年级某个院系某个班级的某个学生拥有惟一标识自身的学号。

  对于搜索引擎来说,编号不仅仅是保证惟一,而且它好像是道连通信息和索引的桥梁。搜索引擎需要处理的信息是海量的为了能够快速检索到这些信息,通常的做法是为信息创建索引。索引也是信息,是那种能够用来找到信息的信息。对于搜索引擎来说,网页是信息,关键词就是索引,索引相对于信息来说是轻量级的。文档干差万别,而关键词总是有限的。因此虽然处理的是海量信息,但是转化到索引后在空间占用上就会变得相当小。检索在索引上完成后,得到一组匹配关键词的文档编号。继而将这些文档编号在文档信息库中取出,通过一系列计算展示出来编号就是这样在检索中发挥了重要的作用。

  一个网页被爬虫抓取,经过分析系统的分析。然后得到结构化的网页对象为此首先需要为结构化的网页对象进行编号存档。在索引系统中,我们统一将这种结构化的网页对象(包含标题、正文和URL等信息的结构体)称为“文档”,网页的编号称为“文档编号。

  文档编号和日常生活中的编号最大的不同在于,它不需要具有具体的含义。与机器不同,日常生活中使用编号大多具有某种意义。例如我们的身份证号每一段都有其特定的含义,然而文档编号有其特殊性。在信息索引阶段,编号无处不在。各种检索及排序计算都依赖于编号,因此文档的编号方法会有一些额外的特别要求。

  文档编号的方法


  文档编号需要满足下面3个条件。

  (1)任何一个文档在其生命周期中仅有一个编号。

  (2)任何两个不同的文档的编号不同。

  (3)编号在计算中尽可能高效,并且为了便于存储,要越短越好。

  第1个条件表明文档编号和文档内容无关,有些文档内容常常发生变化。如果编号与内容有关,编号的稳定性将不能够被满足。

  编号不能直接由文档文件名代替,因为很多网站都有类似index. html和 welcome. html等这样通用的文件名。如果编号由文件名代替,那么就破坏了第2个条件,即不同的文档由于相同的文件名而赋予相同的编号。

  综上所述,文档内容和文件名均不能代表一个文档。事实上,只有URL才能够惟一地表示一个文档。通过浏览器输入一个URL只能到达惟一网页,这首先保证了第2个条件;其次也满足了第1个条件,网页的内容变化不会影响其URL。因此,URL是天然的计算文档编号的来源。

  由于中文万维网网页规模将来必然达到百亿量级的规模,如何合理地对文档进行编号才能符合第3个条件要求的高效计算呢?

  显然将文档的URL直接作为编号是不合适的,一个 ASCII 字符为一个字节,这样的一个Url(hTtp://sports.****.com/20070411/n249364259. shtml)就需要多达48个字节。不论是计算还是存储都是不经济的。计算不经济主要体现在字符串运算慢,这是因为字符串编号在查找和排序时的代价都很大。排序和查找都是利用多次比较完成的,时间的耗费主要在比较操作上,字符串之间的比较耗时远大于整型的比较;存储不经济主要体现在字符串的空间占用较大,增大了磁盘IO的次数。此外,空间占用量大还会影响计算效率。空间占用越大,内存工作集也就相应变大,内存和对换区的换入换出机会就增大。

  综上所述,采用对字符串映射为占64比特大小的长整形整数,利用整数计算高效,存储代价小的特点进行文档编号是必然的选择。

  整型编号不仅可以节约大量存储空间,而且大大提高检索计算中比较排序的效率。采用URL字符串签名的方法(参见第三章),一个32位整型能够表达40亿量级的数。对一个URL字符串签名得到一个占两个整型(8个字节)大小的MD5签名,理论上它能够表达足够多的网页数量,这被认为符合当前时代万维网网页数量的编号要求。对于大规模的网页编号来说,两个整形的空间耗费还是太大。通过编码的技巧可以让其变得更短,更适合计算的需要。

  游程編码


  本节介绍一种通用的编码方式,称为“游程编码”,使用这种方式进行编号长度压缩。在后面还会提到这个技巧,因此这里可以作为一个知识准备。

  假定一个文档编号序列为1,17,34,69,489,512,3456这些都是文档的内部编号。编号为升序序列,即排在后面的数不小于排在前面的数。不妨假定编号为一个整型大小,并且能够满足40亿个不同个体的编号需要。上面这个文档编号序列包含7个整数,因此需要7个整型(28个字节)的数组来存储。

  对于这种单调的序列,可以将增量整数序列被变换为差分序列,这种编码方式也称为“差分编码"( gap encoding)通过转换得到1,17-1,3417,6934,489-69,512-489,3456-512,即116,17,35,420,23,2944。由于差分序列除第1个编号外其余都保存的是间隔距离,因此带来一个好处和一个坏处。

  好处是因为存放的是相对数,所以除第1个数以外,序列中的数都变得较小。

  坏处是为了取出序列中某个特定值,需要由头至尾取出所有数据,并进行多次加法运算。一旦缺失一块数据,则无法序列中的后续部分无法恢复。

  举个例子,在1,16,17,35,420,23,2944这个序列中如果需要取序列中第7个数,首先必须读出全部数据进行连加,也就是需要计算1+16+17+35+420+23+2944=3456。如果由于各种原因,中间的数据缺失或者出现异常,例如第4位应该存放35而读取出来为35,这使得后续的数据无法恢复。通过这个例子不难看出,一方面付出了CPU的代价;一方面付出了维护数据完整性的保证,继续来看得到怎样的补偿。

  由于序列中的数都变得很小,所以可以采用一种变长编码( Variable Byte Coding)[ Williams1999]的技巧。这是一种字节对齐的编码方式,即将整数转化成二进制后,以7位为单位对其分段。每段段尾加一位成为8位,恰好用一个字节表示。末位为0表示该段是最后一段,为1表示还有后续段。例如,135的二进制编码表示为10000111通过编码后为000000100001110。第1段(000001末尾的1表示该字节为段首(还有后续段),倒数第1个1表示135二进制数据中的第1个1。第2段(00001110)末尾的0表示该段不是段首,其余7位表示135二进制数据中的后7位(000011)编码的过程很容易,解码的过程也相当快。

  在实践中, Variable Byte Coding编码不是压缩率最高的编码方式,例如其压缩率不如γcode(Elas),但由于 Variable byte Coding具有字节对齐的优秀特性,所以解码非常快速。具体的解码过程参考下述伪码。

  解码过程的伪码为:

索引系统-文档编号

  在上述伪码中,HEAD(A)表示从A中读取头部的一个字节,并去掉这个字节。例如,135表示为0000011 0000110

  第1次执行HEAD操作返回A的段首字节,该字节的二进制表示为00000011并且去掉这个头部字节。因此此时A的二进制表示为00001110,这时i保存段首字节(00000011).对其右移位(i>1),取其字节后7位(&0x7F),此时i为0000000然后v初始化为0,这样第1次执行后v=1。

  第2次执行HEAD时,返回的结果是字节(00001110),并存放到变量i中,即十进制的7。将变量i右移动1位,并取后7位,得到000011,加上第1次计算的v右移7位,最后得到10000111,即135。

  对于32位的整数,采用 Variable Byte Coding编码方式。小于128的数可用1个字节来表示,从而节省了3/4的空间;而大于268435455(二进制11111111-11111共24位,每位存储7位,因此需要4个字节存储268435455)的数则需要5个字节。这样大于268435455的数用 Variable Byte Coding编码方式需要的存储空间超过了一个整形的大小,不但没有达到压缩的目的,反而增大了空间。但是由于经过排序,序列之间的差值都会保持相对较小,因此差值达到如此大的距离(大于268435455)的概率极小。可以忽略这种情况带来的代价,整体的存储是经济的。此外,由于计算机以字节为操作单位,字节对齐的编码往往更能发挥硬件的优势,所以可变字节编码的压缩和解压缩的速度都较快。

  这个差分序列中的1,16,17,35,23都小于128,因此只需要1个字节。420需要两个字节(420的二进制表示为110100100,每个字节只有7个有效位,因此这里需要两个字节)同理,2944也需要两个字节。这样全部序列需要9个字节,和原序列需要28字节相比压缩了60%。由于这些表示文档编号的序列存放在磁盘中,因此节约存储相当于减少了磁盘IO的次数。压缩存储是典型的以时间换空间,一方面由于多了编码和解码的过程,导致CPU的消耗增加;另一方面由于节约了磁盘,而减少了磁盘读取次数。一般来说,1/O是索引系统的瓶颈。而且CPU和O之间性能差距还在不断扩大,因此采用这种技巧带来的减少了磁盘IO的次数的好处完全可以抵偿因此带来的CPU计算量增大的不利结果。

  文献[ Witten1994]堪称是信息检索的经典书籍,其中介绍大量关于大规模数据压缩的其他方法和技巧,它们各有优劣。需要进一步钻研的读者可以通过阅读本书全面地理解处理大规模数据的各种技巧,通过 Variable Byte Coding的学习,充分理解排序对压缩的关键作用,排序带来的一些冗余数据和处理这种冗余数据的方法。

  在解决了文档编号存档的问题后,接下来就是如何查找到这些文档。记住编号超出人类记忆的能力范围,记住标题也难度颇大。那么对于酒香还怕巷子深的问题,用什么方式来索引这些文档才能符合全文检索的需求呢?下一节我们将着重介绍有关倒排索引的概念。

上一篇:全文检索

下一篇:索引系统-倒排索引

评论区

表情

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

相关内容

点击排行

随机新闻

评论排行榜