algorithm - 霍夫曼编码基于贪婪方法或动态编程

Question

我们可以使用动态规划解决霍夫曼编码问题吗，有什么算法吗？

Answer 1

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

Answer 2

根据我对算法的了解，我相信霍夫曼编码是基于贪婪方法的。正如我们在活动选择问题中所做的那样。任务调度和背包问题是它的另一个例子。

Answer 3

[更新]：我认为我下面提到的解决方案会生成最佳前缀码，但不一定与霍夫曼码相同。根据定义，霍夫曼代码是通过贪婪方法生成的。虽然它是最佳的，但它不是唯一的解决方案。（例如，一旦生成了 Huffman 树，您可以交换同一级别中的叶子以赋予它们不同的代码，同时仍然是最优的）

---

我认为这可以使用动态编程来解决，尽管它不会那么有效。这里的方法与查找最优二叉搜索树非常相似，因为当您向下一层时，您会在叶子中添加更多位。

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