压缩小字符串，用什么创建外部字典？

Question

我希望能够压缩许多小字符串（大约75-100长度的C#字符串）。在创建字典的时候，我已经知道了所有短字符串（近万亿个）。未来不会有其他短字符串。我需要单独提取一个字符串而不解压其他字符串。

现在我正在寻找一种库或最佳方法来执行以下操作：

1. 使用我拥有的所有字符串创建字典 2. 使用此字典压缩每个字符串 3. 使用第1步中的字典压缩一个字符串的方法

我发现了一个好的相关问题，但这不是针对C#的。也许有些我不知道的东西适用于C#，或者有一个花哨的库，或者有人已经完成了这项工作。这就是我提出这个问题的原因。

编辑：

使用字典，我指的是像这样的东西：http://en.wikipedia.org/wiki/Dictionary_coder 但任何可以使字符串更短的方法都有所帮助。这些字符串是各种语言和URL的短文本消息（30％/70％）。压缩后的字符串无需人类可读。它将存储在二进制文件中。

- Chris

---

字符串中包含什么类型的数据？（大多是ASCII码吗？随机字母？GUIDs？） - Cameron

你所说的“字典”，是指存储键值对的.NET Dictionary类吗？这些字符串将作为字典中的键还是值使用？如果这些字符串只是值，那么键是什么？ - Mark Byers

大多数是ASCII码，而不是随机的。就像短信、句子和URL一样。 - Chris

我所指的字典是压缩算法所创建的字典，例如Huffman编码中使用的字典。我并不是在谈论.NET Dictionary。 - Chris

字典中的键是什么？不要跟随你所说的3。 - paparazzo

Answer 1

我没有使用过它，但Smaz听起来很有前途...

Smaz是一个简单的压缩库，适用于压缩非常短的字符串。通用的压缩库会动态地构建压缩数据所需的状态，以便能够压缩各种数据。这是一个非常好的想法，但不适用于特定问题：压缩小字符串将行不通。

相反，Smaz不适合压缩通用数据，但可以在平均情况下将文本压缩40-50％（对英语效果更好），并且还可以对HTML和URL执行一些压缩。重要的是，Smaz甚至可以压缩两到三个字节的字符串！

例如，“the”字符串被压缩为一个字节。

由于它是用C编写的，请查看Bart De Smet通过C#与C进行互操作的示例。

- Steve Wortham

---

如果它们是已知语言的短文本字符串，则smaz听起来非常理想；它将把常见的短动词（the，that，he，she，it，I等）压缩成非常短的字节序列。如果这些字符串失去了这种模式，你甚至可能会发现你的压缩字符串更长了！ - Russ Clarke

你可以尝试翻译它，或者使用Interop（请参见我的更新答案）。 - Steve Wortham

Answer 2

如果有一万亿的字符串且不再增加，那么每个字符串可以用40位（5字节）来表示。你只需要一种方法将这5个字节作为索引来使用这些字符串。

如何知道这万亿个字符串？如果压缩器和解压器都可以访问所有这些字符串，或者有一种方法来排序和重建这些字符串，那么你只需要索引就行了。

如果找不到字符串的索引方法，那么你可以从这些字符串中取一个子集，并将其用作压缩器的字典。只需取最具代表性的样本（你需要想出什么可能使一些字符串比其他字符串更常见或更具代表性），并将它们连接成一个32K的字典。约400个字符串，即这万亿个字符串的子集。然后在压缩端使用zlib的deflateSetDictionary，在解压端使用inflateSetDictionary，两者都使用完全相同的32K字典。这将为短字符串提供良好的压缩效果。

- Mark Adler

---

第一个在特殊领域不适用。但第二个（deflateSetDictionary）听起来非常有前途。我有一个关于字典的问题：假设我的字典中有以下值：“CDEFGHIJK”和“ABC”等。当我压缩字符串“ABCDEFGHIJK”时，它会使用字典中的“ABC”而不是“CDEFGHIJK”，还是不使用“ABC”而使用“CDEFGHIJK”（哪个更好）？ - Chris

另外一个问题：您写道我应该使用我的万亿个字符串中的400个。32K是字典的大小还是值的计数？因为它似乎是一个带有空终止字符串的字节数组，最可能的字符串在末尾。 - Chris

但是Deflate不知道字符串何时结束？当我有“ABC”和“DEF”，并在字典中写入“ABCDEF”时，我只会在两者之间输入一个零字节。创建字典时，我应该使用至少两个字节序列作为条目，还是非常常见的单字节字符也有用（例如“a”，“e”）？目前，我正在扫描所有文本以获取12个字符值，然后是11个字符值，依此类推。然后我得到出现次数。例如，“a”和“e”比“Hello”更常见。我还计划从第二个位置开始为每个字符串重复此过程。 - Chris

Deflate不需要知道字符串的结尾。它所寻找的只是最长匹配的字符串。缺少终止空值会增加匹配的机会。例如，如果您有一个ABC字符串和一个DEF字符串，并且它们在字典中作为ABCDEF存在，那么如果数据被压缩时恰好有一个BCDE，则该匹配项在字典中可用。匹配的最小长度为三个字符，因此常见的单个字节或字节对并不重要。 - Mark Adler

@MarkAdler 那么“将它们用作压缩器的字典”是不可能的，因为通用字典无法在压缩/解压缩单独（离散）的字符串/数据段之间共享。 - user2864740