Преобразование уникальной исходной строки в случайное, но детерминированное значение с плавающей запятой в Ruby

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

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

Вместо этого ваши требования описывают инъективную функцию. Для любых 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 в Float будет дано путем простой интерпретации «String bytes» как «Float bytes» с этого момента, т.е. вы интерпретируете байты по-разному (подумайте C:

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

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

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

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

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