数据压缩_数据压缩算法 - CSDN
  • 压缩算法 ...  数据压缩不仅起源于 40 年代由 Claude Shannon 首创的信息论,而且其基本原理即信息究竟能被压缩到多小,至今依然遵循信息论中的一条定理,这条定理借用了热力学中的名词“熵”( Ent...

      数据压缩,大多数都是涉及算法概念。我们可以通过下图可以明确数据压缩领域所涉及的方面。
      首先压缩算法分为无损压缩和有损压缩;
      无损压缩通过应用于文件和文本中,主要是熵编码法和字典编码,熵编码中最实用最流行的是霍夫曼编码的变种,字典编码最实用最流行的是LZ77和snappy;
      有损压缩主要应用于音频、图像和视频中,基于傅里叶变换、小波变换、离散余弦变换等进行数据降采样,减少数据量,而后会采用霍夫曼编码的变种等无损压缩算法。
      文本会继续更新各种无损、有损算法原理及其使用例程。
      https://zh.wikipedia.org/wiki/数据压缩
    在这里插入图片描述

    无损压缩算法

      无损压缩算法设计:对原始数据在单字符、单词或词组等不同单位上出现的频率构建统计模型,然后将频率最高的单位编码成最短的编码,但最短的编码永远小于整条信息的熵,即整条信息所需的位数。
      

    什么是熵

      数据压缩不仅起源于 40 年代由 Claude Shannon 首创的信息论,而且其基本原理即信息究竟能被压缩到多小,至今依然遵循信息论中的一条定理,这条定理借用了热力学中的名词“熵”( Entropy )来表示一条信息中真正需要编码的信息量:
      考虑用 0 和 1 组成的二进制数码为含有 n 个符号的某条信息编码,假设符号 Fn 在整条信息中重复出现的概率为 Pn,则该符号的熵也即表示该符号所需的位数位为:
      En = - log2( Pn )
      整条信息的熵也即表示整条信息所需的位数为:E = ∑En
      举个例子,对下面这条只出现了 a b c 三个字符的字符串:
      aabbaccbaa
      字符串长度为 10,字符 a b c 分别出现了 5 3 2 次,则 a b c 在信息中出现的概率分别为 0.5 0.3 0.2,他们的熵分别为:
      Ea = -log2(0.5) = 1
      Eb = -log2(0.3) = 1.737
      Ec = -log2(0.2) = 2.322
      整条信息的熵也即表达整个字符串需要的位数为:
      E = Ea * 5 + Eb * 3 + Ec * 2 = 14.855 位
      回想一下如果用计算机中常用的 ASCII 编码,表示上面的字符串我们需要整整 80 位呢!现在知道信息为什么能被压缩而不丢失原有的信息内容了吧。简单地讲,用较少的位数表示较频繁出现的符号,这就是数据压缩的基本准则。
      细心的读者马上会想到,我们该怎样用 0 1 这样的二进制数码表示零点几个二进制位呢?确实很困难,但不是没有办法。一旦我们找到了准确表示零点几个二进制位的方法,我们就有权利向无损压缩的极限挑战了。
      

    模型

      从上面的描述,我们明白,要压缩一条信息,首先要分析清楚信息中每个符号出现的概率。不同的压缩程序通过不同的方法确定符号的出现概率,对符号的概率计算得越准确,也就越容易得到好的压缩效果。在压缩程序中,用来处理输入信息,计算符号的概率并决定输出哪个或哪些代码的模块叫做模型。
      难道对信息中字符的出现概率这么难以估计以至于有各种不同的压缩模型吗?对上面的字符串我们不是很容易就知道每个字符的概率了吗?是的是的,不过上面的字符串仅有 10 个字符长呀,那只是例子而已。考虑我们现实中要压缩的文件,大多数可是有几十 K 甚至几百 K 长,几 M 字节的文件不是也屡见不鲜吗?
      是的,我们可以预先扫描文件中的所有字符,统计出每个字符出现的概率,这种方法在压缩术语里叫做**“静态统计模型”。但是,不同的文件中,字符有不同的分布概率,我们要么先花上大量的时间统计我们要压缩的所有文件中的字符概率,要么为每一个单独的文件保存一份概率表以备解压缩时需要。糟糕的是,不但扫描文件要消耗大量时间,而且保存一份概率表也使压缩后的文件增大了不少。所以,在实际应用中,“静态统计模型”应用的很少。
      真正的压缩程序中使用的大多是一种叫
    “自适应模型”的东西。自适应模型可以说是一台具有学习功能的自动机。他在信息被输入之前对信息内容一无所知并假定每个字符的出现概率均等,随着字符不断被输入和编码,他统计并纪录已经出现过的字符的概率并将这些概率应用于对后续字符的编码。也就是说,自适应模型在压缩开始时压缩效果并不理想,但随着压缩的进行,他会越来越接近字符概率的准确值,并达到理想的压缩效果。自适应模型还可以适应输入信息中字符分布的突然变化,可以适应不同的文件中的字符分布而不需要保存概率表。
      上面提到的模型可以统称为
    “统计模型”**,因为他们都是基于对每个字符出现次数的统计得到字符概率的。另一大类模型叫做“字典模型”。实际上,当我们在生活中提到“工行”这个词的时候,我们都知道其意思是指“中国工商银行”,类似的例子还有不少,但共同的前提是我们心中都有一本约定俗成的缩写字典。字典模型也是如此,他并不直接计算字符出现的概率,而是使用一本字典,随着输入信息的读入,模型找出输入信息在字典中匹配的最长的字符串,然后输出该字符串在字典中的索引信息。匹配越长,压缩效果越好。事实上,字典模型本质上仍然是基于对字符概率的计算的,只不过,字典模型使用整个字符串的匹配代替了对某一字符重复次数的统计。可以证明,字典模型得到的压缩效果仍然无法突破熵的极限。
      当然,对通用的压缩程序来说,保存一本大字典所需的空间仍然是无法让人忍受的,况且,任何一本预先定义的字典都无法适应不同文件中数据的变化情况。对了,字典模型也有相应的“自适应”方案。我们可以随着信息的不断输入,从已经输入的信息中建立合适的字典,并不断更新这本字典,以适应数据的不断变化。
      让我们从另一个角度理解一下自适应模型。Cluade Shannon 曾试图通过一个“聚会游戏”(party game)来测定英语的真实信息容量。他每次向听众公布一条被他隐藏起一个字符的消息,让听众来猜下一个字符是什么,一次猜一个,直到猜对为止。然后,Shannon 使用猜测次数来确定整个信息的熵。在这个实验中,一种根据前面出现过的字符估计下一个字符概率的模型就存在于听众的头脑中,比计算机中使用的自适应模型更为高级的是,听众除了根据字符出现过的次数外,还可以根据他们对语言的经验进行猜测。
      

    编码

      通过模型,我们已经确定了对某一个符号该用多少位二进制数进行编码。现在的问题是,如何设计一种编码方案,使其尽量精确地用模型计算出来的位数表示某个符号。
      最先被考虑的问题是,如果对 a 用 3 个二进制位就可以表示,而对 b 用 4 个二进制位就可以表示,那么,在解码时,面对一连串的二进制流,我怎么知道哪三个位是 a,哪四个位是 b 呢?所以,必须设计出一种编码方式,使得解码程序可以方便地分离每个字符的编码部分。于是有了一种叫**“前缀编码”**的技术。该技术的主导思想是,任何一个字符的编码,都不是另一个字符编码的前缀。反过来说就是,任何一个字符的编码,都不是由另一个字符的编码加上若干位 0 或 1 组成。
      看一下前缀编码的一个最简单的例子:
      符号 编码
      A  0
      B  10
      C  110
      D  1110
      E  11110
      有了上面的码表,你一定可以轻松地从下面这串二进制流中分辨出真正的信息内容了:
      1110010101110110111100010 - DABBDCEAAB
      下一个问题是:象上面这样的前缀编码只能表示整数位的符号,对几点几位的符号只能用近似的整数位输出,那么怎样输出小数位数呢?科学家们用算术编码解决了这个问题。
      

    总结一下

      不同的模型使用不同的方法计算字符的出现概率,由此概率可以得出字符的熵;然后使用不同的编码方法,尽量接近我们期望得到的熵值。所以,压缩效果的好坏一方面取决于模型能否准确地得到字符概率,另一方面也取决于编码方法能否准确地用期望的位数输出字符代码。换句话说,压缩 = 模型 + 编码。如下图所示:
          符号      概率      代码
      输入 ---------------> 模型 ---------------> 编码 ---------------> 输出
      
      
      
      
      

    展开全文
  • 数据压缩算法实现

    千次阅读 2017-06-25 00:10:24
    利用香农-费诺编码、霍夫曼编码、LZ编码、算术编码实现数据压缩
    • 实验目的

      利用香农-费诺编码、霍夫曼编码、LZ编码、算术编码实现数据压缩

    • 实验原理

      1、香农-费诺编码
        首先,将信源符号以概率递减的次序排列进来,将排列好的信源符号划分为两大组,使两组的概率和近于相同,并各赋予一个二元码符号“0”和“1”。然后将每一大组的信源符号再分成两组,使同一组的两个小组的概率和近于相同,并又分别赋予一个二元码符号。依次下去,直至每一个小组只剩下一个信源符号为止。这样,信源符号所对应的码符号序列则为编得的码字。译码原理,按照编码的二叉树从树根开始,按译码序列进行逐个的向其叶子结点走,直到找到相应的信源符号为止。之后再把指示标记回调到树根,按照同样的方式进行下一序列的译码到序列结束。如果整个译码序列能够完整的译出则返回成功,否则则返回译码失败。

      2、霍夫曼编码
        霍夫曼编码属于码词长度可变的编码类,是霍夫曼在1952年提出的一种编码方法,即从下到上的编码方法。同其他码词长度可变的编码一样,可区别的不同码词的生成是基于不同符号出现的不同概率。生成霍夫曼编码算法基于一种称为“编码树”(coding tree)的技术。算法步骤如下:
        (1)初始化,根据符号概率的大小按由大到小顺序对符号进行排序;
        (2)把概率最小的两个符号组成一个新符号(节点),即新符号的概率等 于这两个符号概率之和;
        (3)重复第2步,直到形成一个符号为止(树),其概率最后等于1;
        (4)从编码树的根开始回溯到原始的符号,并将每一下分枝赋值为1,上 分枝赋值为0。

      3、LZ编码
        在LZ算法中,离散信源的输出序列分解成长度可变的分组,码段(phrases)。每当信源输出字符组在最后位置加上一个字符后,与前面的一有已有码段都不相同时,把它作为一种新的码段引入。将这些码段列入一个位置词典,用来记载有码段的位置。在对一个新的码段编码时只要指出字典中现有码段的位置,把新的字符附在后面即可。

      4、算术编码
        算术编码的编码对象是一则消息或一个字符序列,其编码思路是将消息或字符序列表示成0和1之间的一个间隔上的一个浮点小数。 在进行算术编码之前,需要对字符序列中每个字符的出现概率进行统计,根据各字符出现概率的大小,将每个字符映射到[0 ,1]区间上的某个子区间中。然后,在利用递归算法,将整个字符序列映射到[0,1]区间上的某个间隔中。在进行编码时,只需从该间隔中任选一个小数,将其转化为二进制数。 符号序列越长,编码表示他的间隔就越小,表示这个间隔所需的二进制位数就越多,编码输出的码字就越长。
        在进行编码过程中,随着信息的不断出现,子区间按下列规律减小:
        a.新子区间左端=前子区间左端+当前子区间左端×前子区间长度
        b.新子区间长度=前子区间长度×当前子区间长度

    • 实验内容

      1、对于给定的信源的概率分布,用香农-费诺编码实现压缩
      2、对于给定的信源的概率分布,用霍夫曼编码实现压缩
      3、对于给定的信源的概率分布,用LZ编码实现压缩
      4、对于给定的信源的概率分布,用算术编码实现压缩

    • 实验过程

      1、香农-费诺编码

    function c=shannon(p)
    [p,index]=sort(p)   
    p=fliplr(p)    
    n=length(p)   
    pa=0    
    for i=2:n       
        pa(i)= pa(i-1)+p(i-1)
    end   
    k=ceil(-log2(p))    
    c=cell(1,n)    
    for i=1:n        
        c{i}=''
        tmp=pa(i)       
        for j=1:k(i)    
            tmp=tmp*2           
            if tmp>=1   
                tmp=tmp-1
                c{i}(j)='1'
            else               
                c{i}(j)='0'
            end
        end
    end     
    c = fliplr(c)  
    c(index)=c
    

    2、霍夫曼编码

    function c=huffman(p)
    n=size(p,2)
    if n==1
        c=cell(1,1)
        c{1}=''
        return
    end
    [p1,i1]=min(p)
    index=[(1:i1-1),(i1+1:n)]
    p=p(index)
    n=n-1
    [p2,i2]=min(p)
    index2=[(1:i2-1),(i2+1:n)]
    p=p(index2);
    i2=index(i2)
    index=index(index2)
    p(n)=p1+p2
    c=huffman(p)
    c{n+1}=strcat(c{n},'1')
    c{n}=strcat(c{n},'0')
    index=[index,i1,i2]
    c(index)=c
    

    3、LZ编码

    function LZmain()
    clc;
    fid=fopen('source.txt','r');
    seq=fread(fid);
    fclose(fid);
    seq=reshape(seq,1,length(seq));
    if ~isempty(seq)
        [entropy]=Entropy(seq); 
        [dictionary codelength]=LZcode(seq);
        avglength=((codelength*length(dictionary))/length(seq));
        disp(strcat('Entropy = ',num2str(entropy)));
        disp(strcat('Code length = ',num2str(codelength))); 
        disp(strcat('Average length = ',num2str(avglength)));    
        display('Encoded Sequence : Look encode.txt.');
        enseq=LZencode(dictionary);
        fiden=fopen('encode.txt','w');
        en=fwrite(fiden,enseq);
        fclose(fiden);
        display('Decoded Sequence : Look decode.txt.');
        deseq=LZdecode(dictionary);
        fidde=fopen('decode.txt','w');
        de=fwrite(fidde,deseq);
        fclose(fiden);        
    else
        display('Empty Sequence....');
    end
    end
    
    function [dictionary codelength]=LZcode(seq)
    l=length(seq);
    dictionary(1).sym=seq(1);
    k=2;
    index=0;
    str='';
    for i=2:l
        str=[str seq(i)];    
        for j=1:(k-1)
            index=0;
            if strcmp(dictionary(j).sym,str)
                index=1;
                break;
            end
        end    
        if (index==0)
            dictionary(k).sym=str;
            k=k+1;
            str='';       
        end
    end 
    codelength=fix(log2(k-1))+1;
    for i=1:(k-1)
        dictionary(i).code=dec2bin((i-1),codelength);   
    end
    end
    
    function decode=LZdecode(dictionary)
    ld=length(dictionary);
    decode='';
    for i=1:ld
        decode=[decode dictionary(i).sym];
    end
    end
    
    function encode=LZencode(dictionary)
    ld=length(dictionary);
    encode='';
    for i=1:ld
        encode=[encode dictionary(i).code];
    end
    end
    
    function [entropy]=Entropy(seq)
    alpha(1)=seq(1);
    prob(1)=1;
    l=length(seq);
    k=2;
    for i=2:l
        idx=find(alpha==seq(i));
        if isempty(idx)
            alpha(k)=seq(i);
            prob(k)=1;
            k=k+1;
        else
            prob(idx)=prob(idx)+1; 
        end
    end
    prob=prob./l;
    entropy=-prob.*log2(prob);
    entropy=sum(entropy(:));
    end
    

    4、算术编码

    function arithmetic
    S = input('请输入信源符号='); 
    P = input('请输入信源概率向量P=');
    str = input('输入编码的字符串=');
    l = 0;
    r = 1;
    d = 1;
    n = length(str);
    n_S = length(P);
    %**********处理第一个字符***********%
    for i=1:n
        flag = 0;
        for k = 1:n_S 
            if str(i)==S(k) 
                m=k;
                flag =1;
                break;
            end
        end
        if flag ==0 
            error('非信源字符');         
        end  
        %*********当前单个字符的左、右端以及长度处理**************%
        pl = 0;
        pr = 0; 
        for j = 1:m-1 
            pl = pl + P(j);    %左端
        end 
        pr = pl+P(m);     %右端    
        pd = pr-pl;         %子区间长度  
        %*********新子区间的左、右边界以及长度处理**************%
        if i == 1            %首字符
            l = pl;
            r = pr;
            d = pd; 
        else              %算术编码规则
            l = l+d*pl;
            d = d*pd;
            r = l+d;
        end 
        strl = strcat('第',int2str(i),'个符号的间隔左右边界:');
        disp(strl);
        format long;
        disp(l);disp(r);
    end
    strl = strcat('符号的间隔左右边界:');
    disp(strl);
    format long;
    disp(l);disp(r);
    end 
    
    • 实验结果
    >> clear; clc;
    >> P=[0.3 0.25 0.16 0.14 0.1 0.05];
    >> c1=shannon(P);
    c1 =     '00'    '01'    '100'    '101'    '1101'    '11110'
    
    >> c2=huffman(P);
    c2=     '11'    '01'    '00'    '100'    '1011'    '1010'
    
    >> clear; clc;
    >> arithmetic
    请输入信源符号='abcdef'
    请输入信源概率向量P=[0.3 0.25 0.16 0.14 0.1 0.05]
    输入编码的字符串='adbecf'1个符号的间隔左右边界:
       0
       0.3000000000000002个符号的间隔左右边界:
       0.213000000000000
       0.2550000000000003个符号的间隔左右边界:
       0.225600000000000
       0.2361000000000004个符号的间隔左右边界:
       0.234525000000000
       0.2355750000000005个符号的间隔左右边界:
       0.235102500000000
       0.2352705000000006个符号的间隔左右边界:
       0.235262100000000
       0.235270500000000
    符号的间隔左右边界:
       0.235262100000000
       0.235270500000000
    
    >> clear; clc;
    >> LZmain
    Entropy =5.8172
    Code length =8
    Average length =4.6126
    Encoded Sequence : Look encode.txt.
    Decoded Sequence : Look decode.txt.
    
    展开全文
  • 数据压缩的本质

    千次阅读 2019-03-31 03:05:21
    先来个小例子:有一段文字“我我我我我我有点喜欢喜欢喜欢喜欢lxlxlxlxlxlxlx”一共14个汉字加上14个字符,现在采用某种压缩算法,将其压缩为这样一种形式“6个我1个有点4个喜欢7个lx”一共9个汉字加上6个字符(包括...

    对超大规模网络进行划分,得到诸多子图,是否可以用熵来解决呢?对于一个给定的图,其信息量是固定的,图划分会给图的信息带来什么?图的划分或者折叠,是否就是对图的压缩呢?

    先来个小例子:有一段文字“我我我我我我有点喜欢喜欢喜欢喜欢lxlxlxlxlxlxlx”一共14个汉字加上14个字符,现在采用某种压缩算法,将其压缩为这样一种形式“6个我1个有点4个喜欢7个lx”一共9个汉字加上6个字符(包括数字跟字母),显然,总的空间变小了,这就是数据压缩。

            在这里我们只讨论无损压缩,先简单介绍一些有关香农定理的东西,香农这哥们研究的东西的确很有意义,我只能说他太有才了,想想我们随便说的一句话“明天我要发财了”,我想知道这句话到底包含多少信息量呢,在他之前没人搞出来这东西,他那一天才公式一下子解决了这个问题,用数学方法量化了信息量,具体是什么公式就不粘贴了,我们只需要知道根据相关概率可以计算出这句话的信息量,他称之为信息熵。

            下边来分析分析一个问题,有一段字符:aaabcdegxy,在理想情况下,每个字符都随机出现,那么单个字符的信息熵根据香农公式可以计算出来信息熵为4.7,这段10个字符总的信息量为47,但是,一般我们都知道,在人类的语言文字表达中,字符出现的概率并不是随机的,有的字符出现频率高,而有的低,下边的图有一些统计值,在这种情况下,每个字符的平均信息熵重新计算一下大约为2.6,远远小于完全随机的情况,这样10个字符总的信息量为26。

                                        

            好了,有了上边的概念之后,假如我们想要用一段字符描述自己所要表达的信息,也就是说我们要保证总的信息量,定下这个总量,下一步,如果想要用最少的字符来完成任务,那么每个字符的平均信息熵就必须保证要取最大,但是根据上一段的事实,我们在平时的表达中每个字符的平均信息熵并未达到最理想的4.7,所以,要完成这个任务,我们需要用更多的字符来表示,即用增大字符数量来解决,导致了空间浪费,这就是数据冗余的源泉,有什么办法解决这个问题呢,数据压缩正式登场,数据压缩就是要用一种新的描述形式使得单个字符的平均信息熵更大,那么总的信息量不变的前提下,所需的字符总数就会变小,这样就压缩了空间。

            下边再想一个问题,利用压缩软件我们可以大大减小文件大小,那能不能一直压缩下去,将压缩文件继续压缩,使它越来越小,要是能这样该多好。这个问题仔细想想就是一个我们初中都学过的能量守恒原理,我们说这个文件的信息总量是不变的,无论你怎么压缩,由于单个字符的信息熵有极限值,所以压缩文件也必然有个极限,不可能一直压缩下去。

            最后介绍一个信息熵理论的应用,主要思想是香农公式:

                      

            某一次试验之前我们并不能确知试验的结果,那么这一试验可能获得的信息量的期望是香农公式(上边图,还是粘贴过来了)确定,由于这一公式的形式非常类似物理中“熵”的定义,香农把这一平均信息量称为“信息熵”。由函数的性质可知,当各种结果出现的概率均等时,此次试验能获得的信息量的期望最大。下边说说一个应用:有 100 个外表相同的球,已知其中有一个与其他球的质量不同。现要求用没有砝码的天平在最少次数中找出这个球,问怎样的称法才是最佳的?我们把每次称量都视为一次试验,试验结果有三种:天平偏向左边、天平偏向右边重或者相等,那么为获得最大的信息量,我们应该使三种情况出现的概率相等,即把小球平均分成 3 份进行称量,也就是一般答案中给出的最佳称量方法。使用信息论还可以计算出最少所需要的称量次数,因为100个小球中知道某球是假球且偏重或者偏轻这一信息所包含的信息量是 log 2 200,每次测量所能获得的信息是 log 2 3,那么需要测量的最小次数就是 5 次。然而具体到每次测量,由于不能保证将球平均分为 3 份,并不一定能有 log 2 3 的信息熵,所以这个 5 次只是测量的下界,具体能否达到还要看实际的步骤。

     

    参考:

    http://www.zhihu.com/question/22539777

    http://www.zhihu.com/question/20207589
    https://blog.csdn.net/dreamerway/article/details/22718823 

     

    展开全文
  • 数据压缩的极限

    千次阅读 2015-02-19 10:32:43
    数据能不能被无限压缩? 在小学六年级电脑课教使用压缩软件的时候,老师说对已经压缩过的文件再压缩是没有效果的。实际生活中直觉告诉我们也是这样的:像程序代码之类的文本文件,压缩率很高,几十MB的文件经过压缩

    单位的电子邮件最大只能发5MB的附件,因此在发送文件的时候,经常会使用压缩软件把附件进行压缩分卷,一个大的附件经常会分成十几甚至几十个小文件。在压缩的时候想起了很久以前思考的一个问题:

    数据能不能被无限压缩?

    在小学六年级电脑课教使用压缩软件的时候,老师说对已经压缩过的文件再压缩是没有效果的。实际生活中直觉告诉我们也是这样的:像程序代码之类的文本文件,压缩率很高,几十MB的文件经过压缩,有时候都不足5MB一封邮件就能发出去;而像JPG、MP3、RMVB这种文件,压缩后和压缩前基本看不出区别。我想,大概是因为JPG、MP3、RMVB都是已经被压缩过的文件格式,而代码文件是没有经过压缩的,所以才导致了两者压缩率的差异。

    随着后来上了大学,慢慢的对这个问题有了答案:数据是不能被无限压缩的。

    计算机中1个bit有两种状态,0或者1。1个大小为n个bit的文件,包含了2^n种不同的0和1的组合顺序。假如说有一种压缩算法,压缩率可以达到50%。那么压缩后的文件,大小为n/2个bit,只能包含2 ^(n/2)种0和1的组合顺序,是无法将压缩前的2^n种排列表示完整的。

    本质上,压缩的原理其实就是用更精简的字符串去描述复杂的字符串。字符串的规律性越强,压缩的效果越好。

    “CCCCCCCC”可以用”8C”来表示,一下子就缩短了6个字符。

    相应的,内容越是随机没有规律,越是难被压缩,例如随机的字符串”LFSDHFA156″、π、还有上面例子里”CCCCCCCC”压缩后的”8C”。

    在英文里,常用的单词都是比较短小的,例如I、you、a、one、two等,而不怎么常用的单词,都是比较长的,例如biotransformation。我们背这些长的单词的时候,往往会把它分解成简单的一些单词的组合”bio”+”transform”+”tion”这样子来背。其实和数据压缩是大同小异的。顺便说下,这种把常用的单词用尽量少的字母来表达的方法,就是信息学中大名鼎鼎的「哈夫曼编码」的基本原理。

    说了这么多,其实就是想解释下,数据压缩只不过是把海绵中的水挤压出来,再怎么用力,都无法把海绵都挤的消失。

    搬运自我的技术博客:http://www.cc-lab.cn/compression/

    展开全文
  • 大数据-数据压缩

    2019-03-31 14:49:52
    Hadoop数据压缩 压缩能够有效减少底层存储(HDFS)读写字节数,提高网络宽带和磁盘空间的效率 在MapReduce里,通过压缩编码对Mapper或Reducer数据传输进行数据压缩,可以减少磁盘IO 基本原则 (1)运算密集型任务少...
  • 简单的数据压缩

    千次阅读 2018-09-29 17:37:40
    如何压缩配置文件? 把相同的部分用一个简短的字符替换.这就是压缩算法 @@URL@@sc=http,ho=25vm.com@@URL@@pl3,pl4@@URL@@ 这样,本来 5个网址就变成一行简短的文本. 看看他原来的样子: http://blog1.csdn.net/ ...
  • 一些数据压缩手段

    千次阅读 2018-10-22 17:29:29
    甚至有时我们需要用 CPU 换硬盘,即宁可多消耗些 CPU 时也要减少硬盘访问量,一方面 CPU 性能更好,另一方面是 CPU 比硬盘更容易并行,现代计算机的 CPU 核数常常远远超过硬盘的并发访问能力,数据密集型的任务应当...
  • 数据压缩

    2019-07-20 03:26:08
    hdfs的副本的配置修改hdfs-site.xml文件<property><name>dfs.namenode.secondary..../name><value>hd-02:50090</value>...需要同步到其它机器:scp hdfs-site.xml hd-02:$PWDhado...
  • 深入解析数据压缩算法

    万次阅读 2018-06-08 06:26:38
    1、为什么要做数据压缩? 数据压缩的主要目的还是减少数据传输或者转移过程中的数据量。2、什么是数据压缩? 是指在不丢失信息的前提下,缩减数据量以减少存储空间,提高传输、存储和处理效率的一种技术方法。或者...
  • 数据压缩的历史、常用算法原理

    千次阅读 2019-05-28 15:01:44
    数据压缩的概念相当古老,可以追溯到发明了摩尔斯码的19世纪中期。 摩尔斯码的发明,是为了使电报员能够通过电报系统,利用一系列可听到的脉冲信号传递字母信息,从而实现文字消息的传输。摩尔斯码的发明者意识到,...
  • 数据压缩的两种方法

    2018-12-15 15:09:07
    将整型数据存在字节里面 参考了 http://www.cnblogs.com/chencheng/archive/2012/07/01/2572251.html     方法二: 对二进制码流进行压缩 举例:000011111000111111 压缩后:40513061 (4个0 - 5个1 - 3个0...
  • 数据压缩的历史、原理及常用算法

    万次阅读 2017-05-24 14:58:23
    数据压缩的概念相当古老,可以追溯到发明了摩尔斯码的19世纪中期。摩尔斯码的发明,是为了使电报员能够通过电报系统,利用一系列可听到的脉冲信号传递字母信息,从而实现文字消息的传输。摩尔斯码的发明者意识到,...
  • 无损数据压缩算法的历史

    万次阅读 多人点赞 2014-09-25 10:17:44
    引言 有两种主要的压缩算法: 有损和无损。有损压缩算法通过移除在保真情形下需要大量的数据去存储的小细节,从而使文件变小。在有损压缩里,因某些必要数据的移除,恢复原文件...无损数据压缩被广泛的应用在计算机领域
  • 浅析数据压缩算法

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

    万次阅读 多人点赞 2019-07-29 20:24:10
    数据压缩 某工业监控设备不断发回采样数据。每个数据是一个整数(0到1000之间)。各个数据间用空白字符(空格,TAB或回车换行)分隔。这些数据以文本形式被存储在文件中。 因为大多数时候,相邻的采样间隔数据是...
  • HADOOP与HDFS数据压缩格式

    千次阅读 2018-10-17 18:20:11
    HADOOP与HDFS数据压缩格式 1、cloudera 数据压缩的一般准则 一般准则 是否压缩数据以及使用何种压缩格式对性能具有重要的影响。在数据压缩上,需要考虑的最重要的两个方面是 MapReduce 作业和存储在 HBase 中的...
  • 无损数据压缩LZW算法——C++实现

    千次阅读 2018-04-28 14:02:36
    兹于2017年11月,应《多媒体技术基础》课程实验的要求,本人就基于无损数据压缩LZW算法做了较为深入的理解,用C++语言实现无损数据压缩LZW算法。无损数据压缩LZW算法一、实验目的1.掌握LZW算法的编码过程;2.掌握...
  • 解决数据压缩的问题通常可以从三步来分析:第一步是为什么要做,即数据压缩的必要性问题;第二步是为什么可以做,即分析信源数据的特性,并在此基础上进行数据压缩的可行性分析;第三步是在第二步分析的基础上,如何...
  • 作为GISer,处理空间数据才是主要任务,矢量数据压缩这一块要学习学习。 这里矢量数据压缩是指线的数据压缩,意思是假如某根线有n个点,现在如果删除一些点,这条线仍然性质良好,那么就实现了压缩,那么下面的算法...
  • 第七章数据压缩技术

    千次阅读 2016-04-30 10:14:02
    第七章 数据压缩技术 转自:http://www.dataguru.cn/article-3856-1.html     本章导读 前面的章节已经介绍了海量数据的存储、查询、分区、容错等技术,这些技术对于海量数据的处理是必不可少的,但要进一步...
1 2 3 4 5 ... 20
收藏数 705,591
精华内容 282,236
关键字:

数据压缩