有没有更好的方法来计算文件中所有符号的频率？

Question

好的,所以,我说有一个文本文件(不一定包含所有可能的符号),我想计算每个符号的频率,并且在计算频率之后,我需要从最常见的频率访问每个符号及其频率至少频繁.符号不一定是ASCII字符,它们可以是任意字节序列,尽管长度相同.

我正在考虑做这样的事情(伪代码):

function add_to_heap (symbol)
    freq = heap.find(symbol).frequency
    if (freq.exists? == true)
        freq++
    else
        symbol.freq = 1
        heap.insert(symbol)

MaxBinaryHeap heap
while somefile != EOF
    symbol = read_byte(somefile)
    heap.add_to_heap(symbol)
heap.sort_by_frequency()

while heap.root != empty
    root = heap.extract_root()
    do_stuff(root)

我想知道:有没有更好,更简单的方法来计算和存储文件中每个符号出现的次数？

Answer 1

您始终可以使用 HashMap 而不是堆。像这样，您将为找到的每个符号执行 O(1) 的操作，而不是 O(log n)，其中 n 是堆上当前项目的数量。

但是，如果不同符号的数量受到合理数量的限制（1 字节是理想的，2 字节应该仍然可以），您可以只使用该大小的数组，并且再次具有 O(1) 但具有明显较低的常数成本。