2

混乱を避けるために、ハッシュアルゴリズムに関する私の研究に基づいて質問を再構成しています

問題文 可変長データ レコードを含むテキスト ファイルが複数あります。入力に重複するレコードがあるかどうかを確認する必要があります。各テキスト ファイルには、数百万のデータ レコードが含まれている可能性があります。

すべてのデータを一度にメモリにロードすることはできないため、レコードの処理時にキー フィールドのハッシュを作成する予定です。レコードの処理とは、レコードの検証、フィルタリング、および変換を意味します。すべてのテキスト ファイルのすべてのレコードを処理した後、それらをマージして、入力全体 (テキスト ファイルまたはデータベース テーブル) の 1 つのビューを作成します。

すべてのレコードに対してハッシュ値が生成されると、重複の検出がはるかに高速になります。ハッシュ値の衝突がある場合、それらのレコードのみが等しいかどうかをチェックできます (ハッシュ アルゴリズムが決定論的であると仮定します)。

質問 - そのような入力、つまり可変長データに対してどのようなハッシュ アルゴリズムを考慮する必要がありますか?

4

2 に答える 2

4

簡潔な答え

やらないでください。Java マップを使用します。詳細はこちら: http://docs.oracle.com/javase/6/docs/api/java/util/Map.html

長い答え

文字列を base-N の数値として扱うことで、完全なハッシュ関数を作成できます。N は、任意の文字が取り得るすべての可能な値です。ここで問題になるのはメモリです。ハッシュ関数は配列で使用することを意図しています。つまり、ハッシュの結果を処理するのに十分な大きさの配列が必要になりますが、これは非現実的です。

たとえば、10 文字のキーの控えめな例を考えてみましょう。さらに控えめにして、小文字だけで構成されることが保証されていると仮定しましょう。これにより、各文字に 26 の可能性があり、10 文字になります。つまり、可能な組み合わせは次のとおりです。

26 ^ 10 = 141,167,095,653,376

ハッシュ アルゴリズムを調べてみると、最初に含まれているものの 1 つは衝突検出です。これは、衝突が現実の事実であることを認識しているためです。

キーをメモリにロードしていないと言うのに、なぜハッシュを使用しているのですか? ハッシュのポイントは、配列インデックスへのマッピングを提供することです。おそらく、別のメカニズムを使用したほうがよいでしょう。

可能な解決策

メモリが心配な場合は、ファイル内の重複に関する統計を取得してください。ハッシュに特定のキーが出現したことを示すフラグのみを格納し、多くの重複がある場合は、Java のマップをそのまま使用できる場合があります。Java のマップは衝突を処理するため、一意のキーを検出できなくなることはありません。A[x] が見つかった場合、x のハッシュが前のハッシュと衝突したとしても、x が A にあることを意味します。

次に、いくつかのユーティリティを試して重複を引き出すことができます。それらは目的のために特別に作成されたものであるため、大量のデータを処理できるはずです。

最後に、エントリをデータベースに入れて、それを使用して重複を処理することができます。これはやり過ぎのように思えるかもしれませんが、データベースは非常に多数のレコードを処理するように最適化されています。

于 2012-12-17T13:28:24.630 に答える
1

これは、マップのアイデアの拡張です。これに頼る前に、一度にすべての文字列を表す HashSet を単純に構築するだけでは実行できないことを確認します。64 ビットの JVM を使用して、大きなヒープ サイズを設定できることに注意してください。

ディスク上の文字列へのランダム アクセスを実行するために必要なデータを含むクラス StringLocation を定義します。たとえば、RandomAcessFile への参照とファイル内のオフセットです。一度にすべてのファイルを開いたままにしておくことができない場合は、必要に応じて開いたり閉じたりして、最も使用されるファイルの RandomAcessFile をキャッシュします。

を作成しますHashMap<Integer,List<StringLocation>>。

文字列を読み始めます。文字列ごとに小文字に変換し、hashCode() のハッシュを整数形式で取得します。Map にハッシュをキーとするエントリがある場合、新しい文字列を既存の値で表される各文字列と比較し、ランダム ファイル アクセスを実行して、既に処理された文字列を取得します。文字列 equalsIgnoreCase を使用します。一致する場合は、重複があります。一致するものがない場合は、現在の文字列を表す新しい StringLocation を List に追加します。

これには、一度に最大 2 つの文字列がメモリに存在する必要があります。現在処理している文字列と、比較対象と同じ hashCode() の結果を持つ以前に処理された文字列です。

MessageDigest を使用して小文字の文字列に対して、衝突のリスクが低い幅の広いチェックサムを生成し、それを StringLocation オブジェクトに保存することで、等号チェックのために文字列を再読み取りする必要がある回数をさらに減らすことができます。比較中に、チェックサムが一致しない場合は、文字列を再読み取りせずに false を返します。

于 2012-12-17T14:41:42.463 に答える