3

これが私の問題です（私はCでプログラミングしています）：

DNA配列を含む巨大なテキストファイルがいくつかあります（各ファイルには6500万行のようなものがあり、サイズは約4〜5 GBです）。これらのファイルには多くの重複があり（まだいくつあるかはわかりませんが、何百万もあるはずです）、異なる値のみを含むファイルを出力に戻したいと思います。各文字列には品質値が関連付けられているため、たとえば、品質値が異なる5つの等しい文字列がある場合は、最良の文字列を保持し、残りの4つを破棄します。

私ができる限りメモリ要件を減らし、速度効率を改善することは重要です。私のアイデアは、ハッシュ関数を使用してJudyHS配列を作成し、文字列DNAシーケンス（長さ76文字、可能な7文字）を整数に変換してメモリ使用量を削減することでした（多くの場合、76バイトではなく4バイトまたは8バイト）何百万ものエントリはかなりの成果になるはずです）。このようにして、整数をインデックスとして使用し、そのインデックスの最高品質の値のみを格納できます。問題は、そのような長い文字列をUNIVOCALLYで定義し、整数またはlonglong内に格納できる値を生成するハッシュ関数が見つからないことです。

ハッシュ関数についての私の最初のアイデアは、Javaのデフォルトの文字列ハッシュ関数のようなものでした：s [0] * 31 ^（n-1）+ s [1] * 31 ^（n-2）+ ... + s [ n-1]ですが、最大値は8,52 * 10 ^59..大きすぎます。同じことをして、それをダブルに保存するのはどうですか？計算はかなり遅くなりますか？衝突を回避して、文字列を一意に定義する方法が必要であることに注意してください（または、衝突のたびにディスクにアクセスする必要があるため、少なくとも非常にまれなはずです。非常にコストのかかる操作です...）

4

2 に答える 2

3

7 ^ 76の可能なDNA配列があり、それらを衝突なしで2 ^ 32のハッシュにマッピングしたいですか？ありえない。

これを行うには、少なくともlog2（7 ^ 76）= 214ビット、約27バイトが必要です。

私はあなたがいくつかの衝突に耐えることができます私は新しいホイールを再び発明する代わりにCRC32またはmd5に固執することをお勧めします。

于 2011-05-03T14:35:33.150 に答える
1

N個の要素に対して衝突のないハッシュ関数を取得する「簡単な」方法は、適切な混合関数（たとえば、暗号化ハッシュ関数）を使用し、サイズを切り捨てて、ハッシュ結果が少なくともサイズのスペースに存在するようにすることです。N2。_ ここでは、6500万行あります。これは26ビットに収まるため（2 26は6500万に近い）、52ビットで「十分なはずです」。

これはセキュリティ関連の問題ではないため、「壊れた」ものであっても、高速の暗号化ハッシュ関数を使用してみることができます。MD4、MD5、SHA-1 ...次に、結果を最初の（または最後の）64ビットに切り捨て、64ビット整数型に格納します。6500万行の間で衝突が発生しない可能性があります。そして、あなたがいくつかを手に入れれば、それらは非常にまれになります。

ハッシュ関数の最適化されたC実装については、sphlibを検索してください。提供されsph_dec64le()ている関数を使用して、8ビットのシーケンスを64ビットの符号なし整数値に「デコード」します。

于 2011-05-03T15:10:09.447 に答える