精华内容
下载资源
问答
  • 程序用c++实现了常用无损压缩算法Demo,并实时验证了压缩和解压缩后文件的正确性,压缩比能够实时的输出控制台和结果文件
  • 无损压缩算法原理 压缩一般分为两个步骤,建模和编码。一个完美的模型可以描述数据流是如何产生的,相当于一个python类里面的generator。只需要这个generator就可以产生所有数据,从而大大降低需要传输的数据。例如...

    无损压缩算法原理

    image-20210613195117116

    压缩一般分为两个步骤,建模和编码。一个完美的模型可以描述数据流是如何产生的,相当于一个python类里面的generator。只需要这个generator就可以产生所有数据,从而大大降低需要传输的数据。例如 如果需要传输的数据序列是1 1 2 3 5 … 6765 ,那么可以用一个“斐波那契数”来精准表达这个传输的序列。在实际应用中,很难得到这样的精准模型,因此一般都是近似的为数据构建一个数学模型。例如英文文章可以认为是一个字典模型,我们只要有字典以及对应的编号,就能还原出信息;在编码步骤中,信息将会被映射到一个编码中。可以认为是一种字典的映射,为了保证解码时信息的还原,必须要求解码时的信息映射是一一对应的。前缀码是一种比较常用的编码方式。已经证明 [McEliece 1977],对于任何可以唯一解码的非前缀代码,都可以找到具有相同码字长度的前缀代码。

    需要把无损压缩算法与我们平常使用的无损压缩格式区分开,因为无损压缩工具一般都是多种压缩算法重叠使用的,而不是单一的压缩算法。只是不同的工具侧重点不一样,一般压缩算法可以被描述成三元组< 压缩速率,解压速率,压缩率> 目前还没有哪种压缩算法能够达到三者同时最优。

    编码技术

    Huffman coding

    霍夫曼编码是一种熵编码,这种编码方式就是需要知道每个字符(symbol)出现的频率(需要扫描所有数据一次),然后构建哈夫曼二叉树。构建过程就是每次挑选出现频率最低的两个节点作为树的左右子节点,并且将它们合并成新的节点,新节点频率是它两之和。构建好huffman树后,就可以进行huffman编码,从根节点开始,左边支路编码为0,右边支路编码为1。然后再扫描一次数据,得到最优编码。缺点是耗时长,需要扫描两遍数据。因此有相关动态的huffman编码工作来提升它的性能,可能压缩率会有所下降。

    这个句子“this is an example of a huffman tree”中得到的字母频率来建构霍夫曼树。句中字母的编码和频率如图所示。编码此句子需要135 bit(不包括保存树所用的空间)

    image-20210613141559788

    构建完霍夫曼树后,就根据霍夫曼树进行编码

    字母频率编码
    space7111
    a4010
    e4000
    f31101
    h21010
    i21000
    m20111
    n20010
    s21011
    t20110
    l111001
    o100110
    p110011
    r111000
    u100111
    x110010

    而解码的过程则是需要根据霍夫曼树进行解码,因此可能需要额外传输霍夫曼树(除非使用公共的霍夫曼树)。

    缺点:对于具有均匀概率分布的一组符号,霍夫曼编码是无效的。

    Arithmetic Coding

    算术编码是一种无损数据压缩方法,也是一种熵编码的方法。和其它熵编码方法不同的地方在于,其他的熵编码方法通常是把输入的消息分割为符号,然后对每个符号进行编码,而算术编码是直接把整个输入的消息编码为一个数,一个满足(0.0 ≤ n < 1.0)的小数n。这里以一个简单的例子来说明算术编码的原理

    : 对一个简单的信号源进行观察,得到的统计模型如下:

    • 60%的机会出现符号 中性
    • 20%的机会出现符号 阳性
    • 10%的机会出现符号 阴性
    • 10%的机会出现符号 数据结束符

    根据这个统计模型,编码器可以将当前的区间分为若干子区间,子区间长度与对应符号的概率成正比。当前要编码的符号对应的子区间成为下一步编码中的初始区间。

    :对于前面提出的4符号模型:

    • 中性对应的区间是[0, 0.6)
    • 阳性对应的区间是[0.6, 0.8)
    • 阴性对应的区间是[0.8, 0.9)
    • 数据结束符对应的区间是[0.9, 1)

    编码的过程其实就是确定最终小数所在的区间,解码过程则是根据小数所在的区间进行解码。

    假设我们的信号是“中性 阴性 数据结束符”,接下来看看对这个信号进行算数编码的过程

    首先初始区间是[0,1),第一个字符“中性”使得编码后的区间在[0,0.6),然后第二个字符“阴性”使得编码后的区间进一步在[0,0.6) 的 [0.8, 0.9]这个区间,也就是[0+0.6*0.8,0+0.6*0.9) = [0.48,0.54)这个区间。最后一个字符“数据结束符”使得整个区间进一步在[0.48,0.54)的[0.9,1) 这个区间,也就是[0.48+(0.54-0.48)*0.9,0.54)=[0.534, 0.540)这个区间。因此任意在这个区间内的数都可以还原这个信息。

    在解码的过程中,假设我们拿到的数是0.538,首先他出现在初始区间[0, 0.6) 中,我们知道第一个符号肯定是“中性”,然后它又出现在[0,0.6)的[0.8, 0.9)这个区间中,我们知道第二个符号肯定是“阴性”,以此类推。

    Arithmetic_encoding.svg

    与霍夫曼编码相比,算术编码还能接受条件概率,即前面出现的字符会影响后面出现字符的概率这种情况。而原始的霍夫曼编码则是在符号之间相互独立、且分布不同时才能达到比较好的压缩效果。

    Lempel-Ziv Codes

    霍夫曼编码相比,LZW编码法被视作将不同长度字符串以固定长的码编码(霍夫曼编码将固定长度字符用不同长度的码编码)。其优点在于此方法只需存储一个相当小的表格,即可存储资料还原时相对应的值,所以所需成本相对地低;然而,这种算法的设计着重在实现的速度,由于它并没有对数据做任何分析,所以并不一定是最好的算法(参考LZMALZ77)。

    编码过程:

    1. 初始化字典使其包含所有字符串的单一字符(例如ascii码)
    2. 在字典中寻找配当前输入的最长字符串W
    3. 将该字符串对应的字典编码作为结果输出,并且将W从输入中移除
    4. 将W+W后面的那个字符添加到字典
    5. 返回第二步

    解码过程

    解码过程通过从编码后的输入中读取一个值,在字典中找到对应的项目并进行输出。这种编码方式并不需要传输字典,因为字典可以在解码过程中构造出来:当解码一个值并输出一个字符串后,解码器将它与后面值的字符串的第一个字符进行拼接,作为新的字典项目放入字典中。然后处理下一值,直到全部处理完。

    举个例子:假设要编码的字符串是"TOBEORNOTTOBEORTOBEORNOT#"

    编码过程如表

    Current SequenceNext CharOutputExtended DictionaryComments
    CodeBits
    NULLT
    TO201010027:TO27 = first available code after 0 through 26
    OB150111128:OB
    BE20001029:BE
    EO50010130:EO
    OR150111131:OR
    RN181001032:RN32 requires 6 bits, so for next output use 6 bits
    NO1400111033:NO
    OT1500111134:OT
    TT2001010035:TT
    TOB2701101136:TOB
    BEO2901110137:BEO
    ORT3101111138:ORT
    TOBE3610010039:TOBE
    EOR3001111040:EOR
    RNO3210000041:RNO
    OT#34100010# stops the algorithm; send the cur seq
    0000000and the stop code

    解码过程如下

    InputOutput SequenceNew Dictionary EntryComments
    BitsCodeFullConjecture
    1010020T27:T?
    0111115O27:TO28:O?
    000102B28:OB29:B?
    001015E29:BE30:E?
    0111115O30:EO31:O?
    1001018R31:OR32:R?created code 31 (last to fit in 5 bits)
    00111014N32:RN33:N?so start reading input at 6 bits
    00111115O33:NO34:O?
    01010020T34:OT35:T?
    01101127TO35:TT36:TO?
    01110129BE36:TOB37:BE?36 = TO + 1st symbol (B) of
    01111131OR37:BEO38:OR?next coded sequence received (BE)
    10010036TOB38:ORT39:TOB?
    01111030EO39:TOBE40:EO?
    10000032RN40:EOR41:RN?
    10001034OT41:RNO42:OT?
    0000000#

    在实际的应用中,很多压缩算法库会对lz编码后的结果再次进行huffman之类的编码。

    压缩算法

    LZ77 、LZ78以及LZO

    lz77和lz78都是基于字典的编码,lz77则会在压缩过程中维护一个滑动窗口,因此解码的时候必须从输入的起始位置开始。从概念上讲,lz78允许在解压时随机访问输入,如果整个字典都预先知道的话。然而在实际应用中,字典是在编码和解码过程中构造的。前面介绍的lz coding就是lz78编码。这里主要讲下lz77的思想:对于重复出现的字符串,我们只需要用一对<offset,length> 的数字就可以表示。例如“Hello world, hello ketty.”,对于第二个hello,我么可以用<13, 5> 来表示,表示它前面13个字符开始的5个字符(即第一个hello)。但是也可能找不到前面匹配的字符,因此使用一个三元组来表示,如利用<0,0,D>表示D本身。

    具体实现则是使用滑动窗口,维护一个search buffer 和 look-ahead buffer。search buffer+look-ahead buffer的长度就是滑动窗口的大小。search buffer就是用来查找前面出现的字符,因为lz77的编码思想就是将前面出现的字符的位置以及长度来替代当前的字符,所以对于很长的文本必须限定搜索空间,这个搜索空间就是search buffer。look-ahead buffer则包含当前字符的后面的连续字符。一般我们使用的gzip算法默认配置32KB的滑动窗口,其中绝大部分用于存储search buffer,固定长度存储look-ahead buffer (例如 262个字符)。像gzip格式实现的是lz77+huffman,这种组合就成为deflate压缩算法。

    LZO则是控制hash表的大小,并且代码实现上使用宏来减少函数的调用开销,主要通过一些工程上的优化来使得压缩算法更快。

    BWT

    也被称为块排序压缩,是一个被应用在数据压缩技术(如bzip2)中的算法。该算法于1994年被Michael BurrowsDavid Wheeler在位于加利福尼亚州帕洛阿尔托的DEC系统研究中心发明[1]。它的基础是之前Wheeler在1983年发明的一种没有公开的转换方法。

    当一个字符串用该算法转换时,算法只改变这个字符串中字符的顺序而并不改变其字符。如果原字符串有几个出现多次的子串,那么转换过的字符串上就会有一些连续重复的字符,这对压缩是很有用的。该方法能使得基于处理字符串中连续重复字符的技术(如MTF变换游程编码)的编码更容易被压缩。

    变换过程:

    算法将输入字符串的所有循环字符串按照字典序排序,并以排序后字符串形成的矩阵的最后一列为其输出。

    image-20210613194334505

    还原过程:

    基于上述的BWT变换过程,以字符串“banana”为例,我们得到了变换结果annb$aa。其还原过程见以下过程:

    1.1 基于原字符串矩阵的最后一列为annb$aa,我们进行该列进行排序,得到$aaabnn,并将其作为还原矩阵的第一列

    image-20210613194535680

    1.2 经过1.1的转移、排序和组合,我们得到了7对邻接字符串:<a$> <na> <na> <ba> <$b> <an> <an>,将这7对邻接字符串进行排序后,得到<$b> <a$> <an> <an> <ba> <na> <na>,由此,我们得到了还原矩阵的第二列b$nnaaa

    image-20210613194650197

    1.3 经过1.2的转移、排序和组合,我们得到了7对邻接字符串:<a$b> <na$> <nan> <ban> <$ba> <ana> <ana>,将这7对邻接字符串进行排序后,得到<$ba> <a$b> <ana> <ana> <ban> <na$> <nan>,由此,我们得到了还原矩阵的第三列abaan$n 依此类推

    image-20210613194842026

    PPM

    部分匹配预测 (PPM) 是一种基于上下文建模和预测的自适应统计数据压缩技术。 PPM 模型使用未压缩符号流中的一组先前符号来预测流中的下一个符号。 PPM 算法还可用于在聚类分析中将数据聚类为预测分组。例如,如果“compr”在前面出现了,则接下来出现“e”的概率就很高。PPM维护一个上下文信息来估计下一个输入字符的出现概率。算术编码就很适合这种情况,就如文中所提到的。详细来说,长的上下文将提升预估的概率,但是需要更多的时间。该方案一般有比较大的内存需求,因此具体的实现方案出现的并不多。具体实现在细节上差异会很大,目前比较知名的是PPMd,这个算法相关的介绍也比较少,因此我也没弄明白咋回事。它的应用场景却是存在的,就是WinRAR这个软件使用的就是PPMd算法。

    参考

    • https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch
    • https://zh.wikipedia.org/wiki/%E7%AE%97%E6%9C%AF%E7%BC%96%E7%A0%81
    • https://zh.wikipedia.org/wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81
    • https://zh.wikipedia.org/wiki/Burrows-Wheeler%E5%8F%98%E6%8D%A2
    • https://en.wikipedia.org/wiki/Prediction_by_partial_matching
    • Barr, Kenneth C., and Krste Asanović. “Energy-aware lossless data compression.” ACM Transactions on Computer Systems (TOCS) 24.3 (2006): 250-291.
    展开全文
  • 在数据采集和数据传输系统中常运用数据压缩技术,数据压缩通常可分为无损压缩和有损...结合常用数据无损压缩算法原理,给出了实现流程图,并着重讨论各算法的优缺点,最后分析了在实现与优化算法过程中需要注意的问题。
  • 几个常用快速无损压缩算法性能比较_追梦人_新浪博客
  • 几个常用快速无损压缩算法性能比较 SnappySnappy是在谷歌内部生产环境中被许多项目使用的压缩库,包括BigTable,MapReduce和RPC等。谷歌表示算法库针对性能做了调整,而不是针对压缩比或与其他类似工具的兼容性。在...

    几个常用快速无损压缩算法性能比较

    Snappy
    Snappy是在谷歌内部生产环境中被许多项目使用的压缩库,包括BigTable,MapReduce和RPC等。谷歌表示算法库针对性能做了调整,而不是针对压缩比或与其他类似工具的兼容性。在Intel酷睿i7处理器上,其单核处理数据流的能力达到250M/s-500M/s。Snappy同时针对64位x86处理器进行了优化,在英特尔酷睿i7处理器单一核心实现了至少250MB/s的压缩性能和500MB/ s的解压缩性能。Snappy对于纯文本的压缩率为1.5-1.7,对于HTML是2-4,当然了对于JPEG、PNG和其他已经压缩过的数据压缩率为1.0。谷歌强劲吹捧Snappy的鲁棒性,称其是“即使面对损坏或恶意输入也不会崩溃的设计”,并且在谷歌的生产环境中经过了PB级数据压缩的考验而稳定的。
    官方网站:http://code.google.com/p/snappy/

     

    FastLZ
    FastLZ是一个高效的轻量级压缩解压库,其官方测试数据如下表:
     

    几个常用快速无损压缩算法性能比较


    1GB文本数据测试:
     

    几个常用快速无损压缩算法性能比较

     

    官方网站:http://www.quicklz.com/

     

    LZO/miniLZO
    LZO是一个开源的无损压缩C语言库,其优点是压缩和解压缩比较迅速占用内存小等特点(网络传输希望的是压缩和解压缩速度比较快,压缩率不用很高),其提供了比较全的LZO库和一个精简版的miniLZO库,网上测试数据如下:
    测试的时候使用bmp和文本文件,在X86的Linux虚拟机(单核256M内存,Debian 6.0 OS)上测试。

    测试文件

    原始大小

    压缩后大小

    压缩率

    压缩时间

    解压时间

    1.bmp     

    5292054 

    159395

    3.01%

    9.174ms

    23.037ms

    2.bmp     

    6912056 

    33806     

    0.489%

    8.33ms

    36.17ms

    3.bmp     

    6220856 

    5101891 

    82%

    25.78ms

    28.43ms

    lzo.tar

    6645760 

    2457890 

    36.98%

    34.68ms

    38.62ms

    kdoc.tar

    16660480

    6987402

    41.93%

    102.86ms

    108.2ms

    kinc.tar

    18257920

    5684927 

    31.13%   

    106.87ms

    113.86ms


    来自《HBase: The Definitive Guide》中的一个对比: 

    Algorithm

    % remaining

    Encoding

    Decoding

    GZIP

    13.4%

    21 MB/s

    118 MB/s

    LZO

    20.5%

    135 MB/s

    410 MB/s

    Zippy/Snappy

    22.2%

    172 MB/s

    409 MB/s

    展开全文
  • 数据压缩算法—2无损压缩算法

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

    几个常见的编码算法

    (一) 字典算法

      字典算法是最为简单的压缩算法之一。它是把文本中出现频率比较多的单词或词汇组合做成一个对应的字典列表,并用特殊代码来表示这个单词或词汇。例如:
      有字典列表:
      00=Chinese
      01=People
      02=China
      源文本:I am a Chinese people,I am from China 压缩后的编码为:I am a 00 01,I am from 02。压缩编码后的长度显著缩小,这样的编码在SLG游戏等专有名词比较多的游戏中比较容易出现,比如《SD高达》。

    (二) 固定位长算法(Fixed Bit Length Packing)

      这种算法是把文本用需要的最少的位来进行压缩编码。
      比如八个十六进制数:1,2,3,4,5,6,7,8。转换为二进制为:00000001,00000010,00000011,00000100,00000101,00000110,00000111,00001000。每个数只用到了低4位,而高4位没有用到(全为0),因此对低4位进行压缩编码后得到:0001,0010,0011,0100,0101,0110,0111,1000。然后补充为字节得到:00010010,00110100,01010110,01111000。所以原来的八个十六进制数缩短了一半,得到4个十六进制数:12,34,56,78。
      这也是比较常见的压缩算法之一。

    (三) RLE算法

      这种压缩编码是一种变长的编码,RLE根据文本不同的具体情况会有不同的压缩编码变体与之相适应,以产生更大的压缩比率。
      变体1:重复次数+字符
    文本字符串:A A A B B B C C C C D D D D,编码后得到:3 A 3 B 4 C 4 D。
      变体2:特殊字符+重复次数+字符
    文本字符串:A A A A A B C C C C B C C C,编码后得到:B B 5 A B B 4 C B B 3 C。编码串的最开始说明特殊字符B,以后B后面跟着的数字就表示出重复的次数。
      变体3:把文本每个字节分组成块,每个字符最多重复 127 次。每个块以一个特殊字节开头。那个特殊字节的第 7 位如果被置位,那么剩下的7位数值就是后面的字符的重复次数。如果第 7 位没有被置位,那么剩下 7 位就是后面没有被压缩的字符的数量。例如:文本字符串:A A A A A B C D E F F F。编码后得到:85 A 4 B C D E 83 F(85H= 10000101B、4H= 00000100B、83H= 10000011B)
      以上3种不RLE变体是最常用的几种,其他还有很多很多变体算法,这些算法在Winzip Winrar这些软件中也是经常用到的。

    (四) LZ77算法

      LZ77算法是由 Lempel-Ziv 在1977发明的,也是GBA内置的压缩算法。LZ77算法有许多派生算法(这里面包括 LZSS算法)。它们的算法原理上基本都相同,无论是哪种派生算法,LZ77算法总会包含一个滑动窗口(Sliding Window)一个前向缓冲器(Read Ahead Buffer)。滑动窗口是个历史缓冲器,它被用来存放输入流的前n个字节的有关信息。一个滑动窗口的数据范围可以从 0K 到 64K,而LZSS算法使用了一个4K的滑动窗口。前向缓冲器是与滑动窗口相对应的,它被用来存放输入流的前n个字节,前向缓冲器的大小通常在0 – 258 之间。这个算法就是基于这些建立的。用下n个字节填充前向缓存器(这里的n是前向缓存器的大小)。在滑动窗口中寻找与前向缓冲器中的最匹配的数据,如果匹配的数据长度大于最小匹配长度 (通常取决于编码器,以及滑动窗口的大小,比如一个4K的滑动窗口,它的最小匹配长度就是2),那么就输出一对**〈长度(length),距离(distance)〉**数组。长度(length)是匹配的数据长度,而距离(distance)说明了在输入流中向后多少字节这个匹配数据可以被找到。
      LZ77压缩算法采用字典的方式进行压缩,是一个简单但十分高效的数据压缩算法。其方式就是把数据中一些可以组织成短语(最长字符)的字符加入字典,然后再有相同字符出现采用标记来代替字典中的短语,如此通过标记代替多数重复出现的方式以进行压缩。LZ77的主要算法逻辑就是,先通过前向缓冲区预读数据,然后再向滑动窗口移入(滑动窗口有一定的长度),不断的寻找能与字典中短语匹配的最长短语,然后通过标记符标记。
      在这里插入图片描述
      目前从前向缓冲区中可以和滑动窗口中可以匹配的最长短语就是(A,B),然后向前移动的时候再次遇到(A,B)的时候采用标记符代替。

    4.1 压缩

      当压缩数据的时候,前向缓冲区与移动窗口之间在做短语匹配的是后会存在2种情况:
      找不到匹配时:将未匹配的符号编码成符号标记(多数都是字符本身)
      找到匹配时:将其最长的匹配编码成短语标记。
      短语标记包含三部分信息:(滑动窗口中的偏移量(从匹配开始的地方计算)、匹配中的符号个数、匹配结束后的前向缓冲区中的第一个符号)。
      一旦把n个符号编码并生成响应的标记,就将这n个符号从滑动窗口的一端移出,并用前向缓冲区中同样数量的符号来代替它们,如此,滑动窗口中始终有最新的短语。通过图来进行解释:
      在这里插入图片描述

    4.2 解压

      解压类似于压缩的逆向过程,通过解码标记和保持滑动窗口中的符号来更新解压数据。
      在这里插入图片描述
      解码字符标记:将标记编码成字符拷贝到滑动窗口中。
      解码短语标记:在滑动窗口中查找响应偏移量,同时找到指定长短的短语进行替换。
      但数组是无法直接用二进制来表示的,LZ77会把编码每八个数分成一组,每组前用一个前缀标示来说明这八个数的属性。比如数据流:A B A C A C B A C A按照LZ77的算法编码为:A B A C<2,2> <4,5>,刚好八个数。按照LZ77的规则,用“0”表示原文输出,“1”表示数组输出。所以这段编码就表示为:00001111B(等于0FH),因此得到完整的压缩编码表示:F A B A C 2 2 4 5。虽然表面上只缩短了1个字节的空间,但当数据流很长的时候就会突出它的优势,这种算法在zip格式中是经常用到。
      

    (五)香农-范诺算法

      将序列分成两部分,使得左部频率总和尽可能接近右部频率总和。
    在这里插入图片描述

    (六)霍夫曼编码(Huffman Encoding)

      香农 - 法诺并不总是产生最优的前缀码:概率{0.35,0.17,0.17,0.16,0.15}是一个将分配非优化代码的Shannon-Fano的编码的一个例子。
      出于这个原因,香农 - 范诺几乎从不使用; 哈夫曼编码几乎是计算简单,生产总是达到预期最低的码字长度的制约下,每个符号是由一个整数组成一个代码代表的前缀码。在大多数情况下,[算术编码]可以产生比哈夫曼或的香农-范诺更大的整体压缩,因为它可以在小数位编码,这更接近实际的符号信息内容。然而,算术编码并没有取代像霍夫曼取代的香农-范诺一样取代哈夫曼,一方面是因为算术编码的计算成本的方式,因为它是由多个专利覆盖。
      在这里插入图片描述
      例如:
      字符串:
        “beep boop beer!”

    字符次数
    ‘b’3
    ‘e’4
    ‘p’2
    ‘ ’2
    ‘o’2
    ‘r’1
    ‘!’1

      然后,我把把这些东西放到Priority Queue中(用出现的次数据当 priority),我们可以看到,Priority Queue 是以Prioirry排序一个数组,如果Priority一样,会使用出现的次序排序。
      接下来把这个Priority Queue 转成二叉树。
      我们始终从queue的头取两个元素来构造一个二叉树(第一个元素是左结点,第二个是右结点),并把这两个元素的priority相加,并放回Priority中(再次注意,这里的Priority就是字符出现的次数)。
      然后,我们再把前两个取出来,形成一个Priority为2+2=4的结点,然后再放回Priority Queue中。继续我们的算法(我们可以看到,这是一种自底向上的建树的过程)。最终我们会得到下面这样一棵二叉树。
      此时,我们把这个树的左支编码为0,右支编码为1,这样我们就可以遍历这棵树得到字符的编码,比如:‘b’的编码是 00,’p’的编码是101, ‘r’的编码是1000。我们可以看到出现频率越多的会越在上层,编码也越短,出现频率越少的就越在下层,编码也越长。
      在这里插入图片描述
      最终我们可以得到下面这张编码表:

    字符霍夫曼编码
    ‘b’00
    ‘e’11
    ‘p’101
    ‘ ’011
    ‘o’010
    ‘r’1000
    ‘!’1001

      这里需要注意一点,当我们encode的时候,我们是按“bit”来encode,decode也是通过bit来完成,比如,如果我们有这样的bitset “1011110111″ 那么其解码后就是 “pepe”。所以,我们需要通过这个二叉树建立我们Huffman编码和解码的字典表。
      这里需要注意的一点是,我们的Huffman对各个字符的编码是不会冲突的,也就是说,不会存在某一个编码是另一个编码的前缀,不然的话就会大问题了。因为encode后的编码是没有分隔符的。
      于是,对于我们的原始字符串 beep boop beer!
      其对就能的二进制为 : 0110 0010 0110 0101 0110 0101 0111 0000 0010 0000 0110 0010 0110 1111 0110 1111 0111 0000 0010 0000 0110 0010 0110 0101 0110 0101 0111 0010 0010 0001
      我们的Huffman的编码为: 0011 1110 1011 0001 0010 1010 1100 1111 1000 1001

    (七)范式霍夫曼编码(Canonical Huffman Code)

    7.1 为什么霍夫曼编码不好,而采用范式霍夫曼编码?
    (1)解码器需要知道哈夫曼编码树的结构,因而编码器必须为解码器保存或传输哈夫曼编码树;
    (2)
    7.2 范式霍夫曼编码要求(1)是前缀编码(2)某一字符编码长度和使用二叉树建立的该字符的编码长度相同。
    7.3 范式霍夫曼编码的步骤
    (1)统计每个要编码符号的频率;
    (2)依据这些频率信息求出,该符号在传统Huffman编码树中的深度,也就是该符号需要的位数、编码长度、码长;
    (3)编码长度由短到长排列,按照以下方式计算范式霍夫曼编码的码:第一位码是按照霍夫曼编码树的码长全设为0,接下里的码是上一个编码+1;
    (4)如果霍夫曼编码树的码长变长,则需要采用 本次编码 = 2*(本次码长-上次码长) * ( 上一个编码 + 1 )得到。
    例如,依据上节的结果,建立范式霍夫曼编码:

    字符霍夫曼编码霍夫曼编码码长范式霍夫曼编码备注
    ‘b’00200按码长全设为0
    ‘e’11201相同码长时,上一码+1
    ‘p’1013100不同码长时,2*(3-2)*(上一码 + 1)
    ‘ ’0113101相同码长时,上一码+1
    ‘o’0103110相同码长时,上一码+1
    ‘r’100041110不同码长时,2*(4-3) *(上一码 + 1)
    ‘!’100141111相同码长时,上一码+1
    (八)算术编码
    8.1 编码原理

    (1)假设有一段数据需要编码,统计里面所有的字符和出现的次数。
    (2)将区间 [0,1) 连续划分成多个子区间,每个子区间代表一个上述字符, 区间的大小正比于这个字符在文中出现的概率 p。概率越大,则区间越大。所有的子区间加起来正好是 [0,1)。
    (3)编码从一个初始区间 [0,1) 开始,设置: low=0,high=1
    (4)不断读入原始数据的字符,找到这个字符所在的区间,比如 [ L, H ),更新:
        low=low+(high−low)∗L
        high=low+(high−low)∗H
    (5)最后将得到的区间 [low, high)中任意一个小数以二进制形式输出即得到编码的数据。

    8.2 例程

      原始数据:ARBER
      计算出现的频率:

    SymbolTimesP
    A10.2
    B10.2
    E10.2
    R20.4

      将这几个字符的区间在 [0,1) 上按照概率大小连续一字排开,我们得到一个划分好的 [0,1)区间:
    在这里插入图片描述
      开始编码,初始区间是 [0,1)。注意这里又用了区间这个词,不过这个区间不同于上面代表各个字符的概率区间 [0,1)。这里我们可以称之为编码区间,这个区间是会变化的,确切来说是不断变小。我们将编码过程用下图完整地表示出来:
    在这里插入图片描述
      拆解开来一步一步看:
      (1)刚开始编码区间是 [0,1),即
        low=0
        high=1
      (2)第一个字符A的概率区间是 [0,0.2),则 L = 0,H = 0.2,更新
        low=low+(high−low)∗L=0
        high=low+(high−low)∗H=0.2
      (3)第二个字符R的概率区间是 [0.6,1),则 L = 0.6,H = 1,更新
        low=low+(high−low)∗L=0.12
        high=low+(high−low)∗H=0.2
      (4)第三个字符B的概率区间是 [0.2,0.4),则 L = 0.2,H = 0.4,更新
        low=low+(high−low)∗L=0.136
        high=low+(high−low)∗H=0.152
      (5)如此以上往复计算。
      上面的图已经非常清楚地展现了算数编码的思想,我们可以看到一个不断变化的小数编码区间。每次编码一个字符,就在现有的编码区间上,按照概率比例取出这个字符对应的子区间。例如一开始A落在0到0.2上,因此编码区间缩小为 [0,0.2),第二个字符是R,则在 [0,0.2)上按比例取出R对应的子区间 [0.12,0.2),以此类推。每次得到的新的区间都能精确无误地确定当前字符,并且保留了之前所有字符的信息,因为新的编码区间永远是在之前的子区间。最后我们会得到一个长长的小数,这个小数即神奇地包含了所有的原始数据,不得不说这真是一种非常精彩的思想。

    8.3 解码

      如果你理解了编码的原理,则解码的方法显而易见,就是编码过程的逆推。从编码得到的小数开始,不断地寻找小数落在了哪个概率区间,就能将原来的字符一个个地找出来。例如得到的小数是0.14432,则第一个字符显然是A,因为它落在了 [0,0.2)上,接下来再看0.14432落在了 [0,0.2)区间的哪一个相对子区间,发现是 [0.6,1), 就能找到第二个字符是R,依此类推。在这里就不赘述解码的具体步骤了。
      编程实现:
      算数编码的原理简洁而又精致,理解起来也不很困难,但具体的编程实现其实并不是想象的那么容易,主要是因为小数的问题。虽然我们在讲解原理时非常容易地不断计算,但如果真的用编程实现,例如C++,并且不借助第三方数学库,我们不可能简单地用一个double类型去表示和计算这个小数,因为数据和编码可以任意长,小数也会到达小数点后成千上万位。
      怎么办?其实也很容易,小数点是可以挪动的。给定一个编码区间,例如从上面例子里最后的区间 [0.14432,0.1456)开始,假定还有新的数据进来要继续编码。现有区间小数点后的高位0.14其实是确定的,那么实际上14已经可以输出了,小数点可以向后移动两位,区间变成 [0.432,0.56),在这个区间上继续计算后面的子区间。这样编码区间永远保持在一个有限的精度要求上。
      上述是基于十进制的,实际数字是用二进制表示的,当然原理是一样的,用十进制只是为了表述方便。算数编码/解码的编程实现其实还有很多tricky的东西和corner case,我当时写的时候debug了好久,因此我也建议读者自己动手写一遍,相信会有收获。

    8.4 算术编码 vs 哈夫曼编码

      这其实是我想重点探讨的一个部分。在这里默认你已经懂哈夫曼编码,因为这是一种最基本的压缩编码,算法课都会讲。哈夫曼编码和算数编码都属于熵编码,仔细分析它们的原理,这两种编码是十分类似的,但也有微妙的不同之处,这也导致算数编码的压缩率通常比哈夫曼编码略高,这些我们都会加以探讨。
      不过我们首先要了解什么是熵编码,熵是借用了物理上的一个概念,简单来说表示的是物质的无序度,混乱度。信息学里的熵表示数据的无序度,熵越高,则包含的信息越多。其实这个概念还是很抽象,举个最简单的例子,假如一段文字全是字母A,则它的熵就是0,因为根本没有任何变化。如果有一半A一半B,则它可以包含的信息就多了,熵也就高。如果有90%的A和10%的B,则熵比刚才的一半A一半B要低,因为大多数字母都是A。
      熵编码就是根据数据中不同字符出现的概率,用不同长度的编码来表示不同字符。出现概率越高的字符,则用越短的编码表示;出现概率地的字符,可以用比较长的编码表示。这种思想在哈夫曼编码中其实已经很清晰地体现出来了。那么给定一段数据,用二进制表示,最少需要多少bit才能编码呢?或者说平均每个字符需要几个bit表示?其实这就是信息熵的概念,如果从数学上理论分析,香农天才地给出了如下公式:
      在这里插入图片描述
      其中 p (xi) 表示每个字符出现的概率。log对数计算的是每一个字符需要多少bit表示,对它们进行概率加权求和,可以理解为是求数学期望值,最后的结果即表示最少平均每个字符需要多少bit表示,即信息熵,它给出了编码率的极限。
      算术编码和哈夫曼编码的比较
      在这里我们不对信息熵和背后的理论做过多分析,只是为了帮助理解算数编码和哈夫曼编码的本质思想。为了比较这两种编码的异同点,我们首先回顾哈夫曼编码,例如给定一段数据,统计里面字符的出现次数,生成哈夫曼树,我们可以得到字符编码集:

    SymbolTimesEncoding
    a300
    b301
    c210
    d1110
    e2111

    在这里插入图片描述
      仔细观察编码所表示的小数,从0.0到0.111,其实就是构成了算数编码中的各个概率区间,并且概率越大,所用的bit数越少,区间则反而越大。如果用哈夫曼编码一段数据abcde,则得到:00 01 10 110 111。
      如果点上小数点,把它也看成一个小数,其实和算数编码的形式很类似,不断地读入字符,找到它应该落在当前区间的哪一个子区间,整个编码过程形成一个不断收拢变小的区间。
      由此我们可以看到这两种编码,或者说熵编码的本质。概率越小的字符,用更多的bit去表示,这反映到概率区间上就是,概率小的字符所对应的区间也小,因此这个区间的上下边际值的差值越小,为了唯一确定当前这个区间,则需要更多的数字去表示它。我们仍以十进制来说明,例如大区间0.2到0.3,我们需要0.2来确定,一位足以表示;但如果是小的区间0.11112到0.11113,则需要0.11112才能确定这个区间,编码时就需要5位才能将这个字符确定。其实编码一个字符需要的bit数就等于 -log ( p ),这里是十进制,所以log应以10为底,在二进制下以2为底,也就是香农公式里的形式。
      哈夫曼编码的不同之处就在于,它所划分出来的子区间并不是严格按照概率的大小等比例划分的。例如上面的d和e,概率其实是不同的,但却得到了相同的子区间大小0.125;再例如c,和d,e构成的子树,c应该比d,e的区间之和要小,但实际上它们是一样的都是0.25。我们可以将哈夫曼编码和算术编码在这个例子里的概率区间做个对比:
      在这里插入图片描述
      这说明哈夫曼编码可以看作是对算数编码的一种近似,它并不是完美地呈现原始数据中字符的概率分布。也正是因为这一点微小的偏差,使得哈夫曼编码的压缩率通常比算数编码略低一些。或者说,算数编码能更逼近香农给出的理论熵值。
      更好地理解,最简单的例子
      比如有一段数据,A出现的概率是0.8,B出现的概率是0.2,现在要编码数据:
      AAA…AAABBB…BBB (800个A,200个B)
      如果用哈夫曼编码,显然A会被编成0,B会被编成1,如果表示在概率区间上,则A是 [0, 0.5),B是 [0.5, 1)。为了编码800个A和200个B,哈夫曼会用到800个0,然后跟200个1:
      0.000…000111…111 (800个0,200个1)
      在编码800个A的过程中,如果我们试图去观察编码区间的变化,它是不断地以0.5进行指数递减,最后形成一个 [0, 0.5^800) 的编码区间,然后开始B的编码。
      但是如果是算术编码呢?因为A的概率是0.8,所以算数编码会使用区间 [0, 0.8) 来编码A,800个A则会形成一个区间 [0, 0.8^800),显然这个区间比 [0, 0.5^800) 大得多,也就是说800个A,哈夫曼编码用了整整800个0,而算数编码只需要不到800个0,更少的bit数就能表示。
      当然对B而言,哈夫曼编码的区间大小是0.5,算数编码是0.2,算数编码会用到更多的bit数,但因为B的出现概率比A小得多,总体而言,算术编码”牺牲“B而“照顾”A,最终平均需要的bit数就会比哈夫曼编码少。而哈夫曼编码,由于其算法的特点,只能“不合理”地使用0.5和0.5的概率分布。这样的结果是,出现概率很高的A,和出现概率低的B使用了相同的编码长度1。两者相比,显然算术编码能更好地实现熵编码的思想。
      从另外一个角度来看,在哈夫曼编码下,整个bit流可以清晰地分割出原始字符串:
      在这里插入图片描述
      而在算术编码下,每一个字符并不是严格地对应整数个bit的,有些字符与字符之间的边界可能是模糊的,或者说是重叠的,所以它的压缩率会略高:
      在这里插入图片描述
      当然这样的解释并不完全严格,如果一定要究其原因,那必须从数学上进行证明,算数编码的区间分割是更接近于信息熵的结果的,这就不在本文的讨论范围了。在这里我只是试图用更直观地方式解释算数编码和哈夫曼编码之间微妙的区别,以及它们同属于熵编码的本质性原理。

    8.5 总结

      算术编码的讲解就到这里。说实话我非常喜欢这种编码以及它所蕴含的思想,那种触及了数学本质的美感。如果说哈夫曼编码只是直观地基于概率,优化了字符编码长度实现压缩,那么算术编码是真正地从信息熵的本质,展现了信息究竟是以怎样的形式进行无损压缩,以及它的极限是什么。在讨论算术编码时,总是要提及哈夫曼编码,并与之进行比较,我们必须认识到它们之间的关系,才能对熵编码有一个完整的理解。
    reference:
    https://segmentfault.com/img/bVWFcv?w=515&h=287
      
      
      
      
      

    展开全文
  • 无损压缩算法历史

    2019-09-27 11:31:06
    无损压缩算法可行的基本原理是,任意一个非随机文件都含有重复数据,这些重复数据可以通过用来确定字符或短语出现概率的统计建模技术来压缩。统计模型可以用来为特定的字符或者短语生成代码,基于它们出现的频率,...

    引言

    无损压缩算法可行的基本原理是,任意一个非随机文件都含有重复数据,这些重复数据可以通过用来确定字符或短语出现概率的统计建模技术来压缩。统计模型可以用来为特定的字符或者短语生成代码,基于它们出现的频率,配置最短的代码给最常用的数据。这些技术包括熵编码(entropy encoding),游程编码(run-length encoding),以及字典压缩。运用这些技术以及其它技术,一个8-bit长度的字符或者字符串可以用很少的bit来表示,从而大量的重复数据被移除。

    历史

    直到20世纪70年代,数据压缩才在计算机领域开始扮演重要角色,那时互联网变得更加流行,Lempel-Ziv算法被发明出来,但压缩算法在计算机领域之外有着更悠久的历史。发明于1838年的Morse code,是最早的数据压缩实例,为英语中最常用的字母比如"e"和"t"分配更短的Morse code。之后,随着大型机的兴起,Claude Shannon和Robert Fano发明了Shannon-Fano编码算法。他们的算法基于符号(symbol)出现的概率来给符号分配编码(code)。一个符号出现的概率大小与对应的编码成反比,从而用更短的方式来表示符号。

    两年后,David Huffman在MIT学习信息理论并上了一门Robert Fano老师的课,Fano给班级的同学两个选项,写一篇学期论文或者参加期末考试。Huffman选择的是写学期论文,题目是寻找二叉编码的最优算法。经过几个月的努力后依然没有任何成果,Huffman决定放弃所有论文相关的工作,开始学习为参加期末考试做准备。正在那时,灵感爆发,Huffman找到一个与Shannon-Fano编码相类似但是更有效的编码算法。Shannon-Fano编码和Huffman编码的主要区别是构建概率树的过程不同,前者是自下而上,得到一个次优结果,而后者是自上而下。

    早期的Shannon-Fano编码和Huffman编码算法实现是使用硬件和硬编码完成的。直到20世纪70年代互联网以及在线存储的出现,软件压缩才被实现为Huffman编码依据输入数据动态产生。随后,1977年Abraham Lempel 和 Jacob Ziv发表了他们独创性的LZ77算法,第一个使用字典来压缩数据的算法。特别的,LZ77使用了一个叫做slidingwindow的动态字典。1778年,这对搭档发表了同样使用字典的LZ78算法。与LZ77不同,LZ78解析输入数据,生成一个静态字典,不像LZ77动态产生。

    法律问题

    Deflate的崛起

    当前的一些归档软件

    压缩技术

    有许多不同的技术被用来压缩数据。大多数技术都不能单独使用,需要结合起来形成一套算法。那些能够单独使用的技术比需要结合的技术通常更加有效。其中的绝大部分都归于entropy编码类别下面,但其它的一些技术也挺常用,如Run-Length Encoding和Burrows-Wheeler Transform。

    Run-Length Encoding

    Run-Length Encoding是一个非常简单的压缩技术,把重复出现的多个字符替换为重复次数外加字符。单个字符次数为1。RLE非常适合数据重复度比较高的数据,同一行有很多像素颜色相同的渐进图片,也可以结合Burrows-Wheeler Transform等其它技术一起使用。

    下面是RLE的一个简单例子:

    输入: AAABBCCCCDEEEEEEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA输出: 3A2B4C1D6E38A

    Burrows-Wheeler Transform

    Burrows-Wheeler Transform是1994年发明的技术,目的是可逆的处理一段输入数据,使得相同字符连续出现的次数最大化。BWT自身并不做任何的压缩操作,仅简单地转化数据,让Run-Length Encoder等压缩算法可以更有效的编码。

    Entropy Encoding

    数据压缩中,平均来说为了表示一个字符或短语,Entropy意味着所需要的最少bit数。一个基本的entropy编码器包括一个分析模型以及一套编码。输入文件被解析,并产生一个由字符出现概率组成的统计模型。然后,编码器可以利用该统计模型去决定该给每一个字符多少个bit,从而使得最常用的字符用最短的编码,反之最不常用的字符用最长的编码。

    Shannon-Fano Coding

    这是最早的压缩技术,于1949年由Claude Shannon和Robert Fano发明。这个技术的其中一个步骤是产生一个代表字符出现概率的二叉树。字符以这样一种方式排序,出现得越频繁的字符越靠近树的顶端,越不常见的越靠近树的底部。

    一个字符对应的编码通过搜索Shannon-Fano来获得,此外,左分支后面加0,右分支加1。例如,"A"是两个左节点后接一个右节点,那么对于的编码为"0012"。Shannon-Fano coding不总是能够产生最优的编码,主要是由于二叉树是自下而上构建的。由于这个原因,使用的较多的还是对于任意输入都能够得到最优编码的Huffman coding。

    Huffman Coding

    Huffman Coding是另外一个entropy coding的例子,与Shannon-Fano Coding非常的相似,只是为了产生最优编码二叉树是自上而下构建的。

     

    更详细见:http://blog.csdn.net/kimylrong/article/details/39405981

    转载于:https://www.cnblogs.com/bonelee/p/6903843.html

    展开全文
  • 常见的无损压缩算法

    万次阅读 2018-12-01 16:17:00
    无损压缩算法 LZ77 算法 LZ77 算法的关键是搜索,即在已经处理过的符号序列(数据流)中,寻找与待编码符号序列相同的模式,如果找到匹配的模式,就设法对这个模式进行索引,也就是生成一个指针,然后输出该索引...
  • LZW压缩算法(数据无损压缩

    千次阅读 2020-09-02 09:11:53
    零、常用无损数据压缩算法 字典算法 游程编码 基于字典编码技术的LZW算法 基于哈夫曼编码原理的压缩算法 基于算术编码的压缩算法 一、LZW算法介绍 LZW(Lempel-Ziv-Welch Encoding)算法又叫“串表压缩算法...
  • 文件系统的无损压缩算法miniLZO

    千次阅读 2016-09-27 10:54:34
    弄文件系统,为了减少空间,可能...(1)几个常用快速无损压缩算法性能比较 (2)STM32移植 MINI LZO2.09压缩算法 下载 (3)LZO官方网站 (4)百度快照 (5)miniLZO压缩库使用注意事项(good,很容易忽视啊!!!)...
  • 无损压缩算法发展

    千次阅读 2016-12-01 15:50:24
    History of Lossless Data Compression Algorithms Introduction There are two major categories of compression algorithms: lossy and lossless. Lossy compression algorithms involve the redu
  • 二 叉树 引言 随着网络发展的速度越来越快,视频, 音频的广泛应用使得大数据量的传输显得尤 为重要,如何更快更多更好地传输与存 储数据成为数据信息处理的首要问题 在压缩算法中分为无损压缩和有损压
  • 常用压缩算法以及区别

    千次阅读 2017-07-21 11:52:07
    常用压缩算法主要有:deflate、gzip、bzip2、lzo、snappy等。差别如下所示: deflate、gzip都是基于LZ77算法与哈夫曼编码的无损数据压缩算法,gzip只是在deflate格式上增加了文件头和文件尾; bzip2是...
  • 引言 有两种主要的压缩算法: 有损和无损。有损压缩算法通过移除在保真情形下需要大量...无损压缩,也使文件变小,但对应的解压缩功能可以精确的恢复原文件,不丢失任何数据。无损数据压缩被广泛的应用于计算机领域...
  • 无损数据压缩算法发展史

    千次阅读 2015-05-11 22:26:41
    内容丰富,闲暇时可以细品 ...有两种主要的压缩算法: 有损和无损。有损压缩算法通过移除在保真情形下需要大量的数据去存储的小细节,从而使...无损压缩,也使文件变小,但对应的解压缩功能可以精确的恢复原文件,

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,954
精华内容 2,381
关键字:

常用的无损压缩的算法