Преобразование уникальной семенной строки в случайное, но детерминированное значение float в Ruby

Мне сложно с этим концептуально.

В принципе, мне нужно принять некоторую произвольную уникальную строку и иметь возможность преобразовать ее в нормализованное значение float. То, что имеет значение выходного 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

Итак, какой подход в Ruby я могу использовать, чтобы превратить произвольную строку в случайное, но последовательное значение float?

Ответ 1

Ключевая часть, которую вы хотите, - это способ преобразования выходных данных 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

Это генерирует шестнадцатеричный хеш, затем преобразует его в целое число, а затем преобразует его в float. Каждый шаг детерминирован.

Примечание: как указано @emboss, это уменьшает сопротивление столкновению, потому что double равен 8 байтам, а хеш - 16 байтов. Это не должно быть большой проблемой, хотя звуки вашего приложения.

Ответ 2

Если безопасность не проблема, то, что вы описываете, на мой взгляд не хеш-функция. Хеш-функция - это односторонняя функция, означающая, что вычисление хэша легко, но возврат его "жесткий" или, в идеале, невозможный.

Вместо этого ваши требования описывают инъективную функцию Учитывая любые x1, x2 в вашем домене X, выполняется следующее:

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

f (x) = x такая функция, f (x) = x² нет. На простом английском языке: вы хотите иметь разные результаты, если ваши входы разные, одни и те же результаты, только если входы одинаковы. Верно, что это также верно для безопасных хэшей, но они дополнительно обеспечивают односторонние характеристики, такие как свойство неспособности (легко) найти x, если вы только даете f (x) и другие. Насколько я понял, вам не нужны эти свойства безопасности.

Тривиально, такое инъективное сопоставление от String to Float было бы дано просто путем интерпретации "String bytes" как "Float bytes" с этого момента, т.е. вы интерпретируете байты по-разному (подумайте C:

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

). Но в этом есть недостаток - реальная проблема в том, что Float имеет максимальную точность, поэтому вы столкнетесь с ситуацией переполнения, если ваши строки слишком велики (Floats внутренне представлены как значения double, что 8 байтов на 32-битная машина). Поэтому недостаточно места для практически любого варианта использования. Даже 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

Если уникальность имеет абсолютный приоритет, я бы рекомендовал перейти от float к целым числам. Ruby имеет встроенную поддержку больших целых чисел, которые не ограничены внутренними ограничениями значения long (это то, с чем сводится Fixnum). Таким образом, любой произвольный хеш-вывод может быть представлен как большое целое число.

Ответ 3

Да, вы описываете алгоритм хэширования. Вы можете использовать дайджест MD5 или SHA1 (так как они просто производят случайные биты) для генерации числа с плавающей запятой просто с помощью метода String#unpack с аргумент "G" (float с двойной точностью, сетевой порядок байтов) из дайджеста:

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