ファイル内のすべてのシンボルの頻度を計算する良い方法はありますか？

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

ヒープマップには常にハッシュマップが使用できます。このように、O（log n）の代わりに見つかったシンボルごとにO（1）にある演算を実行します.nは現在ヒープ上にある項目の数です。

しかし、異なる数のシンボルが妥当な数（1バイトが理想的ですが、2バイトは依然として問題ありません）でバインドされている場合は、そのサイズの配列を使用して再びO（1）大幅に低い一定コスト。あなたが時間を実行しているに基づいて「最良の」解決策を探しているなら

Answer 2

、ここで私がお勧めしたいものです：あなたは、ファイルを読んでいるとき

、あなたのシンボルが順にソート（またはハッシュ化）が必要ですシンボルそのものの値であり、その周波数の値ではありません。これにより、リスト全体を検索するのではなく、すでに表示されているシンボルのリスト内の現在のシンボルをすばやく見つけることができます。あなたはまた、最初の構造が高速挿入を実行できるようにする必要があります - 私はハッシュのバイナリツリーをお勧めします。

すべてのシンボルを読んだら、頻度カウントに基づいて発注を切り替える必要があります。私はすべてを配列に読み込んだり、インプレースソートを実行したりしますが、これを行うには相当な方法があります。

希望すると便利です。