一种有效的短文本字符串压缩算法

我正在寻找压缩小文本字符串的算法:50-1000字节(即URL).哪种算法最适合这个？

1> 小智..：

---

看看Smaz:

Smaz是一个简单的压缩库,适用于压缩非常短的字符串.

---

请参阅http://github.com/antirez/smaz/blob/master/smaz.c-这是编码的变体,而不是压缩本身(至少不完全).他使用静态单词和字母字典.

---

smaz算法针对英语文本进行了优化,因此对随机字符串不起作用.这里有一些样本(`string:orig_size:compr_size:space_savings`):`这就是它的结尾.:27:13:52%`,`Lorem ipsum dolor坐下来:26:19:27%`,` Llanfairpwllgwyngyll:20:17:15%`,`aaaaaaaaaaaa:13:13:0%`,`2BTWm6WcK9AqTU:14:20:-43%`,`XXX:3:5:-67%`

---

注意:这是antirez的项目.他是Redis的主要作者之一,在发布高质量的生产代码方面享有很高的声誉.

---

另外看看低压缩但快速算法shoco http://ed-von-schleck.github.io/shoco

2> Daniel C. So..：

---

霍夫曼有静态成本,霍夫曼表,所以我不同意这是一个不错的选择.

有适应性版本可以消除这种情况,但压缩率可能会受到影响.实际上,你应该问的问题是"压缩具有这些特征的文本字符串的算法".例如,如果预期长时间重复,则简单的Run-Lengh编码可能就足够了.如果你能保证只有英文单词,空格,punctiation和偶然的数字,那么带有预定义Huffman表的Huffman可能会产生很好的结果.

通常,Lempel-Ziv系列的算法具有非常好的压缩和性能,并且它们的库很多.我会顺其自然.

有了被压缩的信息是URL的信息,那么我建议在压缩之前(使用任何容易获得的算法),你可以对它们进行CODIFY.URL遵循定义明确的模式,其中某些部分具有高度可预测性.通过利用这些知识,您可以将URL编码为较小的内容,并且霍夫曼编码背后的想法可以帮助您.

例如,将URL转换为位流,您可以将"http"替换为位1,并将其他任何位置替换为"0",后跟实际的procotol(或使用表来获取其他常见协议,如https, ftp,文件).只要您可以标记协议的结尾,就可以完全删除"://".阅读有关URL格式的内容,并考虑如何编写它们以减少空间占用.

---

@Daniel:取决于您是否希望随机访问压缩数据.将它们压缩在一起可以防止大多数压缩系统.

---

如果霍夫曼表对于所有文件都是相同的,则不是这样,如果文件彼此相似则这是有意义的.

3> redcalx..：

---

我没有代码可以处理,但我总是喜欢构建大小为256*256个字符的2D查找表(RFC 1978,PPP预测器压缩协议)的方法.要压缩字符串,您将遍历每个char并使用查找表来使用当前和前一个char作为表中的索引来获取"预测的"下一个char.如果匹配则写入1位,否则写入0,char并使用当前char更新查找表.该方法基本上维护数据流中最可能的下一个字符的动态(和粗略)查找表.

你可以从一个归零的查找表开始,但是如果它是用每个字符对的最可能的字符初始化,例如,对于英语而言,它非常适用于非常短的字符串.只要初始查找表对于压缩和解压缩是相同的,您就不需要将其发送到压缩数据中.

这个算法没有提供出色的压缩比,但它对内存和CPU资源非常节俭,并且还可以处理连续的数据流 - 解压缩器在解压缩时维护自己的查找表副本,因此查找表调整为压缩的数据类型.

4> finnw..：

---

任何支持预设字典的算法/库,例如zlib.

这样,您可以使用可能出现在输入中的相同类型的文本来填充压缩器.如果文件在某种程度上相似(例如所有URL,所有C程序,所有StackOverflow帖子,所有ASCII艺术图纸),则某些子字符串将出现在大多数或所有输入文件中.

如果在一个输入文件中多次重复相同的子字符串,则每个压缩算法都将节省空间(例如,英文文本中的"the"或C代码中的"int".)

但在URL的情况下,某些字符串(例如" http:// www.",".com",".html",".aspx"通常会在每个输入文件中出现一次.所以你需要在文件之间共享它们不知何故,而不是每个文件有一个压缩事件.将它们放在预设字典中将实现这一点.

---

使用自定义词典的提示:http://stackoverflow.com/questions/2011653/

5> Ryan Christe..：

---

如果你所说的实际压缩文本不仅缩短了Deflate/gzip(gzip包装),zip对于较小的文件和文本也能很好地工作.其他算法对于bzip2等较大的文件非常有效.

维基百科有一个压缩时间列表.(寻找效率的比较)

Name       | Text         | Binaries      | Raw images
-----------+--------------+---------------+-------------
7-zip      | 19% in 18.8s | 27% in  59.6s | 50% in 36.4s
bzip2      | 20% in  4.7s | 37% in  32.8s | 51% in 20.0s
rar (2.01) | 23% in 30.0s | 36% in 275.4s | 58% in 52.7s
advzip     | 24% in 21.1s | 37% in  70.6s | 57& in 41.6s
gzip       | 25% in  4.2s | 39% in  23.1s | 60% in  5.4s
zip        | 25% in  4.3s | 39% in  23.3s | 60% in  5.7s

---

他想压缩文本而不压缩文件.

---

您可以使用这些算法压缩文本和二进制文件.事实上,我们在运行python的cms系统中使用deflate.