对于这种情况，什么是好的（解）压缩例程
我需要一个针对受限资源环境（例如二进制（十六进制数据）嵌入式系统）进行优化的 FAST 解压缩例程，该例程具有以下特征：
- 数据面向 8 位（字节）（数据总线为 8 位宽）。
- 字节值的范围并非统一为 0 - 0xFF，而是在每个数据集中具有泊松分布（钟形曲线）。
- 数据集是预先固定好的（烧录到Flash中），每组很少>1。 1 - 2MB
压缩可能需要尽可能多的时间，但在最坏的情况下，一个字节的解压缩应该需要 23uS，内存占用最小，因为它将在资源受限的环境（如嵌入式系统）（3Mhz - 12Mhz 核心、2k）上完成字节 RAM）。
什么是好的减压程序？
基本的运行长度编码似乎太浪费了 - 我可以立即看到，向压缩数据添加标头部分以使用未使用的字节值来表示经常重复的模式将带来惊人的性能！
对于我来说，只投入了几分钟，肯定已经有来自热爱这个东西的人的更好的算法了？
我想要一些“随时可用”的示例在 PC 上进行尝试，以便我可以比较基本 RLE 的性能。
I need a FAST decompression routine optimized for restricted resource environment like embedded systems on binary (hex data) that has following characteristics:
- Data is 8bit (byte) oriented (data bus is 8 bits wide).
- Byte values do NOT range uniformly from 0 - 0xFF, but have a poisson distribution (bell curve) in each DataSet.
- Dataset is fixed in advanced (to be burnt into Flash) and each set is rarely > 1 - 2MB
Compression can take as much as time required, but decompression of a byte should take 23uS in the worst case scenario with minimal memory footprint as it will be done on a restricted resource environment like an embedded system (3Mhz - 12Mhz core, 2k byte RAM).
What would be a good decompression routine?
The basic Run-length encoding seems too wasteful - I can immediately see that adding a header setion to the compressed data to put to use unused byte values to represent oft repeated patterns would give phenomenal performance!
With me who only invested a few minutes, surely there must already exist much better algorithms from people who love this stuff?
I would like to have some "ready to go" examples to try out on a PC so that I can compare the performance vis-a-vis a basic RLE.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
当性能是唯一关心的问题时，我使用的两种解决方案：
LZO，刚刚重新打包为更适合嵌入式开发的“缩小”版本。两者在解压时都非常快。我发现在大多数情况下，
LZO将创建比liblzf稍小的压缩数据。您需要制定自己的速度基准，但我认为它们“基本上相同”。两者都比zlib快光年，但压缩效果都不好（正如您所期望的那样）。LZO，特别是miniLZO和liblzf都非常适合嵌入式目标。The two solutions I use when performance is the only concern:
LZO, just repacked in to a 'minified' version that is better suited to embedded development.Both are extremely fast when decompressing. I've found that
LZOwill create slightly smaller compressed data thanliblzfin most cases. You'll need to do your own benchmarks for speeds, but I consider them to be "essentially equal". Both are light-years faster thanzlib, though neither compresses as well (as you would expect).LZO, in particularminiLZO, andliblzfare both excellent for embedded targets.如果您有预设的值分布，这意味着每个值的概率在所有数据集上都是固定的，则可以使用固定代码创建霍夫曼编码（代码树不必嵌入到数据中）。
根据数据，我会尝试使用固定代码或 lz77 的霍夫曼（请参阅布莱恩的链接）。
If you have a preset distribution of values that means the propability of each value is fixed over all datasets, you can create a huffman encoding with fixed codes (the code tree has not to be embedded into the data).
Depending on the data, I'd try huffman with fixed codes or lz77 (see links of Brian).
好吧，我想到的主要两种算法是 Huffman 和 LZ.
第一个基本上只是创建一个字典。如果您充分限制字典的大小，它应该相当快......但不要期望有很好的压缩。
后者的工作原理是向输出文件的重复部分添加反向引用。这可能只需要很少的内存来运行，除非您需要使用文件 I/O 来读取反向引用或将最近读取的数据块存储在 RAM 中。
我怀疑LZ是你最好的选择，如果重复的部分往往彼此接近。正如您提到的，霍夫曼的工作原理是拥有一本经常重复的元素的字典。
Well, the main two algorithms that come to mind are Huffman and LZ.
The first basically just creates a dictionary. If you restrict the dictionary's size sufficiently, it should be pretty fast...but don't expect very good compression.
The latter works by adding back-references to repeating portions of output file. This probably would take very little memory to run, except that you would need to either use file i/o to read the back-references or store a chunk of the recently read data in RAM.
I suspect LZ is your best option, if the repeated sections tend to be close to one another. Huffman works by having a dictionary of often repeated elements, as you mentioned.
因为这似乎是音频，所以我会考虑差分 PCM 或 ADPCM 或类似的东西，这会将其减少到 4 位/样本，而不会造成太大的质量损失。
使用最基本的差分 PCM 实现，您只需存储当前样本和累加器之间的 4 位有符号差，并将该差值添加到累加器并移至下一个样本。如果差值超出 [-8,7]，则必须限制该值，并且累加器可能需要几个样本才能赶上。解码速度非常快，几乎不使用内存，只需将每个值添加到累加器并将累加器输出作为下一个样本。
对基本 DPCM 的一个小改进是使用查找表将 4 位值解码到更大的非线性范围，在信号变得更大和更高的音调时帮助累加器更快地赶上，其中它们仍然是 1 接近零，但以更大的增量增加到极限。和/或您可以保留其中一个值来切换乘数。由编码器决定何时使用它。通过这些改进，您可以实现更好的质量，或者每个样本使用 3 位而不是 4 位。
如果您的设备具有非线性 μ 律或 A 律 ADC，您可以获得与 11-12 位相当的质量8 位样本。或者您可以在解码器中自己完成。 http://en.wikipedia.org/wiki/M-law_algorithm
可能有便宜的芯片已经可以为您完成所有这些工作，具体取决于您正在制作的产品。我还没有调查过任何。
Since this seems to be audio, I'd look at either differential PCM or ADPCM, or something similar, which will reduce it to 4 bits/sample without much loss in quality.
With the most basic differential PCM implementation, you just store a 4 bit signed difference between the current sample and an accumulator, and add that difference to the accumulator and move to the next sample. If the difference it outside of [-8,7], you have to clamp the value and it may take several samples for the accumulator to catch up. Decoding is very fast using almost no memory, just adding each value to the accumulator and outputting the accumulator as the next sample.
A small improvement over basic DPCM to help the accumulator catch up faster when the signal gets louder and higher pitch is to use a lookup table to decode the 4 bit values to a larger non-linear range, where they're still 1 apart near zero, but increase at larger increments toward the limits. And/or you could reserve one of the values to toggle a multiplier. Deciding when to use it up to the encoder. With these improvements, you can either achieve better quality or get away with 3 bits per sample instead of 4.
If your device has a non-linear μ-law or A-law ADC, you can get quality comparable to 11-12 bit with 8 bit samples. Or you can probably do it yourself in your decoder. http://en.wikipedia.org/wiki/M-law_algorithm
There might be inexpensive chips out there that already do all this for you, depending on what you're making. I haven't looked into any.
您应该使用带有命令行开关的压缩软件工具或可以尝试不同算法的压缩库来尝试不同的压缩算法。
使用适合您的应用的典型数据。
然后您就知道哪种算法最适合您的需求。
You should try different compression algorithms with either a compression software tool with command line switches or a compression library where you can try out different algorithms.
Use typical data for your application.
Then you know which algorithm is best-fitting for your needs.
我在嵌入式系统中使用 zlib 作为引导加载程序，在启动时将应用程序映像解压缩到 RAM。该许可证非常宽松，没有 GPL 废话。它确实进行了一次 malloc 调用，但在我的例子中，我只是将其替换为返回指向静态块的指针的存根和相应的 free() 存根。我通过监视其内存分配使用情况来获得正确的大小来做到这一点。如果你的系统可以支持动态内存分配，那么就简单多了。
http://www.zlib.net/
I have used zlib in embedded systems for a bootloader that decompresses the application image to RAM on start-up. The licence is nicely permissive, no GPL nonsense. It does make a single malloc call, but in my case I simply replaced this with a stub that returned a pointer to a static block, and a corresponding free() stub. I did this by monitoring its memory allocation usage to get the size right. If your system can support dynamic memory allocation, then it is much simpler.
http://www.zlib.net/