压缩很多小字符串的算法？

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 和内存使用情况。

Answer 1

您可以使用 Huffman coding在您要压缩的所有文本之间使用共享的霍夫曼树。

虽然您通常为要单独压缩的每个字符串构造一个霍夫曼树，但这需要大量存储开销，此处应避免。这也是针对您的情况使用标准压缩方案时的主要问题:它们中的大多数都有一些开销，这会降低您对非常短的字符串的压缩效率。其中一些没有(大)开销，但通常效率较低。

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

然后构造哈夫曼树并在你的应用程序中存储一次；要么将其硬编码到二进制文件中，要么以文件的形式提供。然后您可以使用此树压缩和解压缩任何文本。每当您决定更改树时，因为您在压缩文本方面获得了更好的体验，压缩的字符串表示形式也会发生变化。引入版本控制并将树版本与您压缩的每个字符串一起存储可能是个好主意。

您可能会想到的另一个改进是使用多字符霍夫曼编码。您可以找到频繁的音节或单词并将它们也放入树中，而不是逐个字符地压缩文本；然后他们在压缩字符串中需要更少的位。然而，这需要稍微复杂一点的压缩算法，但这可能是值得的。

要在 C++ 中^(*) 中处理压缩和解压缩例程中的位串，我推荐 boost::dynamic_bitset 或 std::vector<bool> .两者都在内部将多个位打包成字节。

---

^(*)_{问题曾经有c++标签，所以 OP 显然想用 C++ 实现它。但由于一般问题并非特定于编程语言，因此删除了该标签。但我仍然保留了答案中特定于 C++ 的部分。}