压缩大量小字符串的算法？

Question

我正在寻找一种算法来压缩小的ASCII字符串。它们包含许多字母，但也可能包含数字和很少的特殊字符。它们将很小，平均约50-100字节，最大为250字节。

例如：

Android show EditText.setError() above the EditText and not below it
ImageView CENTER_CROP dont work
Prevent an app to show on recent application list on android kitkat 4.4.2
Image can't save validable in android
Android 4.4 SMS - Not receiving sentIntents
Imported android-map-extensions version 2.0 now my R.java file is missing
GCM registering but not receiving messages on pre 4.0.4. devices

我希望逐个压缩标题，而不是将许多标题一起压缩。我对CPU和内存使用不太关心。

- Luka

---

文本非常适合进行zip压缩，你可能想这样做，它可以作为独立工具使用，并且还是几个库的一部分。 - dtech

搜索压缩库应该能给你一个开始的方向。 - Some programmer dude

我尝试了这个，它使标题变大了。 - Luka

压缩少量数据很少能比原始输入获得更好（更小）的结果，因为需要额外的头部来指示如何解码压缩数据。您可以针对此特定情况应用专有（自己的）方法。您有52个字母、10个数字和空格，总共63个符号。您可以使用7位编码每个符号（而不是8位）。第一位始终为0，其余6位将映射到您的63个符号中的任何一个。对于任何“非常规符号”，请使用1后跟该符号的ASCII代码（即9位而不是8位）。 - barak manos

通常不是最佳解决方案，但在这种情况下...你可以从一组典型的标题中构建一个霍夫曼压缩表，然后对每个标题使用该表进行霍夫曼压缩。 - James Kanze

Answer 1

您可以使用Huffman编码，并在所有要压缩的文本之间共享一个Huffman树。

通常情况下，您需要为每个要压缩的字符串构建一个Huffman树，但这会导致大量存储开销，应该在此避免。这也是在您的情况下使用标准压缩方案的主要问题：它们中的大多数都有一些开销，这会使非常短的字符串的压缩效率降低。其中一些不会有太大开销，但通常在一般情况下效率较低。

当构建用于压缩和解压缩的Huffman树时，通常使用将被压缩的文本来决定哪个字符使用哪些位进行编码。由于在您的情况下要压缩的文本似乎事先不知道，因此需要一些“伪造”的文本来构建树，可能来自人类语言的字典或以前的用户数据经验。

然后构建哈夫曼树并将其存储在应用程序中，可以将其硬编码到二进制文件中或以文件形式提供。然后您就可以使用此树压缩和解压缩任何文本。每当您决定更改树时，因为您对压缩的文本有更好的了解，压缩的字符串表示也会更改。引入版本控制并将树版本与每个压缩的字符串一起存储可能是一个好主意。

另一个您可以考虑的改进是使用多字符哈夫曼编码。而不是逐个字符压缩文本，您可以找到常见的音节或单词，并将它们放入树中；然后它们在压缩字符串中需要的位数更少。但是，这需要稍微复杂一些的压缩算法，但付出的努力可能非常值得。

为了在C++中处理比特串的压缩和解压缩例程，我建议使用boost::dynamic_bitset或std::vector<bool>。两者都在内部将多个位打包成字节。

---

^(*)_{这个问题曾经带有c++标签，所以提问者显然想在C++中实现它。但由于一般问题不特定于编程语言，因此标签被移除了。但我仍然保留了答案中与C++相关的部分。}

- leemes