8

任何人都可以指点我如何在低内存条件下（< 2k）实现 lzw 压缩/解压缩。那可能吗？

4

8 回答 8

4

每个人都使用的 zlib 库在其他问题中很臃肿（对于嵌入式）。我很确定它不适用于您的情况。我有更多的内存，可能是 16K，但无法适应。它分配和归零大块内存并保留内容副本等。算法也许可以做到，但找到现有代码是挑战。

我选择了http://lzfx.googlecode.com 解压循环很小，它是较旧的 lz 类型压缩，它依赖于先前的结果，因此您需要访问未压缩的结果...下一个字节是 0x5 ，下一个字节是 0x23，接下来的 15 个字节是前 15 200 个字节的副本，接下来的 6 个字节是前 127 字节的副本...较新的 lz 算法是基于可变宽度表的，可以变大或增长取决于如何实施。

我正在处理重复数据并试图将几个 K 压缩到几百个，我认为压缩率约为 50%，虽然不是很好，但完成了工作，解压缩程序很小。上面的lzfx包很小，不像zlib，像两个main函数里面有代码，而不是几十个文件。您可能会更改缓冲区的深度，如果您愿意，可能会改进压缩算法。我确实必须修改解压缩代码（可能是 20 或 30 行代码），它的指针很重，我将其切换到数组，因为在我的嵌入式环境中指针位于错误的位置。Burns 可能是一个额外的寄存器，取决于你如何实现它和你的编译器。

如果您发现更好的东西，请在此处发布或通过 stackoverflow 联系我，我也对其他嵌入式解决方案非常感兴趣。我搜索了很多，上面是我发现的唯一有用的一个，我很幸运，我的数据使用该算法压缩得足够好......现在。

于 2010-07-08T20:17:37.480 回答
3

我用过LZSS。我使用Haruhiko Okumura的代码作为基础。它使用未压缩数据（2K）的最后一部分作为字典。如果内存中有所有可用的未压缩数据，我链接的代码可以修改为几乎不使用内存。通过一些谷歌搜索，您会发现很多不同的实现。

于 2010-07-12T08:27:25.997 回答
3

任何人都可以指点我如何在低内存条件下（< 2k）实现 lzw 压缩/解压缩。那可能吗？

为什么选择 LZW？LZW 需要大量内存。它基于散列/字典，压缩率与散列/字典大小成正比。更多内存 - 更好的压缩。更少的内存 - 输出甚至可以大于输入。

我很长时间没有接触过编码，但是 IIRC Huffman 编码在内存消耗方面要好一些。

但这一切都取决于您要压缩的信息类型。

于 2010-07-08T21:33:43.053 回答
2

如果压缩算法的选择不是一成不变的，您可以尝试使用 gzip/LZ77。这是我曾经使用和改编过的一个非常简单的实现：

ftp://quatramaran.ens.fr/pub/madore/misc/myunzip.c

您需要清理它读取输入、错误处理等的方式，但这是一个好的开始。如果您的数据和代码需要适合 2k，它可能也太大了，但至少数据大小已经很小了。

最大的优点是它是公共领域，因此您可以随心所欲地使用它！

于 2010-07-09T06:17:22.707 回答
1

距离我上一次使用 LZW 压缩算法已经过去 15 年了，所以对以下内容持保留态度。

考虑到内存限制，这充其量是很困难的。您构建的字典将消耗您可用的绝大多数内容。（假设代码 + 内存 <= 2k。）

为您的字典选择一个小的固定尺寸。说 1024 个条目。

让每个字典条目采用……的形式。

 struct entry {
    intType   prevIdx;
    charType  newChar;
 };

这种结构使字典递归。您需要前一个索引处的项目有效，才能使其正常工作。这可行吗？我不确定。但是，让我们暂时假设它存在并找出它引导我们的地方......

如果使用 int 和 char 的标准类型，您将很快耗尽内存。你会想把东西尽可能紧密地打包在一起。1024 个条目将需要 10 位来存储。您的新角色可能需要 8 位。总计 = 18 位。

18 位 * 1024 个条目 = 18432 位或 2304 字节。

乍一看，这似乎太大了。我们做什么？利用前 256 个条目已知的事实——您的典型扩展 ascii 集或您有什么。这意味着我们确实需要 768 个条目。

768 * 18 位 = 13824 位或 1728 字节。

这为您留下了大约 320 字节的代码可供使用。当然，您可以随意调整字典大小，看看什么对您有好处，但您的代码最终不会有太多空间。由于您看到的代码空间如此之小，我希望您最终会在汇编中进行编码。

我希望这有帮助。

于 2010-07-08T13:04:26.697 回答
0

我最好的建议是检查BusyBox源代码，看看他们的 LZW 实现是否足够小，可以在您的环境中工作。

于 2010-07-08T12:46:34.727 回答
0

lzw 的最低字典是trie on linked list。请参阅LZW AB中的原始实现。我已经在 fork LZWS中重写了它。Fork 与compress. 详细文档在这里。

n位字典需要(2 ** n) * sizeof(code) + ((2 ** n) - 257) * sizeof(code) + (2 ** n) - 257.

所以：

  1. 9 位代码 - 1789字节。
  2. 12 位代码 - 19709字节。
  3. 16 位代码 - 326909字节。

请注意，这是字典的要求。堆栈中的状态或变量需要大约 100-150 个字节。

解压缩器将比压缩器使用更少的内存。

所以我认为您可以尝试使用9 bit版本压缩数据。但它不会提供良好的压缩比。你有更多的比特 - 比率更好。

于 2018-11-30T17:56:55.197 回答
-2 
typedef   unsigned int     UINT;
typedef   unsigned char    BYTE;

BYTE *lzw_encode(BYTE *input ,BYTE *output, long filesize, long &totalsize);
BYTE *lzw_decode(BYTE *input ,BYTE *output, long filesize, long &totalsize);
于 2013-09-13T08:39:07.863 回答