我正在改进我的编程技能并实施 Huffman 算法。现在，我只考虑没有特殊字符的 [az]。az 的概率值已从维基百科中使用。
当我运行它时，我对随机段落进行了大约 2 倍的压缩。但是对于这个计算，我假设原始字母每个需要 8 位（ASCII）。
但如果我想一想，要表示 26 个项目，我只需要 5 位。如果我根据这个事实来计算，那么压缩系数下降到几乎 1.1
所以我的问题是，在实际应用中如何确定压缩系数？
第二个问题 - 如果我编写一个使用 5 位表示 az 的编码器/解码器（比如 a=0、b=1 等） - 这是否也被认为是一种有效的“压缩”算法？
您基本上得到了正确的答案，即如果您正在使用的只是英语的字母频率，那么您就不能期望进行大量压缩。
计算字母频率知识所产生的增益的正确方法是考虑与英文字母熵相等概率的 26 个符号字母表的熵。
（我希望stackoverflow允许像math.stackexchange.com这样的TeX方程。然后我可以在这里写出体面的方程。哦，好吧。）
关键公式是 -p log(p)，其中 p 是该符号的概率，日志以 2 为底，以位为单位得到答案。您为每个符号计算此值，然后对所有符号求和。
然后在一个理想的算术编码方案中，一个等概率的 26 个符号集将被编码为每个符号 4.70 位。对于英语分布（使用Wikipedia 文章中的概率），我们得到每个符号 4.18 位。仅减少约11%。
这就是频率偏差本身可以买到的所有东西。（它在拼字游戏分数中为你买了更多，但我离题了。）
我们也可以在霍夫曼编码的近似空间中看同样的东西，其中每个编码都是整数位数。在这种情况下，您不会假设每个字母有 5 位（浪费了 6 个代码）。对等概率的 26 个符号应用霍夫曼编码得到 6 个长度为 4 位的代码和 20 个长度为 5 位的代码。这导致平均每个字母 4.77 位。使用英语中出现的字母频率的霍夫曼编码平均每个字母有 4.21 位。减少了 12%，和熵计算差不多。
真正的压缩机有很多方法比这做得更好。首先，他们对文件中的实际内容进行编码，使用那里的频率而不是它们在英语中的频率。这使得它独立于语言，针对实际内容进行了优化，甚至不对不存在的符号进行编码。其次，您可以将输入分解为多个部分，并为每个部分创建一个新代码。如果片段足够大，则传输新代码的开销很小，并且增益通常更大，可以在更小的块上进行优化。第三，您可以寻找更高阶的效果。代替单个字母的频率，您可以考虑前一个字母并查看下一个字母给定其前身的概率。现在您有 26^2 个概率（仅用于字母）要跟踪。这些也可以为手头的实际数据动态生成，但现在您需要更多数据才能获得收益、更多内存和更多时间。您可以以内存和时间为代价进行三阶、四阶等以获得更高的压缩性能。
还有其他方案来预处理数据，例如，进行行程编码、查找匹配字符串、应用块转换、标记 XML、对音频或图像进行增量编码等，以进一步暴露冗余然后利用熵编码器。我提到了算术编码，它可以用来代替 Huffman 在不到一位的时间内对非常可能的符号进行编码，并将所有符号编码为小数位精度，以便在熵步骤中获得更好的性能。
回到你关于什么构成压缩的问题，你可以从你喜欢的任何起点开始，例如每个字母一个八位字节，对你的输入进行断言，例如所有小写字母（接受如果断言为假，则方案失败），然后评估压缩效果。只要您在比较两种不同的压缩方案时使用所有相同的假设。您必须小心，任何与数据相关的内容也必须被视为压缩数据的一部分。例如，从数据块派生的自定义霍夫曼代码必须与该数据块一起发送。
26 个字符不是 5 位，它是 log(26) / log(2) = 4,7 位。这是最大熵，但您需要知道具体的熵。对于德语，它是 4,0629。当您知道可以使用公式 R=Hmax - H 时。请看这里：http ://de.wikipedia.org/wiki/Entropie_(Informationstheorie ) http://en.wikipedia.org/wiki/Information_theory#Entropy
如果您对同一文本运行不受限制的霍夫曼编码压缩，您将获得相同的结果，所以我认为可以合理地说您在同一文本的 ASCII 编码上获得 2 倍压缩。我更倾向于说您的程序正在获得预期的压缩，但目前有一个限制，即它无法处理任意输入，并且如果该限制存在，其他更简单的压缩方案也可以通过 ASCII 获得压缩。
为什么不扩展你的算法来处理任意字节值呢？这样更容易进行真正的单挑比较。