精华内容
下载资源
问答
  • 在计算机数据压缩处理中,霍夫曼编码使用变长编码表()对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现几率的方法得到的,出现几率高的字母使用较短的编码,反之出现几率低的则...

    有损压缩

    概念

    按照压缩方法是否丢失信息分为有损压缩和无损压缩,有损压缩解压缩后的数据与原始数据完全相同。 解压缩后获得的数据是原始数据的副本,是一种不可逆压缩。

    主要算法

    消除编码冗余: 哈夫曼编码和算术编码。
    消除像素间冗余:LZW编码,位平面编码,行程编码和无损预测编码。

    哈夫曼编码

    定义

    哈夫曼编码,又称为霍夫曼编码,是一种字符编码。

    在计算机数据压缩处理中,霍夫曼编码使用变长编码表()对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现几率的方法得到的,出现几率高的字母使用较短的编码,反之出现几率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。

    性质

    • 可变字长编码(VLC)
    • 源符号出现的频率越高,使用的代码字长越少。
    • 一致的编码方法(也称为“熵编码方法”),用于数据的无损压缩。

    信息熵

    英文entoropy,反映图像中的平均信息量。

    定长和变长编码比较

    定长编码:fixed length coding (FLC),如定长一字节或者定长二字节
    变长编码:virable length coding(VLC)

    示例

    SymbolProbabilityFLCVLC1VLC2VLC3
    K1/20001110
    L1/401101101
    P1/8101101001
    C1/811111010

    对 KLKPLCKK 用上述四个方式编码

    方式表示编码长度length
    FLC00 01 00 10 11 00 002*8 =16 bits
    VLC10 10 0 110 10 111 0 01+2+1+3+2+3+2 = 14 bits
    VLC2111 110 111 10 110 0 111 1113+3+3+2+3+1+3+3 = 21 bits
    VLC30 1 0 01 1 10 0 01+1+1+2+1+2+1+1 = 10 bits

    总结 根据最后编码长度,VLC3 的长度最短,符合出现概率高的字母使用较短的编码,因此是哈夫曼码。

    信息熵:反映图像中的平均信息量,用H(entoropy)表示,小于等于Lavg(average length)

    示例

    在这里插入图片描述

    生成哈夫曼编码

    在这里插入图片描述

    展开全文
  • Zip解压-可设置压缩文件编码方式

    热门讨论 2015-09-19 22:32:24
    jdk自带的ZipEntry类解压zip文件,中文文件会出现乱码,jar包是根据Apache的解压缩包进行改造的,也适合于Android使用
  • 图像压缩之算术编码

    千次阅读 2019-04-15 10:43:15
    JPEG中使用了量化、哈夫曼编码等,极大的压缩了图片占用的空间,那么是否可以进一步压缩呢? 从技术角度讲,是可以的。如DropBox开源的lepton,在目前的JPEG...同样由于专利限制没有广泛使用的还有gif中的压缩编码l...

    JPEG中使用了量化、哈夫曼编码等,极大的压缩了图片占用的空间,那么是否可以进一步压缩呢?
    从技术角度讲,是可以的。如DropBox开源的lepton,在目前的JPEG压缩基础上,可以再节省22%左右的空间。
    lepton中使用算术编码(VP8)替换哈夫曼编码,以得到更高的压缩率。算术编码90年代已经出现,但是受限于专利,没有被广泛使用。同样由于专利限制没有广泛使用的还有gif中的压缩编码lzw。


    下面介绍一下,算术编码的基本原理和过程。


    算术编码(  Arithmetic coding )发展历史
    1948 年,香农就提出将信源符号依其出现的概率降序排序,用符号序列累计概率的二进值作为对信源数据的编码,并从理论上论证了它的优越性。
    1960 年,  Peter Elias 发现无需排序,只要编、解码端使用相同的符号顺序即可,提出了算术编码的概念。  Elias 没有公布他的发现,因为他知道算术编码在数学上虽然成  立,但不可能在实际中实现。
    1976 年,  R. Pasco 和  J. Rissanen 分别用定长的寄存器实现了有限精度的算术编码。
    1979 年  Rissanen 和  G. G. Langdon 一起将算术编码系统化,并于  1981 年实现了二进制编码。
    1987 年  Witten 等人发表了一个实用的算术编码程序,即  CACM87 (后用  于  ITU-T 的  H.263 视频压缩标准)。同期,  IBM 公司发表了著名的  Q- 编码器(后用于  JPEG 和  JBIG 图像压缩标准)。从此,算术编码迅速得到了广泛的注意。

    算术编码介绍
    算术编码是一种无损数据压缩方法,也是一种熵编码的方法。
    一般的熵编码方法通常是把输入的消息分割为符号,然后对每个符号进行编码。而算术编码将整个要编码的数据映射到一个位于  [0,1) 的实数区间中。利用这种方法算术编码可以让压缩率无限的接近数据的熵值,从而获得理论上的最高压缩率。

    算术编码用到两个基本的参数:符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率,也决定编码过程中信源符号的间隔,而这些间隔包含在  0 到  1 之间。编码过程中的间隔决定了符号压缩后的输出。

    算术编码可以是静态的或者自适应的。
    在静态算术编码中,信源符号的概率是固定的。在自适应算术编码中,信源符号的概率根据编码时符号出现的频繁程度动态地进行修改,在编码期间估算信源符号概率的过程叫做建模。
    需要开发动态算术编码的原因是因为事先知道精确的信源概率是很难的,而且是不切实际的。当压缩消息时,我们不能期待一个算术编码器获得最大的效率,所能做的最有效的方法是在编码过程中估算概率。因此动态建模就成为确定编码器压缩效率的关键。

    算术编码思想
    算术编码的基本原理是将编码的消息表示成实数  0 和  1 之间的一个间隔(  Interval ),消息越长,编码表示它的间隔就越小,表示这一间隔所需的二进制位就越多。

    算术编码进行编码时,从实数区间  [0,1) 开始,按照符号的频度将当前的区间分割成多个子区间。根据当前输入的符号选择对应的子区间,然后从选择的子区间  中继续进行下一轮的分割。不断的进行这个过程,直到所有符号编码完毕。对于最后选择的一个子区间,输出属于该区间的一个小数。这个小数就是所有数据的编码。

    给定事件序列的算术编码步骤如下:
    ( 1 )编码器在开始时将  “ 当前间隔  ” [ L ,  H)  设置为  [0 ,  1) 。
    ( 2 )对每一个输入事件,编码器按下边的步骤(  a )和(  b )进行处理
    ( a )编码器将 “  当前间隔 ” 分为子间隔,每一个事件一个。一个子间隔的大小与将出现的事件的概率成正比
    ( b )编码器选择与下一个发生事件相对应的子间隔,并使它成为新的  “ 当前间隔  ” 。
    ( 3 )最后输出的  “ 当前间隔  ” 的下边界就是该给定事件序列的算术编码。

    在算术编码中需要注意几个问题:
    ( 1 )由于实际计算机的精度不可能无限长,运算中出现溢出是一个明显的问题,但多数及其都有  16 位,  32 位或者  64 位的精度,因此这个问题可以使用比例缩放方法解决。
    ( 2 )算术编码器对整个消息只产生一个码字,这个码字是在间隔  [0,1) 中的一个实数,因此译码器在接受到表示这个实数的所有位之前不能进行译码。
    ( 3 )算术编码是一种对错误很敏感的编码方法,如果有一位发生错误就会导致整个消息译错。

    算术编码伪代码
    定义一些变量,设  Low 和  High 分别表示  “ 当前间隔  ” 的下边界和上边界;
    CodeRange 为编码间隔的长度,即 " 当前间隔  " 的长度;
    LowRange(symbol) 和 HighRange(symbol)  分别代表为了事件  symbol 的编码间隔下边界和上边界。

    如果 symbol 的编码间隔固定不变,则为静态编码;
    反之,如果  symbol 的编码间隔随输入事件动态变化,则为自适应编码。

    算术编码的编码过程可用伪代码描述如下:
    set Low to 0
    set High to 1
    while there are input symbols do
        take a symbol
        CodeRange = High – Low
        High = Low + CodeRange *HighRange(symbol)
        Low = Low + CodeRange * LowRange(symbol)
    end of while
    output Low
     

    算术编码解码过程用伪代码描述如下:
    get encoded number
    do
        find symbol whose range straddles the encoded number
        output the symbol
        range = symbo.LowValue – symbol.HighValue
        substracti symbol.LowValue from encoded number
        divide encoded number by range
    until no more symbols

    静态的算术编码
    算术编码器的编码解码过程可用例子演示和解释。
    例 1 :假设信源符号为  { A  ,  B  ,  C  ,  D}  ,这些符号的概率分别为  {  0.1 ,  0.4 ,  0.2 ,  0.3 } ,根据这些概率可把间隔  [0 ,  1] 分成  4 个子间隔:  [0 ,  0.1] ,  [0.1 ,  0.5] ,  [0.5 ,  0.7] ,  [0.7 ,  1] ,其中  [x ,  y] 表示半开放间隔,即包含  x 不包含  y 。上面的信息如下表。

      信源符号,概率和初始编码间隔
    符号
    A
    B
    C
    概率
    0.1
    0.4
    0.2
    0.3 
    初始编码间隔
    [0, 0.1)
    [0.1, 0.5)
    [0.5, 0.7)
    [0.7, 1] 

    如果二进制消息序列的输入为:  C A D A C D B 。
    编码时首先输入的符号是  C ,找到它的编码范围是  [0.5 ,  0.7] 。由于消息中第二个符号  A 的编码范围是  [0 ,  0.1] ,因此它的间隔就取  [0.5 ,  0.7] 的第一个十分之一作为新间隔  [0.5 ,  0.52] 。
    依此类推,编码第 3 个符号  D 时取新间隔为  [0.514 ,  0.52] ,编码第  4 个符号  A 时,取新间隔为  [0.514 ,  0.5146] ,  … 。
    消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如下图所示。

         算术编码过程举例

      取一个  (0.5143876~0.514402) 之间的数: 0.5143876 
       (0.5143876)D ≈  (0.1000001)B ,去掉小数点和前面的  0 ,得  1000001 。   
      所以:  cadacdb 的编码  =1000001 ,长度为  7 。

    十进制小数转换为二进制参考:点击打开链接

    编码和译码的全过程分别表示如下。   
      编码过程
    步骤
    输入符号
    编码间隔   
    编码判决
    1
    C
    [0.5, 0.7]
    符号的间隔范围[0.5, 0.7] 
    2
    A
    [0.5, 0.52]
    [0.5, 0.7]间隔的第一个1/10
    3
    D
    [0.514, 0.52]
    [0.5, 0.52]间隔的最后一个1/10
    4
    A
    [0.514, 0.5146]
    [0.514, 0.52]间隔的第一个1/10
    5
    C
    [0.5143, 0.51442]
    [0.514, 0.5146]间隔的第五个1/10开始,二个1/10
    6
    D
    [0.514384, 0.51442]
    [0.5143, 0.51442]间隔的最后3个1/10
    7
    B
    [0.5143836, 0.514402]
    [0.514384,0.51442]间隔的4个1/10,从第1个1/10开始
    8
    从[0.5143876, 0.514402]中选择一个数作为输出:0.5143876
     
                             表  译码过程
    步骤
    间隔
    译码符号   
    译码判决   
    1
    [0.5, 0.7]
    C
    0.51439在间隔 [0.5, 0.7)
    2
    [0.5, 0.52]
    A
    0.51439在间隔 [0.5, 0.7)的第1个1/10
    3
    [0.514, 0.52]
    D
    0.51439在间隔[0.5, 0.52)的第7个1/10
    4
    [0.514, 0.5146]
    A
    0.51439在间隔[0.514, 0.52]的第1个1/10
    5
    [0.5143, 0.51442]
    C
    0.51439在间隔[0.514, 0.5146]的第5个1/10
    6
    [0.514384, 0.51442]
    D
    0.51439在间隔[0.5143, 0.51442]的第7个1/10
    7
    [0.51439, 0.5143948]
    B
    0.51439在间隔[0.51439,0.5143948]的第1个1/10
    8
    译码的消息:C A D A C D B

    在上面的例子中,我们假定编码器和译码器都知道消息的长度,因此译码器的译码过程不会无限制地运行下去。实际上在译码器中需要添加一个专门的终止符,当译码器看到终止符时就停止译码。

    为什么说算术编码压缩率更高?
    算术编码可以对一个二进制序列进一步编码,得到比原序列更小的编码结果。

    例如,假设二进制序列信源符号为  { 1,0}  ,如果消息序列的输入为  1101  。   
      则符号  1 和  0 的概率分别为  :  符号  1 的概率  3/4 ,符号  0 的概率  1/4  。整个编码过程如图所示。


    算术编码的结果:
    下界 =121/256  ,即 0.47265625  或二进制 0.0111 ;
    上界为 37/64  ,即 0.578125  或二进制 0.10010 。

    在该区间范围内任取一个数,例如  0.5 (对应二进制  0.1 ),只取小数点后边的部分,即  1 。   
    这样,原来的 1101  序列就可以用编码  1 来代替。   

    自适应的算术编码
    自适应模型中,在编码开始时,各个符号出现的概率相同,都为  1/n 。随着编码的进行再更新出现概率。另外,在计算时理论上要使用无限小数。这里为了说明方便,四舍五入到小数点后  4 位。

    举个例子来说明自适应算术编码。
    假设一份数据由 “A”  、 “B”  、 “C”  三个符号组成。现在要编码数据  “BCCB” ,编码过程如图所示。



    ( 1 )算术编码是从区间 [0,1) 开始。这时三个符号的概率都是  1/3 ,按照这个概率分割区间。
    ( 2 )第一个输入的符号是 “B” ,所以我们选择子区间  [0.3333,0.6667) 作为下一个区间。
    ( 3 )输入 “B”  后更新概率,根据新的概率对区间  [0.3333,0.6667) 进行分割。
    ( 4 )第二个输入的符号是 “C” ,选择子区间  [0.5834,0.6667) 。
    ( 5 )以此类推,根据输入的符号继续更新频度、分割  区间、选择子区间,直到符号全部编码完成。

    我们最后得到的区间是 [0.6390,0.6501) 。输出属于这个区间的一个小数,例如  0.64 。那么经过算  术编码的压缩,数据  “BCCB” 最后输出的编码就是  0.64 。

    自适应模型的解码
    算术编码进行解码时仅输入一个小数。整个过程相当于编码时的逆运算。解码过程是这样:
    ( 1 )解码前首先需要对区间  [0,1) 按照初始时的符号频度进行分割,然后观察输入的小数位于哪个子区间,输出对应的符号。
    ( 2 )之后选择对应的子区间,然后从选择的子区间中继续进行下一轮的分割。
    ( 3 )不断的进行这个过程,直到所有的符号都解码出来。

    在我们的例子中,输入的小数是  0.64 。
    ( 1 )初始时三个符号的概率都是  1 / 3 ,按照这个概率分割区间。
    ( 2 )根据上图可以发现 0.64 落在子区间  [0.3333,0.6667) 中,于是可以解码出  "B" ,并且选择子区间  [0.3333,0.6667) 作为下一个区间。
    ( 3 )输出 “B”  后更新频度,根据新的概率对区间  [0.3333,0.6667) 进行分割。
    ( 4 )这时 0.64  落在子  区间  [0.5834,0.6667) 中,于是可以解码出  “C” 。
    ( 5 )按照上述过程进行,直到所有的符号都解码出来。
    可见,只需要一个小数就可以完整还原出原来的所有数据。

    自适应模型的整数编码方式
    上边介绍的编码都是得到一个  [0,1)  内的小数,下面说明整数编码方式,以  8 位编码为例,阐述算术编码和解码过程  .

    例如对字符串 "ababcab"  进行编解码,最终得到  8 位编码。
    确定上下界:由于 8 位的取值范围是  [0,255] ,因此下界为  0 ,上界为  255  。
    符号概率:编码开始时,  a 、  b 、  c 的出现概率都是  1/3  。

    编码过程
    ( 1 ) "ababcab"  第 1  个字符为 a ,初始化时三个字符出现概率相同,因此  a 的编码间隔为  [0,1/3] ,即  LowRange(a) = 0, HighRange(a) = 1/3
    ( 2 )更新上下界的值为  [0, 85] ,根据伪代码:
        CodeRange = High – Low
        High = Low + CodeRange *HighRange(symbol)
        Low = Low + CodeRange * LowRange(symbol)
    计算得到:
    CodeRange = 255 - 0 = 255
    High = 0 + 255 * 1/3 = 85
    Low = 0 + 255 * 0 = 0

    此时各个符号的编码间隔动态调整为:  a :  [0, 2/4] ,  b  :  [2/4, 3/4] , c :  [3/4, 1]

    ( 3 )  "ababcab" 第 2 个字符为 b  ,取编码间隔  [2/4, 3/4] ,并更新上下界:
    CodeRange = 85 - 0 = 85
    High = 0 + 85 * 3/4 = 63    (向下取整)
    Low = 0 + 85 * 2/4 = 43    (向上取整)

    ( 4 )同理可得到  "ababcab" 第 3 、 4 个字符 a  、 b  的编码。
    ( 5 )计算 "ababcab"  第 5  个字符 c 的编码,此时  High=49 ,  Low=49 。因为是有限整数,每次又是取的上一区间的子区间  ,high 和  low 趋于相等是必然的。

      8  位编码过程

    我们在此使用 High  和 L ow  向左移的方式进行扩大区间
    极限情况:位移后 Low 的二进制首位为  0 ,其他位为全  1 ;  High 的二进制首位为  1 ,其他位为全  0 。如  8 位时:  Low=01111111B ,  High=10000000B 的情况。
    出现这种情况时,我们可以规定,保留相同位,并将该区间扩展至原始区间,如  8 位是  [0, 255) ,  32 位是  [0, 0xffffffff) 。

    位移时遵循两个原则  :
    (1)  设  Total 为字符表中的字符数  + 已出现的字符数(即编码间隔的分母),需保证  High-Low>=total ,否则继续位移
    (2)  保证  [Low, High] 在上一个  [Low, High] 的子区间。  ( 实际上这条已经在取整运算时得到了保证  )

    上下界左移  1 位后溢出位用新变量  out 存储,同时,用  bits 保存  out 到底存了几个位。  (0B 表示二进制  0)
    位移轮数
    Total
    Out
    Bits
    High
    Low
    1
    7
    0 B
    1
    98 (49<<1)
    94 (47<<1)
    2
    7
    00B
    2
    196 (98<<1)
    188 (94<<1)

    此时满足两条  " 位移原则  " ,继续编码。

      位移和继续编码

    编码第 6 个字符  a 和第  7 个字符  b ,分别需要位移  3 次和  2 次。
                          编码第 6 个字符  a 时位移 3
    位移轮数
    Total
    Out
    Bits
    High
    Low
    1
    8
    0 01B
    3
    136
    134
    2
    8
    00  11B
    4
    16 (136<<1)
    12 (134<<1)
    3
    8
    00110B
    5
    32
    24

          编码第 7 个字符  b 时位移 2
    位移轮数
    Total
    Out
    Bits
    High
    Low
    1
    9
    0 01100B
    6
    54
    48
    2
    9
    00  11000B
    7
    108
    96

    编码结束时最后的区间是  [102, 105] ,后面已经没有字符,不需要位移了。记下此区间的某一个数即可,这里选  magic=104 。

    整个编码过程结束,得到编码结果:
    out=0011000B ,  bits=7 ,  magic=104 。

    编码全过程如图
      
      编码全过程

    解码过程
    根据编码结果:  out=0011000B ,  bits=7 ,  magic=104 。(  Total=9 可选)
    将 magic 转换为  8 位二进制,拼在  out 后,得到  15 位数:
    X = out<<8 | magic = 0011000 01101000B 

    ( 1 )取  X 的高  8 位,令  z = 00110000B = 48;
    ( 2 )  48 是  a 所在区间,于是解码得到字符  "a"
    ( 3 )更新上下界为 [0, 85]  ,更新各符号的编码间隔  a :  [0, 2/4] ,  b  :  [2/4, 3/4] ,  c :  [3/4, 1]
    ( 4 )满足位移原则 1  ,不需要位移,继续解码。  48 是  b 所在区间,解码得到字符串  "ab" 。更新上下界和编码间隔;
    ( 5 )继续解码得到字符串 ”abab” ,此时上下界为  [47, 49] ,不满足位移原则  1 ,需要位移;
    ( 6 )去掉 z  的首位,即左边第一位;取  X 中下一位接到  z 右边,得到  z = 01100001B = 97 。 
    Total=7 ,上下界 [94, 98]  ,不满足原则  1 ,继续位移得到  z = 11000011B = 195 ; 
    满足原则 1 ,继续解码;
    ( 7 ) 195 是 c 所在区间,解码得到字符串  "ababc" ;
    ( 8 )此时需要位移,位移 3 次,得到  z = 00001101B = 25 ,解码得到字符串  "ababca" ;
    ( 9 )此时需要位移,位移 2 次,  Total=9 ,上下界  [96, 108) ,满足位移原则  1 。 
    但是 z = 00110100B = 52 ,不在上下界范围内,于是  z 位移  z = 01101000B = 104 ( 到达 X 末尾  ) ; 
    解码得到字符串  "ababcab" ;
    ( 10 )此时需要位移,位移 1 次,上下界为  [152, 164) ,满足位移原则  1 。 
    但是 z = 01101000B = 104 ,不在上下界范围内,  z 需要位移。此时  X 已经到达末尾,  z 不能继续位移,此时编码结束。 
    (若编码结果中有  Total=9 信息,在上一步就可以结束)


    JPEG 中为什么没有使用算术编码
    因为算术编码的使用存在版权问题。
    JPEG 标准说明的算术编码的一些变体方案属于  IBM ,  AT&T 和  Mitsubishi 拥有的专利。要合法地使用  JPEG 算术编码必须得到这些公司的许可。
    像 JPEG 这种开源的标准,虽然传播广泛,但是大家都是免费在用,明显没有钱买那么贵的专利。
    参考


    转自:https://blog.csdn.net/shelldon/article/details/54234436
    展开全文
  • 数字图像霍夫曼编码压缩编码MATLAB实现
  • 基于MATLAB的图像压缩程序(包含各种压缩编码与解码方法),算法包含详细代码,是图像编码技术的总结
  • 基于Matlab的图像压缩编码

    热门讨论 2010-03-23 15:56:44
    JPEG基本系统是一种有损编码,无法完全恢复出原图象,信息有一定的丢失,称为有损压缩。尽管我们希望能够无损压缩,但是通常有损压缩压缩比(即原图象占的字节数与压缩后图象占的字节数之比,压缩比越大,说明压缩...
  • 文件压缩与解压(哈夫曼编码

    热门讨论 2011-11-06 15:13:55
    利用哈夫曼编码原理对磁盘文件进行压缩与解压
  • 哈夫曼编码用于解压和压缩的示例代码,非常简单易懂,C风格C++写法。
  • Huffman编码实现压缩压缩

    千次阅读 2016-04-04 23:22:05
    Huffman编码实现压缩压缩 什么是Huffman压缩 Huffman( 哈夫曼 ) 算法在上世纪五十年代初提出来了,它是一种无损压缩方法,在压缩过程中不会丢失信息熵,而且可以证明 Huffman 算法在无损压缩算法中是最优的。 ...

    这是我们的课程中布置的作业,找一些资料将作业完成,顺便将其写到博客,以后看起来也方便。

    原理介绍

    • 什么是Huffman压缩

      Huffman( 哈夫曼 ) 算法在上世纪五十年代初提出来了,它是一种无损压缩方法,在压缩过程中不会丢失信息熵,而且可以证明 Huffman 算法在无损压缩算法中是最优的。 Huffman 原理简单,实现起来也不困难,在现在的主流压缩软件得到了广泛的应用。对应用程序、重要资料等绝对不允许信息丢失的压缩场合, Huffman 算法是非常好的选择。

    • 怎么实现Huffman压缩
      哈夫曼压缩是个无损的压缩算法,一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号(例如,文本文件中的字符)用一个特定长度的位序列替代。因此,在文件中出现频率高的符号,使用短的位序列,而那些很少出现的符号,则用较长的位序列。

      1. 二叉树
        在计算机科学中,二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作 “ 左子树 ” ( left subtree )和 “ 右子树 ” ( right subtree )。
        二叉树
      2. 哈夫曼编码 (Huffman Coding)
        哈夫曼编码是一种编码方式,哈夫曼编码是可变字长编码 (VLC) 的一种。 uffman 于 1952 年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字,有时称之为最佳编码,一般就叫作 Huffman 编码。
    • Huffman编码生成步骤
      1. 扫描要压缩的文件,对字符出现的频率进行计算。
      2. 把字符按出现的频率进行排序,组成一个队列。
      3. 把出现频率最低(权值)的两个字符作为叶子节点,它们的权值之和为根节点组成一棵树。
      4. 把上面叶子节点的两个字符从队列中移除,并把它们组成的根节点加入到队列。
      5. 把队列重新进行排序。重复步骤 3、4、5 直到队列中只有一个节点为止。
      6. 把这棵树上的根节点定义为 0 (可自行定义 0 或 1 )左边为 0 ,右边为 1 。这样就可以得到每个叶子节点的哈夫曼编码了。
        这里写图片描述
        如 (a) 、 (b) 、 (c) 、 (d) 几个图,就可以将离散型的数据转化为树型的了。
        如果假设树的左边用0 表示右边用 1 表示,则每一个数可以用一个 01 串表示出来。
        这里写图片描述
        则可以得到对应的编码如下:
        1–>110
        2–>111
        3–>10
        4–>0
        每一个01 串,既为每一个数字的哈弗曼编码。
    • 为什么能压缩
      压缩的时候当我们遇到了文本中的1 、 2 、 3 、 4 几个字符的时候,我们不用原来的存储,而是转化为用它们的 01 串来存储不久是能减小了空间占用了吗。(什么 01 串不是比原来的字符还多了吗?怎么减少?)大家应该知道的,计算机中我们存储一个 int 型数据的时候一般式占用了 2^32-1 个 01 位,因为计算机中所有的数据都是最后转化为二进制位去存储的。所以,想想我们的编码不就是只含有 0 和 1 嘛,因此我们就直接将编码按照计算机的存储规则用位的方法写入进去就能实现压缩了。
      比如:
      1这个数字,用整数写进计算机硬盘去存储,占用了 2^32-1 个二进制位
      而如果用它的哈弗曼编码去存储,只有110 三个二进制位。
      效果显而易见。

    编码实现

    1. 流程图
      编码流程
    Created with Raphaël 2.1.0 开始 读入待压缩文件,计算文件中各字符的权重 根据权重构建Huffman树 根据Huffman树获得各个字符的HUffman编码, 并建立Huffman编码的HashTable 将字符总数、字符种数, 以及Huffman树写入压缩文件文件头 再次读入待压缩文件, 根据其内容和coding hash table 将压缩后的数据写入文件 结束
    1. 数据结构
      CharacterWeight:记录字符值,以及其在待压缩文件中的权重。
    public class CharacterCode {
        private int weight;//字符值  
        private char character;//字符值 
        private String code;//其对应huffman编码 
        } 

    HuffmanNode:huffman树中的节点信息。

    public class HuffmanNode {
        private int parent;//父节点
        private int lChild;//左子
        private int rChild;//右子
        private int weight;//权重
        }
    1. 程序关键步骤
      • Huffman树的构建
        Huffman树的变量:ArrayList list;
        流程图
    Created with Raphaël 2.1.0 开始 i=0 n=字符的种数 循环遍历查找列表中权重最小的两个node 创建一个新的节点作为找到的两个权重最小的节点的父节点, 并将该父节点的权重置为权重最小的两节点的权重和, 将该节点加入数组中。i++ i<n-1 结束 yes no

    代码

    for(int i=0;i<list.size()-1;i++){  
                //w1 : the first min weight w2: the second min weight   
                //i1 : the first min weight index, i2: the second min weight index  
                int w1 = MAX_VALUE, w2=MAX_VALUE;   
                int i1 = 0, i2 = 0;  
                // find the two node with the minimum weight  
                for(int j=0;j<tree.size();j++){  
                    HuffmanNode node = tree.get(j);  
                    if(node.getWeight()< w1 && node.getParent()==-1){  
                        w2 = w1;  
                        w1 = node.getWeight();  
                        i2 = i1;  
                        i1 = j;  
                    }  
                    else if(node.getWeight()<w2 && node.getParent()==-1){  
                        w2 = node.getWeight();  
                        i2 = j;  
                    }  
                }  
                //set the two node to be the children of a new node, and add the new node to the tree  
                HuffmanNode pNode = new HuffmanNode(w1+w2);  
                pNode.setlChild(i1);  
                pNode.setrChild(i2);  
                tree.add(pNode);  
                tree.get(i1).setParent(tree.indexOf(pNode));  
                tree.get(i2).setParent(tree.indexOf(pNode));}  
    • 根据Huffman 树获得Huffman编码
      从叶子节点开始网上遍历Huffman树,直到到达根节点,根据当前节点为其父节点的左儿子还是右儿子确定这一位值是0还是1。最后将依次获得的0,1字符串反转获得Huffman编码。
    for(int i=0;i<list.size();i++){  
                HuffmanNode node = tree.get(i);  
                HuffmanNode pNode = tree.get(node.getParent());  
                String code ="";  
                while(true){  
                    if(pNode.getlChild()==tree.indexOf(node)){  
                        code = "0"+code;  
                    }  
                    else if(pNode.getrChild() == tree.indexOf(node)){  
                        code = "1"+code;  
                    }  
                    else {  
                        System.out.println("Tree Node Error!!!");  
                        return null;  
                    }  
                    node=pNode;  
                    if(node.getParent()!=-1)  
                        pNode=tree.get(node.getParent());  
                    else   
                        break;  
                }  
                list.get(i).setCode(new String(code));  
            }  
    • 头文件设计

      编码类型字节数
      字符总数Int4
      字符种类数Short2
      叶子节点char字符 short 父节点3
      非叶子节点Short 左儿子 short 右儿子 short父节点6

      文件头长度(单位: byte)
      l= 9n
      其中n 为字符种类数。

      • 文件内容的编码和写入
    Created with Raphaël 2.1.0 开始 将待压缩文件读入字符数组 根据coding hash table 获得huffman编码字符串, 并将该字符串添加到buff中 查看buff,如果字符数大于8 则将字符串转换为Short类型变量并写入文件 将写入的字符从buff中删除 是否到达文件尾? 结束 yes no

    代码

    while((temp=reader.read())!=-1){ //!= EOF     
                // get the code from the code table  
                String code = codeTable.get((char)temp);  
                c++;  
                if(c>=count/96){  
                    System.out.print("=");  
                    c=0;  
                }  
                try{  
                    StringBuilder codeString = new StringBuilder(code);  
                    outputStringBuffer.append(codeString);  
                    while(outputStringBuffer.length()>8){  
                        out.write(Short.parseShort(outputStringBuffer.substring(0, 8),2));  
                        outputStringBuffer.delete(0, 8);  
                    }  
                } catch(Exception e){  
                    e.printStackTrace();  
                }  
    
            }  

    解码实现

    • 流程图
    Created with Raphaël 2.1.0 开始 读压缩文件,读入文件头, 获得字符总数,字符种数以及huffman表信息, 重建huffman树 读入正文, 根据重建得到的huffman树获得原本的字符, 将字符写入解压缩后的文件 是否到达文件尾部? 结束 yes no
    • 数据结构
      HuffmanNode:huffman树中的节点信息。
    public class HuffmanNode {
        private int parent;//父节点
        private int lChild;//左子
        private int rChild;//右子
        private int weight;//权重
        }
    • 程序关键步骤

      • 重建Huffman树。在文件头中存放的原本就是Huffman树的节点信息。

        in = new DataInputStream(new FileInputStream(file));  
            count = in.readInt();  
            charNum = in.readShort();  
            nodeNum = 2*charNum -1;  
            //rebuild the huffman tree  
            for(int i=0;i<charNum;i++){  
                HuffmanNode node = new HuffmanNode((char)in.readByte());  
                int parent = in.readShort();  
                node.setParent(parent);  
                tree.add(node);  
            }  
        
            for(int i=charNum;i<nodeNum;i++){  
                HuffmanNode node = new HuffmanNode(' ');  
                int l = in.readShort();  
                int r = in.readShort();  
                int p = in.readShort();  
                node.setlChild(l);  
                node.setrChild(r);  
                node.setParent(p);  
                tree.add(node);  
            }  
      • 解码
        流程图

    Created with Raphaël 2.1.0 开始 Buff.length<32 从文件中读入整数 将读入的整数转为二进制字符串,并将其加到buff中 根据buff中的01字符从顶向下遍历huffman树, 得到叶子节点、其对应的解码值,将其写入文件, 从buff中遍历删去已经遍历过的字符 字符数是否达到总数 处理buff中剩余内容 结束 yes no yes no

    代码

    while(true){  
                while(buff.length()<32){  
                    temp = in.readInt();  
                    String codeString = Integer.toBinaryString(temp);  
                    while(codeString.length()<32){  
                        codeString='0'+codeString;  
                    }  
                    buff.append(codeString);  
                }  
                node = tree.get(tree.size()-1);  
                dep = 0;  
                while(!(node.getlChild()==-1&&node.getrChild()==-1)){  
                    if(dep>=buff.length()){  
                        System.out.println( "Buff overflow");  
                    }  
                    if(buff.charAt(dep)=='0'){  
                        node = tree.get(node.getlChild());  
                    }  
                    else if(buff.charAt(dep)=='1'){  
                        node = tree.get(node.getrChild());  
                    }  
                    else{  
                        System.out.println("Coding error");  
                    }  
                    dep++;  
                }  
    
                char c = node.getCH();  
                num++;  
                if(num>=n/99){  
                    System.out.print("=");  
                    num=0;  
                }  
                count++;  
                if(count>=n){  
                    break;  
                }  
                charBuff+=c;  
                if(charBuff.length()>256){  
                    writer.write(charBuff);  
                    charBuff="";  
                }  
                buff.delete(0, dep);  
    
            }  
    
        } catch(EOFException e){  
            //just do nothing  
        }  
        catch(Exception e){  
            e.printStackTrace();  
        } finally{  
            //there may be data released in the buff and charbuff, so we need to process them  
            while(buff.length()>0){  
                node = tree.get(tree.size()-1);  
                dep = 0;  
                while(!(node.getlChild()==-1&&node.getrChild()==-1)){  
                    if(dep>=buff.length()){  
                        break;  
                    }  
                    if(buff.charAt(dep)=='0'){  
                        node = tree.get(node.getlChild());  
                    }  
                    else if(buff.charAt(dep)=='1'){  
                        node = tree.get(node.getrChild());  
                    }  
                    else{  
                        System.out.println("Coding error");  
                        //return;  
                    }  
                    dep++;  
                }  
                char c = node.getCH();  
                num++;  
                if(num>=n/99){  
                    System.out.print("=");  
                    num=0;  
                }  
                count++;  
                if(count>=n){  
                    break;  
                }  
                charBuff+=c;  
                if(charBuff.length()>256){  
                    try {  
                        writer.write(charBuff);  
                    } catch (IOException e1) {  
                        // TODO Auto-generated catch block  
                        e1.printStackTrace();  
                    }  
                    charBuff="";  
                }  
                buff.delete(0, dep);  
            }  
    
            try {  
                writer.write(charBuff);  
                writer.close();  
            } catch (IOException e) {  
                // TODO Auto-generated catch block  
                e.printStackTrace();  
            }   
        }  
        try{  
            writer.close();  
        } catch(IOException e){  
            throw e;  
        }  

    项目源码
    留坑回头放上

    参考文章
    http://blog.csdn.net/u010485034/article/details/30750245
    http://blog.sina.com.cn/s/blog_694448320100nd5v.html

    展开全文
  • 本实例是用Matlab编写的对图像进行无损压缩的.m文件,里面要处理的文件是comp你可以换成你想要压缩的文件,功能不是很强的,但很实用,供初级人员学习用
  • 无损压缩——Huffman编码

    千次阅读 2019-05-10 11:07:07
    最近项目中涉及到人脸关键点中神经网络的压缩,采用了性能较好的哈夫曼编码进行。 源码地址:https://github.com/believeszw/HuffmanCompress 1 引言  哈夫曼(Huffman)编码算法是基于二叉树构建编码压缩结构的...

    最近项目中涉及到人脸关键点中神经网络的压缩,采用了性能较好的哈夫曼编码进行。

    源码地址:https://github.com/believeszw/HuffmanCompress

    1 引言

     哈夫曼(Huffman)编码算法是基于二叉树构建编码压缩结构的,它是数据压缩中经典的一种算法。算法根据文本字符出现的频率,重新对字符进行编码。因为为了缩短编码的长度,我们自然希望频率越高的词,编码越短,这样最终才能最大化压缩存储文本数据的空间。 
      假设现在我们要对下面这句歌词“we will we will r u”进行压缩。我们可以想象,如果是使用ASCII码对这句话编码结果则为:119 101 32 119 105 108 108 32 119 101 32 119 105 108 108 32 114 32 117(十进制表示)。我们可以看出需要19个字节,也就是至少需要152位的内存空间去存储这些数据。 
      很显然直接ASCII码编码是很浪费空间的,Unicode就更不用说了,下面我们先来统计一下这句话中每个字符出现的频率。如下表,按频率高低已排序:


    2 哈夫曼二叉树构建

    2.1 初始队列

      那么我们按出现频率高低将其放入一个优先级队列中,从左到右依次为频率逐渐增加。

    下面我们需要将这个队列转换成哈夫曼二叉树,哈夫曼二叉树是一颗带权重的二叉树,权重是由队列中每个字符出现的次数所决定的。并且哈夫曼二叉树始终保证权重越大的字符出现在越高的地方。

    2.2 第一步合并

           首先我们从左到右进行合并,依次构建二叉树。第一步取前两个字符u和r来构造初始二叉树,第一个字符作为左节点,第二个元素作为右节点,然后两个元素相加作为新空元素,并且两者权重相加作为新元素的权重。

     同理,新元素可以和字符i再合并,如下:

    2.3 重新调整队列

    上图新元素权重相加后结果是变大了,需要对权重进行重新排序。

    然后再依次从左到右合并,每合并一次则进行一次队列重新排序调整。如下:

    经过多步操作之后,得到以下的哈夫曼二叉树结构,也就是一个带有权重的二叉树:

    2.4 哈夫曼编码

    有了上面带权重的二叉树之后,我们就可以进行编码了。我们把二叉树分支中左边的支路编码为0,右边分支表示为1,如下图:

    这样依次遍历这颗二叉树就可以获取得到所有字符的编码了。例如:‘ ’的编码为10,‘l’的编码为00,‘u’的编码为11100等等。经过这个编码设置之后我们可以发现,出现频率越高的字符越会在上层,这样它的编码越短;出现频率越低的字符越会在下层,编码越短。经过这样的设计,最终整个文本存储空间才会最大化的缩减。 
      最终我们可以得到下面这张编码表:

    2.5 字符串编码


      有了上面的编码表之后,”we will we will r u”这句重新进行编码就可以得到很大的压缩,编码表示为:01 110 10 01 1111 00 00 10 01 110 10 01 1111 00 00 10 11101 10 11100。这样最终我们只需50位内存,比原ASCII码表示节约了2/3空间,效果还是很理想的。当然现实中不是简单这样表示的,还需要考虑很多问题。

    3 补充


      我们需要弄明白哈夫曼二叉树概念,它是带权路径达到最小的二叉树,也叫最优二叉树。它不一定是完全二叉树,也不一定是平衡二叉树,它们描述的完全不是一件事情,完全没有概念上的重叠关系。
     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • 视频压缩编码和音频压缩编码的基本原理

    万次阅读 多人点赞 2014-06-03 00:01:20
    本文介绍一下视频压缩编码和音频压缩编码的基本原理。其实有关视频和音频编码的原理的资料非常的多,但是自己一直也没有去归纳和总结一下,在这里简单总结一下,以作备忘。
  • 哈夫曼编码实现文件的压缩和解压

    万次阅读 多人点赞 2018-12-25 14:22:33
    哈夫曼编码是基于哈夫曼树实现的一种文件压缩方式。 哈夫曼树:一种带权路径最短的最优二叉树,每个叶子结点都有它的权值,离根节点越近,权值越小(根节点权值为0,往下随深度增加以此类推),树的带权路径等于...
  • 本文采用哈夫曼编码的方式进行文件(文本文件)压缩和解压缩,首先介绍项目的整体思路:哈夫曼编码压缩文件实际就是统计出文件中各个字符出现的频率,然后为每个字符生成对应的编码,然后将每个字符用哈夫曼编码的...
  • 基于JPRG的彩色图像分块,量化,zigzag,编码压缩matlab代码,适合初学者学习
  • 压缩原理及步骤&&压缩比的计算压缩原理及步骤压缩的第一步: 将一个文件以各个字符出现的次数为权值建立哈夫曼树,这样每个字符可以用从树根到该字符所在到叶子节点的路径来表示。(左为0,右为1) 压缩第二步: ...
  • 信息论中的编码压缩基础

    千次阅读 2014-12-01 14:48:15
    大脑是终极的压缩和通信系统。 ----《INFORMATION THEROY,INFERENCE,AND LEARNING ALGORITHMS》
  • 信息熵、编码冗余/信息熵冗余、压缩与解压缩速度等知识点的解释
  • 霍夫曼编码压缩算法

    千次阅读 2017-08-02 23:04:00
    霍夫曼编码压缩算法
  • 相位编码脉冲压缩信号的理论研究

    千次阅读 2020-09-23 20:56:55
    LFM与NLFM的调制函数是连续的,都属于连续型信号,而相位编码信号完全不同,其相位调制函数是离散的,这个和LFM及NLFM有着本质的区别。由于相位编码采用的是伪随机序列,因此这类信号又可以称之为伪随机序列编码信号...
  • 图像压缩编码冗余

    千次阅读 2019-07-21 10:29:34
    即在不丢失信息的条件下是否存在一个最小数据量来足够充分地描述一幅图像? 二、计算熵 % 创建一幅 简单的 4 x 4 图像,共含有 16 个像素 >> f = [119 123 168 119;123 119 168 168]; >> f = [f;119 ...
  • 算术编码压缩算法

    千次阅读 2018-04-08 21:51:05
    算术编码,是图像压缩的主要算法之一。 是一种无损数据压缩方法,也是一种熵编码的方法。和其它熵编码方法不同的地方在于,其他的熵编码方法通常是把输入的消息分割为符号,然后对每个符号进行编码,而算术编码是...
  • 压缩算法之字典编码(上)

    万次阅读 2017-09-23 10:50:12
    算法 信息论 字典压缩 LZ77
  • Table of Contents 1.图像压缩简介 2.图像压缩用途 3. 源编码与信道编码 4. 有损压缩与无损压缩 ...5. Huffman编码信息熵 为什么要进行编码? 概率高的符号用短码,概率低的符号用长码 Huffman...
  • 基于huffman编码的txt文件压缩和解压缩程序的C语言实现,能够对txt文件进行字符统计和信源熵计算,据此进行huffman编码,对文件进行压缩,然后解压,并编写文件对比程序,能够对解压前后的文件进行对比。
  • 数据压缩编码方法

    万次阅读 2016-12-18 12:57:55
    经典的数据压缩算法 三大类:预测编码、变换编码、统计编码 常用的解除相关性的措施是预测和变换,其实质都是进行序列的映射。 一般,预测编码有可能完全解除序列的相关性,但须确知序列的概率特性;变换编码一般...
  • 图片压缩一:霍夫曼编码压缩算法

    千次阅读 2019-03-11 22:12:48
    我们直接来看示例,如果我们需要来压缩下面的字符串: “beep boop beer!” 首先,我们先计算出每个字符出现的次数,我们得到下面这样一张表 : 然后,我把把这些东西放到Priority Queue中(用出现的次数据当 ...
  • 图像压缩编码原理

    千次阅读 2018-01-10 17:23:12
    为什么要进行图像压缩编码? 1) 在数字分量编码中,按照4:2:2格式对电视信号进行取样、量化、编码后,数据率达27MW/S。 2) 在数字高清晰度电视格式中,取样、量化、编码后的数据率会更大。 3) 电视信号...
  • JPEG压缩编码算法原理

    万次阅读 2017-11-16 15:33:12
    本文介绍JPEG压缩技术的原理,对于DCT变换、Zig-Zag扫描和Huffman编码,给出一个较为清晰的框架。 1. JPEG压缩的编解码互逆过程: 编码 解码 2. 具体过程
  • 行程编码压缩算法

    万次阅读 2015-12-21 21:20:36
    1. 算法说明RLE(Run Length Encoding行程编码)算法是一个简单高效的无损数据压缩算法,其基本思路是把数据看成一个线性序列,而这些数据序列组织方式分成两种情况:一种是连续的重复数据块,另一种是连续的不重复...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 284,730
精华内容 113,892
关键字:

压缩属于信息的编码