计算每个字符的频率然后输入霍夫曼编码的过程是什么？

Question

我正在研究一种方法来降低霍夫曼编码之前过程的时间和空间复杂度，其中计算机必须将每个字符的频率提供给代码。我想知道找到频率的过程是这样的通过 2 个复杂度为 O(n2) 的嵌套循环，还是使用更有效的方式完成，例如复杂度为 O(n) 的哈希映射。或者是机器计算字符频率的其他方式。

哈夫曼编码的整个过程需要O(nlogn)。我想问一下，字符计数是否也包含在这个过程中，导致总时间为O(n) + O(nlogn)，还是其他什么？机器内部做什么？

有什么方法可以消除频率计数吗？

我尝试浏览各种论文，但找不到霍夫曼获取字符频率作为输入的过程。

Answer 1

有多少个可能的字符？ 256？无论数字是多少，都制作一个包含那么多条目的整数表。使整数足够大以包含最长可能输入的长度。将它们全部设置为零。然后遍历输入数据，增加遇到的每个字符的计数。

标签中未指定语言，但类似：

    table[ch]++;

对于输入中的每个字符

ch

。