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

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 而不是 Heap。像这样，您将为找到的每个符号执行 O(1) 的操作，而不是 O(log n)，其中 n 是当前堆上的项目数。

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