logo标签列表

非常简单的字符串压缩

c#stringcompressionshort
25

有没有一种适用于长度不超过255个字符的字符串的非常简单的压缩技术（是的，我正在压缩URLs）？

我不关心压缩的强度 - 我正在寻找一些表现非常好且实现快速的东西。我想要比SharpZipLib更简单的东西：一些可以用几个简短的方法实现的东西。

为什么？你所询问的问题可能有更好的解决方法。 - Sam Harwell
2
“为什么”确实是一个好答案。然而，顺带一提，Huffman编码非常适用于简单文本压缩，而无需求助于外部库和LZW压缩。 - 3Dave
3
可能是短文本字符串的最佳压缩算法的重复问题。 - Donal Fellows
9个回答
20

我认为这里的关键问题是：“你为什么想要压缩URL？”

是为了缩短地址栏上的长URL吗？

你最好将原始URL存储在某个地方（数据库、文本文件等），并将非域部分的哈希码（MD5可行）与其一起存储。然后可以有一个简单的页面（或者如果你感觉兴奋，可以使用一些HTTP模块）来读取MD5并查找真正的URL。这就是TinyURL和其他类似服务的工作原理。

例如：

http://mydomain.com/folder1/folder2/page1.aspx

可以缩短为：

http://mydomain.com/2d4f1c8a

使用压缩库来处理这个问题是行不通的。字符串将被压缩为较短的二进制表示形式，但将其转换回需要作为URL一部分有效的字符串（例如Base64）将抵消您从压缩中获得的任何收益。

需要在内存或磁盘中存储大量URL吗？

请使用System.IO.Compression中内置的压缩库或简单且表现非常好的ZLib库进行压缩。由于您将存储二进制数据，因此压缩输出本身就已经足够。您需要解压缩它以将其用作URL。

10
这不是对问题的回答。如果你没有地方存储哈希表怎么办？ - endolith
@endolith - 关键是字符串压缩在这里没有帮助，只有将其与哈希或类似的东西相关联。请参见Cheeso的答案，其中包含现实世界中的示例，当转换回有效URL时，压缩长度更长但原始长度相同。您总是有“某个地方”可以存储哈希。如果您真的没有“任何地方”可以存储它，请将其硬编码到您的URL重定向代码中！ - badbod99
1
你并不总是有地方来存储一个哈希表，而且它也不会总是使URL变长。例如http://en.wikipedia.org/wiki/Data_URI_scheme。 - endolith
Data uri并不是任何形式的压缩，也与缩短URL没有任何关系。实际上，data uri是用于在网页中嵌入数据并使用base64编码的。如果您阅读了chesso的答案，您将会发现它更长。那么在什么情况下您没有地方存储url/hash代码引用呢？如果您有一种可以缩短URL而仍然是有效URL的压缩形式，请将其发布为答案，我相信社区将受益。 - badbod99
12

正如被接受的回答建议的那样，使用数据压缩并不能缩短已经相当短的 URL 路径。

DotNetZip 有一个 DeflateStream 类，它公开了一个静态的（在 VB 中为 Shared 的）CompressString 方法。这是一种使用 DEFLATE（RFC 1951）压缩字符串的一行代码方式。DEFLATE 实现完全兼容System.IO.Compression.DeflateStream，但 DotNetZip 压缩效果更好。以下是可能的用法：

string[] orig = {
    "folder1/folder2/page1.aspx",
    "folderBB/folderAA/page2.aspx",
};
public void Run()
{
    foreach (string s in orig)
    {
        System.Console.WriteLine("original    : {0}", s);
        byte[] compressed = DeflateStream.CompressString(s);
        System.Console.WriteLine("compressed  : {0}", ByteArrayToHexString(compressed));
        string uncompressed = DeflateStream.UncompressString(compressed);
        System.Console.WriteLine("uncompressed: {0}\n", uncompressed);
    }
}

使用该代码，这是我的测试结果：

original    : folder1/folder2/page1.aspx
compressed  : 4bcbcf49492d32d44f03d346fa0589e9a9867a89c5051500
uncompressed: folder1/folder2/page1.aspx

original    : folderBB/folderAA/page2.aspx
compressed  : 4bcbcf49492d7272d24f03331c1df50b12d3538df4128b0b2a00
uncompressed: folderBB/folderAA/page2.aspx
因此，您可以看到“压缩”字节数组在十六进制表示时比原始数组长约两倍。原因是十六进制字节实际上是两个 ASCII 字符。
您可以通过使用基于 62 进制而不是基于 16 进制（十六进制）来表示数字来在某种程度上弥补这一点。在这种情况下，a-z 和 A-Z 也是数字，为您提供了0-9（10）+ a-z（+26）+ A-Z（+26）= 62个数字。 这将显着缩短输出长度。我还没有尝试过。
编辑：好的，我已经测试了基于 62 进制的编码器。它将十六进制字符串缩短了约一半。我认为它会将其减少到 25％（62/16〜4），但我认为我在离散化方面失去了一些东西。在我的测试中，结果基于 62 进制编码的字符串与原始 URL 的长度大致相同。因此，使用压缩然后进行基于 62 进制的编码仍然不是一个好方法。您真的需要哈希值。
1
使用十六进制相当愚蠢，它根本不是一种密集的格式。使用base64甚至base85，并用正确的字符替换无效字符（再次转义会占用空间），肯定会减少输出。虽然没有你所声称的那么多，但肯定会有所减少。当然，URI越短，期望的压缩就越少，而且上下文也很重要。 - Maarten Bodewes
1
这个答案的结论（“使用压缩然后...仍然不是一个好方法”）已经不再有效-请参见我的答案-https://dev59.com/UHM_5IYBdhLWcg3w3nRs#50751602 - Kind Contributor
3
3

我刚刚创建了一个压缩方案，针对URL并实现了约50%的压缩（与原始URL文本的base64表示相比）。

请参见http://blog.alivate.com.au/packed-url/

如果有一家大型科技公司能够将其完善并发布供所有人使用，那将是非常好的。谷歌推出了Protocol Buffers。这个工具可以为像谷歌这样的公司节省很多磁盘空间，同时仍然可以进行扫描。或者也许是伟大的船长自己？https://twitter.com/capnproto

从技术上讲，我会称之为数据模型的二进制（位）序列化方案，该数据模型是URL底层数据的文本表示形式，然后使用专门的序列化器对该概念数据模型进行序列化。当然，结果是原始版本的更压缩版本。这与通用压缩算法的工作方式非常不同。

我认为这正是我正在寻找的。你有任何示例代码或项目可以分享吗？我在你提供的网站上没有找到任何东西。 - Jake Shakesworth
我有一些代码可以找出来。请在我的博客上留言，我们可以通过那里联系。 - Kind Contributor
你找到它了吗？ - Endless
1

您可以直接使用deflate算法，不需要任何头部校验和尾部，如此问题中所述：Python：Inflate和Deflate实现。

在我的测试中，这将一个4100个字符的URL削减到了1270个base64字符，使其适合IE的2000限制。

And here's an example of a 4000-character URL, which can't be solved with a hashtable since the applet can exist on any server.

1
不关心压缩的强度 - 我正在寻找一个性能非常好且快速实现的东西。你能指引我使用base64吗？ - cbp
6
Base64不会压缩任何内容 :) - Jon Grant
@Jon Grant：正确。Base64是个愚蠢的建议。只有在实际压缩后才能得到一些（也许）更小但仍然是ASCII的东西。已将所有与此相关的内容删除。 - peSHIr
0
0

你尝试过只使用gzip吗？

我不确定它是否能有效地处理这么短的字符串，但我认为这可能是你最好的选择。

0

开源库SharpZipLib易于使用，可为您提供压缩工具

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接