XML地图 黑帽SEO培训为广大SEO爱好者提供免费SEO教程,致力于SEO优化、SEO服务
首页 > SEO培训 » 搜索引擎索引压缩

搜索引擎索引压缩

2018-10-11T11:40:28 | 人围观 | 关键词:搜索引擎索引压缩--SEO培训


  搜索引擎索引压缩
 

  “佛土生五色茎,
 

  一花一世界,
 

  一叶一如来。”
 

  [图片]《华严经》
 

  对于海量网页数据,为其建立倒排索引往往需要耗费较大的磁盘空间,尤其是一些比较常见的单词,其对应的倒排列表可能大小有几百兆。如果搜索引擎在响应用户查询的时候,用户查询中包含常见词汇,就‍需要将大量的倒排列表信息从磁盘读入内存,之后进行查询处理给出搜索结果。由于磁盘读/写速度往往是个瓶颈,所以包含常用词的用户查询,其响应速度会受到严重影响。索引压缩则可以利用数据压缩算法,有效地将数据量减少,这样一方面可以减少索引占用的磁盘空间资源,另一方面可以减少磁盘读/写数据量,加快用户查询的响应速度。
 

  倒排索引主要包含两个构成部分:单词词典和单词对应的倒排列表。所以针对索引的压缩算法,也分为针对词典的压缩和针对倒排列表的压缩。而对倒排列表压缩又可以细分为无损压缩和有损压缩两种。所谓无‍损压缩,就是将原始倒排列表数对于海量网页数据,为其建立倒排索引往往需要耗费较大的磁盘空间,尤其是一些比较常见的单词,其对应的倒排列表可能大小有几百兆。如果搜索引擎在响应用户查询的时候,用户查询中包含常见词汇,就‍需要将大量的倒排列表信息从磁盘读入内存,之后进行查询处理给出搜索结果。由于磁盘读/写速度往往是个瓶颈,所以包含常用词的用户查询,其响应速度会受到严重影响。索引压缩则可以利用数据压缩算法,有效地将数据量减少,这样一方面可以减少索引占用的磁盘空间资源,另一方面可以减少磁盘读/写数据量,加快用户查询的响应速度。
 

  倒排索引主要包含两个构成部分:单词词典和单词对应的倒排列表。所以针对索引的压缩算法,也分为针对词典的压缩和针对倒排列表的压缩。而对倒排列表压缩又可以细分为无损压缩和有损压缩两种。所谓无‍损压缩,就是将原始倒排列表数据量减小,但是信息并不会因为占用空间的减小而有所损失,通过解压缩算法可以完全恢复原始信息。而有损压缩则是通过损失部分不重要的信息,以此来获得更高的数据压缩率。
 

  本章主要介绍针对搜索引擎索引的压缩算法,首先介绍针对词典的相关压缩技术,第4.2节会介绍针对倒排列表的‍经典压缩算法,之后是对文档ID重排序技术的说明,这是另一种形式的无损压缩思路。最后一节简单介绍静态索引裁剪这一有损压缩算法。
 

  4.1 词典压缩
 

  为了快速响应用户查询,词典数据往往会全部加载到内存中,以加快查找速度。如果文档集合数据量很大,包含的不同单词数目会非常多,内存是否能够放得下全部词典信息就成了问题。为了减小词典信息所占内存,一般可考虑采用词典压缩技术来达到此目的。
 

  上一章介绍了词典的组织方式有两种:哈希加链表和B树形词典结构。在链表内部或者B树的叶子节点会存储单词相关信息,一般至少会存储以下3项:单词本身内容,文档频率信息(DF)及指向倒排列表的指针信息。图4-1是词典结构和信息的示意图。
 

  [图片]图4-1 词典信息
 

  对于某个词典项来说,文档频率信息和倒排列表指针信息各自使用4个字节表示即可,而单词本身内容可长可短,长的单词比如“中华人民共和国”,短的单词比如“我”,长度差异很大。为了能够容纳最长的单词,需要给单词内容分配足够大的空间,我们假设词典中最长单词是10个汉字,即每个单词内容需要分配20个字节,即使是像“我”这种单字词,也会占用20个字节的位置,浪费严重,很明显这里可以采取一些优化的数据结构来省出存储空间。
 

  图4-2是针对单词内容存储结构的一种优化措施,在这个技术方案里,可以将单词连续存储在某个内存区域,原先存储单词内容的部分由指向这个存储区对应单词起始位置的指针代替,单词结尾可以用词典中下一个单词的指针所指向位置来做判断,如此就可以将原先浪费的存储空间利用起来。
 

  [图片]图4-2 优化的词典结构
 

  在上述优化词典结构的基础上,还可以继续做出改进,图4-3是进一步改进方案的示意图。其基本思想是:将连续词典进行分块,图中的例子是将每两个单词作为一个分块,在实际开发时,可动态调整分块大小,以获取最优压缩效果。原先每个词典项需要保留一个指向连续词典区的指针,而分块之后,相邻的两个词典项可以共享同一个指针,这样每两个词典项就节省出了一个4字节长的指针信息,因为此时连续词典分块内包含多个单词,为了能够标出其分隔位置,需要为每个单词增加单词长度信息,这样就可以在提取单词时对块内的不同单词予以正确区分。
 

  [图片]图4-3 进一步优化的词典结构
 

  实验表明,经过上述优化的词典比不做优化的词典占用内存数量减少了60%,可见这些优化措施还是非常有效的手段。
 

  4.2 倒排列表压缩算法
 

  单词对应的倒排列表一般记载3类信息:文档编号、词频信息及单词位置序列信息。因为文档编号及单词位置序列是依次递增的,所以通常的做法是存储其差值,而非原始数据。经过差值转换,文档编号和单词位置信息往往会被转换成大量的小整数,而词频信息大部分是小整数,因为一个单词在正文中出现的频率通常都不高。压缩算法的处理对象就是这3类信息,从以上描述可以看出,倒排列表数据有其特点,即数字分布严重不均衡,小数值占了相当大的比例。
 

  4.2.1 评价索引压缩算法的指标
 

  目前有很多种倒排列表压缩算法可供选择,但是评判算法的优劣需要定量指标。一般来说,评价倒排列表压缩算法会考虑3方面的指标:压缩率、压缩速度和解压速度。
 

  所谓压缩率,就是数据压缩前大小和压缩后大小的比例关系,很明显,压缩率越高,就越节省磁盘空间,同时也节省了倒排列表从磁盘读入到内存的I/O时间。
 

  压缩速度是指压缩一定量的数据所花费的时间,相对而言,这个指标不如其他两个指标重要,因为压缩往往是在建立索引过程中进行的,而建立索引是一个后台运行过程,不需要即时响应用户查询,即使速度慢些也没有太大关系。另外,建立索引的次数相对而言也不算多,所以从几个方面考虑,压缩速度不是一个重要指标。
 

  解压速度在3个指标中是最重要的,其含义是将压缩数据再次恢复为原始数据所花费的时间。因为搜索引擎在响应用户查询时,从磁盘读入的是压缩后的数据,需要实时解压以快速响应用户,所以解压速度直接关系到系统的用户体验,其重要性不言而喻。
 

  4.2.2 一元编码与二进制编码
 

  一元编码(Unary Code)和二进制编码(Binary Code)是所有倒排列表压缩算法的基本构成元素,不论压缩算法内部逻辑思路是怎样的,最终都要以这两种格式来对数据进行表示。要么是以一元编码和二进制编码混合的方式,要么是单独以二进制编码的方式。可以认为这两种编码格式是压缩算法的基础构件。
 

  一元编码是非常简单直观的数据表示方式,对于整数X来说,使用X-1个二进制数字1和末尾一个数字0来表示这个整数。图4-4是1到5这几个数字相对应的一元编码。可以看出,一元编码仅仅适合表示非常小的整数,比如对于数字23000,如果用一元编码表示明显是很不经济的。
 

  [图片]图4-4 一元编码
 

  二进制表示方式是计算机内部的标准数据存储方式,即由二进制数字0和1进行组合来表示实际的数据。不同的比特宽度代表了不同的数字表示范围,图4-5给出了不同的比特宽度能够表达的数值范围及一些对应的二进制表示示例。比如对于比特宽度为3的情形,即用3个比特位来表示数字,那么其能够表达的数值范围为0到7这8个数字;对于数字5来说,将3个比特位设置为二进制101的方式就能够获得表达,其他例子与此相同。在计算机内部,一般是以字节为单位的,即比特宽度为8的二进制编码就是一个字节。相对于一元编码来说,只要比特宽度足够长,那么二进制编码可以表示几乎任意范围的数字。
 

  [图片]图4-5 二进制编码方式
 

  了解了一元编码和二进制编码这两个压缩基础构件,我们下面介绍一些经典的倒排列表压缩算法。
 

  4.2.3 Elias Gamma算法与Elias Delta算法
 

  Elias Gamma压缩算法利用分解函数将待压缩的数字分解为两个因子,之后分别用一元编码和二进制编码来表达这两个因子。
 

  Elias Gamma算法采用的分解函数如下。
 

  x=2e+d
 

  其中,x为待压缩的数字,e和d分别为其因子,得到分解因子后,对于因子e+1采用一元编码来表示,对于因子d采用比特宽度为e的二进制编码来表示。
 

  假设待压缩的数字为9,因为9可以分解为2的3次方加1,所以e=3而d=1,对e+1用一元编码后为:1110,而对d用比特宽度为3的二进制编码进行转换后为001,将两者拼接获得:1110:001,此即为数字9对应的Elias Gamma编码。
 

  Elias Delta算法是建立在Elias Gamma算法基础上的改进,在概念上可以认为是利用两次Elias Gamma算法,将待压缩的数字分解为3个因子,之后利用一元编码和二进制编码来进行数值压缩。
 

  对于待压缩数字x,Elias Delta算法根据分解函数,将其分解为因子e和因子d,对因子d采用比特宽度为e的二进制编码进行压缩,而对于因子e+1,则使用Elias Gamma算法再次进行压缩,即分解出另外两个因子。由此过程可以看出,Delta算法等于使用了两次Elias Gamma算法,将待压缩数字分解为3个因子,然后分别编码获得最后的压缩数据。
 

  我们仍然以数字9来说明Elias Delta的编码过程。根据分解函数可知,e=3而d=1,对d利用3比特宽度的二进制编码压缩为001,对e+1即数字4采用Elias Gamma算法获得编码110:00,将两者拼接获得最终压缩编码为110:00:001。
 

  从以上两个压缩算法的过程可以看出,Elias Delta算法对于大数值来说压缩效果要优于Elias Gamma算法。
 

  4.2.4 Golomb算法与Rice算法
 

  Golomb算法和Rice算法在大的思路上也与上述的两个Elias算法类似,即根据分解函数将待压缩数值分解为两个因子,分别用一元编码和二进制编码来进行数据压缩表示。不同点在于,它们采用了和Elias算法不同的分解函数。
 

  对于待压缩数值X,Golomb和Rice算法采用了如下的因子分解方式:
 

  因子1=(X-1)/b
 

  因子2=(X-1)mod b
 

  因子1是将X减1后除以参数b向下取整后获得的整数,将其值加1然后采用一元编码压缩;而因子2则是对参数b进行取模运算,获得取值范围在0到b-1之间的X除以b后的余数,对因子2使用二进制编码进行压缩,因为取模运算决定了其取值范围一定在0到b-1之间,所以二进制编码的比特宽度设定为log(b)就能表示这个范围内的数值。
 

  对于Golomb算法和Rice算法来说,b如何取值是其关键,这两个算法的不同点也仅仅在于b的不同取值方式。b的取值依据是什么呢?b的设定依赖于待编码数值序列的平均值或者中位数,在此基础上,Golomb和Rice算法对b的设定采取了不同的策略,假设一个待压缩数值序列的平均值为Avg,则Golomb算法设定为:
 

  b=0.69×Avg;
 

  这里的0.69是个经验参数,而Rice算法则要求b一定要为2的整数次幂,同时b必须是所有小于平均值Avg的2的整数次幂的数值中最接近Avg的数值。假设Avg的数值为113的话,则b会被设定为64,因为如果是128,则超过了113,如果是32,则此值不是小于113且最接近113的数值,只有64符合这些条件。
 

  图4-6给出了利用Golomb算法和Rice算法对待压缩数值序列进行压缩的示例。首先,获得数值序列的平均值133,Golomb算法设定b=78,其二进制编码的比特宽度可以取6或者7,即对在0到77范围内的数值,如果因子分解后因子2的值小于50,则采取6比特宽度,如果因子2的值大于50则采取7比特宽度,这样可以有效减少压缩数据的大小;而Rice算法设定b=64,其二进制编码的比特宽度取6。当这些参数都可以确定下来后,即可对数值进行压缩编码,我们以数值144为例说明,首先对其减去1,即需要对143进行压缩。对于Golomb算法来说,其对应的因子1取值为1,数值加1后采用一元编码得到10,因子2取值为65,对其进行二进制编码得到1000001,拼接两者获得最终编码10:1000001。对于Rice算法来说,143对应的两个因子分别为2和15,对2加1后进行一元编码得到110,对15进行二进制编码得到001111,拼接两者得到最终编码110:001111。
 

  [图片]图4-6 Golomb算法和Rice算法示例
 

  对于Rice算法来说,之所以要设定b为2的整数次幂,是为了在具体实现算法时能够采取掩码操作或者比特位移操作等快速运算方式,所以Rice在运算效率方面要高于Golomb算法。
 

  而对设定好的参数b来说,其适用范围可以是局部的也可以是全局的,所谓全局的适用范围,就是说确定好b后所有单词对应的倒排列表都采用同一个数值;而所谓局部的适用范围,则是不同单词的倒排列表采取不同的参数b。一般来说,如果索引非常庞大,则采取局部参数b效果更好,原因也很明显,因为局部参数b等于是对待编码序列根据局部分布情况进行自适应调整,这样会使得压缩效果更好。
 

  4.2.5 变长字节算法(Variable Byte)
 

  变长字节算法以字节(即比特宽度为8)为一个基本存储单位,而之前介绍的压缩算法都是变长比特算法,即以比特位(Bit)作为基本存储单位。之所以称之为“变长字节”,是因为对于不同的待压缩数字来说,在压缩编码后占用的字节数目不一定相同,可长可短,是变化的。
 

  一个字节包含8个比特位,因为对于变长字节算法来说,每个数字压缩后的字节数目是变动的,为了确定两个连续数字压缩后的边界,需要利用字节中一个比特位作为边界判断符号,一般如果边界判断比特位设定为0,则可以认为这个字节是数字压缩编码的最后一个字节,而如果设定为1,则说明后续的字节仍然属于当前的压缩数据数字。所以每个字节在概念上被划分为两部分,其中一个比特位用来做边界判断;其他7个比特位采用二进制编码来存储压缩数据,即每个字节的数值表示范围为128个数字。
 

  给定一个数值,如何对其进行变长字节压缩?图4-7给出了数值33549的变长字节压缩示例,因为一个字节可表示的数值范围为0到127,所以按照128作为基数将待压缩数值进行分解,分解后的因子分别为2、6和13,则在相应的字节存储这几个因子的二进制编码,同时设置边界指示位置为1、1和0,即说明这个数值需要3个字节来进行存储。
 

  [图片]图4-7 变长字节压缩示例
 

  对于多个连续待压缩数值,则每个数值依照上例进行压缩编码,将其压缩编码连续存储即可。图4-8给出了多个连续数值序列对应的变长字节编码序列。
 

  [图片]图4-8 多数值的变长字节编码序列
 

  4.2.6 SimpleX系列算法
 

  SimpleX系列算法最常见的是Simple9,在此基础上有改进算法Simple16、relate10及carryover12等,本节我们主要介绍Simple9算法的计算思路。
 

  Simple9是一种字对齐算法,最常用的是利用32个比特位(即4个字节)来作为一个压缩单位,给定固定大小的压缩单位后,每个压缩单位试图存储多个待压缩的数字。图4-9给出了Simple9算法的字划分布局。
 

  [图片]图4-9 Simple9的9种字划分布局
 

  从图4-9可以看出,每个32位比特字被划分为两个组成部分,其中4个比特作为管理数据存储区,剩下28个比特作为压缩数据存储区,而压缩数据存储区根据实际使用情况,可以划分为9种布局类型(这也是Simple9的名字来源)。4比特类型指示位用来指示后续的数据存储区属于哪种类型,而图中的B则指出了后续数据存储区的基本单元的比特宽度。
 

  比如对于B为1的情况,说明后续数据存储区基本单元比特宽度为1,数据存储区共有28个比特,所以数据区被划分为28个1比特宽度的基本单元构成。因为一个比特只能存储二进制数值0或者1,即区分两种状况,所以这个32位比特字可以存储28个范围在0到1的数字。
 

  对于B为2的情况,数据存储区基本构成单元比特宽度为2,即数据存储区由14个2比特位基本单元拼接而成,因为2比特位可以表达4个数字,所以这种类型的布局,在一个32位比特字中,可以存储14个范围在0至3的数字。
 

  类似地,还可以根据B的不同大小设置其他的布局方式,图4-9给出了9种不同的布局,这里要注意的是:对于有些宽度的基本构成单元,因为不能被28整除,所以在数据存储区会有字节被废弃不用。比如对于B为3的情况,则最后一位比特位被废弃(图中有网线的单元指出了在各种情况下废弃的比特位)。
 

  在利用Simple9对数据进行压缩时,首先读取待压缩数值队列后续的28个数字,如果发现这28个数字都是0或者1,那么说明可以利用B=1这种布局来存储,则将28个数字编码为二进制后存入28个数据位,同时在类型指示位标出这种类型。如果发现有大于1的数值,说明B=1这个布局无法容纳这组数据,于是由读取后续28个数字改为读取后续的14个数字,判断是否能够使用B=2这种布局,即判断后续14个待压缩数据是否都在0到3的数值范围,如果是的话则采取B=2布局压缩,否则继续考虑B=3的布局,依次如此试探,即可将待压缩数字都表示为固定长度为32位比特的压缩表示方式。
 

  利用Simple9进行解码的时候,因为编码是固定长度的,所以可以一次读取4个字节(即32比特),从4比特类型指示位判断后续数据存储区是哪种布局方式,对于每种布局方式可以事先准备好对应的掩码,判断出布局方式后,直接利用掩码可以一次性解压出后续的多个压缩数字。
 

  Simple16等后续改进算法在Simple9基础上做出了改进,改进思路大致相同。首先,Simple9的类型指示位由4比特位构成,即说明其可以指示16种不同情况,而Simple9因为只有9种类型,所以并未完全利用这4比特指示位置,可以将9种布局进行扩展,扩展为更多种布局方式,Simple16就是将后续28位数据存储区划分为16种组成方式。另外一点,从图4-9可以看出,Simple9在有些布局方式下会有废弃比特位,而这明显是对存储资源的浪费,可以考虑如何将其利用起来。Simple9之所以会出现废弃位,是因为它对28位数据存储区是等宽度划分的,所以必然会有无法被28整除而出现的废弃位。Simple16等改进算法则放宽了这种要求,即数据存储区不一定是等宽的,比如对于Simple9的B=5的状况,可以划分为4个5比特及后续的两个4比特,这样就可以全部利用存储区的位置,同时表达能力得到增强,即在压缩时,可以有更多种方式来进行压缩编码。
 

  4.2.7 PForDelta算法
 

  PForDelta压缩算法是目前解压速度最快的一种倒排文件压缩算法,其基本出发点是:尽可能一次性压缩和解压多个数值。尽管SimpleX系列算法也利用了这一点,但PForDelta算法在这方面做得更好。
 

  一次性压缩多个数值面临实际困难:因为连续的数值序列有大有小,如果每个数值按照序列中最大的数值来决定比特宽度,很明显对于小数值来说会存在空间浪费的情形,而如果不按照最大数值分配比特宽度,那么对于后续连续数值来说,因为比特宽度不够,存在有些大数值无法表示的问题。
 

  PForDelta希望能在压缩率和压缩解压速度方面找到一个平衡点,使得算法可以一次压缩解压多个数值。PForDelta的折中方案是:对于待编码的连续K个数值(一般K取128,即一次性压缩解压128个数值),找出其中10%比例的大数,根据剩下90%的数值范围来决定应该采取的比特宽度,而10%的大数则当做异常数据单独存储,即采取了“照顾大多数”的原则,对于少数情况做特殊处理。
 

  下面以具体实例来看看PForDelta算法的静态结构、压缩过程及解压过程。假设一次性要压缩的数值序列为:24,40,9,13,31,67,19,44,22,10,即K取10,另外为了方便说明问题,这里取30%的大数作为异常数,而在真实场景K往往取128,大数比例一般取10%。图4-10是PForDelta算法压缩以上数据序列后形成的静态结构,压缩后的数据可以划分为3块:异常数据存储区、常规数据存储区和异常链表头。
 

  [图片]图4-10 PForDelta算法压缩数据的静态结构
 

  异常数据存储区存储的是数值序列中30%比例的大数,这些异常数值不做压缩编码,每个数值用4个字节来存储,并放置在静态结构的尾端,存储顺序与其在原始数值序列的出现顺序相反。
 

  常规数据存储区则存储了70%的小数及一个异常数据链表结构,在上述例子中除了30%的3个大数外,最大的数值为31,所以为了能够表示这70%的数值,比特宽度需要设定为5,因为每个数值利用5个比特位存储,那么可存储的最大数值为31,这样就保证这70%的数值都可以以等长的比特宽度压缩存储。尽管30%的大数已经被存储在尾端,但是为了能够记载这些数在原始序列中的位置信息,PForDelta在常规数据存储区维护了异常大数的一个顺序链表,比如对于异常数值40,其常规数据存储区对应位置设定为3,含义是指跳过后面3个数值即是另外一个异常大数的位置,同理,数值67的对应位置设定为1,意即跳过后面1位数值即是后续的异常大数位置,通过这样就将异常大数的位置信息保留下来,这样在解压的时候能够快速恢复原始数据。
 

  异常链表头则存放一个指针,指向了异常链表的第1个数值的位置,本例中链表头的值为1,意即跳过后续一个常规数值即可获得第1个异常大数的位置,通过链表头,就可以将所有异常大数快速串联起来。
 

  以上介绍的是PForDelta算法的静态压缩结构,那么给定上述10个待压缩数据流,是如何形成最终的压缩结构的?PForDelta采取了3个步骤来形成压缩结构,图4-11展示了这3个连续的步骤。
 

  [图片]图4-11 PForDelta的压缩过程
 

  第1步,根据待压缩的数据流,确定30%比例的大数个数及分别是哪些数值,在此例中依次为40、67和44,根据剩下的70%数值大小,可以确定压缩采取的比特宽度为5,此时即可确定静态结构所需存储区的大小。
 

  第2步,对原始数据循环遍历,本步骤主要处理异常大数,一方面将遇到的大数逆序放置到静态数据尾端;另一方面将原先的异常大数转换成链表结构,所以3个异常大数对应位置被置换成3、1和2,形成了链表结构。
 

  第3步,一次性将所有10个数值快速压缩,然后存入常规数据存储区中。经过第2步后,可以保证10个待压缩的数据都在32以下,如果是这样就可以采取措施快速压缩。
 

  通过以上3个步骤,即可对多个数值成功地进行一次性压缩,至于解压,则可以理解为压缩过程后面两个步骤的逆过程,即通过两遍完成。首先,一次性将常规存储区的10个数值进行解压,然后根据异常链表头,依次顺序读出异常大数的位置,结合尾部存储的异常大数恢复原始数值序列。
 

  多项实验表明,PForDelta的解压速度是现有压缩算法里最快的,而且性能大幅度超过其他算法。主要原因是其能够一次性解压多个数据,尽管恢复异常数据速度比较慢,但是因为其所占比例很小,所以影响不大;另一点,PForDelta之所以将解压设置为两遍方式,而非一遍做完,是为了在程序中避免做IF-ELSE这种分支判断,因为大量分支判断严重影响解压执行速度。比如Simple9算法解压,每4个字节就需要做一次分支判断,因为要判断压缩数据是9种布局中的哪一种;而变长字节算法解压则每个字节都需要做分支判断,以决定当前字节是否是某个数字的最后一个字节,相对应地,PForDelta在其解压流程中是不做任何分支判断的,这也是其速度快的重要原因之一。
 

相关内容推荐:

Top