对哈夫曼树的应用感到困惑

Question

哈夫曼树算法的实际应用是什么？贪婪的方法是怎样的？ 我需要关于哈夫曼树在计算机科学问题解决中的使用的简要说明，我想知道在日常编程中我可以在哪里使用这个算法。

Answer 1

霍夫曼树根据令牌的分布将前缀为 属性 的可变长度位模式分配给一组令牌中的每一个，从而产生非常紧凑的输出编码。净效应：令牌流的字节版本具有高熵。这意味着它的编码非常高效。

假设您有一千个标记可能出现在流中。但是其中一个出现的概率为 40%，其余的则大致平均分布。使用霍夫曼树，您最终会以比其他树更少的位数存储该树。就好像你为它发明了一个 shorthand 只是树在概率范围内这样做。令牌越有可能，位数越少。

因此，它通常用于压缩。像 GZip 这样的东西做了一个步骤来尝试用较少数量的标记来描述原始数据，然后使用 Huffman 来尝试使它产生的标记流尽可能小。

它是贪婪的，因为树是通过从输入集中重复选择最可能的剩余标记来构建的。