5

巨大なテキストファイル（使用可能なRAMメモリよりも大きい）があります。すべての単語の頻度をカウントし、単語と頻度カウントを新しいファイルに出力する必要があります。結果は、頻度カウントの降順で並べ替える必要があります。

私のアプローチ：

  1. 指定されたファイルを並べ替える-外部並べ替え
  2. 各単語の頻度を順番にカウントし、カウントを別のファイルに（単語と一緒に）保存します
  3. 頻度カウントに基づいて出力ファイルをソートします-外部ソート。

それを行うためのより良いアプローチがあるかどうか知りたいです。ディスクベースのハッシュテーブルについて聞いたことがありますか？またはB+木ですが、これまで試したことはありません。

注：SOで同様の質問が行われるのを見たことがありますが、メモリよりも大きいデータの問題に対処する必要はありません。

編集：コメントに基づいて、実際の辞書は今日のコンピューターの記憶に収まるはずであることに同意しました。しかし、記憶に収まらないほど巨大な単語の架空の辞書を見てみましょう。

4

4 に答える 4

14

私はmap reduceアプローチで行きます：

  1. ノード内の各テキストがRAMに収まると仮定して、テキストファイルをノードに配布します。
  2. ノード内の各単語の頻度を計算します。（を使用してhash tables）
  3. 各結果をマスターノードに収集し、それらをすべて結合します。
于 2013-02-07T08:15:39.070 に答える
4

すべてのユニークな単語はおそらくメモリに収まるので、私はこのアプローチを使用します：

  • 辞書を作成します（HashMap<string, int>）。
  • 巨大なテキストファイルを1行ずつ読んでください。
  • 辞書に新しい単語を追加し、値を1に設定します。
  • 既存の単語の値に1を追加します。

巨大なファイル全体を解析した後：

  • 辞書を頻度で並べ替えます。
  • ソートされた辞書を単語と頻度で新しいファイルに書き込みます。

ただし、単語を小文字または大文字に変換することに注意してください。

于 2013-02-07T08:16:32.610 に答える
3

これを実現する最善の方法は、ファイルを1行ずつ読み取り、単語をマルチマップ（Guavaなど）に保存することです。このマップがメモリを拡張する場合は、Key-Valueストア（Berkeley JE DB、MapDBなど）を使用してみてください。これらのKey-Valueストアはマップと同様に機能しますが、HDDに値を保存します。私は同様の問題にMapDBを使用しましたが、それは非常に高速でした。

于 2013-02-07T08:24:01.240 に答える
1

一意の単語のリストと頻度がメモリに収まる場合（ファイルだけでなく、一意の単語）、ハッシュテーブルを使用して、ファイルを（保存せずに）順番に読み取ることができます。

次に、ハッシュテーブルのエントリを出現回数で並べ替えることができます。

于 2013-02-07T08:15:00.247 に答える