c - 在嵌入式设备上膨胀(解压缩)数据流

Question

我打算对通过慢速串行接口(interface)传输的数据流进行压缩。解压缩应该在资源有限(无操作系统、无线程、有限内存)的低成本微 Controller 上进行。

在之前的类似配置中，我使用了 zlib 的 puff.c，但在那种情况下，a 有一个缓冲区存储之前的所有数据，并且可以一次膨胀。

在我的实际情况下，我没有足够的内存来容纳这种缓冲区，所以我需要逐步膨胀数据。因此，我需要能够在每次新数据到达时调用它，而不是让 puff 在缓冲区上工作，从而在后续调用之间保持内部状态。

在我开始深入研究 zlib 或 zlibs puff.c 之前，有人知道这类问题是否已经在某处解决了吗？

Answer 1

.GIF文件格式压缩算法(LZW，LZ78 的变体)几乎只需要在内存中维护一个哈希表。当表填满时，它会被清空，并重复该过程，这意味着表不会无限增长。也没有必要保留压缩数据。几乎不需要维护其他状态。使用这样的算法(也许，哈希表大小减小)，您可以在数据进入时对其进行解压缩。

我没有研究其他 LZ 算法，但我希望(部分或全部？)它们在本质上是相似的。