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

Heap の代わりに HashMap をいつでも使用できます。このように、O(log n) ではなく、見つかったシンボルごとに O(1) にある操作を実行します。ここで、n は現在ヒープにあるアイテムの数です。

ただし、個別のシンボルの数が妥当な数に制限されている場合 (1 バイトが理想的ですが、2 バイトでも問題ないはずです)、そのサイズの配列を使用して、再び O(1) を使用できますが、定数は大幅に低くなります。料金。

于 2011-10-04T19:09:27.523 に答える
2

実行時間に基づいた「最良の」ソリューションを探している場合は、次のことをお勧めします。

ファイルを読み取るときは、頻度ではなく、シンボル自体の値でシンボルをソート（またはハッシュ）する必要があります。これにより、リスト全体を検索するのではなく、すでに表示されているシンボルのリストから現在のシンボルをすばやく見つけることができます。また、初期構造で高速挿入を実行できるようにする必要があります。ハッシュのバイナリツリーをお勧めします。

すべての記号を読んだら、頻度カウントに基づくように順序を切り替える必要があります。すべてを配列に読み込んでからインプレースソートを実行しますが、これを行うための同等の方法がたくさんあります。

お役に立てれば！

于 2011-10-04T19:13:42.730 に答える