22

~220,000,000 (~220 ミリオン) の単語/文字列を含むファイル (サイズ = ~1.9 GB) があります。それらには重複があり、100単語ごとにほぼ1つの重複単語があります。

2 番目のプログラムでは、ファイルを読み取りたいと考えています。BufferedReader を使用して、ファイルを行単位で読み取ることに成功しました。

重複を削除するには、Set (およびその実装) を使用できますが、次の 3 つの異なるシナリオで説明するように、Set には問題があります。

  1. デフォルトの JVM サイズでは、Set には最大 70 万から 80 万の単語を含めることができ、次に OutOfMemoryError を含めることができます。
  2. 5 億 1200 万の JVM サイズでは、Set には最大 500 万から 600 万の単語が含まれ、その後 OOM エラーが発生する可能性があります。
  3. JVM サイズが 1024M の場合、Set には最大 1200 万から 1300 万の単語が含まれ、その後 OOM エラーが発生する可能性があります。ここで Set に 1000 万件のレコードが追加されると、操作が非常に遅くなります。たとえば、次の ~4000 レコードの追加には 60 秒かかりました。

JVM サイズをこれ以上増やすことができないという制限があり、ファイルから重複した単語を削除したいと考えています。

このような巨大なファイルから Java を使用して重複する単語を削除する他の方法やアプローチについて何か考えがあれば教えてください。どうもありがとう ：）

質問への情報の追加: 私の言葉は基本的に英数字であり、システム内で一意の ID です。したがって、それらは平易な英単語ではありません。

4

13 に答える 13

14

マージソートを使用して、2 番目のパスで重複を削除します。マージ中に重複を削除することもできます (RAM の出力に追加された最新の単語を保持し、候補と比較するだけです)。

于 2012-09-19T19:07:11.630 に答える
11

単語の最初の文字に基づいて、巨大なファイルを 26 個の小さなファイルに分割します。レター ファイルのいずれかがまだ大きすぎる場合は、2 番目のレターを使用してそのレター ファイルを分割します。

を使用して各レター ファイルを個別に処理し、Set重複を削除します。

于 2012-09-19T19:07:55.767 に答える
7

トライデータ構造を使用して、1 回のパスでジョブを実行できる場合があります。このようなお悩みにおすすめできるメリットがあります。ルックアップと挿入は迅速です。そして、その表現は比較的スペース効率が良いです。すべての単語を RAM で表すことができる場合があります。

于 2012-09-19T21:33:11.887 に答える
5

アイテムを並べ替えると、重複が束ねられるため、重複を簡単に検出して削除できます。

大きなファイルをマージソートするために使用できるコードがここにあります: http://www.codeodor.com/index.cfm/2007/5/10/Sorting-really-BIG-files/1194

于 2012-09-19T19:17:26.767 に答える
4

大きなファイルの場合、データをメモリに読み込まないようにしますが、代わりにメモリマップされたファイルを操作し、OS が必要に応じてメモリをページイン/ページアウトできるようにします。セット構造に、実際の文字列ではなく、このメモリ マップ ファイルへのオフセットが含まれている場合、メモリの消費量が大幅に少なくなります。

この記事をチェックしてください：

http://javarevisited.blogspot.com/2012/01/memorymapped-file-and-io-in-java.html

于 2012-09-19T19:07:56.813 に答える
4

質問: これらは本当に WORDS ですか、それとも別の何か (フレーズ、部品番号など) ですか?

一般的な話し言葉の WORDS の場合、最初の 2,000 語後にはほとんどの固有の単語が見つかると予想されるため、実際に必要なことは、単語を読み込んで辞書と照合し、見つかった場合はスキップすることだけです見つからない場合は、辞書に追加して書き出します。

この場合、あなたの辞書は数千語しかありません。また、一意の単語を見つけたらすぐに書き出すため、ソース ファイルを保持する必要はありません (または、完了したら辞書を単にダンプできます)。

于 2012-09-19T19:13:46.637 に答える
4

データベースの一時テーブルに (バッチ挿入を使用して) 単語を挿入できる場合は、そのテーブルに対する個別の選択になります。

于 2012-09-19T20:03:59.517 に答える
3

この種の問題を解決する 1 つの古典的な方法は、ブルーム フィルターです。基本的に、単語を何度もハッシュし、ハッシュ結果ごとにビットベクトルにいくつかのビットを設定します。単語をチェックしていて、そのハッシュからのすべてのビットがベクトルに設定されている場合は、おそらく (ベクトル内のハッシュ/ビットの数を増やすことで、この確率を任意に低く設定できます) 以前に見たことがあり、それは重複しています。 .

これが、初期のスペル チェッカーの仕組みでした。彼らは単語が辞書にあるかどうかは知っていましたが、現在の単語が表示されているかどうかしかわからないため、正しいスペルが何であるかを知ることはできませんでした.

java-bloomfilterを含む多くのオープン ソース実装があります 。

于 2012-09-19T19:10:43.967 に答える
1

実装についてあまり心配する必要がないようにするには、データベースシステムを使用する必要があります。これは、単純な古いリレーショナルSQLまたはNo-SQLソリューションのいずれかです。たとえば、Berkeley DB javaエディションを使用してから実行できると確信しています（擬似コード）

for(word : stream) {
  if(!DB.exists(word)) {
     DB.put(word)
     outstream.add(word)
  }
}

問題は本質的に簡単です。十分なメモリがないため、ディスクに保存する必要があります。次に、並べ替えO（N log N）（不要）またはハッシュO（N）を使用して、一意の単語を見つけます。

動作する可能性が非常に高いが、動作が保証されていないソリューションが必要な場合は、LRUタイプのハッシュテーブルを使用してください。経験的なジップの法則によれば、あなたは大丈夫なはずです。

そこにいる賢い人へ​​のフォローアップの質問、64ビットマシンを持っていてヒープサイズを12GBに設定した場合、仮想メモリが問題を処理するべきではない（最適な方法ではありませんが）、またはJavaが設計されていない場合はどうなりますか？こちらです？

于 2012-09-20T01:56:01.277 に答える
1

Java でこれに取り組む方法は、他のすべての言語と同じです。つまり、重複除去フィルターを作成し、必要に応じてパイプします。

これが私が意味することです（疑似コードで）：

  • 入力パラメータ: Offset,Size
  • サイズの検索可能な構造を割り当てますSize(= Set, ただし、1 である必要はありません)
  • stdin から要素を読み取りOffset(または EOF が検出され)、それらを stdout にコピーするだけです
  • Sizestdin (または EOF) から要素を読み取り、それらを Set に格納します。重複する場合は削除し、そうでない場合は stdout に書き込みます。
  • stdin から EOF まで要素を読み取り、要素が含まれている場合はSet削除し、そうでない場合は stdout に書き込みます

Offsets と saneを増やして、必要な数のインスタンスをパイプします (ストレージに問題がない場合は、おそらくコアと同じ数だけ) Size。プロセスが CPU バウンドであると思われるため、これにより、より多くのコアを使用できます。netcatお急ぎの場合は、処理を複数のマシンに分散して使用することもできます。

于 2012-09-19T19:09:20.317 に答える
1

自然言語として膨大な単語数を持つ英語でも、上限の見積もりは約80000語にすぎません。それに基づいて、 a を使用してHashSetすべての単語を追加するだけです（おそらく、大文字と小文字の問題を避けるためにすべて小文字で）：

Set<String> words = new HashSet<String>();
while (read-next-word) {
    words.add(word.toLowerCase());
}

それらが実際の単語である場合、これはメモリの問題を引き起こすことはなく、かなり高速になります!

于 2012-09-20T02:32:21.430 に答える
0

ほとんどのパフォーマンスの高いソリューションは、不要なものを省略することから生まれます。重複のみを探すため、単語自体を保存せずにハッシュを保存します。しかし待ってください。あなたはハッシュにも興味がありません。それらがすでに見られている場合のみです - それらを保存しないでください。ハッシュを非常に大きな数として扱い、bitset を使用して、この数を既に見たかどうかを確認します。

したがって、問題は、ハッシュ幅に応じたサイズの非常に大きなまばらなビットマップに要約されます。ハッシュが 32 ビットまでの場合は、riak ビットマップを使用できます。

... 128 ビット以上のハッシュに対する非常に大きなビットマップについて考えるのはやめました %) (また戻ってきます )

于 2012-10-09T09:18:55.287 に答える
0

この場合、必要なメモリが少ないため、マージソートよりもクイックソートの方が適しています。このスレッドには、その理由についての適切な説明があります。

于 2012-09-19T20:17:53.867 に答える