两个符号的最小描述长度和霍夫曼编码？
Minimum description length and Huffman coding for two symbols?
我对两个符号的字母表的最小描述长度的解释感到困惑。
更具体地说，假设我们要对二进制字符串进行编码，其中 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 出现的概率相等的字符串相比，"cheaper" 对该字符串进行编码。但是，在实践中，我不明白为什么会这样。至少，我们需要一位来区分 1 和 0。我看不出前缀代码比只写二进制字符串而不编码更好。
有人可以帮我澄清一下吗？
I don't see how prefix codes could do better than just writing the
binary string without encoding.
您不能使用前缀代码，除非您组合位来生成更多符号。例如，如果您每两位编码一次，那么您现在有四个概率分别为 0.64、0.16、0.16 和 0.04 的符号。这将用 0、10、110、111 编码。这给出了每个符号平均 1.56 位，或每个原始位 0.7800 位。我们越来越接近最佳的 0.7219 位/位 (-0.2 log20.2 - 0.8 log20.8).
对三位分组执行此操作，您将得到每位 0.7280 位。出乎意料地接近最佳状态。在这种情况下，代码长度恰好与概率很好地组合在一起。对于概率为 0.512 的符号，代码为 1 位（0），对于概率为 0.128 的三个符号，代码为 3 位（100、101、110），对于具有概率 0.032 和概率 0.008 的一个符号。
您可以继续前进并逐渐接近最优的 0.7219 位/位。尽管它在时间上变得更加低效，并且 space 对于更大的分组。 Pareto Front 结果是三位的倍数直到 15。6 位给出 0.7252 位每位，9 位给出 0.7251，12 位是 0.7250，15 位是 0.7249。该方法非常慢，您需要使用 28 位才能达到 0.7221。所以你最好停在 6 点。或者甚至只是 3 点也不错。
或者，您可以使用前缀编码以外的编码，例如算术编码、范围编码或非对称数字系统编码。他们有效地为每个符号使用小数位。
我对两个符号的字母表的最小描述长度的解释感到困惑。
更具体地说，假设我们要对二进制字符串进行编码，其中 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 出现的概率相等的字符串相比，"cheaper" 对该字符串进行编码。但是，在实践中，我不明白为什么会这样。至少，我们需要一位来区分 1 和 0。我看不出前缀代码比只写二进制字符串而不编码更好。
有人可以帮我澄清一下吗？
I don't see how prefix codes could do better than just writing the binary string without encoding.
您不能使用前缀代码，除非您组合位来生成更多符号。例如，如果您每两位编码一次，那么您现在有四个概率分别为 0.64、0.16、0.16 和 0.04 的符号。这将用 0、10、110、111 编码。这给出了每个符号平均 1.56 位，或每个原始位 0.7800 位。我们越来越接近最佳的 0.7219 位/位 (-0.2 log20.2 - 0.8 log20.8).
对三位分组执行此操作，您将得到每位 0.7280 位。出乎意料地接近最佳状态。在这种情况下，代码长度恰好与概率很好地组合在一起。对于概率为 0.512 的符号，代码为 1 位（0），对于概率为 0.128 的三个符号，代码为 3 位（100、101、110），对于具有概率 0.032 和概率 0.008 的一个符号。
您可以继续前进并逐渐接近最优的 0.7219 位/位。尽管它在时间上变得更加低效，并且 space 对于更大的分组。 Pareto Front 结果是三位的倍数直到 15。6 位给出 0.7252 位每位，9 位给出 0.7251，12 位是 0.7250，15 位是 0.7249。该方法非常慢，您需要使用 28 位才能达到 0.7221。所以你最好停在 6 点。或者甚至只是 3 点也不错。
或者，您可以使用前缀编码以外的编码，例如算术编码、范围编码或非对称数字系统编码。他们有效地为每个符号使用小数位。