我正在寻找一种压缩小型文本字符串的算法：50-1000字节（即URL）。哪种算法最适合这种情况？
一种高效的用于短文本字符串的压缩算法
152
- Vasily Korolev
10
2你想在哪里使用这些压缩字符串？ - Gumbo
1这是要用于“tinyurls”还是与存储空间有关？ - nik
7我对一种压缩URL的算法很感兴趣，压缩比比运行成本更重要。我不想使用像tinyurl或tr.im这样的在线服务，而是寻找一种算法。没有其他信息可以提供。 - Vasily Korolev
3“短字符串的文本压缩算法”足以找到算法，为什么你对知道它们的用途如此感兴趣？我相信原帖作者能够找到符合他要求的算法。 - Dervin Thunk
7@Vasily，小提示：每当您在SO上以“什么是最好的XYZ？”的形式提出问题时，您的问题几乎肯定会收到关闭投票，因为询问最佳可能会导致不必要的产品比较，或者在最坏的情况下甚至引发口水战。（通常只需要非常小的更改就可以避免这种情况：如果您像这样问相同的问题：“请推荐一个XYZ。”，您将不会获得那么多的关闭投票，尽管它本质上是同一个问题！） - stakx - no longer contributing
显示剩余5条评论
7个回答
77
请看Smaz：
Smaz是一个简单的压缩库，适用于压缩非常短的字符串。
- stvchu
5
18请参阅http://github.com/antirez/smaz/blob/master/smaz.c -- 这是一种编码变体，而不完全是压缩。他使用静态词汇和字母词典。 - Roy Tinker
7注意：这是antirez的项目。他是Redis的主要作者之一，并以发布高质量、可用于实际生产的代码而闻名。 - Homer6
7smaz算法是针对英文文本进行优化的，因此对于随机字符串效果不佳。以下是一些样例 (
string:orig_size:compr_size:space_savings)：This is the very end of it. : 27:13:52%， Lorem ipsum dolor sit amet:26:19:27%， Llanfairpwllgwyngyll:20:17:15%， aaaaaaaaaaaaa:13:13:0%， 2BTWm6WcK9AqTU:14:20:-43%， XXX:3:5:-67%。 - mykhal4请看一下一个压缩比较低但速度比较快的算法shoco。
http://ed-von-schleck.github.io/shoco - Dickey Singh
请将我的库Unishox添加到列表https://github.com/siara-cc/unishox中。它的性能比Smaz和Shoco更好，并支持压缩UTF-8字符串。 - Arundale Ramanathan
32
Huffman有静态成本——Huffman表，所以我不认为它是一个好选择。
虽然有一些自适应版本可以避免这种成本，但可能会降低压缩率。实际上，你应该问的问题是“用哪个算法来压缩具有这些特点的文本字符串”。例如，如果预计有很长的重复，简单的游程编码就足够了。如果你能保证只有英语单词、空格、标点符号和偶尔的数字出现，那么带有预定义的Huffman表的Huffman可能会产生良好的结果。
总的来说，Lempel-Ziv家族的算法具有非常好的压缩和性能，而且有很多库可供使用。我会选择它们。
根据被压缩的内容是URLs这一信息，那么在压缩之前，我建议您对它们进行编码。URL遵循明确定义的模式，其中某些部分是高度可预测的。利用这种知识，您可以将URL编码成更小的形式，并且汉弗曼编码背后的思想可以帮助您实现这一点。
例如，将URL翻译成位流，可以用1来替换"http"，用0位和实际协议（或使用表来获取其他常见协议，比如https、ftp、file）后面的位数来表示其他任何内容。 "://"可以完全省略，只要你能标记协议的结束。等等。去阅读一下URL格式，并思考一下它们如何被编码成更小的形式。
- Daniel C. Sobral
3
4如果对于所有文件都是相同的哈夫曼表，这就是有意义的，尤其是这些文件彼此非常相似时。 - finnw
1如果你有许多相似的小文件，那么你做错了。首先，将它们全部连接起来（就像tar一样），然后再压缩。这样可以获得更好的压缩效果，并且问题不再是“50-1000字节”。 - Daniel C. Sobral
9取决于你是否需要对压缩数据进行随机访问。将所有数据一起压缩会防止大多数压缩系统进行随机访问。 - Steve Jessop
24
我手头没有代码，但我一直喜欢建立一个大小为256 * 256个字符的二维查找表的方法（RFC 1978， PPP Predictor Compression Protocol）。要压缩字符串，您循环遍历每个字符并使用查找表获取当前和上一个字符作为索引的“预测”的下一个字符。如果匹配成功，则写入单个1位，否则写入0位、字符并更新查找表。该方法基本上维护了数据流中最可能出现的下一个字符的动态（且粗略的）查找表。
您可以从零开始建立查找表，但是如果对于每个字符对，例如英语，将其初始化为最可能的字符，它在非常短的字符串上运行最佳。只要初始查找表在压缩和解压缩时相同，您就不需要将其发射到压缩的数据中。
这种算法不能提供出色的压缩比率，但它非常节省内存和CPU资源，并且也可以处理连续的数据流——解压缩器在解压缩时维护它自己的查找表，因此查找表会调整到正在压缩的数据类型。
- redcalx
4
但是预测器在普通英语句子中的表现如何呢？给定的例子具有非常强的冗余性，而收益很小。 - Danubian Sailor
1一个256*256的查找表听起来并不是“非常节约内存”...！ - MikeW
@MikeW 嗯，它是65千字节。 - redcalx
如果它是65字节，我可能会同意！ - MikeW
14
任何支持预设词典的算法/库，例如zlib。
这样，您可以使用与输入中可能出现的相同类型的文本来初始化压缩器。如果文件在某种方式上相似（例如所有URL、所有C程序、所有StackOverflow帖子、所有ASCII艺术图），则某些子字符串将出现在大多数或所有输入文件中。
每个压缩算法都会节省空间，如果同一子字符串在一个输入文件中被重复多次出现（例如英文文本中的“the”或C代码中的“int”）。
但是，在URL的情况下，某些字符串（例如“http://www。”、“.com”、“.html”、“.aspx”）通常每个输入文件只会出现一次。因此，您需要以某种方式在文件之间共享它们，而不是在每个文件中有一个压缩后的实例。将它们放在预设词典中即可实现此目的。
- finnw
1
4使用自定义词典的技巧：https://dev59.com/SnI-5IYBdhLWcg3wHUdB - Trenton
6
霍夫曼编码通常对此工作效果良好。
- Zifre
2
7这不是一个仅包含链接的回答；即使没有链接，它仍然是一个有效的回答。 - S.L. Barth
3仍然不是一个很好的答案。（没有带入足够相关的信息。） - user2864740
3
如果您想要压缩文本而不仅仅是缩短，那么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
- Ryan Christensen
5
9他想要压缩文本而不是文件。 - Gumbo
4这些算法可以压缩文本和二进制文件。事实上，在一个运行于Python的CMS系统中，我们使用Deflate算法进行压缩。 - Ryan Christensen
C#中使用gzip压缩字符串的示例在此处：http://www.csharphelp.com/archives4/archive689.html - Ryan Christensen
Python中用于压缩字符串的zlib模块：http://www.python.org/doc/2.5.2/lib/module-zlib.html - Ryan Christensen
4gzip（和zlib）使用deflate，并添加包装/框架开销。直接使用deflate/LZ77（字典开销和效率仍取决于其实现和设置）可以减少达到盈亏平衡所需的开销。当然，这只适用于几十到几百个字符的“短”字符串（仍需要一些位来指示“是否已压缩”以避免数据扩大）。更大的额外开销随着文本增加而不重要。此处发布的数字似乎针对大型文本文件（需要很长时间才能运行！），而OP要求50-1000个字符 - 相比之下是非常小的。 - user2864740
3
您可能想要查看Unicode标准压缩方案。SQL Server 2008 R2在内部使用它，可以实现高达50％的压缩。
- Le Hibou
1
SCSU可以在UTF-16/MB编码中“压缩”非英语Unicode字符。如果是基于英语的Unicode /纯旧ASCII，则UTF-8也可以“压缩”UTF-16的50%。 - user2864740
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接