Conversione di una stringa di seme univoca in un valore float casuale, ma deterministico in Ruby

Question

Mi sto divertendo molto, concettualmente.

Fondamentalmente, devo accettare alcune stringhe univoche arbitrarie, ed essere in grado di convertirle in un valore float normalizzato. Ciò che il valore float dell'output non è importante, a condizione che lo stesso input di stringa abbia sempre lo stesso output float normalizzato.

Quindi questo è un algoritmo di hash giusto? Ho familiarità con SHA1 o MD5 e questo sembra simile all'hash della password, dove il risultato è lo stesso per la password corretta. Ma quei metodi producono stringhe di personaggi, credo. E quello che non sto ottenendo è come avrei trasformato il risultato di uno SHA1 o MD5 in un valore float consistente.

# 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 

Quindi, che tipo di approccio in Ruby posso prendere che sarebbe trasformare una stringa arbitraria in un valore float casuale ma consistente?

Answer 1

la parte chiave che si desidera è un modo di convertire uno SHA1 o uscita hash MD5 in un galleggiante che è sia deterministica e 1-1. Ecco una soluzione semplice basata su MD5. Questo potrebbe essere usato anche come numero intero.

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 

Questo genera un hash esadecimale, quindi lo converte in un numero intero, quindi converte che ad un galleggiante. Ogni passaggio è deterministico.

Nota: come sottolineato da @emboss, riduce la resistenza di collisione poiché un doppio è 8 byte e l'hash è 16 byte. Non dovrebbe essere un grosso problema attraverso i suoni della tua applicazione.

Answer 2

Sì, si sta descrivendo un algoritmo di hashing. È possibile utilizzare un digest MD5 o SHA1 (poiché producono solo bit casuali) per generare un numero in virgola mobile semplicemente utilizzando lo String#unpack method con un argomento di "G" (float a precisione doppia, ordine byte di rete) da un digest:

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! 

Si noti che se si desidera che i galleggianti risultanti siano in un intervallo particolare, è necessario eseguire un massaggio.

Si noti inoltre che il numero decompresso non utilizza tutti i bit del digest, quindi è possibile combinare il numero di byte per un numero a virgola mobile doppio (sebbene sia necessario fare attenzione a non diminuire l'entropia della funzione di hash, se vi preoccupate per questo genere di cose), ad esempio:

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 

Answer 3

Se la sicurezza non è un problema, quello che stai descrivendo è a mio parere non una funzione di hash. Una funzione hash è una funzione unidirezionale, il che significa che calcolare l'hash è facile, ma ripristinarlo è "difficile" o, idealmente, impossibile.

Le vostre esigenze, invece descrivono un injective function dato alcuna x1, x2 nel dominio X vale quanto segue:

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

f (x) = x è una tale funzione, f (x) = x² non lo è. In parole semplici: vuoi avere risultati diversi se i tuoi input sono diversi, gli stessi risultati solo se gli input sono gli stessi. È vero che anche questo è vero per gli hash sicuri, ma forniscono anche le caratteristiche unidirezionali come la proprietà di non essere in grado (facilmente) di trovare x se si è data solo f (x), tra gli altri. Per quanto ho capito, non hai bisogno di queste proprietà di sicurezza.

Banalmente, una mappatura quali iniettiva da String a galleggiare sarebbe dato semplicemente interpretando i "byte stringa" come "Float byte" da ora in poi, vale a dire si interpretano i byte in modo diverso (si pensi C:

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

). Ma c'è un rovescio della medaglia: il vero problema è che Float ha una precisione massima, quindi ti imbatterai in una situazione di overflow se le tue stringhe sono troppo lunghe (i Floats sono internamente rappresentati come valori double, ovvero 8 byte su un 32 bit macchina). Quindi non c'è abbastanza spazio per quasi tutti i casi d'uso. Persino MD5, prima di tutto, non risolve il problema: l'output MD5 è già lungo 16 byte.

Quindi questo potrebbe essere un problema reale, a seconda dei vostri esatti requisiti. Sebbene MD5 (o qualsiasi altro hash) funzionerà a sufficienza con l'input per renderlo il più casuale possibile, si taglia comunque l'intervallo di valori possibili da 16 byte a 8 byte effettivi. (Nota: il troncamento casuale dell'uscita a 16 byte a 8 byte è generalmente considerato "sicuro" in termini di conservazione della casualità. La crittografia a curve ellittiche fa qualcosa di simile, ma per quanto ne so nessuno può davvero dimostrarlo, ma nessuno potrebbe provarlo al contrario finora). Quindi una collisione è molto più probabile con la tua gamma Float limitata. Per il paradosso del compleanno, trovare una collisione richiede sqrt (numero di valori in un intervallo finito). Per MD5 questo è 2^64, ma per il tuo schema è solo 2^32. È ancora molto, molto improbabile che produca una collisione. Probabilmente è qualcosa nell'ordine di vincere alla lotteria, mentre allo stesso tempo viene colpito da un fulmine. Se si potesse vivere con questo minima possibilità, andare per esso:

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

Se unicità è di priorità assoluta che consiglierei di passare da carri a numeri interi. Ruby ha il supporto integrato per i grandi numeri interi che non sono limitati dai vincoli interni di un valore long (questo è il motivo per cui un Fixnum si riduce a). Quindi qualsiasi output hash arbitrario potrebbe essere rappresentato come un numero intero di grandi dimensioni.