6

好的，所以，假设我有一个文本文件（不一定包含每个可能的符号），我想计算每个符号的频率，在计算频率之后，我需要从最频繁访问每个符号及其频率最不频繁。这些符号不一定是 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)

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

4

2 回答 2

3

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

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

于 2011-10-04T19:09:27.523 回答
2

如果您正在寻找基于运行时间的“最佳”解决方案，我建议您这样做：

当您阅读文件时，您应该根据符号本身的值而不是它们的频率对符号进行排序（或散列）。这将让您在已看到的符号列表中快速找到当前符号，而不必搜索整个列表。您还应该使初始结构能够执行快速插入 - 我建议使用哈希的二叉树。

阅读完所有符号后，您应该将排序切换为基于频率计数。我会将所有内容读入一个数组，然后执行就地排序，但是有很多等效的方法可以做到这一点。

希望这可以帮助！

于 2011-10-04T19:13:42.730 回答