最近做给一块蓝牙芯片做了一个decode的功能，数据是用RLE（http://en.wikipedia.org/wiki/Run-length_encoding）流程算法压缩的。为什么选用RLE算法，因为蓝牙芯片自身memory的局限性，最大只能获得不到2K的内存，还是不连续，而解压出的数据有2K多，所以需要一种能够边解压边发送的算法，查看现在流行的几种算法：霍夫曼算法，RLE算法，查表算法。
| 压缩率 | 实现复杂度 | 内存占用量 | |
| 霍夫曼算法 | 小 | 中 | 中 |
| RLE算法 | 中 | 小 | 小 |
| 查表算法 | 大 | 大 | 大（一般几十K） |
由于查表算法的内存占用量一般需要几十K，所以所以首先排除，而且比较霍夫曼算法和RLE算法，RLE算法在压缩率，实现复杂度，内存占用量三个方面都占有优势，所以最终选择RLE作为压缩和解码的方法。
花了几天时间实现了改算法，今天对其进行了性能测试，发现解压目标数据需要200多ms，遂决定对其进行优化。
step1，还原行解压函数，减少一百多次的函数调用，但是实验的结果是反而增加了100多ms，猜测可能是有远指针调用，遂放弃。
step2，将行解压函数中，对堆内存的访问换成对栈上数据的访问，实验下来时间减小到了70-80ms，性能提升了一倍多。
step3，由于采用的RLE算法是经过改进过的，n + 1行的数据是和n行数据异或过，所以增加相同数据的几率，比如有三行数据时1010 1010，理论上是不能压缩的，当时经过异或，后面两行数据都变成了0000 0000，便可以采用RLE算法进行压缩。所以根据这一特性，在step3做的优化是，比较解压出的值，如果是0，则不需要和上一行的数据进行异或（因为任何数和零异或都不变）。改进后可以将时间减小到30-40ms，又提升了一倍多。
step4，在step3的基础，在行解压算法中，如果检测到行的剩余部分都是0，则直接跳过该行剩下的部分。改进后时间减小到了十几个ms。
所以进过step2-4，性能提升了10倍多。
posted on 2011-01-19 20:40 chinese_submarine 阅读(528) 评论() 收藏 举报
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。