霍夫曼编码基于贪心算法还是动态规划？

Question

3

我们可以通过使用动态规划来解决哈夫曼编码问题，是否有相应的算法？

- user2375464

3个回答

2

据我所知，算法中的哈夫曼编码是基于贪心思想的。就像我们在活动选择问题中所做的一样。任务调度和背包问题也是其它例子。

- user2273202

1

如果我没记错的话，标准方法是使用优先队列（例如二叉堆）。低概率意味着高优先级。用字母表的初始叶节点填充队列。然后取出两个最高优先级（即最低概率）的节点。添加一个以它们为子节点、概率为它们之和的节点，然后将这个新的子树添加回优先队列中。重复此过程，直到队列中只剩下一个项目。 - user180247

1

我猜在每一步选择两个最少存在的子树来形成可能最小的新子树被认为是贪心的，因为在每一步它最大化了下一组子树的熵。 - user180247

1

[更新]: 我认为下面提到的解决方案生成了最优前缀编码，但不一定与哈夫曼编码相同。哈夫曼编码根据贪心算法生成，虽然它是最优的，但不是唯一的解决方案。例如，一旦生成了哈夫曼树，您可以在同一层中交换叶子以给它们不同的编码，同时仍然保持最优。

我认为这可以通过动态规划来解决，尽管效率可能不是很高。这里的方法与查找最优二叉搜索树非常相似，因为当你向下一层时，会向叶子节点添加一个比特位。

这里是计算总位数最小的代码链接。当然，这是指数级的，但如果使用DP，可以在O(n^2)时间内解决。我还没有尝试生成编码，但我相信应该是可能的。

- vikky.rk

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Deepu · Accepted Answer

哈夫曼编码通过创建一个节点的二叉树来实现。这些节点可以存储在常规数组中，其大小取决于符号的数量n。使用贪心算法方法，哈夫曼编码可以在O(n logn)时间内实现。由于该问题不包含重叠子问题，因此哈夫曼编码不适用于动态规划解决方案。