string - 使用 Ascii 进行压缩，试图找出有效存储以下内容的位数

Question

我正在尝试仅使用 ASCII 来学习压缩的基础知识。

如果我要发送一封包含小写字母字符串的电子邮件。如果文件中的n 每个字符都存储为 8 位扩展 ASCII 码，那么我们需要 8n 位。但是根据压缩的指导原则：我们丢弃不重要的信息。所以使用它我们不需要所有的 ASCII 代码来编码小写字母的字符串：它们只使用 26 个字符。我们可以只用 5 位代码字 (25 = 32 > 26) 编写自己的代码，使用这种编码方案对文件进行编码，然后在收到电子邮件后解码。

The size has decreased by 8n - 5n = 3n, i.e. a 37.5% reduction.

但是，如果电子邮件由小写字母 (26)、大写字母和额外m字符组成，并且必须有效地存储，该怎么办？

Answer 1

如果您有 n 个概率相等的符号，则可以使用 log2(n) 位对每个符号进行编码。即使 log2(n) 是小数，使用算术或范围编码也是如此。如果将其限制为 Huffman（每个符号的固定位数）编码，您可以接近 log2(n)，平均每个符号的位数仍然是小数。

例如，您可以使用算术编码以非常接近每个符号 3.322 位的方式对十个符号（例如十进制数字）进行编码。使用霍夫曼编码，您可以用 3 位编码 6 个符号，用 4 位编码 4 个符号，平均每个符号 3.4 位。

使用 shift-up 和 shift-down 操作可能是有益的，因为在英文文本中，您希望有小写字符的字符串，偶尔会有大写字符。现在你正在进入高阶模型和不等频率分布。