algorithm - 1TB を超えるデータから頻度 k ワードを出力するにはどうすればよいですか?

Question

この質問は私のインタビューで聞かれました。解決策を知りたかった。

各行に 1 つの単語を含み、ファイルのサイズが 1TB を超えるテキスト ファイルを指定します。タスクは、頻度がkである単語のみをファイルに出力することです。

私は質問に完全には答えませんでした。しかし、私は正しい方法でそれを始めたと思います。ハッシュ技術を使用しており、コードには少なくとも O(n) 時間がかかります (ファイルを読み取る必要があるため)

これを効率的に行うことができる人は誰ですか？

Answer 1

一般に、このクラスの問題は、「トップ K」または「選択」アルゴリズムのトピックです。一般的なトピックに関するウィキペディアの記事は次のとおりです:ウィキペディア: 選択アルゴリズム。それは一般的に「ビッグデータ」システムで流行しているようであり、おそらく、すべての真面目な候補者がクイックソートとヒープソートのコードを覚えていた時代をはるかに超えて、ソートアルゴリズムに焦点を当てた前世代のインタビューを乗り越えるためです.

実際問題として、これは「ビッグデータ」(Hadoop およびその他の Map/Reduce システム) が構築された教科書の問題にすぎません。データが N 個のノードに分散されている場合、それぞれが個別の部分ヒストグラムを計算し (ヒストグラム関数をデータ セット全体にマッピング)、結果をマージします (小計を総計に減らします)。

インタビューのシナリオでは、簡単なトリックがないため、これはよくある質問です。学術文献で公開されているいくつかのアプローチを列挙するか、 de novoで問題に取り組むことができます。

「語彙」が比較的小さい場合 (たとえば、典型的な英語の辞書には数万語しかないため、25 万語の語彙はかなり広範です)。その場合、典型的な最新のハードウェアの RAM にカウントが収まると予想されます。このデータセットの「単語」がより広範である場合 (数千万または数億を超える場合)、そのようなアプローチはもはや実行できません。

おそらく、適応的または統計的アプローチを試すことができます。単一の「単語」の主要なクラスターがないことがわかっている場合...データセットの統計的に有意なサンプルは他のサンプルとほぼ同じであることがわかっている場合...ヒストグラムを作成してそれらの「単語」を破棄するよりも (およびその数) は、他のものよりもかなりまれです。データがストリームとしてのみ表示され、項の分布について厳密な保証が与えられていない場合、これは実現可能なアプローチではありません。しかし、ランダムアクセスファイルシステムにデータがある場合、データセットをまばらかつランダムにサンプリングして、最も可能性の高い上位 K * M のセットを構築することができます(ここで、M は、目的の K 要素の任意の倍数であり、すべてがRAMに収まります）。

ハッシュは、各単語のカウンターを見つけるのに役立つかもしれませんが、「単語」自体をデータ構造に保持せずにハッシュのみのカウントを保持しようとすると、衝突の可能性を考慮する必要があります。一般的に、ヒープの方が良いと思います（メモリ内ヒープの下部からストレージヒープまたはトライにドロップすることを含む可能性があります）。

キャッシング (最終的には統計モデリング) を使用して、現在最も頻度の高い「単語」を RAM に保持し、最も頻度の低い単語をストレージにシャッフルすることができるため、先ほど「適応的」と言いました (最初に頻度の高い「単語」が含まれる縮退したデータ セットから保護するため)。データセットを深く掘り下げるにつれて、最初はまれな単語に取って代わられます）。

いくつかのインタビューでは、これらの考慮事項の会話調査がうまくいくかもしれませんが、私が引用したウィキペディアの記事のさまざまなセクションに精通していることをお勧めします。そうすれば、それらの少なくとも 1 つまたは 2 つの疑似コードをスケッチできます。そして、あなたがこの資料について何らかの学歴を持っていることを示してください。

「トップ K」クラスの質問が投げかけられているインタビューでは、分散処理についての議論を絶対におろそかにしないでください。提起されている問題の制約を明確にし、そのような問題が現代の「ビッグデータ」分散処理システムの原動力となっていることを認めるためにのみ、そうしてください。

また、同じ一般的なトピックに関する質問もあります: StackOverflow: The Most Efficient Way To Find Top K Frequent Words In A Big Word Sequence .

Answer 2

この質問への回答は、一意の単語のサイズに完全に依存します。一意の単語数が少ない場合は、任意の文字列->数値マッピング データ構造 (トライ ツリーなど) を使用して、単語の頻度をカウントできます。複雑さはn log(m)(m は個々の単語の長さ)、実装が容易になります。しかし、問題が説明されているように、おそらく一意の単語数はメモリに保存できるほど大きいです。その場合、次のアプローチを使用できます。

1 TB のデータ1.0*10^12は、入力ファイルに約バイトのデータがあることを意味します。1 バイトは 1 文字であり、平均して 1 つの単語が 4 文字であるとすると、約2.5*10^11単語になります。この単語リストを50k別の単語リストに分割します。5mしたがって、入力ファイルから未読の単語を読み取るたびに、この5m単語リストをソートし、このソートされたリストをファイルに書き込みます。50k番号の配列 ( と呼びましょう)を使用Parrayして、すべてのソート済みリストの開始位置をファイルに格納します (最初Parrayは、0、5m+1、10m+1 などの番号があります)。すべてのリストから上位の単語を読み取り、50kそれらを最小ヒープに入れると、ヒープの一番上にある最小の単語が取得されます。現在の最小の単語を取得した後（それを呼び出しましょうcur_small）すべてのソートされたリストから、各リストからその単語を読み上げます（この操作の後、Parray各リストで次に小さい単語を指します）。ここで の数を取得しますcur_small- に基づいて決定し、ヒープから のKすべてのエントリを削除しcur_small、最後に各リストから少なくとも 1 つの単語があったヒープに新しい単語を追加しますcur_small。ソートされたすべてのリストを読み上げるまで、このプロセスを続けます。全体の複雑さはn log(n)