• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
    • / 18
    • 下载费用:30 金币  

    重庆时时彩技巧经验: 一种新的压缩比特位图索引的方法.pdf

    关 键 词:
    一种 压缩 比特 位图 索引 方法
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    摘要
    申请专利号:

    CN201410182226.8

    申请日:

    2014.04.30

    公开号:

    CN103942329A

    公开日:

    2014.07.23

    当前法律状态:

    授权

    有效性:

    有权

    法律详情: 授权|||实质审查的生效IPC(主分类):G06F 17/30申请日:20140430|||公开
    IPC分类号: G06F17/30 主分类号: G06F17/30
    申请人: 清华大学
    发明人: 陈震; 温禹豪; 马戈; 曹军威
    地址: 100084 北京市海淀区北京市100084-82信箱
    优先权:
    专利代理机构: 北京众合诚成知识产权代理有限公司 11246 代理人: 黄家俊
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201410182226.8

    授权公告号:

    ||||||

    法律状态公告日:

    2017.10.10|||2014.08.20|||2014.07.23

    法律状态类型:

    授权|||实质审查的生效|||公开

    摘要

    本发明公开了计算机网络或大数据分析领域的一种新的压缩比特位图索引的方法,即ICX算法,用以解决目前压缩比特位图的研究中存在的问题。该方法主要是对COMPAX算法进行改进,提出Nearly?Identical的概念,具体包括:把待压缩的01比特序列分成以31bits为单位的块,对块进行分类标记:F-块和L-块,L块又分为C-L-块,0-NI-L-块和1-NI-L块,0-NI2-L块,1-NI2-L块;根据ICX码本与编码规则,在码本编码FL序列基础上,进一步编码,具体分为:L-字编码,F-字编码,FLF-字编码,LFL-字编码,NI-FL字编码,NI2-FL字编码。与COMPAX算法相比,本发明提高了编码效率,有效实现了一种新的压缩比特位图索引的方法。

    权利要求书

    权利要求书
    1.  一种新的压缩比特位图索引的方法,其特征是所述方法包括:
    步骤1:把待压缩的01比特序列分成以31bits为单位的块,对块进行分类标记;
    步骤2:根据ICX码本与编码规则,在码本编码FL序列基础上,进一步编码。

    2.  根据权利要求1所述的一种新的压缩比特位图索引的方法,其特征是所述把待压缩的01比特序列分成以31bits为单位的块,对块进行分类标记具体包括:F-块和L-块,L块又分为C-L-块,0-NI-L-块和1-NI-L-块,0-NI2-L块,1-NI2-L块。

    3.  根据权利要求2所述的一种新的压缩比特位图索引的方法,其特征是所述0-NI-L-块的定义为:一个L-块(补0后)与全0字比较,差异比特在同一个字节内,则记做0-NI-L-块。

    4.  根据权利要求2所述的一种新的压缩比特位图索引的方法,其特征是所述1-NI-L-块的定义为:一个L-块(补1后)与全1字比较,差异比特在同一个字节内,则记做0-NI-L-块。

    5.  根据权利要求2所述的一种新的压缩比特位图索引的方法,其特征是所述0-NI2-L-块的定义为:一个L-块(补0后)与全0字比较,差异比特在同2个字节内,则记做0-NI2-L-块。

    6.  根据权利要求2所述的一种新的压缩比特位图索引的方法,其特征 是所述1-NI2-L-块的定义为:一个L-块(补1后)与全1字比较,差异比特在同2个字节内,则记做1-NI2-L-块。

    7.  根据权利要求1所述的一种新的压缩比特位图索引的方法,其特征是所述根据ICX码本与编码规则,在码本编码FL序列基础上,进一步编码,具体包括:L-字编码,F-字编码,FLF-字编码,LFL-字编码,NI-FL字编码,NI2-FL字编码。

    8.  根据权利要求7所述的一种新的压缩比特位图索引的方法,其特征是所述FLF-字编码的定义为:对满足[1个或多个同类型F-块]-[1个0-NI-L块或者1-NI-L块]-[1个或多个同类型的F-块]的块组合进行编码。

    9.  根据权利要求7所述的一种新的压缩比特位图索引的方法,其特征是所述LFL-字编码的定义为:对满足[一个NI-L-块]-[1个或多个F-块]-[一个NI-L块]的块组合进行编码。

    10.  根据权利要求7所述的一种新的压缩比特位图索引的方法,其特征是所述NI-FL-字编码的定义为:对满足[一个NI-LF块]-[一个或者多个同类型F块]的块组合进行编码。

    11.  根据权利要求7所述的一种新的压缩比特位图索引的方法,其特征是所述NI-FL-字编码的定义为:对满足[一个NI2-LF块]-[一个或多个同类型的F-块]的块组合进行编码。

    说明书

    说明书一种新的压缩比特位图索引的方法
    技术领域
    本发明涉及计算机网络或大数据分析领域,特别涉及一种新的压缩比特位图索引的方法。
    背景技术
    互联网技术的迅猛发展把我们带进了信息爆炸的时代,海量信息内容极大丰富了用户。而移动互联网的爆发,使得用户可以从任何地方,任何时间访问网络上的任何内容,产生更为丰富流量数据。
    据思科(Cisco)公司预测,任何一家大型互联网公司在日常运营中生成和累计的用户流量数据是相当庞大的,以至于不能用千兆(Giga,G)或万亿(Trillion,T)级字节的数据来衡量。为此,思科曾预言,网络的数据流量在2011到2016年之间将以4倍的速率增长,并于2016年达到1.3泽(Zetta,十万亿亿)字节。据中国联通的数据,联通WCDMA3G网络移动用户流量的年复合增长率为135%,目前已经达到5千万亿字节(Petabyte,PB)规模。
    对网络的内容和运行状况监控,保证网络健康正常地运行已成为一项重要工作。在中国“十二五”规划纲要第三篇第十三章第二节中,已经明确提出要“加强网络与信息安全保障”,充分体验了国家对信 息安全的重视。而网络的自由性造成了网络攻击的普遍性。在网络链路方面,网络中某个节点的错误配置可能会给整个网络带来灾难性的后果;网络攻击会造成链路的阻塞,服务器的崩溃,甚至是局部网络通信的中断。在网络内容方面,人们可以在各个地方上传不良信息,进行非法活动,给其他互联网的使用者带来不好的思想、精神、经济等方面的影响和损失。由于这些行为常常不能在发生时被发现,因此需要对网络流量进行记录,以供后期进行研究、分析和举证。
    流量记录的一项核心技术是高速网包索引,流量记录的目的是为以后检索与查找,从而识别可能的网络事件。以10Gbps链路为例,如果按每个网包64字节计算,每秒将达1400万网包,产生的索引量巨大,检索查找速度慢。
    因特网服务提供商(Internet Service Provider,ISP)管理和运行的大型的高速网络,链路速度在10-100Gbps级,即每秒中产生的数据量为1-10GB量级,如果要进行流量的记录,代价非常高。这样的设备和技术的价格也是一般用户无法承受的。而同时,互联网的发展使得许多公司拥有自己的企业网络,也有许多公司将自己的服务器托管到因特网数据中心(Internet Data Center,IDC)运行。这样的局部网络的数目非常庞大,他们的网络带宽一般在100~1000Mbps。管理这些局部的网络也是一个非常现实的问题,为这样的网络设计和实现廉价的网络流量记录工具具有很大的应用前景。
    网包的索引信息具有以下一些特点:海量、数据结构固定、只增不改、重复性较高。海量是指网包索引信息条数众多,一天可以产生 几百万条甚至上亿条索引信息。数据结构固定是指每一条网包的索引信息都有固定的格式和固定的长短。只增不改是指网包的索引信息只会不断增加,一旦产生,以后不可能也不需要在进行修改。重复性高指就每一个域来看,一个域中的千万条数据出现大量的重复。这些特点导致使用关系型数据库处理这样的数据效率并不高,因为传统的关系型数据库是面向更改的,储存在数据库中的数据需要经常的改动。
    Bitmap压缩数据库
    Bitmap索引数据库专门为科学数据而设计,这些数据通常是由科学仪器或是科学仿真产生的,特点是数据量极其大,而且不再更改。Bitmap索引数据库解决了如何在海量的科学数据中快速的找出那些需要的少量的数据的问题,而传统关系型数据库并不适合这项任务。
    Bitmap索引数据库中用到的技术主要是Bitmap索引、Bitmap压缩和归类。在Bitmap索引数据库中,数据是按列存储的,一个列的数据存储在一起,并做Bitmap索引。一个简单的Bitmap索引的例子如图1所示。其中RowID表示对应值在表中第几行,生成的索引是一个矩阵,矩阵中每一行只有一个1,其余都是零,标1的位置对应于该行数据在这一列上的取值。这样生成的Bitmap索引有一个比较大的缺点,索引的列数随着取值的多样话而线性增长。为了控制索引的大小和查询时间,需要对索引压缩和归类。压缩是减小索引中大量0或1带来的空间消耗,归类是对Bitmap索引的一些列的合并。比如值1.01和1.02可以归类成1。通过归类可以减少Bitmap索引的列数,增加查询和储存的效率。
    目前主要的位图索引压缩算法为字对齐混合编码(Word-Aligned Hybrid code,WAH),Position List Word-Aligned Hybrid code(PLWAH)和Compressed Adaptive Index(COMPAX)。其中PLWAH有改进版(即为PLWAH with adaptive counter),COMPAX也有改进版(COMPAX+oLSH)。
    1WAH索引压缩算法
    WAH是Fastbit比特位压缩数据库的默认算法,如图2。将原始码流分成以31bits(对于WAH64就是63bits)为单位的块(chunk)。chunk有两种类型:
    (1)Literal,即这31bits中有0有1。
    (2)Fill,即这31bits全为0或者全为1。
    Literal类型的Chunk:类型标志位为0,余下的31bit即为原来的literal chunk;Fill类型的Chunk:分为1-Fill和0-Fill。此时32bits中类型标志位为1,第二位作为Fill类型的标志(0-Fill即为0,1-Fill即为1),余下为30bits作为counter,表示连续出现多少个0-Fill(或者1-Fill)的chunk的。
    2PLWAH索引压缩算法
    同样是将原始码流分成以31bits为单位的chunk。Chunk也和上文一样分成Literal和Fill两种类型,但是压缩方式有变化。
    第一步:依照WAH方法对于Fill-chunk和Literal-chunk添加标志位与编码,形成一组以32-bits word为单位的编码(标志位为0称之为literal-word,标志位为1的称之为fill-word,下同)。此处的区 别是对于fill-word只有低25bits作为counter(WAH方法是低30bits都是counter,PLWAH要留出中间的5bits作为position list,下面会用到.)
    第二步:
    检查每个fill-word后的word。如果下一个word是literal-word且是”nearly identical”的(nearly identical定义是literal-word和上一个fill-word的差异小于等于s位,s此处暂时为1,后面会进一步讨论),则在fill-word的position list上填入下一个word(此时为literal-word)的差异位位置(此处是31位,因此差异位标号为1-31,留出5bits目的在此),同时删去下一个word(因为信息已经保存在此fill-word中,没有必要继续留着)若fill-word后的word是如下三种情况:(1)异类型的fill-word(2)非nearly-identical的literal-word(3)同类型的fill-word(这种情况产生的原因是连续的fill-chunk超出了1个fill-word的counter的计数范围),则position list不变。
    进行扩展讨论:
    对于32位PLWAH,但是nearly identical的定义中的s不为1,则在第一步(即利用WAH原理编码)时需要留出5*s位position list,余下的32-2-5*s位为counter.在第二步时,向fill-word中的position list添加差异位时须按序添加差异位位置(5个bits标示一个差异位,5*s个bits标示至多s个差异位,但是原文没有明确说当实际差异位小于s时是向最高有效位(most significant bit,MSB)对齐还是向最低有效位(Least significant bit,LSB)位对齐,只给了个接口),当s=0 时PLWAH退化成WAH。
    对于64位PLWAH,position list以6为单位,即留出6*s位为position list,余下的64-2-6*位为counter.
    PLWAH+adaptive counter方法,如图4所示,对PLWAH进行了小幅改进,即考虑连续出现极多的0或者1以至于1个word的counter无法完全容纳。此处选用的方法为使用两个连续的同类型fill-word,把两个counter部分视为一个大的counter,第一个fill-word记录LSB25位,第二个fill-word记录MSB25位(相当于50位的大counter),同时第一个fill-word的position list为空,第二个fill-word的position list照常进行计算。这样的好处是无需将扩展word位数即可完成对更多连续码流的编码任务,节约index空间。
    3COMPAX算法
    COMPAX算法如图5所示,这里以32位为例。
    COMPAX的标志位相对较多。这里Literal和Fill的定义同WAH和PLWAH。
    同样是每31bits分成一个chunk,并且将这些chunk按照以下特征分组:
    (1)Literal-Fill-Literal(LFL),即1个literal chunk+N个Fill chunk+1个literal chunk,且这两个literal chunk的非0位(或者非1位)在同一个byte上(一个chunk在前面补一位0即构成4个完整的byte,要求非零位在同一个完整的byte上)
    (2)Fill-Literal-Fill(FLF),即N个Fill-chunk+1个literal chunk +N个fill-chunk(对literal chunk的要求同上)
    (3)Fill(F),分为0-Fill和1-Fill,无法按照(1)和(2)进行分组的fill-chunk即归入此类型。
    (4)Literal(L),无法按照(1)和(2)进行分组的literal chunk即归入此类型。
    对于这四种类型,有四种不同的word。
    (1)L-word第一位为标志位1,余下31位即为原来的literal chunk。
    (2)F-word第一位为标志位0,对于0-Fill第二、三位为00,对于1-Fill第二、三位为11。余下29bits为counter,即记录有多少个连续这样的chunk。
    (3)LFL-word第一位为标志位0,二三位为01,第4、5位(2bits)标示第一个literal chunk的非零byte位置(共4个byte,标号为00-11),第6、7位(2bits)标示第二个literal chunk的非零byte位置(共4个byte,标号为0-3)第八位标识F类型,0为0-Fill,1为1-Fill;第9-16位(8bits,1byte)为第一个literal chunk中非零byte,第17-24位(8bits,1byte)为Fill的counter,标示有多少个连续的fill chunk(即多少个连续31bits的0/1),第25-32位(8bits,1byte)为第二个literal chunk中的非零byte。
    (4)FLF-word第一位为标志位0,第二、三位为10,第四位为第一个fill的类型(0-Fill为0,1-Fill为1,下同),第五位为第二个fill的类型,第六、七位为L的非零byte位置(标号为00-11),第八 位空闲。第9-16位(8bits)为第一个fill的counter,第17-24位(8bits,1byte)为literal chunk的非零byte,第25-32位为第二个fill的counter。
    在已知COMPAX的情况读码方式如下:
    (1)第一位如果为1,为L-word;
    (2)第一位如果为0:
    (2.1)第二、三位为00:0-fill word
    (2.2)第二、三位为11:1-fill word
    (2.3)第二、三位为01:LFL
    (2.4)第二、三位为10:FLF
    COMPAX+oLSH(online-locality-sensitive-hashing)
    压缩方式同COMPAX,但是先对输入码流进行处理,将相近的包放在相近的位置,这样对压缩率提高非常明显。
    发明内容
    本发明的目的在于,提出一种新的压缩比特位图索引的方法(Improved COMPAX,ICX),用以解决目前位图索引压缩算法中存在的问题。
    为实现上述目的,本发明提出的技术方案是,一种新的压缩比特位图索引的方法,其特征是所述方法包括下列步骤:
    步骤1:把待压缩的01比特序列分成以31bits为单位的块,对块进行分类标记;
    步骤2:根据ICX码本与编码规则,在码本编码FL序列基础上,进一步编码。
    所述步骤1中把待压缩的01比特序列分成以31bits为单位的块,对块进行分类标记,具体包括:F-块和L-块,L块又分为C-L-块,0-NI-L-块和1-NI-L块,0-NI2-L块,1-NI2-L块。
    所述0-NI-L-块的定义为:一个L-块(补0后)与全0字比较,差异比特在同一个字节内,则记做0-NI-L-块。
    所述1-NI-L-块的定义为:一个L-块(补1后)与全1字比较,差异比特在同一个字节内,则记做0-NI-L-块。
    所述0-NI2-L-块的定义为:一个L-块(补0后)与全0字比较,差异比特在同2个字节内,则记做0-NI2-L-块。
    所述1-NI2-L-块的定义为:一个L-块(补1后)与全1字比较,差异比特在同2个字节内,则记做1-NI2-L-块。
    所述步骤2中根据ICX码本与编码规则,在码本编码FL序列基础上,进一步编码,具体包括:L-字编码,F-字编码,FLF-字编码,LFL-字编码,NI-FL字编码,NI2-FL字编码。
    所述FLF-字编码的定义为:对满足[1个或多个同类型F-块]-[1个0-NI-L块或者1-NI-L块]-[1个或多个同类型的F-块]的块组合进行编码。
    所述LFL-字编码的定义为:对满足[一个NI-L-块]-[1个或多个F-块]-[一个NI-L块]的块组合进行编码。
    所述NI-FL-字编码的定义为:对满足[一个NI-LF块]-[一个或者 多个同类型F块]的块组合进行编码。
    所述NI-FL-字编码的定义为:对满足[一个NI2-LF块]-[一个或多个同类型的F-块]的块组合进行编码。
    本发明的有益效果在于ICX比COMPAX有更好的编码效率。
    附图说明
    图1是Bitmap索引示例。
    图2是WAH算法示例。
    图3是PLWAH32算法示例。
    图4是PLWAH+adaptive counter:(以PLWAH32,s=1为例)。
    图5是COMPAX算法。
    图6是将1个C-L-块编码为L-字。
    图7是当原比特序列中连续出现7个0-F-块时的编码结果。
    图8是当原比特序列中连续出现3个1-F-块时的编码结果。
    图9是通过COMPAX和ICX算法分别将原比特序列编码为FLF。
    图10是用ICX将原比特序列编码为FLF,用COMPAX将原比特序列编码为一个F字+一个L字+一个F字。
    图11是可以被COMPAX和ICX两种方式编码为LFL的一个原比特序列。
    图12是不可以被COMPAX方式编码为LFL,只能被ICX编码为LFL的一个原比特序列。
    图13是图12中的原比特序列被COMPAX编码的结果。
    图14是不可以被COMPAX方式编码为LFL,只能被ICX编码为LFL的一个原比特序列。
    图15是图14中的原比特序列被COMPAX编码的结果。
    图16是NI-L类型且第二个是Fill时编码的流程图。
    图17是无法被WAH和COMPAX进行编码的一个原比特序列。
    图18是NI2-FL字编码中第6-8位的编码规则。
    图19是无法被WAH和COMPAX进行编码的一个原比特序列。
    图20是ICX的码本。
    具体实施方式
    下面结合附图,对优选实施例作详细说明。应该强调的是,下述说明仅仅是示例性的,而不是为了限制本发明的范围及其应用。
    本发明解决问题的思路是完成ICX算法:首先,对01比特序列进行有效压缩的算法,通过设计的ICX码本,对符合特征的01串转换为两类31比特块,称为F-块和L-块,L块又分为C-L-块,0-NI-L-块和1-NI-L块,0-NI2-L-块和1-NI2-L块;然后,根据ICX码本与编码规则,在码本编码FL序列基础上,进一步编码,具体包括:L-字编码,F-字编码,FLF-字编码,LFL-字编码,NI-FL字编码,NI2-FL字编码。
    下面以互联网流量大数据检索系统为例,实现ICX位图索引压缩算法。
    基于提出位图索引编码的大数据检索系统实现分成三个??椋菏?据预处理???,位图索引构建???,数据检索???。
    1数据预处理??椋?
    在数据进入??橹坝性ご砉?,以动态和静态模式进行数据处理。对于静态模式(对于已经存储的原始数据文件进行重新处理来实现压缩与构建索引),将数据文件中的数据项利用局部敏感函数(LSH,相近的数据项得到的哈希值也相近)计算哈希值,并按照哈希值顺序进行重排序(reorder)过程,之后将数据提交给数据压缩??橛胨饕菇?榻邢乱徊酱?。对于动态模式,用一段固定存储空间,缓存接收实时抓取的流量,当缓存数据达到上限时,提交给下一级来进行重排序的操作(类似于静态模式),之后数据提交给索引构建??榻邢乱徊酱?。而由于此时缓存已经被清空,可以继续接受网络上的实时流量,这样就实现了动态处理的过程。
    2位图索引构建??椋?
    位图编码部分为利用所提的编码方法,将原始位图编码成最终的位图索引文件,并进行存储。利用位图索引的理由是检索速度快,在实际对海量数据进行查找分析时相对更为实用与方便,但是位图本身的特点是空间占用巨大,会成为空间开销的主要负担,需要对于位图进行重新编码来降低此部分的空间开销。位图索引构建传统有两个步骤:位图生成与位图编码,也可以合二为一。
    3数据检索??椋?
    用户输入希望检索的条件,之后系统从构建的位图索引文件中依照索引查找对应的条目,可快速执行与,或,非与JOIN操作。如果 对索引文件全部解码的话,会造成巨大的时间开销与空间开销,因此引入了动态判断策略,输入检索条件通过动态判断策略的处理决定是部分解码(partial-decompression)还是全部解码(full-decompression).部分解码的方法是只对命中条目附近的块(block)进行解码并抽出检索命中的数据,而全部解码则利用在部分解码带来收益不大的场景,这样可以相对提高检索效率。
    下面的实施例是按照本发明提出的ICX算法对位图索引构建??橹械奈煌急嗦氩糠纸写?,将其原始位图编码成最终的位图索引文件,并进行存储的过程。
    下面结合附图说明本发明的具体实现方式。该方法包括如下的步骤:
    步骤1:把待压缩的01比特序列分成以31bits为单位的块,对块进行分类标记,可分为以下几类:Fill(F-块)和Literal(L-块),L-块又分为common-literal-chunk(C-L-块),0-nearly identical-literal-chunk(0-NI-L-块)和1-nearly identical-literal-chunk(1-NI-L块),0-nearly identical-2-literal-chunk(0-NI2-L块),1-nearly identical-2-literal-chunk(1-NI2-L块)。
    1.F-块,代表块中31比特全为0或者全为1,全为0的块定义为0-Fill块(下面简称0-F-块),全为1的块定义为1-Fill块(下面简称1-F-块)。
    2.L-块,代表块中31比特不全为0且不全为1。
    3.将31比特块分为7-8-8-8四部分,最前面补上一位空白位(不 一定是零,下面会分情况说明),构成四个字节(一个32位字),如果和一个全0字比较,空白位置0;如果和全1字比较,空白位置1。
    定义Nearly Identical块为如下四种类型:
    1.如果一个L-块(补0后)与全0字比较,差异比特在同一个字节内,则认为这个L-块和一个0-F-块是nearly identical的,记作0-NI-L-块;
    2.如果一个L-块(补1后)与全1字比较,差异比特在同一个字节内,则认为这个L块和一个1-F-块是nearly identical的,记作1-NI-L-块;
    3.如果一个L-块(补0后)与全0字比较,差异比特在两个字节内,则认为这个L-块和一个0-F-块是nearly identical(type2)的,记作0-NI2-L-块;
    4.如果一个L-块(补1后)与全1字比较,差异比特在两个字节内,则认为这个L块和一个1-F-块是nearly identical的,记作1-NI2-L-块。
    5.其他的L-块记作C-L-块。
    步骤2:根据ICX码本与编码规则,在码本编码FL序列基础上,进一步编码。主要分为以下几种类型:Literal word(L-字)编码,Fill Word(F-字)编码,Fill-Literal-Fill Word(FLF-字)编码,Literal-Fill-Literal Word(LFL-字)编码,Fill(Nearly Identical)-Literal Word(NI-FL字)编码,Fill(Nearly Identical-Type Two)(NI2-FL字)编码。
    1.一个L-字是对1个C-L-块进行编码,编码方式为在这个C-L-块的最高位前补1构成一个字。图6是将1个C-L-块编码为L-字。
    2.一个F-字是对1个或多个同类型的F-块进行编码,前五位为类型标志位00000,第六位表示的为F-字所编码的F-块的类型(0为0-F-块,1为1-F-块),后26位为计数器(counter),标志着连续出现的同类型F-块的数量。
    图7是当原比特序列中连续出现7个0-F-块时的编码结果。
    图8是当原比特序列中连续出现3个1-F-块时的编码结果。
    3.一个FLF-字是对满足如下条件的块的组合进行编码:[1个或多个同类型F-块]-[1个0-NI-L块或者1-NI-L块]-[1个或多个同类型的F-块],或者说[F-字]-[NI-L块]-[F-字].(此处说F-字并不完全准确,但是首先COMPAX中原文写的也是Fill Word,且此处实质上也是对多个同类型F-块合并后所得,因此借用F-字概念,实际长度并非为一个字,FLF-字整个的长度为一个字,本段后文以及下一段中提到的F-字与此处均相同)
    前三位为字的类型标志位011,第四位为第一个F-字的类型(0为0-Fill,1为1-Fill.下同),第五位为第二个F-字的类型,第六位为NI-L块的类型(0为0-NI-L-块,1为1-NI-L-块),第七、八位为差异位所在字节的位置(从00到11,可表示四个字节)。第二个字节(9-16位)为第一个F-字的计数器,第三个字节(17-24位)为NL-块的差异字节(dirty byte,如果为第一个字节,则在最高位补一位,内容为NI-L块对应的类型,如果是其余三个字节中的一个的话原样复制即 可)。
    图9是通过COMPAX和ICX算法将原比特序列编码为FLF。
    图10是用ICX将原比特序列编码为FLF,用COMPAX将原比特序列编码为一个F字+一个L字+一个F字。ICX能够将原比特序列编码为FLF,但是由于原比特序列不满足COMPAX对于FLF的定义,COMPAX无法将原比特序列编码为FLF,只能编码为一个F字+一个L字+一个F字。
    4.一个LFL-字是对满足如下条件的块的组合进行编码:[一个NI-L-块]-[1个或多个F-块(或者直接称作F-字)]-[一个NI-L块].
    由于两个NL-块的类型不一定一致,因此前三位分配了两种编码方法:001表示两个NI-L-块类型相同,010表示两个NI-L-块类型不同。但二者仅在第四位的含义上有差别:
    对于001-:第四位表示两个NI-L块的类型。为0表示均为0-NI-L块,为1表示均为1-NI-L块。
    对于010-:第四位为0表示第一个为0-NI-L-块,第二个为1-NI-L块;第四位为1表示第一个为1-NI-L块,第二个为0-NI-L块。0为0-NI-L块,1为1-NI-L块。
    第5-6位表示第一个NI-L块的差异位所在字节的位置(00-11),第7-8位表示第二个NI-L块差异位所在字节的位置。第9-16位为第一个NI-L块的差异字节(dirty byte,与FLF中的复制方式相同),第17位为F-字类型标志位,第18-24位为F-字的计数器,第25-32位为第二个NI-L块的差异字节(dirty byte,与上文中的复制方式相同).
    例如:
    (1)图11是可以被COMPAX和ICX两种方式编码为LFL的一个原比特序列。它符合符合COMPAX和ICX对于LFL的定义,因此可以被两种方式编码。这里解释ICX的编码。由于从原比特序列可看出两个NI-L块均为0-NI-L块,因此为0;第5-6位标志第一个NI-L块差异字节位置,此处为01;第7-8位表示第二个NI-L块的差异字节位置,此处为11(需要在填入第二个NI-L块差异字节时补上NI-L块类型,对于本例相当于在第25位填0)。第17位标示F-字的类型,此处为0。
    (2)图12是不可以被COMPAX方式编码为LFL,只能被ICX编码为LFL的一个原比特序列。此时COMPAX无法将其归入LFL类。图13是图12中的原比特序列被COMPAX编码的结果??梢钥闯?,COMPAX将其编为Literal Word+1-Fill Word+Literal Word。而ICX可以将其归入LFL类型,因此此时ICX比COMPAX有更好的编码效率。
    (3)图14是不可以被COMPAX方式编码为LFL,只能被ICX编码为LFL的一个原比特序列。图15是图14中的原比特序列被COMPAX编码的结果。此时ICX比COMPAX有更好的编码效率。
    由上述(1)(2)(3)的例子可以看出当原比特序列只能被ICX编码为LFL,不可以被COMPAX编码为LFL时,ICX比COMPAX有更好的编码效率。
    5.一个NI-FL字是对满足如下条件的块的组合进行编码:[一个 NI-LF块]-[一个或者多个同类型F块(即1个F字)]。对于一个NI-FL字,前五位为类型标志位00001,第六位表示NI-L块的类型,第七、第八位表示NI-L块的差异位所在字节的位置,第9-16位为NI-L的差异位,第17位为Fill Word的类型,第18-32位作为Fill Word的计数器。
    由于编码过程中NI-FL字和FLF字的判断可能产生部分重叠,现将二者的编码过程区分如下:
    如果出现NI-L类型下一个是Fill:先判断计数器大小,如果小于128,且再下一个是NI-L类型,将这三个块编码成LFL;否则再考虑压缩成LF类型;如果上述情况均不满足,则为L和F分开的类型。图16是NI-L类型且第二个是Fill时编码的流程图。
    下面举例说明。
    图17是无法被WAH和COMPAX进行编码的一个原比特序列。由于WAH和COMPAX都无法对原比特序列进行编码,只能将图17中的原比特序列编码为一个L字+一个F字+一个L字的形式,但原比特序列能够满足ICX中对于NI-FL的定义,因此ICX将其编码为一个NI-FL字+一个L字,此时能够看出ICX相比于COMPAX有着更高的编码效率。
    6.一个NI2-FL字对于满足如下条件的块的组合进行编码:[一个NI2-LF块]-[一个或多个同类型的F-块].前四位为类型标志位0001,第五位为NI2-LF块的类型,第6-8位通过一定的编码方式来标示两个差异位的位置。图18是NI2-FL字编码中第6-8位的编码规则。
    第9-16位为第一个差异位的内容,第17-24位为第二个差异位的内容,第25位为Fill Word的类型,第26-32位为Fill Word的计数器。
    下面举例说明:
    图19是无法被WAH和COMPAX进行编码的一个原比特序列。由于WAH和COMPAX都没有办法对于原比特序列进行压缩,只能编成一个L字+一个F字的形式,而ICX能够将原比特序列压缩成一个NI2-LF字的形式。
    图20是ICX的码本。
    由上面的具体实施例可以看出ICX是以COMPAX为基础进行了改进,ICX的优点如下所示:
    1.对于FLF字情况:
    COMPAX只能处理两个F-字属于同种类且L-块为0-NI-L块的情况(事实上,COMPAX没有考虑1-NI-L块的所有情况),而ICX对于F-字是否同种类,以及NI-L块的类型没有要求,这样相当于扩展了大约三倍的可编码情况数(假定0-F字出现的概率和1-F字出现的概率相近,1-NI-L块和0-NI-L块出现的概率相近)。
    而在ICX可以处理而COMPAX无法处理的情况时COMPAX的编码效率退化成WAH(如FLF中的例2)。也就是说ICX比COMPAX有着更好的编码效率。
    2.对于LFL字情况:
    COMPAX只能处理两个L同为0-NI-L块这种情况,而ICX对于 NI-L的种类没有要求,这样相当于扩展了三倍的可编码情况数(假定1-NI-L块和0-NI-L块出现的概率相近,1-NI2-L块和0-NI2-L块出现的概率相近)。
    3.对于NI-LF字的情况
    如果无法满足LFL字,ICX可以对于NI-LF字这种情况进行处理,而COMPAX则直接编码成一个L字+一个F字。
    4.对于NI2-LF字的情况
    COMPAX中没有对于NI2-LF块的定义,因此无法对于这种情况进行进一步的压缩,而ICX对于这种情况进行了考虑并且可以将这两部分合并成为一个字。
    在上述ICX可处理而COMPAX无法处理的情况时,COMPAX的编码效率退化成WAH(如LFL中的例(2)、(3))。
    也就是说ICX比COMPAX有更好的编码效率。
    因此可知,对于互联网流量大数据检索系统中的位图索引构建???,ICX编码的效率比COMPAX更高。
    以上所述,仅为本发明较佳的具体实施方式,但本发明的?;し段Р⒉痪窒抻诖?,任何熟悉本技术领域的技术人员在本发明揭露的技术范围内,可轻易想到的变化或替换,都应涵盖在本发明的?;し段е?。因此,本发明的?;し段вΩ靡匀ɡ蟮谋;し段?。

    关于本文
    本文标题:一种新的压缩比特位图索引的方法.pdf
    链接地址://www.4mum.com.cn/p-6143621.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
  • 北京pk10怎么玩才赚钱 今天内蒙古时时开奖结果查询 赛车pk10一天开奖图片 平投方案 稳赚 扑克牌算命 七星彩在今晚开奖结果 11选5计划软件神器 在微信群赌博输了怎么办 足球2串1稳赚技巧月入十万 pk10人工免费计划app 分分彩后二复式稳赚方案 3d投注技巧与口诀 360足彩混合投注计算器 北京时时5分钟开奖号 玩北京pk10有赢到钱的人吗 11选5手机计划软件手机版