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

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

16 голосов
/ 18 августа 2011

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

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

Так это алгоритм хеширования, верно? Я знаком с 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 я могу использовать, чтобы превратить произвольную строку в случайное, но непротиворечивое значение с плавающей точкой?

Ответы [ 3 ]

20 голосов
/ 18 августа 2011

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

4 голосов
/ 19 августа 2011

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

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

3 голосов
/ 18 августа 2011

Да, вы описываете алгоритм хеширования. Вы можете использовать дайджест 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
...