精华内容
下载资源
问答
  • 经常有人问,对于实时数据库,该如何计算存贮一年历史数据所需要的磁盘空间? 让我们以一个具体例子进行说明吧:一个项目中,总共有1万个模拟测点,这些测点平均每秒变化一次,每次变化均要保存,存贮一年历史...

    经常有人问,对于实时数据库,该如何计算存贮一年历史数据所需要的磁盘空间?

    让我们以一个具体例子进行说明吧:一个项目中,总共有1万个模拟量测点,这些测点平均每秒变化一次,每次变化均要保存,存贮一年历史数据,需要多少磁盘空间?

     

    为了很好地说明这个问题,我们先来分析一下,如果采用关系数据库来保存这些历史数据,需要多少磁盘空间。假定关系数据库采用一个表来保存历史数据,表的格式定义如下:

     

    字段名

    类型

    长度

    备注

    TagID

    整型

    4字节

    测点编号,1万个测点只需2字节整型,但考虑到最大保存测点可能超过65536,因此,定义为4字节整型

    Second

    整型

    4字节

    MillSecond

    短整型

    2字节

    毫秒

    Quality

    字节

    1字节

    质量戳

    Value

    双精度数

    8字节

     

    关系数据库中,计算历史数据应考虑如下几个方面的因素:

    管理文件

    表格式描述头

    数据

    索引

    其中,管理文件及表格式描述头可以忽略不计,只需要考虑数据和索引即可。另外,在此也不考虑日志文件的大小。

     

    假定关系数据库中不对数据进行任何压缩,采用定时保存,则数据容量的计算公式如下所示:

     

    数据容量=单条历史数据的尺寸*秒数*分钟数*小时数*天数*测点数

     

    所以,数据容量=(4+4+2+1+8)*60*60*24*365*10000=5580G

     

    假定对该表中的TagIDSecondMillSecond建立唯一索引,同时假定关系数据库的索引结构为B+树索引,一般的B+树的利用效率在40%左右,因此,索引大小的计算公式如下所示:

     

    索引容量=单条索引的尺寸*秒数*分钟数*小时数*天数*测点数/0.4

     

    所以,索引容量=(4+4+2)*60*60*24*365*10000/0.4=7342G

     

    因此,用关系数据库保存10000个每秒钟变化一次的双精度数,同时建立一个索引,需要磁盘空间为:12922G

    ------------------------------------------------------------------------------

    下面,我们再来计算一下实时数据库的历史数据容量的计算方法。

     

    首先要说明,不同的实时数据库对历史数据采用了不同的存贮方法,因此,计算方法也各不相同,在此,仅以我们自己的实时数据库为例,进行计算。

     

    首先需要介绍一下我们的实时数据库的特点:

    历史数据按时间段分为多个文件保存,每个文件保存一段时间内的历史数据,保存一年的历史数据大概需要60个文件;

    每段时间内的数据和索引保存在同一个文件内;

    测点的ID与其它数据在文件内分开保存。

     

    针对我们的实时数据库,计算历史数据应考虑如下几个方面的因素:

    管理文件

    文件头

    数据

    索引

     

    其中,管理文件的大小大概为100K左右,可以忽略。

     

    文件头大小=单个文件头大小*所有历史数据文件头大小=512K*60=0.03G,也可以忽略

     

    在完全不压缩的情况下,数据容量的计算公式为:

     

    不压缩数据容量=单条历史数据的尺寸*秒数*分钟数*小时数*天数*测点数

     

    其中,单条历史数据的尺寸已经过紧密化处理,只占14字节,所以,数据容量=14*60*60*24*365*10000=4111G

     

    实时数据库一般采用了特殊的索引机制,不需要对每条数据进行索引,平均200条数据才需要记录一次索引,在完全不压缩的情况下,索引容量的计算方法为:

     

    不压缩索引容量=单条索引的尺寸*秒数*分钟数*小时数*天数*测点数/200

     

    所以,索引容量=10*60*60*24*365*10000/200=15G

     

    最后,再考虑压缩率。采用不同的压缩算法会有不同的压缩比,另外,还与压缩率有关,这个没有统一的计算公式。但是,在工程现场,一般而言,采用哈佛曼算法的压缩比为15:1左右,采用变化压缩算法的压缩比为20:1左右,采用旋转门算法的压缩比为30:1左右。如果再加上一些特殊的技术(如二次压缩技术,质量戳与数据值分开保存等),压缩比可以达到40:1左右。我们就按40:1进行计算

     

    压缩后总容量=(不压缩数据容量+不压缩索引容量)/压缩比

     

    所以,以上例子中,实时数据库历史数据总容量=4111+15/40=103G

     

    注意,以上计算只考虑了双精度数测点,如果系统中还有开关量、字符串、单精度数,其中,开关量的变化可能非常缓慢,这些没有准确的计算公式,可以近似地处理为,将以上结果再除以4

     

    最后,给出一个在我们的实时数据库中,大致计算历史数据容量的公式:

     

    历史数据容量=年数*万点数*25/平均变化一次的秒数

    ---------------->就存储来说:RTDBDB 1/100



    ------------------------------------------------------------------------------------------------------------------------------------

    转自前辈的技术文章,深表感谢,http://blog.csdn.net/happypolo/article/details/6449332

    ------------------------------------------------------------------------------------------------------------------------------------

    展开全文
  • 备份数据占多少空间?其实,就效果而言,这往往会和数据类型以及存放方式直接相关,不同的方式以及不同的设备类型,产生的实际效果差异非常大,因此这个问题说实话是非常难用一句话来回答。但是,无论如何,备份数据...

     

    常常在工作中被问及,你们备份软件,重删效果如何?备份数据占多少空间?其实,就效果而言,这往往会和数据类型以及存放方式直接相关,不同的方式以及不同的设备类型,产生的实际效果差异非常大,因此这个问题说实话是非常难用一句话来回答。但是,无论如何,备份数据是需要磁盘空间进行存储的,在备份项目的设计过程中,必然会有备份存储库的容量设计。通常这个设计会直接关系到用户的存储成本、存储效率以及备份的可用性,因此这个设计在备份项目中非常关键,尽可能准确的设计存储容量和带宽,直接关系到项目的成败。

     

    这里我会以一个典型的虚拟化环境为例来说明应该如何去进行这个计算。

    环境信息:

    ESXi Host :25台

    VM:500个

    每个VM平均磁盘容量:200GB

    总Datastore使用容量:100TB

     

    带宽设计

    通常来说,备份过程中会有全备份和增量备份两种模式,一般情况下,首次备份是全备份,它将传输虚拟化环境中的所有数据至备份存储设备,因此这个传输量几乎为所有的Datastore的使用量;而后续的所有传输则是增量备份,传输的是虚拟化环境中的变化量,常见比较多的是每日变化量,本文暂时按照每日作为变化量的单位来计算。

    每个环境中,每日的变化量可以根据Veeam ONE的变化评估报告获取,是相对准确的数值,我这里假设这个变化量为7%。所以我们的到以下数值:

    首次传输数据量 : 100TB

    每天增量传输数据量:7TB

    开启Veeam的优化压缩重删后,假设这个重删能够达到常规的效果,实际传输数据为datastore容量的50%:

    首次真实传输数据量:50TB

    每天真实传输数据量:3.5TB

    因此我们需要的带宽计算如下,假设首次传输,我们可以开启周六24小时连续传输而后续增量备份则在每天业务空闲时20:00PM~6:00AM进行,除去备份作业的基础配置耗时后,我们大约估算实际数据传输时间为总耗时的80%,也就是10小时的备份工作时间内2小时为备份基础配置和等待时间,8小时为实际数据传输时间。因此简单的计算公式示例如下:

    全备份需要带宽:50*1024*8/(24*3600*80%)=5.93Gbps

    增量备份需要带宽:3.5*1024*8/(10*3600*80%)=1Gbps

    以上,我们可以看到这样的一个大概状况,那么在网络上和磁盘上的读写吞吐量可以按照这个数据去进行规划,配置相应数量的网卡/HBA卡以实现以上这样的一个备份吞吐量。

     

    容量设计

    根据不同的备份模式,在数据存储无任何重删技术的情况下,这个容量设计是最容易进行计算的,以下将以最常见的常见常规增量备份为例来说明计算方法,这也是一个比较简单的计算题。

    至少保留14份备份数据,每周执行1次全备份,每天进行1次增量备份。

    格式

    大小

    全备份

    1

    50 TB

    增量

    2

    3.5TB

    增量

    3

    3.5TB

    增量

    4

    3.5TB

    增量

    5

    3.5TB

    增量

    6

    3.5TB

    增量

    7

    3.5TB

    全备份

    8

    50 TB

    增量

    9

    3.5TB

    增量

    10

    3.5TB

    增量

    11

    3.5TB

    增量

    12

    3.5TB

    增量

    13

    3.5TB

    增量

    14

    3.5TB

    全备份

    15

    50 TB

    增量

    16

    3.5TB

    增量

    17

    3.5TB

    增量

    18

    3.5TB

    增量

    19

    3.5TB

    增量

    20

    3.5TB

    总容量估算:

    159.5TB

    +15%缓存剩余容量:

    23.9TB

    总计预估容量:

    183.43TB

     

    这就是常规的备份容量的设计思路,在这里我还有一个非常棒的工具推荐给大家,这是Veeam国外的同事制作的Veeam备份存储库容量规划工具,在这个工具中有更全面更详细的计算方法,可以根据实际情况输入更多数据来进行计算。这个在线工具地址如下,推荐在电脑上打开会比较好:

    http://vee.am/rps

     

    更正:

    上周容量计算一文中有处错误,在容量计算上,简单的计算题加法漏加了50TB,准确的容量应该为209.5TB,而增加缓存工作空间为31.4.TB,因此预计备份存储库容量应为240.9TB;

    展开全文
  • 数据量,海量数据 处理方法总结

    万次阅读 2010-09-22 17:17:00
    1.Bloom filter适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集基本原理及要点:对于原理来说很简单,位数组+k个独立hash函数。将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位...

    1.Bloom filter

    适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集

    基本原理及要点:
    对于原理来说很简单,位数组+k个独立hash函数。将hash函数对应的值的位数组置1,
    查找时如果发现所有hash函数对应位都是1说明存在,很明显这个过程并不保证查找的
    结果是100%正确的。同时也不支持删除一个已经插入的关键字,因为该关键字对应的位
    会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter,用一个
    counter数组代替位数组,就可以支持删除了。

    还有一个比较重要的问题,如何根据输入元素个数n,确定位数组m的大小及hash函数个
    数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下,m至少
    要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些,因为还要保证bit数
    组里至少一半为 0,则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底
    的对数)。

    举个例子我们假设错误率为0.01,则此时m应大概是n的13倍。这样k大概是8个。

    注意这里m与n的单位不同,m是bit为单位,而n则是以元素个数为单位(准确的说是不同
    元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通
    常都是节省的。

    扩展:
    Bloom filter将集合中的元素映射到位数组中,用k(k为哈希函数个数)个映射位是否
    全1表示元素在不在这个集合中。Counting bloom filter(CBF)将位数组中的每一位
    扩展为一个counter,从而支持了元素的删除操作。Spectral Bloom Filter(SBF)将
    其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。

    问题实例:给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G
    ,让你找出A,B文件共同的URL。如果是三个乃至n个文件呢?

    根据这个问题我们来计算下内存的占用,4G=2^32大概是40亿*8大概是340亿,n=50亿,
    如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿,相差并不多,这
    样可能会使出错率上升些。另外如果这些urlip是一一对应的,就可以转换成ip,则大
    大简单了。

    2.Hashing

    适用范围:快速查找,删除的基本数据结构,通常需要总数据量可以放入内存

    基本原理及要点:
    hash函数选择,针对字符串,整数,排列,具体相应的hash方法。
    碰撞处理,一种是open hashing,也称为拉链法;另一种就是closed hashing,也称开
    地址法,opened addressing。

    扩展:
    d-left hashing中的d是多个的意思,我们先简化这个问题,看一看2-left hashing。2
    -left hashing指的是将一个哈希表分成长度相等的两半,分别叫做T1和T2,给T1和T2
    分别配备一个哈希函数,h1和h2。在存储一个新的key时,同时用两个哈希函数进行计
    算,得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[
    key]位置,哪一个位置已经存储的(有碰撞的)key比较多,然后将新key存储在负载少
    的位置。如果两边一样多,比如两个位置都为空或者都存储了一个key,就把新key 存
    储在左边的T1子表中,2-left也由此而来。在查找一个key时,必须进行两次hash,同
    时查找两个位置。

    问题实例:
    1).海量日志数据,提取出某日访问百度次数最多的那个IP。

    IP的数目还是有限的,最多2^32个,所以可以考虑使用hash将ip直接存入内存,然后进
    行统计。

    3.bit-map

    适用范围:可进行数据的快速查找,判重,删除,一般来说数据范围是int的10倍以下

    基本原理及要点:使用bit数组来表示某些元素是否存在,比如8位电话号码

    扩展:bloom filter可以看做是对bit-map的扩展

    问题实例:

    1)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。

    8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。

    2)2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。

    将bit-map扩展一下,用2bit表示一个数即可,0表示未出现,1表示出现一次,2表示出
    现2次及以上。或者我们不用2bit来进行表示,我们用两个bit-map即可模拟实现这个
    2bit-map。

    4.堆

    适用范围:海量数据前n大,并且n比较小,堆可以放入内存

    基本原理及要点:最大堆求前n小,最小堆求前n大。方法,比如求前n小,我们比较当
    前元素与最大堆里的最大元素,如果它小于最大元素,则应该替换那个最大元素。这样
    最后得到的n个元素就是最小的n个。适合大数据量,求前n小,n的大小比较小的情况,
    这样可以扫描一遍即可得到所有的前n元素,效率很高。

    扩展:双堆,一个最大堆与一个最小堆结合,可以用来维护中位数。

    问题实例:
    1)100w个数中找最大的前100个数。

    用一个100个元素大小的最小堆即可。

    5.双层桶划分

    适用范围:第k大,中位数,不重复或重复的数字

    基本原理及要点:因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步
    确定范围,然后最后在一个可以接受的范围内进行。可以通过多次缩小,双层只是一个
    例子。

    扩展:

    问题实例:
    1).2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。

    有点像鸽巢原理,整数个数为2^32,也就是,我们可以将这2^32个数,划分为2^8个区域
    (比如用单个文件代表一个区域),然后将数据分离到不同的区域,然后不同的区域在利
    用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间,就可以很方便的解决。

    2).5亿个int找它们的中位数。

    这个例子比上面那个更明显。首先我们将int划分为2^16个区域,然后读取数据统计落
    到各个区域里的数的个数,之后我们根据统计结果就可以判断中位数落到那个区域,同
    时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域
    中的那些数就可以了。

    实际上,如果不是int是int64,我们可以经过3次这样的划分即可降低到可以接受的程
    度。即可以先将int64分成2^24个区域,然后确定区域的第几大数,在将该区域分成2^
    20个子区域,然后确定是子区域的第几大数,然后子区域里的数的个数只有2^20,就可
    以直接利用direct addr table进行统计了。

    6.数据库索引

    适用范围:大数据量的增删改查

    基本原理及要点:利用数据的设计实现方法,对海量数据的增删改查进行处理。
    扩展:
    问题实例:


    7.倒排索引(Inverted index)

    适用范围:搜索引擎,关键字查询

    基本原理及要点:为何叫倒排索引?一种索引方法,被用来存储在全文搜索下某个单词
    在一个文档或者一组文档中的存储位置的映射。

    以英文为例,下面是要被索引的文本:
    T0 = "it is what it is"
    T1 = "what is it"
    T2 = "it is a banana"
    我们就能得到下面的反向文件索引:
    "a":      {2}
    "banana": {2}
    "is":     {0, 1, 2}
    "it":     {0, 1, 2}
    "what":   {0, 1}
    检索的条件"what", "is" 和 "it" 将对应集合的交集。

    正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档
    有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中,文档
    占据了中心的位置,每个文档指向了一个它所包含的索引项的序列。也就是说文档指向
    了它包含的那些单词,而反向索引则是单词指向了包含它的文档,很容易看到这个反向
    的关系。

    扩展:

    问题实例:文档检索系统,查询那些文件包含了某单词,比如常见的学术论文的关键字
    搜索。

    8.外排序

    适用范围:大数据的排序,去重

    基本原理及要点:外排序的归并方法,置换选择 败者树原理,最优归并树

    扩展:

    问题实例:
    1).有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16个字节,内存
    限制大小是1M。返回频数最高的100个词。

    这个数据具有很明显的特点,词的大小为16个字节,但是内存只有1m做hash有些不够,
    所以可以用来排序。内存可以当输入缓冲区使用。

    9.trie树

    适用范围:数据量大,重复多,但是数据种类小可以放入内存

    基本原理及要点:实现方式,节点孩子的表示方式

    扩展:压缩实现。

    问题实例:
    1).有10个文件,每个文件1G, 每个文件的每一行都存放的是用户的query,每个文件
    的query都可能重复。要你按照query的频度排序 。

    2).1000万字符串,其中有些是相同的(重复),需要把重复的全部去掉,保留没有重复的
    字符串。请问怎么设计和实现?

    3).寻找热门查询:查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不
    超过3百万个,每个不超过255字节。

    10.分布式处理 mapreduce

    适用范围:数据量大,但是数据种类小可以放入内存

    基本原理及要点:将数据交给不同的机器去处理,数据划分,结果归约。

    扩展:

    问题实例:

    1).The canonical example application of MapReduce is a process to count the
    appearances of

    each different word in a set of documents:
    void map(String name, String document):
    // name: document name
    // document: document contents
    for each word w in document:
    EmitIntermediate(w, 1);

    void reduce(String word, Iterator partialCounts):
    // key: a word
    // values: a list of aggregated partial counts
    int result = 0;
    for each v in partialCounts:
    result += ParseInt(v);
    Emit(result);
    Here, each document is split in words, and each word is counted initially
    with a "1" value by

    the Map function, using the word as the result key. The framework puts
    together all the pairs

    with the same key and feeds them to the same call to Reduce, thus this
    function just needs to

    sum all of its input values to find the total appearances of that word.

    2).海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。

    3).一共有N个机器,每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如
    何找到N^2个数的中数(median)?


    经典问题分析

    上千万or亿数据(有重复),统计其中出现次数最多的前N个数据,分两种情况:可一次
    读入内存,不可一次读入。

    可用思路:trie树+堆,数据库索引,划分子集分别统计,hash,分布式计算,近似统
    计,外排序

    所谓的是否能一次读入内存,实际上应该指去除重复后的数据量。如果去重后数据可以
    放入内存,我们可以为数据建立字典,比如通过 map,hashmap,trie,然后直接进行
    统计即可。当然在更新每条数据的出现次数的时候,我们可以利用一个堆来维护出现次
    数最多的前N个数据,当然这样导致维护次数增加,不如完全统计后在求前N大效率高。

    如果数据无法放入内存。一方面我们可以考虑上面的字典方法能否被改进以适应这种情
    形,可以做的改变就是将字典存放到硬盘上,而不是内存,这可以参考数据库的存储方
    法。

    当然还有更好的方法,就是可以采用分布式计算,基本上就是map-reduce过程,首先可
    以根据数据值或者把数据hash(md5)后的值,将数据按照范围划分到不同的机子,最好
    可以让数据划分后可以一次读入内存,这样不同的机子负责处理各种的数值范围,实际
    上就是map。得到结果后,各个机子只需拿出各自的出现次数最多的前N个数据,然后汇
    总,选出所有的数据中出现次数最多的前N个数据,这实际上就是reduce过程。

    实际上可能想直接将数据均分到不同的机子上进行处理,这样是无法得到正确的解的。
    因为一个数据可能被均分到不同的机子上,而另一个则可能完全聚集到一个机子上,同
    时还可能存在具有相同数目的数据。比如我们要找出现次数最多的前100个,我们将
    1000万的数据分布到10台机器上,找到每台出现次数最多的前 100个,归并之后这样不
    能保证找到真正的第100个,因为比如出现次数最多的第100个可能有1万个,但是它被
    分到了10台机子,这样在每台上只有1千个,假设这些机子排名在1000个之前的那些都
    是单独分布在一台机子上的,比如有1001个,这样本来具有1万个的这个就会被淘汰,
    即使我们让每台机子选出出现次数最多的1000个再归并,仍然会出错,因为可能存在大
    量个数为1001个的发生聚集。因此不能将数据随便均分到不同机子上,而是要根据hash
    后的值将它们映射到不同的机子上处理,让不同的机器处理一个数值范围。

    而外排序的方法会消耗大量的IO,效率不会很高。而上面的分布式方法,也可以用于单
    机版本,也就是将总的数据根据值的范围,划分成多个不同的子文件,然后逐个处理。
    处理完毕之后再对这些单词的及其出现频率进行一个归并。实际上就可以利用一个外排
    序的归并过程。

    另外还可以考虑近似计算,也就是我们可以通过结合自然语言属性,只将那些真正实际
    中出现最多的那些词作为一个字典,使得这个规模可以放入内存。

    展开全文
  • 浅析数据压缩算法

    千次阅读 2017-05-17 15:51:17
    数据压缩是减少信息传输最经济直接的办法,所以这篇文章将讲解一些经典的数据压缩算法。 一 热身:基因组 对于生物学的基因研究中,A、C、T、G是是用来表示生物DNA的四种碱基,对基因序列的处理实际上是对这四种...

    数据压缩是减少信息传输量最经济直接的办法,所以这篇文章将讲解一些经典的数据压缩算法。

    一 热身:基因组

    对于生物学的基因研究中,A、C、T、G是是用来表示生物DNA的四种碱基,对基因序列的处理实际上是对这四种碱基的处理,因此为了解决这种字符种类较少且固定的字符序列,我们可以用双位编码(用2bit位可以表示四中字符)压缩来解决这个问题。在这种方法中,只需要建立字母表即可对字符序列进行压缩和展开。

    例如有以下DNA序列:ATAGAGCATA,我们可以建立以下字母表:

    A 00
    C 01
    T 10
    G 11

    对应的压缩编码如下:00100011001101001000

    二 游程编码(RLE)

    游程编码是一种无损压缩编码,JPEG图片压缩就用此方法。比特流中最简单的冗余相识就是一长串重复的比特,我们可以利用游程编码来压缩冗余数据。例如下面这条40位长的字符串:

    0000000000000001111111000000011111111111

    该字符串含有15个0,7个1,7个0以及11个1,因此我们将该字符压缩为15,7,7,1。所有字符串都是有交替出现的01组成的,因此我们是需要将游程的长度编码即可。在这个例子中用4位表示长度,那么就可以得到一个16位长的字符串(15=1111,7=0111,7=0111,1=0001):

    1111011101110001

    压缩率为16/40=40%。

    对于游程编码,我们有以下约定:

    1 游程长度应在0-255之间,用8位编码

    2 在需要的情况下使用长度为0的游程来保证所有游程长度不超过256

    3 对于较短的游程也会编码,但这样有可能是输入变长

    该方法并不适合含有大量短游程的输入,只有在游程长度大于将他们用二进制表示所需的长度时才能节省空间。


    三 霍夫曼压缩

    哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号,长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示,而不常见的符号需要很多位来表示。哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而,它并不处理符号的顺序和重复或序号的序列。

    图 2.2 显示了一个 10 个字节的未压缩的数据。根据符号频率,哈夫曼编码器生成哈夫曼树(图 2.4 )和相应的编码表示(图 2.3 )。

    压缩后的数据流是 24 位(三个字节),原来是 80 位( 10 个字节)。当然,我应该存储霍夫曼树,这样解码器就能够解码出对应的压缩流了,这就使得该例子中的真正数据流比输入的流数据量大。这是相对较短的数据上的副作用。对于大数据量来说,上面的哈夫曼树就不占太多比例了。

    四 LZW压缩

    LZW压缩是一种无损压缩,应用于gif图片。适用于数据中存在大量重固子串的情况。

    1 原理

    LZW算法中,首先建立一个字符串表,把每一个第一次出现的字符串放入串表中,并用一个数字来表示,这个数字与此字符串在串表中的位置有关,并将这个数字存入压缩文件中,如果这个字符串再次出现时,即可用表示它的数字来代替,并将这个数字存入文件中。压缩完成后将串表丢弃。如"print" 字符串,如果在压缩时用266表示,只要再次出现,均用266表示,并将"print"字符串存入串表中,在图象解码时遇到数字266,即可从串表中查出266所代表的字符串"print",在解压缩时,串表可以根据压缩数据重新生成。

    该算法最令人惊讶的特性在于,和霍夫曼编码不同,输出中并不需要附上这张串表,而霍夫曼编码要将霍夫曼树存储在输出中,在解码中使用。

    2 适用范围

    举个例子,原来的数值范围可以用8bit来表示,那么就认为原始的数的范围是0~255,压缩程序生成的标号的范围就不能为0~255(如果是0-255,就重复了)。只能从256开始,但是这样一来就超过了8位的表示范围了,所以必须要扩展数据的位数,至少扩展一位,但是这样不是增加了1个字符占用的空间了么?但是却可以用一个字符代表几个字符,比如原来255是8bit,但是现在用256来表示254,255两个数,还是划得来的。从这个原理可以看出LZW算法的适用范围是原始数据串最好是有大量的子串多次重复出现,重复的越多,压缩效果越好。反之则越差,可能真的不减反增了

    假设需要读取一列由7位ASC码编码的字符串ABRACADABRABRABRA,则需要扩展一位,用8位来表示。为了简单起见用十六进制来表示,这样A的编码为41等等。我们将80(10000000)作为结束标志,将其余编码值(81-FF)作为标号。

    编码过程:

    前缀 后缀 Entry(前缀+后缀) 是否存在 输出 Entry标号
      A (,A)      
    A B (A,B) N 41(A) 81
    B R (B,R) N 42(B) 82
    R A (R,A) N 52(R) 83
    A C (A,C) N 41(A) 84
    C A (C,A) N 43(C) 85
    A D (A,D) N 41(A) 86
    D A (D,A) N 44(D) 87
    A B (A,B) Y    
    AB R (AB,R) N 81(AB) 88
    R A (R,A) Y    
    RA B (RA,B) N 83(RA) 89
    B R (B,R) Y    
    BR A (BR,A) N 82(BR) 8A
    A B (A,B) Y    
    AB R (AB,R) Y    
    ABR A (ABR,A) N 88(ABR) 8B
    A   (A,)   41(A)  
            80(End)  

    编码后输出:41 42 52 41 43 41 44 81 83 82 88 41 80

    输入为17个7位ASC字符,总共119位,输出为13个8位编码,总共104位,压缩比为87%。

    解码过程:

    对输出的41 42 52 41 43 41 44 81 83 82 88 41 80进行解码,如下表所示

    前缀 后缀 Entry 是否存在 输出 Entry标号
    41(A) 42(B) (A,B) N A 81
    42(B) 52(R) (B,R) N B 82
    52(R) 41(A) (R,A) N R 83
    41(A) 43(C) (A,C) N A 84
    43(C) 41(A) (C,A) N R 85
    41(A) 44(D) (A,D) N A 86
    44(D) 81(AB) (D,A) N D 87
    81(AB) 83(RA) (AB,R) N AB 88
    83(RA) 82(BR) (RA,B) N RA 89
    82(BR) 88(ABR) (BR,A) N BR 8A
    88(ABR) 41(A) (ABR,A) N ABR 8B
    41(A) 80(End) (A,)   A  

    解码后输出:ABRACADABRABRABRA

    特殊标记:

    随着新的串(string)不断被发现,标号也会不断地增长,如果原数据过大,生成的标号集(string table)会越来越大,这时候操作这个集合就会产生效率问题。如何避免这个问题呢?Gif在采用lzw算法的做法是当标号集足够大的时候,就不能增大了,干脆从头开始再来,在这个位置要插入一个标号,就是清除标志CLEAR,表示从这里我重新开始构造字典,以前的所有标记作废,开始使用新的标记
    这时候又有一个问题出现,足够大是多大?这个标号集的大小为比较合适呢?理论上是标号集大小越大,则压缩比率就越高,但开销也越高。 一般根据处理速度和内存空间连个因素来选定。GIF规范规定的是12位,超过12位的表达范围就推倒重来,并且GIF为了提高压缩率,采用的是变长的字长。比如说原始数据是8位,那么一开始,先加上一位再说,开始的字长就成了9位,然后开始加标号,当标号加到512时,也就是超过9为所能表达的最大数据时,也就意味着后面的标号要用10位字长才能表示了,那么从这里开始,后面的字长就是10位了。依此类推,到了2^12也就是4096时,在这里插一个清除标志,从后面开始,从9位再来。
    GIF规定的清除标志CLEAR的数值是原始数据字长表示的最大值加1,如果原始数据字长是8,那么清除标志就是256,如果原始数据字长为4那么就是16。另外GIF还规定了一个结束标志END,它的值是清除标志CLEAR再加1。由于GIF规定的位数有1位(单色图),4位(16色)和8位(256色),而1位的情况下如果只扩展1位,只能表示4种状态,那么加上一个清除标志和结束标志就用完了,所以1位的情况下就必须扩充到3位。其它两种情况初始的字长就为5位和9位。此处参照了http://blog.csdn.net/whycadi/

    五 参考文章

    http://www.cnblogs.com/jillzhang/archive/2006/11/06/551298.html

    算法(第四版)

    展开全文
  • 数据压缩知识点整理

    千次阅读 2017-04-27 16:57:20
    数据压缩 是指在丢失有用信息的前提下, 缩减数据量 以减少存储空间, 提高传输、存储和处理效率, 或按照一定的算法对数据进行重新组织, 减少数据的冗余和存储的空间的一种技术.
  • 音视频压缩技术是编解码中难点,常常会涉及很多算法...未经压缩的数字视频的数据量巨大 存储困难:一张DVD只能存储几秒钟的未压缩数字视频。 传输困难 : 1兆的带宽传输一秒的数字电视视频需要大约4分钟。 压缩编码的重
  • 深入理解数据压缩与重复数据删除

    万次阅读 热门讨论 2011-04-14 20:29:00
    数据压缩与重复数据删除两种技术有何区别与联系呢?实际中又该如何正确应用呢?笔者之前对数据压缩原理和技术没有研究,因此做了点功课,查阅整理了相关资料,并与重复数据删除技术进行对比分析。
  • 无损数据压缩算法的历史

    万次阅读 多人点赞 2014-09-20 00:00:24
    有损压缩主要用来存储图像和音频文件,同时通过移除数据可以达到一个比较高的压缩率,不过本文讨论无损压缩。无损压缩,也使文件变小,但对应的解压缩功能可以精确的恢复原文件,丢失任何数据。无损数据压缩被...
  • 数据压缩的本质

    千次阅读 2019-03-31 03:05:21
    对于一个给定的图,其信息是固定的,图划分会给图的信息带来什么?图的划分或者折叠,是否就是对图的压缩呢? 先来个小例子:有一段文字“我我我我我我有点喜欢喜欢喜欢喜欢lxlxlxlxlxlxlx”一共14个汉字加上14个...
  • 然而,随着场景规模的增大,大规模虚拟场景中往往包含上万个多边形,甚至多达几百万个多边形和几百兆的高分辨率纹理数据。同时,系统不仅要对几何数据进行坐标变换与纹理加载等处理,还要在此基础上,为增进仿真效果...
  • 数据重删压缩

    千次阅读 2016-02-24 15:17:53
    另外一项节约存储空间的技术是数据压缩数据压缩技术在比较小的范围内以比较小的粒度查找重复数据,粒度一般为几个比特到几个字节。而重复数据删除是在比较大的范围内查找大块的重复数据,一般重复数据
  • 数据量的问题是很多面试笔试中经常出现的问题,比如baidu google 腾讯 这样的一些涉及到海量数据的公司经常会问到 下面的方法是我对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并能完全覆盖...
  • 数据压缩】Huffman原理与代码实现

    万次阅读 2015-12-21 23:00:14
    Huffman算法也是一种无损压缩算法,但与上篇文章LZW压缩算法不同,Huffman需要得到每种字符出现概率的先验知识。通过计算字符序列中每种字符出现的频率,为每...Huffman编码为最优前缀码,即压缩数据量最小。 -------
  • 润乾V4 润乾报表 大数据量 导出excel 打包输出
  • Hadoop:数据压缩、Yarn、企业优化

    万次阅读 2020-06-03 20:41:20
    Hadoop数据压缩、Yarn架构以及工作流程、Hadoop企业优化方案
  • “为什么进行压缩”,我的理解是:网络的快速发展及大数据时代的到来,給我们的生活带来更便利的同时也大大增加了信息和数据的大量传输,我们的网络宽带有限,还有存储容量的问题,如果对传输信息数据不进行压缩,...
  • 网络压缩-量化方法对比

    千次阅读 2016-06-15 08:58:03
    本次介绍的是一种压缩神经网络模型大小的方法,来自《2014 arxiv:Compressing Deep Convolutional Networks using Vector Quantization》。该方法和很多之前的神经网络压缩方法一样,基本只对全连接层有效,因此...
  • 音视频数据压缩及编解码基础

    千次阅读 2017-03-07 15:10:35
    音视频数据压缩及编解码基础 ... 音视频压缩技术是编解码中难点,常常会涉及很多算法处理问题。数据封装,转封装等,看下Agenda: ...音视频为何需要压缩?...常用压缩编码的方法 编码器中的关键技术 
  • 数据量及海量数据处理算法总结

    千次阅读 2017-11-03 15:58:27
    下面的一些问题基本直接来源于公司的面试笔试题目,方法不一定最优,如果你有更好的处理方法,欢迎与我讨论。  1.Bloom filter  适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集  基本...
  • 声音文件大小的计算方法

    千次阅读 2013-12-21 23:21:13
    采样频率越大,采样点之间的间隔就越小,数字化后得到的声音就越逼真,但相应的数据量就越大。声卡一般提供11.025kHz、22.05kHz和44.1kHz等不同的采样频率。 采样位数是记录每次采样值数值大小的位数。采样位数通常...
  • 数据量的算法面试题

    万次阅读 2016-08-19 15:16:28
    何谓海量数据处理?...何谓海量,就是数据量太大,所以导致要么是无法在较短时间内迅速解决,要么是数据太大,导致无法一次性装入内存。  那解决办法呢?针对时间,我们可以采用巧妙的算法搭配合适的数据结构
  • LZO--实时数据压缩

    千次阅读 2017-04-15 14:42:37
    首先从网址https://www.oberhumer.com/opensource/lzo/下载LZO源代码,解压缩后的文件:lzo-2.10 doc/LZO.TXT
  • 由香农定理看数据压缩的本质

    千次阅读 2014-04-01 10:40:17
    开门见山上结论:所谓的压缩就是在损失信息的前提下,用新的描述方式表示原有的数据,而这种方式占用的空间更少。  先来个小例子:有一段文字“我我我我我我有点喜欢喜欢喜欢喜欢xlxlxlxlxlxlxl”一共14个汉字...
  • 索引压缩

    千次阅读 2017-08-10 16:59:27
    当待搜索的数据量极为庞大时,数据所对应的索引的数据量也会非常大。就拿最常见的倒排索引来说,特别是当用户查询的关键词是常用词时,这些词所对应的倒排列表可以达到几百兆,而将这样庞大的索引由磁盘读入内存,...
  • 第七章数据压缩技术

    千次阅读 2016-04-30 10:13:26
    第七章 数据压缩技术 ...     本章导读 前面的章节已经介绍了海量数据的存储、查询、分区、容错等技术,这些技术对于海量数据的处理是必...数据压缩是指在丢失信息的前提下,缩减数据量以减少存储空间,提高其传输
  • 使用GZIP和Zip压缩Java数据

    千次阅读 2018-06-15 09:51:16
    转载自 使用GZIP和Zip压缩Java数据流本文通过对数据压缩算法的简要介绍,然后以详细的示例演示了利用java.util.zip包实现数据压缩与解压,并扩展到在网络传输方面如何应用java.util.zip包现数据压缩与解压综述...
  • 然而,随着场景规模的增大,大规模虚拟场景中往往包含上万个多边形,甚至多达几百万个多边形和几百兆的高分辨率纹理数据。同时,系统不仅要对几何数据进行坐标变换与纹理加载等处理,还要在此基础上,为增进仿真效果...
  • 无损压缩经典算法

    万次阅读 多人点赞 2016-10-25 22:54:04
    进行文件压缩的必要性像图片、声音、视频这些类型的多媒体数据要比文本数据占用多得多的内存空间,尤其是视频文件,文件传输时占用带宽大,存储又占用大量的硬盘空间。举个例子:一个1080p分辨率
  • 数据压缩算法—2无损压缩算法

    千次阅读 2018-12-12 20:55:43
      字典算法是最为简单的压缩算法之一。它是把文本中出现频率比较多的单词或词汇组合做成一个对应的字典列表,并用特殊代码来表示这个单词或词汇。例如:   有字典列表:   00=Chinese   01=People   02=...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 199,908
精华内容 79,963
关键字:

不压缩数据量计算方法