17

概念的に、これには苦労しています。

基本的に、任意の一意の文字列を受け入れ、それを正規化された浮動小数点値に変換できる必要があります。同じ文字列入力が常に同じ正規化された float 出力になる限り、出力 float 値が何であるかは実際には重要ではありません。

これはハッシュアルゴリズムですよね？私は SHA1 または MD5 に精通していますが、これは正しいパスワードに対して結果が同じであるパスワード ハッシュに似ているようです。しかし、それらのメソッドは文字列を出力すると思います。そして、私が得ていないのは、SHA1 または MD5 の結果を一貫した float 値に変換する方法です。

# Goal
def string_to_float(seed_string)
  # ...
end

string_to_float('abc-123') #=> 0.15789
string_to_float('abc-123') #=> 0.15789

string_to_float('def-456') #=> 0.57654
string_to_float('def-456') #=> 0.57654

では、任意の文字列をランダムだが一貫性のある float 値に変換するには、Ruby でどのようなアプローチを取ることができるでしょうか?

4

3 に答える 3

23

必要な重要な部分は、SHA1 または MD5 ハッシュ出力を決定論的かつ 1-1 である float に変換する方法です。これは、md5 に基づく簡単なソリューションです。これは整数としても使用できます。

require 'digest/md5'

class String
  def float_hash
    (Digest::MD5.hexdigest(self).to_i(16)).to_f
  end
end

puts "example_string".float_hash  # returns 1.3084281619666243e+38

これは 16 進数のハッシュを生成し、それを整数に変換してから、それを float に変換します。各ステップは決定論的です。

注: @emboss で指摘されているように、double は 8 バイトでハッシュは 16 バイトであるため、これにより衝突耐性が低下します。ただし、アプリケーションの音によっては大したことではありません。

于 2011-08-18T19:28:51.493 に答える
5

セキュリティが問題にならない場合、あなたが説明しているのは私の意見ではハッシュ関数ではありません. ハッシュ関数は一方向関数です。つまり、ハッシュの計算は簡単ですが、元に戻すのは「難しい」か、理想的には不可能です。

代わりに、要件は単射関数を記述します ドメイン X 内の x1、x2 を考えると、次が成り立ちます。

For all x1, x2 element of X, x1 != x2  => f(x1) != f(x2)

f(x) = x はそのような関数ですが、f(x) = x² はそうではありません。簡単に言えば、入力が異なる場合は異なる結果が必要であり、入力が同じ場合にのみ同じ結果が必要です。これは安全なハッシュにも当てはまりますが、f(x) しか与えられていない場合、x を (簡単に) 見つけることができないという特性など、一方向の特性を追加で提供します。私が理解している限り、これらのセキュリティ プロパティは必要ありません。

自明なことですが、このような String から Float への単射マッピングは、"String バイト" を "Float バイト" として単純に解釈することで得られます。つまり、バイトを別の方法で解釈します (C:

unsigned char *bytes = "...";
double d = (double)bytes;

）。しかし、これには欠点があります - 本当の問題は Float が最大の精度を持っていることですdouble. ）。そのため、ほとんどすべてのユースケースに十分なスペースがありません。最初に文字列を MD5 処理しても問題は解決しません。MD5 出力はすでに 16 バイトの長さです。

したがって、正確な要件によっては、これが実際の問題になる可能性があります。MD5 (またはその他のハッシュ) は、入力を可能な限りランダムにするために十分に混乱しますが、可能な値の範囲を 16 バイトから事実上 8 バイトに削減します。(注: ランダムな 16 バイト出力を 8 バイトで切り捨てることは、ランダム性を維持するという点で一般に「安全」と見なされます。楕円曲線暗号は同様のことを行います。しかし、私の知る限り、誰も実際にそれを証明することはできません。今までと逆）。したがって、制限された Float 範囲では衝突が発生する可能性がはるかに高くなります。誕生日のパラドックスにより、衝突を見つけるには sqrt (有限範囲内の値の数) の試行が必要です。MD5 の場合、これは 2^64 ですが、あなたのスキームでは 2^32 しかありません。それでも、衝突が発生する可能性は非常に低いです。これ' 雷に打たれながら宝くじに当選するようなものだろう。この最小限の可能性で生活できる場合は、それを選択してください。

def string_to_float(str)
  Digest::MD5.new.digest(str).unpack('D')
end

一意性が絶対的な優先事項である場合は、浮動小数点から整数に移行することをお勧めします。Ruby には、値の内部制約によって制限されない大きな整数のサポートが組み込まれていlongます (これが Fixnum の要約です)。したがって、任意のハッシュ出力は大きな整数として表すことができます。

于 2011-08-18T20:13:51.083 に答える
4

はい、あなたはハッシュアルゴリズムを説明しています。MD5またはSHA1ダイジェスト（ランダムビットを生成するだけなので）を使用して、ダイジェストから「G」（倍精度浮動小数点数、ネットワークバイトオーダー）の引数を持つString#unpackメソッドを使用するだけで、浮動小数点数を生成できます。

require 'digest/sha1'

def string_to_float(str)
  Digest::SHA1.digest(str).unpack("G")[0]
end

string_to_float("abc-123") # => -2.86011943713676e-154
string_to_float("def-456") # => -1.13232994606094e+214
string_to_float("abc-123") # => -2.86011943713676e-154 OK!
string_to_float("def-456") # => -1.13232994606094e+214 OK!

結果のフロートを特定の範囲にしたい場合は、マッサージを行う必要があることに注意してください。

また、アンパックされた数値はダイジェストのすべてのビットを使用するわけではないため、二重浮動小数点数のバイト数に結合することをお勧めします（ただし、ハッシュ関数、そのようなことを気にするなら）、例えば：

def str2float(s)
  d = Digest::SHA1.digest(s)
  x, y = d[0..9], d[10..19]
   # XOR the 1st (x) and 2nd (y) halves to use all bits.
  (0..9).map {|i| x[i] ^ y[i]}.pack("c*").unpack("G")[0]
end
于 2011-08-18T19:07:09.277 に答える