假设 A 是一个数组，其中 A[0] 保存字母表中第 0 个字母的频率。
计算代码长度的最有效（*）方法是什么？不确定，但我猜效率可能取决于内存使用或所需的步骤。
我感兴趣的是数组L，其中L[0]包含字母表中第 0 个字母的代码长度（位数），其中代码来自由 A 频率数组构建的规范哈夫曼树。
问问题
1565 次
1 回答
5
如果频率形成单调序列，即。A[0]<=A[1]<=...<=A[n-1] 或 A[0]>=A[1]>=...>=A[n-1]，那么你可以在 O(n) 时间和 O(1) 额外空间内生成最佳代码长度。该算法只需要对数组进行 2 次简单的传递，而且速度非常快。完整的描述在 [1] 中给出。
如果您的频率没有排序，首先您需要对它们进行排序，然后应用上述算法。在这种情况下，时间复杂度为 O(n log n)，并且需要一个由 n 个整数组成的辅助数组来存储排序顺序 - 空间复杂度 O(n)。
[1]：Alistair Moffat 和 Jyrki Katajainen 就地计算最小冗余码，可在线获取：http ://www.diku.dk/~jyrki/Paper/WADS95.pdf
于 2011-03-29T18:35:25.577 回答