我对两个符号的字母表的最小描述长度的解释感到困惑。
更具体地说，假设我们要编码一个二进制字符串，其中 1 的出现概率为 0.80；例如，这是一个长度为 40 的字符串，有 32 个 1 和 8 个 0：
1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 0 0 1
按照标准的 MDL 分析，我们可以使用前缀代码（如 Huffman 的）来编码这个字符串，编码这个字符串的代码将是 (-log(0.8) * 32 - log(0.2) * 8)，它低于复制字符串没有任何编码。
直观地说，编码这个字符串比 1 和 0 以相等概率出现的某个字符串“便宜”。但是，在实践中，我不明白为什么会这样。至少，我们需要一位来区分 1 和 0。我看不出前缀代码如何比只编写不编码的二进制字符串做得更好。
有人可以帮我澄清一下吗？
我看不出前缀代码如何比只编写不编码的二进制字符串做得更好。
您不能使用前缀代码，除非您组合位以制作更多符号。例如，如果您每两位编码，您现在有四个符号，概率分别为 0.64、0.16、0.16 和 0.04。这将被编码为 0、10、110、111。这给出了平均每个符号 1.56 位，或每个原始位 0.7800 位。我们离最优的每比特 0.7219 位（-0.2 log 2 0.2 - 0.8 log 2 0.8）有点接近。
对三位分组执行此操作，您将获得每位 0.7280 位。出乎意料地接近最佳值。在这种情况下，代码长度恰好与概率很好地组合在一起。对于概率为 0.512 的符号，编码为 1 位 (0)，对于概率为 0.128 的三个符号，编码为 3 位 (100, 101, 110)，对于概率为 0.128 的三个符号，编码为 5 位 (11100, 11101, 11110, 11111)概率 0.032 和概率 0.008 的一个符号。
您可以继续前进并逐渐接近最佳的 0.7219 位/位。尽管对于较大的分组，它在时间和空间上变得更加低效。帕累托前沿在 15 之前是 3 位的倍数。6 位为每位 0.7252 位，9 位为 0.7251，12 为 0.7250，15 为 0.7249。这种方法非常缓慢，您需要达到 28 位才能达到 0.7221。所以你不妨停在 6 点。甚至只有 3 点也不错。
或者，您可以使用前缀编码以外的其他方法，例如算术编码、范围编码或非对称数字系统编码。它们有效地为每个符号使用小数位。