单片机 压缩 算法_单片机数据压缩算法 - CSDN
  • http://www.embed-net.com/thread-192-1-1.html
    展开全文
  • 数据压缩算法在单片机上的实现 焦作大学学报
  • ![图片说明](https://img-ask.csdn.net/upload/201911/01/1572577495_787443.png) 试过了最小需要400K的内存,但是我的stm32 Ram只有192K,咋办?有人知道么?
  • 数据压缩代码,数据压缩在各种嵌入式领域得到广泛的应用,针对单片机资源有限的特点,本程序实现在单片机上可以进行数据压缩的代码。
  • 浅析数据压缩算法

    2017-05-17 16:00:23
    数据压缩是减少信息传输量最经济直接的办法,所以这篇文章将讲解一些经典的数据压缩算法。 一 热身:基因组 对于生物学的基因研究中,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

    算法(第四版)

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

    弄文件系统,为了减少空间,可能需要用到压缩。已有产品用到了LZM算法,用了之后文件大小为原先的1/10。
    在网上找了一下,找到了个miniLZO的stm32工程的例子。
    相关文章有:
    (1)几个常用快速无损压缩算法性能比较
    (2)STM32移植 MINI LZO2.09压缩算法 下载
    (3)LZO官方网站
    (4)百度快照

    (5)miniLZO压缩库使用注意事项(good,很容易忽视啊!!!)

    展开全文
  • 数据压缩算法

    2018-11-06 20:07:17
    1、传统的数据压缩算法,(https://www.cnblogs.com/esingchan/p/3958962.html这篇博文中讲的特别清楚) 2、应用神经网络的数据压缩算法:RAISR(Google)与TSR(腾讯)

    1、传统的数据压缩算法,(https://www.cnblogs.com/esingchan/p/3958962.html这篇博文中讲的特别清楚)

    2、应用神经网络的数据压缩算法:RAISR(Google)与TSR(腾讯)

    展开全文
  • C实现ZIP压缩算法

    2020-07-30 23:30:53
    用C语言实现ZIP压缩算法,包含其他一些压缩算法
  • 常见的无损压缩算法

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

    2019-06-20 04:34:36
    今天在浏览论坛的时候,看到有个网友说他的公司用的是一种新的数据压缩方法,是对应用层协议的算法做了点修改,将数据压缩给对方,速度提高原来的5倍。 呵呵,真想了解下这种技术,求高人指点下………… 转载...
  • 几种压缩算法

    2018-01-24 16:37:34
    一、 行程长度压缩  原理是将一扫描行中的颜色值相同的相邻像素用一个计数值和那些像素的颜色值来代替。... 1.PCX行程压缩方法: 该算法实际上是位映射格式到压缩格式的转换算法,该算法对于连续 出现1次的字节
  • 在一些嵌入式的项目设计中,空间是相当宝贵的,因为一个CPU的存储是有限的,所以此时我们在保存数据的时候,喜欢来进行压缩保存,著名的有哈夫曼树算法,专门用来做压缩算法,当然,本节我们不讨论这些稍微高级的...
  • 1、为什么要做数据压缩?  数据压缩的主要目的还是减少数据传输或者转移过程中的数据量。 2、什么是数据压缩? ... 是指在不丢失信息的前提下,缩减... 3、常见的数据压缩算法 (1).LZW压缩  LZW压缩是一种无...
  • 算法通过建立字典,实现字符重用与编码,适用于source中重复率很高的文本压缩。本文首先讲下LZW的编解码原理,然后给出LZW的实现code。 *********************原理********************* 编码: 编码0-...
  • 久闻 LZ4 大名,很久前就想将之与譬如 ZLib 等压缩算法作作比较了。这篇简单的测试来得晚了些,不过至少(暂时)了却了我的一桩心事。  本来我只计划对 ZLib、LZ4 和 Snappy 等作测试,但这里的LZ4 HC (r129) 引起...
  • C++: string压缩算法

    2020-03-01 12:11:10
    [编程题]压缩算法 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M 小Q想要给他的朋友发送一个神秘字符串,但是他发现字符串的过于长了,于是小Q发明了一种压缩算法对字符串中重复的部分...
  • miniLZO是一种轻量级的压缩和解压缩库,它是基于LZO压缩和解压缩算法实现的。LZO虽然功能强大,但是编译后的库文件较大,而minilzo编译后的库则小于5kb,因此miniLZO为那些仅需要简单压缩和解压缩功能的程序而设计,...
  • Lzw 针对大量的子串多次重复出现的压缩  ...今天我所给大家分享的就是一个更为引用广泛的压缩算法lzw压缩算法。 一、lzw的介绍  LZW压缩算法是一种新颖的压缩方法,由Lemple-Ziv-Welch 三人共同创造,用他们的名
  • 这是一个在CSDN论坛中讨论过的压缩算法代码。与WinRAR以最快方式压缩ZIP比较,255M的文件Level=0时 用时24.98秒 大小95.1MLevel=255时 用时30.24秒 大小91.6MWinRAR最快压缩ZIP 用时 25.2秒 大小58.6M标准RAR压缩,...
1 2 3 4 5 ... 20
收藏数 2,927
精华内容 1,170
关键字:

单片机 压缩 算法