假设A是一个数组,其中A [0]保持字母表的第0个字母的频率.
计算代码长度的最有效(*)方法是什么？不确定,但我想效率可以是内存使用或所需的步骤.
所有我感兴趣的是数组L,其中L[0]的字母,其中代码来自内置了频率阵列的规范哈夫曼树的0个字母包含代码长度(比特数).
小智 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