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

小开

Huffman 编码通常可以很好地解决这个问题。

小开

如果你说的是实际压缩文本，而不仅仅是缩短，那么 Deflate/gzip (gzip 周围的包装器) ，对于较小的文件和文本，zip 工作得很好。其他算法对于像 bzip2这样的大文件非常有效。

Wikipedia 有一个压缩时间列表(查看效率比较)

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

小开

霍夫曼有一个静态成本，霍夫曼表，所以我不同意这是一个很好的选择。

有一些自适应版本可以消除这个问题，但是压缩率可能会受到影响。实际上，您应该问的问题是“用什么算法压缩具有这些特征的文本字符串”。例如，如果需要长时间的重复，那么简单的运行长度编码就足够了。如果您可以保证只有英语单词、空格、标点符号和偶尔出现的数字会出现，那么带有预定义 Huffman 表的 Huffman 可能会产生很好的结果。

一般来说，Lempel-Ziv 系列算法具有很好的压缩性能和良好的性能，而且它们的库比比皆是。我觉得也是。

根据被压缩的信息是 URL，那么我建议，在压缩之前(使用任何容易获得的算法) ，对它们进行 CODIFY。URL 遵循定义良好的模式，其中有些部分是高度可预测的。通过利用这些知识，您可以将 URL 编码为更小的内容，Huffman 编码背后的想法可以帮助您。

例如，将 URL 转换成一个位流，您可以将“ http”替换为位1，并将其他任何位“0”替换为实际协议(或者使用一个表来获得其他通用协议，如 https、 ftp、 file)。可以完全删除“ ://”，只要您可以标记协议的结束。等等。去阅读关于 URL 格式的文章，并思考如何将它们编码以节省空间。

小开

任何支持预设字典的算法/库，例如 Zlib。

通过这种方式，您可以使用输入中可能出现的相同类型的文本来启动压缩器。如果文件在某些方面是相似的(例如所有的 URL，所有的 C 程序，所有的 StackOverflow 文章，所有的 ASCII-art 绘图) ，那么某些子字符串将出现在大多数或所有的输入文件中。

如果同一个子串在一个输入文件中重复多次，每个压缩算法都会节省空间(例如，英文文本中的“ the”或 C 代码中的“ int”)

但是在 URL 的情况下，某些字符串(例如“ http://www”)“ .com”。Html 」，「。Aspx”通常在每个输入文件中出现一次。因此，您需要以某种方式在文件之间共享它们，而不是为每个文件提供一个压缩的匹配项。将它们放在预设的字典中就可以做到这一点。

小开

最佳答案

看看 Smaz:

Smaz 是一个简单的压缩库，适用于非常短的压缩绳子。

小开

我手头没有代码，但是我总是喜欢构建一个大小为256 * 256个字符(RFC 1978，预测压缩协议)的2D 查找表的方法。要压缩字符串，您需要遍历每个字符，并使用查找表获取“预测的”下一个字符，使用当前和以前的字符作为表中的索引。如果有匹配你写一个1位，否则写一个0，字符和更新查找表与当前字符。这种方法基本上维护数据流中最可能的下一个字符的动态(和原始)查找表。

您可以从一个零查找表开始，但是显然，如果使用每个字符对的最可能的字符(例如，对于英语)进行初始化，它在非常短的字符串上工作得最好。只要初始查找表对于压缩和解压缩是相同的，就不需要将其发送到压缩数据中。

这个算法并没有给出一个完美的压缩比，但是它对于内存和 CPU 资源非常节约，并且可以处理连续的数据流——解压缩器在解压缩时维护自己的查找表副本，因此查找表可以根据被压缩的数据类型进行调整。

小开

你可能想看看 Unicode 标准压缩方案。

SQLServer2008R2在内部使用它，可以实现高达50% 的压缩。