简单/高效的文本压缩

Question

什么是最简单但高效的压缩算法？

Deflate，LZMA等不是有效选项。我需要像RLE、LZX、Huffman等编译得非常小的东西。

注意：数据95%为ASCII文本
编辑：数据目前为20kb，但我预计会增长到1mb

编辑2：
其他有趣的选项
smaz https://github.com/antirez/smaz
FastLZ http://fastlz.org/

- arthurprs

---

你要压缩多少文本？压缩12个字符和12Mb的字符是非常不同的。 - Daniel

使用Huffman编码进行压缩通常使用的是Deflate算法...你在这里自相矛盾了。 - Billy ONeal

你正在压缩什么类型的数据？设备日志？用户日志？这些数据存储在哪个平台/设备上？ - Cypher

Answer 1

听起来LZO就是为满足您的要求而设计的：

• 解压非常简单且非常快。
• 解压时不需要任何内存。
• 压缩速度相当快。

- Greg Hewgill

---

运行得很好，压缩后的数据大小约为原始数据的58%。 - arthurprs

更新：我对文件结构进行了一些优化，现在压缩后的大小约为原始大小的40%。 - arthurprs

请注意，它的许可证是GPL。 - itsho

Answer 2

对于这种情况，采用基于BWT的方法可能会更好。 http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform
它比LZs压缩文本效果更好，而且很容易从头开始实现，并且有好的库。
http://libbsc.com
http://encode.ru/threads/104-libBWT?p=22903&viewfull=1#post22903
http://code.google.com/p/libdivsufsort/

或者，另一种选择是使用ppmd进行文本压缩，用于rar/winzip/7-zip等，但它更加复杂。
http://www.compression.ru/ds/ppmdj1.rar
http://www.compression.ru/ds/ppmsj.rar（更快/内存占用更小）
http://www.ctxmodel.net/files/PPMd/ppmd_Jr1_sh8.rar（备用端口）

- Shelwien

---

谢谢，非常有趣的选项，特别是基于BWT的选项。 - arthurprs

然而，LZma比基于BWT的bzip2更好。 - user611775

可能是在900k+个文件上。但我并没有提到bzip2，而且链接的编码者更好。 - Shelwien

Answer 3

你可以尝试使用http://scz-compress.sourceforge.net/。

- Keith Nicholas

---

看起来非常有前途，我一定会去看看。 - arthurprs

Answer 4

这个基准测试包含了很多比较内容。看一看，因为它还会显示用于压缩过程的算法。

- INS

Answer 5

大多数字典方案都可以胜任。任何一种LZ算法都可以。我们在嵌入式系统中使用LZ77变体来进行许多简单的压缩操作，它几乎没有内存开销，效果非常好。压缩和解压缩所用的系统是什么？这将决定您可以使用哪种压缩器。

- Michael Dorgan

---

我发现了两个非常好的实现，http://src.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/uts/common/os/compress.c 和 http://michael.dipperstein.com/lzw/ 第一个非常小，而且压缩效果非常好。 - arthurprs