3

使用したいアルゴリズムはわかっていますが、ファイルが非常に大きいため、何を変更する必要があるかを知りたいです。

ハッシュを使用して単語の頻度を格納し、最小ヒープを使用して最も頻度の高い単語を格納し、それに応じて最小ヒープを調整して単語をループします。これにはO（nlogk）が必要だと思います。データが多すぎてメモリに保存できない場合、アルゴリズムをどのように変更する必要がありますか。これは、この特定の質問だけでなく、説明に役立つようにコンテキストを提供しているだけで、一般的に理解するのが難しい問題です。

4

3 に答える 3

4

ファイル全体をメモリに保存せずに（または高価な種類のマージソートを作成せずに）それを行う決定論的な方法はないと思います。

しかし、いくつかの優れた確率的アルゴリズムがあります。Count-Minスケッチを見てください。

このライブラリには、このアルゴリズムや他のアルゴリズムの優れた実装があります。

マージソートの説明：ファイルがすでにソートされている場合は、最小ヒープを使用してkを最も頻繁に見つけることができます。はい、競争力のある用語を見つけたときに、頻度の低い用語を破棄できるようにするための最小ヒープ。ファイル全体を読まなくても現在の単語の頻度を知ることができるので、これを行うことができます。ファイルがソートされていない場合は、リスト全体を保持する必要があります。これは、最も頻繁な用語がファイルのいたるところに表示され、「非競合」としてすぐに破棄される可能性があるためです。

限られたメモリでマージソートを行うのは非常に簡単ですが、これはI / Oを多用する操作であり、時間がかかる場合があります。実際には、あらゆる種類の外部ソートを使用できます。

于 2013-02-26T21:02:40.440 に答える
4

頻度を計算する必要があるというコメントの後に追加されました。

データに期待する単語の数や、単語を構成するものは何も言いません。英語の文章だとしたら、50万語を見てびっくりします。そして、5ギガバイトのテキストに10億語が含まれることは確かにありません。しかし、単語の数に関係なく、テクニックは実際には変わりません。

まず、キーと値のペア（単語、カウント）を含む辞書またはハッシュマップを作成します。各単語を読みながら、辞書で調べてください。そこにある場合は、その数を増やします。そこにない場合は、1のカウントで追加します。

メモリが多いか、単語が比較的少ない場合は、すべてメモリに収まります。もしそうなら、あなたは私が以下に説明するヒープのことをすることができます。

メモリがいっぱいになった場合は、次のように、キーと値のペアを1行に1ワードずつテキストファイルに書き込むだけです。

word1, count
word2, count

次に、辞書をクリアして、単語を追加したり、単語数を増やしたりして、続けます。入力の最後に到達するまで、単語のブロックごとに必要に応じて繰り返します。

これで、単語とカウントのペアを含む巨大なテキストファイルができました。単語で並べ替えます。それを行う外部ソーティングツールはたくさんあります。頭に浮かぶのは、WindowsSORTユーティリティとGNUソートの2つです。どちらも、短い行の非常に大きなファイルを簡単に並べ替えることができます。

ファイルを単語で並べ替えると、次のようになります。

word1, count
word1, count
word2, count
word3, count
word3, count
word3, count

これで、ファイルを順番に調べて、単語の数を累積するだけです。単語の区切りごとに、以下に説明するように、ヒープに対するカウントを確認します。

このプロセス全体には時間がかかりますが、非常にうまく機能します。単語のブロックを並べ替えて個々のファイルに書き込むことで、速度を上げることができます。次に、入力の最後に到達したら、いくつかのブロックでN-wayマージを実行します。これは高速ですが、マージプログラムが見つからない限り、マージプログラムを作成する必要があります。私がこれを一度やっていたとしたら、私は簡単な解決策を選びます。頻繁に行う場合は、カスタムマージプログラムを作成するために時間を費やしていました。

頻度を計算した後...

ファイルに単語とその頻度が含まれていると仮定するkと、最も頻度の高い単語を取得するだけで、O（n log k）になり、すべてのアイテムをメモリに保存する必要はありません。ヒープに必要なのはk個のアイテムのみです。

アイデア：

heap = new minheap();
for each item
    // if you don't already have k items on the heap, add this one
    if (heap.count < k)
        heap.Add(item)
    else if (item.frequency > heap.Peek().frequency)
    {
        // The new item's frequency is greater than the lowest frequency
        // already on the heap. Remove the item from the heap
        // and add the new item.
        heap.RemoveRoot();
        heap.Add(item);
    }

すべてのアイテムを処理した後、ヒープにはk最も頻度の高いアイテムが含まれます。

于 2013-02-26T21:36:56.033 に答える
0

選択アルゴリズム（http://en.wikipedia.org/wiki/Selection_algorithm）を使用して、k番目に大きい数を計算できます。次に、線形スキャンを実行し、k個の大きな数値のみを選択します。

実際には、kth minがfalseになる推定範囲から始めて、そこから続行することをお勧めします。例えば。最初のM個の数値を読み取り、推定kth max =（k * M / N）thmaxをM個で計算します。データに偏りがある（つまり、部分的に並べ替えられている）と思われる場合は、それらのM個の数値をランダムに選択します。

于 2013-02-26T21:37:39.873 に答える