Cómo proyectar uniformemente un hash en un número fijo de cubos

Hola colegas estadísticos,

Tengo una fuente que genera hashes (por ejemplo, calcular una cadena con una marca de tiempo y otra información y hashing con md5) y quiero proyectarla en un número fijo de cubos (digamos 100).

hash de muestra: 0fb916f0b174c66fd35ef078d861a367

Lo que pensé al principio era usar solo el primer carácter del hash para elegir un cubo, pero esto conduce a una proyección salvajemente no uniforme (es decir, algunas letras aparecen muy raramente y otras muy frecuentemente)

Luego, traté de convertir esta cadena hexa en un entero usando la suma de los valores de caracteres, luego tomé el módulo para elegir un cubo:

import sys

for line in sys.stdin:
    i = 0
    for c in line:
        i += ord(c)
    print i%100

Parece funcionar en la práctica, pero no sé si hay algún sentido común o resultados teóricos que puedan explicar por qué y en qué medida esto es cierto.

[Editar] Después de pensarlo, llegué a la siguiente conclusión: en teoría, puedes convertir el hash en un entero (muy grande) interpretándolo como un número: i = h [0] + 16 * h [1] + 16 * 16 * h [2] ... + 16 ^ 31 * h [31] (cada letra representa un número hexadecimal). Entonces podría modular este gran número para proyectarlo en el espacio del cubo. [/Editar]

Gracias !

uniform oDDsKooL
fuente

Un hash real no debería dar resultados no uniformes. ¿Estás seguro de que el algoritmo hash está implementado correctamente?

whuber

Dudo que haya un error en el algoritmo de hash en sí. Pero sospecho que los caracteres del resumen hexadecimal no son estrictamente uniformes y se distribuyen de forma independiente.

oDDsKooL

Eso es lo que encuentro dudoso: un hash "criptográficamente seguro" como MD5 debería tener distribuciones uniformes de todos los dígitos, a menos que haya algo muy especial sobre la distribución de la entrada ("especial" significa íntimamente vinculado con el algoritmo MD5). Su solución propuesta equivale a volver a aplicar hash al hash, que no debería ser necesario en absoluto.

whuber

El primer carácter del hash Md5 debe ser uniforme. Pero solo obtendría 16 valores (es una codificación hexadecimal)

leonbloy

Gracias por insistir en ese punto, volví a contar con la primera letra de los hashes y, de hecho, parece ~ distribuido uniformemente: {'a': 789, 'c': 769, 'b': 755, 'e': 730, 'd': 804, 'f': 749, '1': 716, '0': 758, '3': 734, '2': 735, '5': 787, '4': 756, '7': 771, '6': 721, '9': 764, '8': 765}. Por lo tanto, mi pregunta está más o menos respondida, ya que solo necesito proyectar este generador aleatorio de 16 estados en un espacio de 100 estados, lo que se puede hacer usando las primeras 2 letras del hash para generar un número entero de rango [0,16+ 16 * 16] y modúlelo a 100. ¿Le importa si respondo mi propia pregunta;)?

oDDsKooL

Respuestas:

NB: poner en forma la respuesta que surgió de la discusión en los comentarios para que sea más fácil de leer para las personas interesadas

(Versión actualizada)

Supongamos que tenemos una fuente que genera eventos independientes que queremos distribuir uniformemente en cubos. $B$

Los pasos clave son:

hash cada evento a un entero de tamaño $e$ $i$ $2^N$
proyectar en como $\mathcal{R} \times [0, 1[$ $p = \frac{i}{2^N}$
encuentre el cubo coincidente para que $b_i$ $\frac{b_i}{B} \le p \lt \frac{b_{i+1}}{B}$

Para 1. una solución popular es usar MurmurHash para generar un entero de 64 o 128 bits.

Para 3. una solución simple es iterar en y verificar que esté en $j = 1..B$ $p$ $[\frac{b_j}{B}, \frac{b_{j+1}}{B}[$

En el seudocódigo (python), el procedimiento general podría ser:

def hash_to_bucket(e, B):
    i = murmurhash3.to_long128(str(e))
    p = i / float(2**128)
    for j in range(0, B):
        if j/float(B) <= p and (j+1)/float(B) > p:
            return j+1
    return B

(versión anterior, realmente no es óptima)

La primera observación es que el n carta -ésima del hash debe ser distribuido de manera uniforme con respecto al alfabeto (que es aquí 16 letras de largo - gracias a @leonbloy por señalarlo).

~~Luego, para proyectarlo a un rango [0,100 [, el truco consiste en tomar 2 letras del hash (por ejemplo, 1ª y 2ª posiciones) y generar un número entero con eso:~~

~~int_value = int(hash[0])+16*int(hash[1])~~

~~Este valor vive en el rango [0,16+ (16-1) * 16 [, por lo tanto, solo tenemos que modularlo a 100 para generar un depósito en el rango [0, 100 [:~~ como se señaló en los comentarios, haciendo así que impacta la uniformidad de la distribución ya que la primera letra es más influyente que la segunda.

bucket = int_value % 100

En teoría, puede convertir el hash completo en un entero (muy grande) interpretándolo como un número: i = h [0] + 16 * h [1] + 16 * 16 * h [2] ... + 16 ^ 31 * h [31] (cada letra representa un número hexadecimal). Entonces podría modular este gran número para proyectarlo en el espacio del cubo. Entonces se puede notar que tomar el módulo de i se puede descomponer en una operación distributiva y aditiva:

\begin{aligned} i \mod N = ( \\ (h_{0} \mod N) \\ + (16 \mod N \times h_{1} \mod N) \\ + . . . \\ + (16^{31} \mod N \times h_{31} \mod N) \\ ) \mod N \end{aligned}

$\begin{align} i \mod N = (&\\ &(h_0 \mod N) \\ &+ (16 \mod N \times h_1 \mod N) \\ &+ ... \\ &+ (16^{31} \mod N \times h_{31} \mod N)\\ &) \mod N \end{align}$

oDDsKooL
fuente

Cualquier mejora a esta respuesta es bienvenida.

oDDsKooL

Esto no parece una buena solución porque cuando "cualquiera de las dos letras" están "distribuidas uniformemente", los cubos del al generalmente obtendrán un 50% más de visitas por cubo que los cubos del al . En efecto, está utilizando una función hash terrible en un intento de dividir el hash en 100 cubos. ¿Por qué no usar una buena función hash conocida para ese propósito?

0

$0$

55

$55$

56

$56$

99

$99$

whuber

Estoy de acuerdo. Una mejor solución enrollada a mano sería tomar un trozo de la cadena hexadecimal que podría traducirse en un entero de 16 bits. Luego divida el valor real por el valor entero máximo de 16 bits, multiplique por cien y redondee.

spdrnl

Si usa varios cubos en forma de , puede tomar solo los últimos bits del hash (y es equivalente en caracteres hexadecimales). De esta forma, el resultado de la operación de módulo será exactamente el mismo que cuando se calcula en la conversión completa a entero. También puede funcionar bien si usa una cantidad de cubos que no es una potencia de .

2^{n}

$2^n$

n

$n$

2

$2$

alesc

@whuber Estoy de acuerdo en que esto no es del todo óptimo y proyectar a un intervalo continuo [0,1 [es mucho mejor. He verificado eso experimentalmente también. Editaré la respuesta para reflejar esa opinión.

oDDsKooL

Tuve un problema similar y se me ocurrió una solución diferente que puede implementarse más rápido y más fácilmente en cualquier idioma.

Mi primer pensamiento fue enviar artículos de manera rápida y uniforme en un número fijo de cubos, y también para ser escalable, debería imitar la aleatoriedad.

Así que codifiqué esta pequeña función que devuelve un número flotante en [0, 1 [dada una cadena (o cualquier tipo de datos de hecho).

Aquí en Python:

import math
def pseudo_random_checksum(s, precision=10000):
    x = sum([ord(c) * math.sin(i + 1) for i,c in enumerate(s)]) * precision
    return x - math.floor(x)

Por supuesto, no es aleatorio, de hecho, ni siquiera es pseudoaleatorio, los mismos datos siempre devolverán la misma suma de verificación. Pero actúa como aleatorio y es bastante rápido.

Puede despachar y recuperar elementos en N depósitos simplemente asignando cada elemento al número de depósito math.floor (N * pseudo_random_checksum (item)).

fbparis
fuente

¿Tiene una intuición o prueba de que colocará las muestras de manera uniforme en [0,1]?

sud_

@sud_ Esta función se trata aquí: stackoverflow.com/a/19303725/1608467

fbparis

@sud_ Además, he realizado algunas pruebas para compararlo con un generador de números aleatorios legítimos y estuvo bien en todos los casos que he probado.

fbparis