17

从概念上讲，我很难做到这一点。

基本上，我需要接受一些任意唯一的字符串，并能够将其转换为规范化的浮点值。输出浮点值是什么并不重要，只要相同的字符串输入总是产生相同的标准化浮点输出。

所以这是一个哈希算法对吗？我熟悉 SHA1 或 MD5，这似乎类似于密码哈希，其中正确密码的结果是相同的。但我相信这些方法会输出字符串。而我没有得到的是如何将 SHA1 或 MD5 的结果转换为一致的浮点值。

# 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

那么我可以在 Ruby 中采用哪种方法将任意字符串转换为随机但一致的浮点值？

4

3 回答 3

23

您想要的关键部分是将 SHA1 或 MD5 哈希输出转换为确定性和 1-1 的浮点数的方法。这是一个基于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

这会生成一个十六进制哈希，然后将其转换为整数，然后将其转换为浮点数。每一步都是确定性的。

注意：正如@emboss 所指出的，这会降低碰撞阻力，因为双精度是 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 的属性等。据我了解，您不需要这些安全属性。

简单地说，从现在开始，只需将“字符串字节”解释为“浮点字节”，即可以不同地解释字节（想想 C：

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

）。但是，这也有不利之处 - 真正的问题是 Float 具有最大精度，因此如果您的字符串太长，您将遇到溢出情况（浮点数在内部表示为double值，在 32 位机器上是 8 个字节）。因此几乎没有足够的空间用于任何用例。即使首先对字符串进行 MD5 处理也不能解决问题 - MD5 输出已经有 16 个字节长。

因此，这可能是一个真正的问题，具体取决于您的确切要求。尽管 MD5（或任何其他散列）会与输入充分混淆以使其尽可能随机，但您仍将可能值的范围从 16 个字节减少到有效的 8 个字节。（注意：在保持随机性方面，将随机 16 字节输出截断为 8 个字节通常被认为是“安全的”。椭圆曲线密码学做类似的事情。但据我所知，没有人能真正证明这一点，但也没有人能证明到目前为止相反）。因此，您受限的浮动范围更有可能发生碰撞。根据生日悖论，发现碰撞需要 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 回答