适用于嵌入式单片机的压缩算法 - 服务器托管|北京服务器租用|机房托管租用|IDC托管租用|机房机柜带宽租用-价格及费用咨询

1. 简介

因为MCU的内存和算力的限制，那些对内存消耗大或算力需求大的压缩算法就不适合在MCU中使用。适用于MCU的压缩算法主要有：RLE、LZ77、Huffman、LZO、DEFLATE、LZ4。

2. 算法

2.1. RLE

RLE(Run Length Encoding)，也称为行程编码，压缩算法是一种无损压缩算法。算法特点：简单、易实现。使用RLE压缩方法可以将 RRRRRGGBBBBBBABCD 压缩为 5R2G6B1A1B1C1D。基于RLE算法升级，可以将RRRRRGGBBBBBBABCD可以压缩为b’x85Rx82Gx86Bx03ABCD’，0x85表示后面有5个相同的字符，0x03表示后面有3个不连续的字符。
RLE的实现非常简单，针对一些图片颜色少或服务器托管网重复字符多的文件有非常好的压缩率，RLE的适用场景比较少，通用压缩率较差。

2.2. LZ77

LZ77是一种基于字典的算法，它将长字符串（也称为短语）编码成短小的标记，用小标记代替字典中的短语，从而达到压缩的目的。LZ77算法的压缩率、速度、内存消费都是中等，但是代码复杂度较低，适用于MCU的使用。

2.3. LZO

LZO压缩算法采用(重复长度L，指回距离D)代替当前已经在历史字符串中出现过的字符串。LZO致力于解压速度，不同的参数下的LZO压缩率不同。LZO内存消耗中等，解压速度较快，压缩速度较快，但是代码复杂度较低，适用于Bootloader等追求压缩率和解压速度的场景。

2.4. Huffman

霍夫曼(Huffman)编码使用变长编码表对源符号进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。霍夫曼编码使用的编码表，使用霍夫曼树来进行存储，让出现概率最高的编码最容易查找，以提升解码速度。霍夫曼编码算法的压缩率分布在20%-90%，因为要扫描整个数据来构建霍夫曼树，所以其压缩速度较慢，且需要一定的内存来存储编码表，但是解压速度较快。霍夫曼的算法复杂度较简单。

2.5. DEFLATE

DEFLATE是同时使用了LZ77算法与哈夫曼编码（Huffman Coding）的一个无损数据压缩算法。DEFLATE压缩与解代码可以在自由、通用的压缩库zlib上找到。DEFLATE算法压缩速度、解压速度均处于中等，却有着比较好的压缩率，所以是zlib、gzip使用的主要压缩算法。DEFLATE的算法复杂度较高，但是性能表现优秀，适用于比较大型的MCU系统。

2.6. LZ4

LZ4是一种LZ系列压缩算法，着重于压缩和解压的速度，压缩率相对较低。LZ4压缩率较低，算法复杂度和内存消耗中等，但是压缩和解压速度，尤其是解压速度远超其他算法。因为其综合性能优秀，在Linux、Android中的内存压缩技术一般使用LZ4压缩算法。LZ4 HC，有着更好的压缩率，但是算法复杂度大幅提升，且压缩速度也大幅减慢，但是依然有着很好的解压速度，适合Bootloader这种应用场景。LZ4的内存消耗从几百字节到几十K字节。

3. 基准测试

3.1. 工具用法

RLE
● 测试文件

I:Linux>RLE.exe d:a.exe
d:a.exe
Orignal Size:132096-Compressed Size:125400
Compressed rate:94%

● 测试目录

I:Linux>RLE.exe E:ATLDemoDemoDebug
E:ATLDemoDemoDebugATLProject1.exe
Orignal Size:9160192-Compressed Size:7105584
Compressed rate:77%
E:ATLDemoDemoDebugATLProject1.map
Orignal Size:19710649-Compressed Size:16943928
Compressed rate:85%

Huffman
● 测试文件

I:Linux>Huffman.exe d:a.exe
d:a.exe
Orignal Size:132096-Compressed Size:123772
Compressed rate:93%

● 测试目录

I:Linux>Huffman.exe E:ATLDemoDemoDebug
E:ATLDemoDemoDebugATLProject1.exe
Orignal Size:9160192-Compressed Size:7695483
Compressed rate:84%
E:ATLDemoDemoDebugATLProject1.map
Orignal Size:19710649-Compressed Size:15878850
Compressed rate:80%

LZ77

I:Linux>lzbench18.exe -elz4 d:a.exe
lzbench 1.8 (64-bit Windows)   Assembled by P.Skibinski
Compressor name         Compress. Decompress. Compr. size  Ratio Filename
memcpy                  35490 MB/s 35924 MB/s      132096 100.00 a.exe
lz4 1.9.2                 616 MB/s  4388 MB/s       91011  68.90 a.exe
done... (cIters=1 dIters=1 cTime=1.0 dTime=2.0 chunkSize=1706MB cSpeed=0MB)

I:Linux>lzbench18.exe -elzo1 d:a.exe
lzbench 1.8 (64-bit Windows)   Assembled by P.Skibinski
Compressor name         Compress. Decompress. Compr. size  Ratio Filename
memcpy                  35442 MB/s 36160 MB/s      132096 100.00 a.exe
lzo1 2.10 -1              150 MB/s   433 MB/s       90130  68.23 a.exe
lzo1 2.10 -99              70 MB/s   415 MB/s       85293  64.57 a.exe
done... (cIters=1 dIters=1 cTime=1.0 dTime=2.0 chunkSize=1706MB cSpeed=0MB)

I:Linux>lzbench18.服务器托管网exe -elz4 d:a.exe
lzbench 1.8 (64-bit Windows)   Assembled by P.Skibinski
Compressor name         Compress. Decompress. Compr. size  Ratio Filename
memcpy                  35085 MB/s 34689 MB/s      132096 100.00 a.exe
lz4 1.9.2                 615 MB/s  4388 MB/s       91011  68.90 a.exe
done... (cIters=1 dIters=1 cTime=1.0 dTime=2.0 chunkSize=1706MB cSpeed=0MB)

I:Linux>lzbench18.exe -elz4hc d:a.exe
lzbench 1.8 (64-bit Windows)   Assembled by P.Skibinski
Compressor name         Compress. Decompress. Compr. size  Ratio Filename
memcpy                  34462 MB/s 35944 MB/s      132096 100.00 a.exe
lz4hc 1.9.2 -1             79 MB/s  3851 MB/s       81847  61.96 a.exe
lz4hc 1.9.2 -2             79 MB/s  3840 MB/s       81847  61.96 a.exe
lz4hc 1.9.2 -3             69 MB/s  3862 MB/s       81207  61.48 a.exe
lz4hc 1.9.2 -4             63 MB/s  3885 MB/s       80896  61.24 a.exe
lz4hc 1.9.2 -5             59 MB/s  3885 MB/s       80750  61.13 a.exe
lz4hc 1.9.2 -6             56 MB/s  3896 MB/s       80650  61.05 a.exe
lz4hc 1.9.2 -7             53 MB/s  3908 MB/s       80604  61.02 a.exe
lz4hc 1.9.2 -8             51 MB/s  3919 MB/s       80586  61.01 a.exe
lz4hc 1.9.2 -9             47 MB/s  3943 MB/s       80568  60.99 a.exe
lz4hc 1.9.2 -10            29 MB/s  3919 MB/s       80454  60.91 a.exe
lz4hc 1.9.2 -11            22 MB/s  3931 MB/s       80442  60.90 a.exe
lz4hc 1.9.2 -12            20 MB/s  3896 MB/s       80420  60.88 a.exe
done... (cIters=1 dIters=1 cTime=1.0 dTime=2.0 chunkSize=1706MB cSpeed=0MB)

DEFLATE

I:Linux>lzbench18.exe -elibdeflate d:a.exe
lzbench 1.8 (64-bit Windows)   Assembled by P.Skibinski
Compressor name         Compress. Decompress. Compr. size  Ratio Filename
memcpy                  35711 MB/s 36420 MB/s      132096 100.00 a.exe
libdeflate 1.3 -1          92 MB/s   382 MB/s       69917  52.93 a.exe
libdeflate 1.3 -2          88 MB/s   387 MB/s       69425  52.56 a.exe
libdeflate 1.3 -3          85 MB/s   391 MB/s       69207  52.39 a.exe
libdeflate 1.3 -4          81 MB/s   394 MB/s       69085  52.30 a.exe
libdeflate 1.3 -5          70 MB/s   411 MB/s       68098  51.55 a.exe
libdeflate 1.3 -6          67 MB/s   408 MB/s       68034  51.50 a.exe
libdeflate 1.3 -7          62 MB/s   409 MB/s       67972  51.46 a.exe
libdeflate 1.3 -8          22 MB/s   413 MB/s       67138  50.83 a.exe
libdeflate 1.3 -9          17 MB/s   403 MB/s       66693  50.49 a.exe
libdeflate 1.3 -10         16 MB/s   401 MB/s       66627  50.44 a.exe
libdeflate 1.3 -11         13 MB/s   400 MB/s       66604  50.42 a.exe
libdeflate 1.3 -12         10 MB/s   407 MB/s       66598  50.42 a.exe
done... (cIters=1 dIters=1 cTime=1.0 dTime=2.0 chunkSize=1706MB cSpeed=0MB)

3.2. 脚本测试

脚本是基于Cygwin环境执行的shell脚本。用法如下：

26/01/2024 11:15.41/drives/i/Linux/compression_test.sh
请输入待测目录：
e:ATLDemo

total size 297101065 , total compressed size: 210777636
RLE compression rate: 70%

total size 297101065 , total compressed size: 205327668
Huffman compression rate: 69%

total size 297059235 , total compressed size: 109202247
LZ4 compression rate: 36%

total size 296918510 , total compressed size: 115966722
LZO compression rate: 39%

4. 总结

4.1. 性能

● 综合压缩率排名：DEFLATE > LZ4HC > LZO > LZ77 > Huffman > LZ4 >> RLE。
● 压缩速度排名：LZ4 > LZO > RLE > LZ77 > DEFLATE > Huffman > LZ4HC。
● 解压速度排名：RLE > LZ4=LZ4HC >> Huffman > LZO > DEFLATE > LZ77。
● 算法复杂度排名：RLE ● 算法内存消耗排名：RLE

4.2. 应用场景

不同的压缩算法，有不同的应用场景。

高压缩率，压缩速度慢，但是解压速度快的算法，适用于Bootloader。高压缩率，可以节省ROM空间，高解压速度对Boot速度影响小。因为是外部工具压缩，压缩速度不影响Bootloader的功能。适用于此场景的压缩算法有lzo、lz4hc。
追求压缩率，且算力和内存资源充足，并且压缩和解压均不错的算法，选择DEFLATE。
有一定的压缩率(50%)，追求压缩和解压速度，且算法相对简单，优先LZ4，再选择LZ77，再先LZO.
在一定的压缩率(50%)的基础上，追求算法简单，优先LZ77。
4.3. LZ77 vs LZ4
● 如果LZ77的算法复杂度为100，则LZ4的为130。压缩和解压C代码，LZ77在400行左右，LZ4在500行左右。
● 如果LZ77的内存消耗为100，则LZ4的内存消耗为50。LZ77的内存消耗十几K到几十K，LZ4的内存从几百字节到十几K字节。
● 如果LZ77的压缩速度为100，则LZ4的压缩速度为700。
● 如果LZ77的解压速度为100，则LZ4的解压速度为800。
总结，LZ4的综合性能远优于LZ77。这也是LZ4应用于Linux和Android内存压缩的重要原因。

4.3. 代码

代码

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: .NET开源免费、功能强大的 Windows 截图录屏神器

前言今天大姚给大家分享一款.NET开源免费（基于GPL3.0开源协议）、功能强大、简洁灵活的 Windows 截图、录屏、Gif动图制作神器：ShareX。功能特性 ShareX 是一个开源的屏幕捕捉工具，具有丰富的功能特性，包括但不限于：屏幕截图：支持…