3

バイオインフォマティクス プロジェクトでは、 Rubyの大量のビット文字列 (0 と 1 のみを含む文字列)をより小さな文字列に圧縮して、メモリ使用量を削減する必要があります。

したがって、理想的には、「0001010010010010010001001」のような文字列は「2a452c66」のようになります。回避したい衝突の可能性について何かを読むまで、最初に MD5 ハッシュを使用しました。

unpack、to_i、to_s などのさまざまな組み合わせを試しましたが、正しい組み合わせが得られないようです。

解決策は次のとおりです。

  • 先頭の 0 を保持します。
  • 可逆的であること。
  • 圧縮します（明らかに）。
  • また、出力は奇妙な文字を避ける必要があります。できれば、英数字スペースにとどまりたいと思います。(a-zA-Z0-9)。

ありがとう！

4

2 に答える 2

4

試す：

FORMAT = '%0.*b'

bitmask = "0001010010010010010001001"
bitmask.to_i(2) # => 2696329
hexval = bitmask.to_i(2).to_s(16) # => "292489"
FORMAT % [bitmask.size, hexval.to_i(16)] # => "0001010010010010010001001"

それがしていることは次のとおりです。

  • to_i(2)何が起こっているかを示すために、文字列をバイナリから整数値に変換します。
  • to_i(2).to_s(16)文字列としての 16 進表現に変換します。
  • FORMAT渡された最初のパラメータから取得した不明な長さ ( ) の先行バイト ( )printfを使用して、渡された値をバイナリ文字列表現 ( ) に変換することを示す書式文字列が含まれています ( )。%b0%0b%0.*bbitmask.size

より長いビットマスクを使用した別の例を次に示します。

bitmask = "11011110101011011011111011101111"

hexval = bitmask.to_i(2).to_s(16) # => "deadbeef"
FORMAT % [bitmask.size, hexval.to_i(16)] # => "11011110101011011011111011101111"

さらに長く:

bitmask = "1101111010101101101111101110111111111110111011011010110111011010"

hexval = bitmask.to_i(2).to_s(16) # => "deadbeeffeedadda"
FORMAT % [bitmask.size, hexval.to_i(16)] # => "1101111010101101101111101110111111111110111011011010110111011010"
于 2013-08-14T15:43:57.783 に答える
3

興味深い観察: 基数 2 の文字列をより高い基数 (基数 n など) に変換する場合、圧縮率は1/log2(n)です。これは、他の回答が示唆するように 16 進数に変換すると、元の 25% の圧縮が得られることを意味します。ベース 64 まで移動すると (純粋な英数字よりも 2 つの記号だけ多くなります)、約 17% の圧縮にジャンプします。それは、そのトレードオフのどこに座りたいかによって異なります!

あるいは、可逆性要件を取り除き、平等を維持するだけであれば、MD5 で問題ありません。MD5 が衝突を生成する前に、いくつのランダム要素を参照してください。スポイラー：それはたくさんあります。これから読む衝突の「問題」は、意図的な衝突です。MD5 の知識を使用して衝突を検出する暗号学者。偶発的な衝突は、すべての実用的な目的で不可能です。

アップデート

実際に Ruby で base64 エンコードを実装するという点では、わかりません。実はRubyは知りません。ネイティブでサポートされていない場合は、すべての英数字 + 2 の配列を作成し(したがって、配列の長さは 64 です)、その 6 桁の 2 進数を使用して、6 桁の 2 進数のチャンクを対応する文字に変換します。文字配列のインデックス。62 (またはその他の 2 の累乗以外) を使用する場合は、アルゴリズムが異なります。

于 2013-08-15T15:28:50.990 に答える