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

Question

我正在寻找一种压缩小文本字符串的算法：50-1000个字节（即URL）。哪种算法对此最有效？

Answer 1

查看Smaz：

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

Answer 2

霍夫曼表具有静态成本，即霍夫曼表，因此我不同意这是一个不错的选择。

有一些适应性版本可以解决此问题，但是压缩率可能会受到影响。实际上，您应该问的问题是“使用哪种算法压缩具有这些特征的文本字符串”。例如，如果需要长时间重复，则简单的运行长度编码就足够了。如果可以保证仅显示英文单词，空格，标点和偶数位，那么带有预定义霍夫曼表的霍夫曼可能会产生良好的结果。

通常，Lempel-Ziv系列算法具有很好的压缩和性能，并且有大量的库供他们使用。我会去的。

有了被压缩的是URL的信息，那么我建议您在压缩之前（使用任何容易获得的算法）对它们进行编码。URL遵循定义明确的模式，并且其中的某些部分是高度可预测的。通过利用这些知识，您可以将URL编入较小的内容，而Huffman编码背后的思想可以为您提供帮助。

例如，将URL转换为位流，您可以将“ http”替换为位1，将其他任何内容替换为“ 0”，再加上实际的procotol（或使用表格获取其他常见协议，例如https， ftp，文件）。只要可以标记协议的结尾，就可以完全删除“：//”。等阅读有关URL格式的内容，并思考如何将它们编码以减少空间。

Answer 3

我没有可用的代码，但是我一直喜欢构建大小为256 * 256个字符的2D查找表的方法（RFC 1978，PPP Predictor压缩协议）。要压缩字符串，请遍历每个字符，并使用查找表使用当前和上一个字符作为表的索引来获取“预测的”下一个字符。如果匹配，则写入单个1位，否则写入0，即为char，并使用当前char更新查询表。这种方法基本上维护了数据流中最可能出现的下一个字符的动态（原始）查找表。

您可以从零查找表开始，但是如果它用每个字符对（例如英语）中最有可能出现的字符初始化，则很显然，它在非常短的字符串上最有效。只要初始查找表对于压缩和解压缩是相同的，就不需要将其发送到压缩数据中。

该算法的压缩率不高，但是在内存和CPU资源方面却非常节俭，并且还可以处理连续的数据流-解压缩器在解压缩时会维护自己的查找表副本，因此查找表调整为要压缩的数据类型。