低内存条件下的LZW压缩/解压缩

任何人都可以指出如何在低内存条件下(<2k)实现lzw压缩/解压缩。 那可能吗?

每个人都使用的zlib库在其他问题(对于嵌入式)中臃肿。 我很确定它不适合你的情况。 我有更多的记忆可能16K并且无法让它适合。 它分配和存储大块内存并保存东西的副本等。算法可以做到但是找到现有代码是挑战。

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

我正在处理重复数据并尝试将几K压缩到几百,我认为压缩率约为50%,不是很好但是工作和减压程序很小。 上面的lzfx包很小,不像zlib,就像两个主要函数那样有代码,而不是几十个文件。 您可能可能会更改缓冲区的深度,如果您愿意,可能会改进压缩算法。 我确实必须修改解压缩代码(可能是20或30行代码)它指针很重,我把它切换到数组,因为在我的嵌入式环境中,指针位于错误的位置。 Burns可能是一个额外的寄存器,取决于你如何实现它和你的编译器。 我也这样做,所以我可以抽取字节的提取和存储,因为我将它们打包到不可字节寻址的内存中。

如果你发现更好的东西请在这里发布或通过stackoverflow ping我,我也对其他嵌入式解决方案很感兴趣。 我搜索了很多,上面是我找到的唯一有用的,我很幸运,我的数据是这样的,它使用该算法压缩得足够好……现在。

任何人都可以指出如何在低内存条件下(<2k)实现lzw压缩/解压缩。 那可能吗?

为何选择LZW? LZW需要大量内存。 它基于哈希/字典,压缩比与哈希/字典大小成正比。 更多内存 – 更好的压缩。 内存越少 – 输出甚至可能大于输入。

长时间没有触及编码,但是在内存消耗方面,IIRC 霍夫曼编码要好一些。

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

如果压缩算法的选择没有一成不变,您可以尝试使用gzip / LZ77。 这是一个非常简单的实现,我使用和改编一次:

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

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

大加是它是公共领域,所以你可以随意使用它!

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

自从我上次使用LZW压缩算法以来已经超过15年了,所以请注意以下几点。

鉴于内存限制,这将是最困难的。 您构建的字典将消耗您可用的绝大部分内容。 (假设代码+内存<= 2k。)

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

让每个字典条目采取….的forms

  struct entry { intType prevIdx; charType newChar; }; 

这种结构使字典递归。 您需要先前索引处的项有效才能使其正常工作。 这可行吗? 我不确定。 但是,让我们暂时考虑它是什么,并找出它带领我们的地方….

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

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

乍一看,这看起来太大了。 我们做什么? 利用前256个条目已知的事实 – 典型的扩展ascii集或者你有什么。 这意味着我们确实需要768个条目。

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

这使得代码可以使用大约320个字节。 当然,您可以使用字典大小来查看对您有用的内容,但是您的代码不会占用很多空间。 既然你正在寻找如此少的代码空间,我希望你最终会在汇编中编码。

我希望这有帮助。

我最好的建议是检查BusyBox源代码,看看它们的LZW实现是否足够小,无法在您的环境中工作。

 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);