霍夫曼树 - 给出完美树的最高可能频率
Huffman tree - highest possible frequency that gives perfect tree
假设您有一个包含 4 个字符的字母表：A、B、C、D。假设哈夫曼树是完美的，最频繁出现的字符的最高可能出现频率是多少。
我们有理论认为它是总长度的2/5，但我们希望看到更具体的证明或解释。
不失一般性，我们假设 p(A) <= p(B) <= p(C) <= p(D)。哈夫曼算法会将 A 和 B 组合成一个分支。 （同样，如果某些概率相等，则不失一般性。）为了使生成的树是平坦的，我们必须将 C 和 D 组合成一个分支。然后最后一步是合并这两个分支。
为了确保我们将C和D组合成一个分支，p(C)和p(D)都必须小于p(A) + p(B)。所以 p(D) < p(A) + p(B)。请注意，如果 p(C) = p(D) = p(A) + p(B)，则霍夫曼算法可以选择在下一步中选择任何对，其中两种情况会导致树偏斜。所以 p(D) 必须严格小于 p(A) + p(B).
剩下的留作 reader 的练习。
（您的猜测很接近。它必须比 2/5 少。所以 2/5–ε，其中 ε 是允许从频率，大概是一个整数，小于 2/5。达到最大值的一组概率示例是 {1/5, 1/5, 1/5+ε, 2/5–ε}。）
假设您有一个包含 4 个字符的字母表：A、B、C、D。假设哈夫曼树是完美的，最频繁出现的字符的最高可能出现频率是多少。
我们有理论认为它是总长度的2/5，但我们希望看到更具体的证明或解释。
不失一般性，我们假设 p(A) <= p(B) <= p(C) <= p(D)。哈夫曼算法会将 A 和 B 组合成一个分支。 （同样，如果某些概率相等，则不失一般性。）为了使生成的树是平坦的，我们必须将 C 和 D 组合成一个分支。然后最后一步是合并这两个分支。
为了确保我们将C和D组合成一个分支，p(C)和p(D)都必须小于p(A) + p(B)。所以 p(D) < p(A) + p(B)。请注意，如果 p(C) = p(D) = p(A) + p(B)，则霍夫曼算法可以选择在下一步中选择任何对，其中两种情况会导致树偏斜。所以 p(D) 必须严格小于 p(A) + p(B).
剩下的留作 reader 的练习。
（您的猜测很接近。它必须比 2/5 少。所以 2/5–ε，其中 ε 是允许从频率，大概是一个整数，小于 2/5。达到最大值的一组概率示例是 {1/5, 1/5, 1/5+ε, 2/5–ε}。）