一个有效的短文本string压缩algorithm
我正在寻找一种algorithm来压缩小文本string：50-1000字节（即URL）。 哪种algorithm最适合这个？
退房Smaz ：
Smaz是一个简单的压缩库，适合压缩非常短的string。
霍夫曼有一个静态成本，霍夫曼表，所以我不同意这是一个很好的select。
有适应性的版本可以解决这个问题，但压缩率可能会受到影响。 其实，你应该问的问题是“用这些特征压缩文本串的algorithm是什么”。 例如，如果期望长时间的重复，简单的Run-Lengh Encoding可能就足够了。 如果你能保证只有英文单词，空格，短句和偶尔的数字出现，那么带有预先定义的霍夫曼表的霍夫曼可能会产生好的结果。
一般来说，Lempel-Ziv家族的algorithm具有很好的压缩性能，而且它们的库很多。 我会去那个。
有了什么被压缩的信息的url，那么我build议，在压缩之前（无论什么algorithm很容易获得），你要对它们进行编码。 URL遵循定义明确的模式，其中一些部分是高度可预测的。 通过利用这些知识，你可以将URL编码成更小的东西，哈夫曼编码背后的想法可以帮助你。
例如，将URL转换为比特stream，可以用位1代替“http”，用“0”代替实际的协议（或者使用表来获得其他常用协议，如https， ftp，文件）。 只要你可以标记协议的结尾，“：//”就可以完全丢弃。 等等阅读URL格式，并考虑如何编写这些代码来占用较less的空间。
我没有代码，但我总是喜欢build立一个尺寸为256 * 256字符（ RFC 1978 ， PPP预测压缩协议 ）的二维查找表的方法。 要压缩一个string，您可以遍历每个字符，并使用查找表获取“预测的”下一个字符，并使用当前字符和前一个字符作为索引。 如果有一个匹配，你写一个1位，否则写一个0，字符和更新当前字符的查找表。 这种方法基本上保持了数据stream中最可能的下一个字符的dynamic（粗略的）查找表。
您可以从一个归零查找表开始，但是如果使用每个字符对的最可能的字符（例如英语语言）进行初始化，则显然对于非常短的string来说效果最好。 只要最初的查找表对于压缩和解压缩是相同的，则不需要将其发送到压缩数据中。
这个algorithm不能提供出色的压缩比，但是它非常节省内存和CPU资源，并且也可以在连续的数据stream上工作 – 解压缩器在解压缩时维护自己的查找表副本，因此查找表根据被压缩的数据types进行调整。
任何支持预设字典的algorithm/库，例如zlib 。
通过这种方式，您可以使用与input中可能出现的相同types的文本填充压缩器。 如果这些文件在某些方面是相似的（例如，所有的URL，所有的C程序，所有的StackOverflow文章，所有的ASCII艺术图纸），那么某些子string将出现在大部分或全部input文件中。
如果在一个input文件中多次重复相同的子string（例如，英文中的“the”或C代码中的“int”），每个压缩algorithm将节省空间。
但在URL的情况下，某些string（例如“ http：// www 。”，“.com”，“.html”，“.aspx”）通常会在每个input文件中出现一次，因此您需要在文件之间共享它们而不是每个文件都有一个压缩的事件，把它们放到一个预置的字典里就可以达到这个目的。
如果您正在讨论实际上压缩文本，而不仅仅是缩短Deflate / gzip（围绕gzip的包装），那么压缩文件和文本更好。 其他algorithm对于像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
霍夫曼编码通常适用于此。
你可能想看看Unicode的标准压缩scheme 。
SQL Server 2008 R2在内部使用它，可以实现高达50％的压缩率。
