有人能指导我如何在低内存条件（＜2k）下实现LZW压缩/解压缩吗？这可行吗？
低内存条件下的LZW压缩/解压缩
8
- Manas
4
1环境是什么？ - ULysses
我需要将这段代码放入一款低端手机的专有软件中... - Manas
我已经更新了您的标签，添加了“嵌入式”，这样您就可以接触到与<2K等受限资源一起工作的程序员。由于需要使用字典，您可能需要探索其他压缩算法（例如LZ77？）。 - tomlogic
1约束条件是瞬态内存使用还是输入/输出大小？ - MSN
8个回答
4
大家都使用的zlib库在嵌入式等方面存在臃肿等问题。我很确定它不适合你的情况。即使我有更多的内存，可能达到16K，也无法让它适应。它会分配和清零大块内存并保留副本等。算法或许可以实现，但是找到现有代码是个挑战。
我选择了http://lzfx.googlecode.com。解压循环非常小，这是较旧的lz类型压缩，依赖于之前的结果，因此需要访问未压缩的结果...下一个字节是0x5，下一个字节是0x23，接下来的15个字节是15个字节前的副本，接下来的6个字节是127个字节前的副本...新的lz算法是基于可变宽度表的，可以根据实现方式变得很大或增长。
我正在处理重复数据，并试图将几个K压缩成几百个字节，我认为压缩率约为50％，虽然不是很好，但完成了工作，解压缩例程很小。上面的lzfx包很小，不像zlib那样，只有两个主要函数，代码就在那里，没有几十个文件。您可以更改缓冲区的深度，可能还可以改进压缩算法。我确实需要修改解压缩代码（大约20或30行代码），它使用指针很多，我将其切换到数组，因为在我的嵌入式环境中指针位置不正确。根据您的实现方式和编译器，它可能会烧掉额外的寄存器或者不会。我这样做是为了能够抽象出字节的提取和存储，因为我将它们打包到不可寻址的内存中。
如果您找到更好的东西，请在此处发布或通过stackoverflow联系我，我也非常感兴趣其他嵌入式解决方案。我搜索了很多，上述是我找到的唯一有用的一个，而且我很幸运，我的数据足够压缩使用该算法...至少目前是这样。
我选择了http://lzfx.googlecode.com。解压循环非常小，这是较旧的lz类型压缩，依赖于之前的结果，因此需要访问未压缩的结果...下一个字节是0x5，下一个字节是0x23，接下来的15个字节是15个字节前的副本，接下来的6个字节是127个字节前的副本...新的lz算法是基于可变宽度表的，可以根据实现方式变得很大或增长。
我正在处理重复数据，并试图将几个K压缩成几百个字节，我认为压缩率约为50％，虽然不是很好，但完成了工作，解压缩例程很小。上面的lzfx包很小，不像zlib那样，只有两个主要函数，代码就在那里，没有几十个文件。您可以更改缓冲区的深度，可能还可以改进压缩算法。我确实需要修改解压缩代码（大约20或30行代码），它使用指针很多，我将其切换到数组，因为在我的嵌入式环境中指针位置不正确。根据您的实现方式和编译器，它可能会烧掉额外的寄存器或者不会。我这样做是为了能够抽象出字节的提取和存储，因为我将它们打包到不可寻址的内存中。
如果您找到更好的东西，请在此处发布或通过stackoverflow联系我，我也非常感兴趣其他嵌入式解决方案。我搜索了很多，上述是我找到的唯一有用的一个，而且我很幸运，我的数据足够压缩使用该算法...至少目前是这样。
- old_timer
2
1有一个叫做pucrunch的压缩程序http://www.cs.tut.fi/~albert/Dev/pucrunch/，也许你会觉得很有趣。 - ninjalj
我发现了这个网址：http://www.embedded.com/design/opensource/217800397
它说：“这种压缩技术能够实现可观的压缩比，通常在50%至60%之间，同时只消耗大约2K的RAM”……我需要试一下。 - Manas
3
有人能指导一下我如何在低内存条件（＜2k）下实现LZW压缩/解压缩吗？这可能吗？
为什么选择LZW？LZW需要大量的内存。它基于哈希/字典，压缩比与哈希/字典大小成正比。内存越多-压缩越好。内存越少-输出甚至可能比输入更大。
我已经很久没有碰编码了，但我记得在内存消耗方面霍夫曼编码可能会更好一些。
但这都取决于您想要压缩的信息类型。
为什么选择LZW？LZW需要大量的内存。它基于哈希/字典，压缩比与哈希/字典大小成正比。内存越多-压缩越好。内存越少-输出甚至可能比输入更大。
我已经很久没有碰编码了，但我记得在内存消耗方面霍夫曼编码可能会更好一些。
但这都取决于您想要压缩的信息类型。
- Dummy00001
3
我曾经使用过 LZSS。我使用了来自 Haruhiko Okumura 的代码作为基础。它使用未压缩数据的最后一部分（2K）作为字典。如果您在内存中拥有所有未压缩的数据，则可以修改链接的代码以几乎不使用任何内存。通过一些谷歌搜索，你会找到许多不同的实现。
- Gerhard
2
如果压缩算法的选择并非固定不变，建议尝试gzip/LZ77。以下是我曾使用和修改过的非常简单的实现：ftp://quatramaran.ens.fr/pub/madore/misc/myunzip.c。需要清理输入、错误处理等方面，但这是一个很好的起点。如果你的数据和代码都需要适应2k，那么它可能也太大了，但至少数据大小已经很小了。最大的优点是它是公有领域的，所以你可以随意使用！
- R.. GitHub STOP HELPING ICE
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个字节的代码空间。当然，您可以尝试调整字典大小以找到适合自己的大小，但是您最终可用于代码的空间将非常有限。由于您只有很少的代码空间，我预计您最终会使用汇编语言编写代码。
希望这能有所帮助。
- Sparky
2
是否有可能在每次查找时放弃字典并重新解析以仅获取所需条目？当然，这将非常缓慢，但这可能是唯一的方法。 - R.. GitHub STOP HELPING ICE
@R..：我不这么认为。字典是编/解码器的状态。编码流中的位是字典中的索引。 - Dummy00001
0
lzw 的最低字典是基于链表的 trie。可以在 LZW AB 中查看原始实现。我已经在 fork LZWS 中进行了重写。该 fork 与 compress 兼容。详细文档请参见 此处。
n 位字典需要 (2 ** n) * sizeof(code) + ((2 ** n) - 257) * sizeof(code) + (2 ** n) - 257。
所以：
- 9 位代码 - 1789 字节。
- 12 位代码 - 19709 字节。
- 16 位代码 - 326909 字节。
解压器将比压缩器使用更少的内存。
因此，我认为您可以尝试使用9位版本压缩数据。但它不会提供很好的压缩比率。您拥有的位数越多，比率就越好。
- puchu
0
我的最佳建议是检查BusyBox的源代码，看看他们的LZW实现是否足够小，可以在你的环境中使用。
- R.. GitHub STOP HELPING ICE
3
可能不是这样的 - BusyBox 旨在用于资源更丰富的系统。 - tomlogic
1你是否进行了检查，而不仅仅是说“可能不行”？BusyBox中的几乎所有算法都是开发人员能够找到/创建的最小算法（无论是代码大小还是工作空间），通常以牺牲良好性能为代价。如果性能太差，通常有一个编译时选项可以在小尺寸和可怕性能之间进行选择。 - R.. GitHub STOP HELPING ICE
@tomlogic：我过去看到的大多数LZW实现都将字典（主内存）的大小作为编译时定义。值得检查一下。如果我没记错，字典的最小大小是257+1。但那相当于根本没有压缩。 - Dummy00001
-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);
- demon
1
2这怎么能回答问题呢？哪里有关于库的描述或链接。或者关于大小或其他信息的资料。 - jeb
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接