string - 通过将字符串中每个字母的出现次数相加 k 次来改变霍夫曼树

Question

假设我有一个字符串，并且我通过将字符串中每个字母的出现次数增加 k 倍来增加字符串（假设我们有原始字符串 aabbbcc，并且 k=1，那么更改后的新字符串将是 aaabbbbccc） - 是这可能会导致该字符串的霍夫曼树发生变化？

我试图找到一个字符串的例子，通过改变上面写的字符串会发生这种变化，但到目前为止我失败了。

标签： stringhuffman-code

Answer 1

如果“增加”是指乘以k，那么不，符号的相对频率不会改变，因此产生的霍夫曼码也不会改变。如果“增加”是指添加k，那么如果原始字符串的符号频率不相等，则相对频率会发生变化，哈夫曼代码很可能会发生变化。（不确定，因为您可能已经接近具有相等的频率。）

更新：

从评论中，您的意思是添加k 次出现。所以是的，如果你还没有接近一个平坦的分布，霍夫曼代码可以改变。很容易看出，随着 k 变大，您会接近平坦分布，因为与 k 相比，原始频率变得微不足道。