algorithm - 如果霍夫曼树的成本是 2^len，那么最好的编码是什么？

Question

我最近遇到了一个编码问题，它与Huffman Tree Encoding非常相似：项目出现的越多，我们得到的代码就越短。

但不同的是：在霍夫曼编码中，一种项目的所有成本都是length_of_code_for_item *frequentness，但在我的要求中，成本是2^length_of_code_for_item *frequentness。

任何现有的编码算法？

标签： algorithmhuffman-code

Answer 1

由于武汉爆发冠状病毒，中国延长了春节假期。所以我在业余时间回顾了这个需求。

我找到了一些关于这个问题的论文并写了一个注释（中文但你可以使用谷歌翻译）和python中的示例代码。

论文是：Parker, Jr D S. Huffman 算法的最优性条件[J]。SIAM 计算杂志，1980，9(3)：470-489。

简而言之，论文讨论了如果父母的权重不是孩子的总和(F(x,y)=x+y)。得出的结论是，如果 Function 是拟线性的（有一些要求），原来的 Huffman 算法仍然会产生具有最低根权重的二叉树。

就我而言，我们需要定义F(x,y)=2(x+y)，一切顺利。