构建规范哈夫曼树最有效（*）的方法是什么？
假设 A 是一个数组，其中 A[0] 保存字母表中第 0 个字母的频率。
计算代码长度最有效（*）的方法是什么？不确定，但我想效率可以体现在内存使用或所需步骤方面。
我感兴趣的是数组 L ，其中 L[0] 包含字母表中第 0 个字母的代码长度（位数），其中代码来自规范由频率数组构建的霍夫曼树。
Assume A is an array where A[0] holds the frequency of 0-th letter of the alphabet.
What is the most efficient(*) way of calculating code lengths? Not sure, but I guess efficiency can be in terms of memory usage or steps required.
All I'm interested is the array L where L[0] contains code lengths (number of bits) of 0-th letter of the alphabet, where code comes from canonical huffman tree built out of A frequency array.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果频率形成单调序列，即。 A[0]<=A[1]<=...<=A[n-1] 或 A[0]>=A[1]>=...>=A[n -1]，那么您可以在 O(n) 时间和 O(1) 额外空间内生成最佳代码长度。该算法只需要对数组进行两次简单的传递，而且速度非常快。 [1] 中给出了完整的描述。
如果您的频率未排序，首先您需要对其进行排序，然后应用上述算法。在这种情况下，时间复杂度为 O(n log n)，需要一个包含 n 个整数的辅助数组来存储排序顺序 - 空间复杂度为 O(n)。
[1]：
Alistair Moffat 和 Jyrki Katajainen 的《就地计算最小冗余代码》，可在线获取：http ://www.diku.dk/~jyrki/Paper/WADS95.pdf
If frequencies form a monotonic sequence, ie. A[0]<=A[1]<=...<=A[n-1] or A[0]>=A[1]>=...>=A[n-1], then you can generate an optimal code lengths in O(n) time and O(1) additional space. This algorithm requires only 2 simple passes over the array and it's very fast. A full description is given in [1].
If your frequencies aren't sorted, first you need to sort them and then apply the above algorithm. In this case time complexity is O(n log n) and an auxiliary array of n integers is needed to store sorted order - space complexity O(n).
[1]:
In-Place Calculation of Minimum-Redundancy Codes by Alistair Moffat and Jyrki Katajainen, available online: http://www.diku.dk/~jyrki/Paper/WADS95.pdf