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

Question

Hola colegas estadísticos,

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

hash de ejemplo: 0fb916f0b174c66fd35ef078d861a367

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

Luego, intenté convertir esta cadena hexadecimal en un entero usando la suma de los valores de los caracteres, luego tomar el módulo para elegir una cubeta:

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 un poco 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). Luego podrías tomar el módulo de este número grande para proyectarlo al espacio de las cubetas. [/Editar]

¡Gracias!

Answer 1

NB: poniendo 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 $B$ buckets.

Los pasos clave son:

1. hashear cada evento $e$ a un entero $i$ de tamaño $2^N
2. proyectar en $\mathcal{R} \times [0, 1[$ como $p = \frac{i}{2^N}
3. encontrar el bucket coincidente $b_i$ de modo que $\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 $j = 1..B$ y verificar que $p$ esté en $[\frac{b_j}{B}, \frac{b_{j+1}}{B}[$

En pseudo-có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 óptima)

La primera observación es que la letra \em>-ésima del hash debería estar distribuida uniformemente con respecto al alfabeto (que aquí tiene 16 letras - gracias a @leonbloy por señalarlo).

\strike> Luego, para proyectarlo en un rango [0,100[, el truco es tomar 2 letras del hash (por ejemplo, las posiciones 1 y 2) y generar un entero con eso:

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

Este valor está en el rango [0,16+(16-1)*16[, por lo tanto solo tenemos que aplicarle el modulo de 100 para generar un bucket en el rango [0, 100[: Como se señaló en los comentarios, hacer esto afecta la uniformidad de la distribución, ya que la primera letra tiene más influencia que la segunda.

bucket = int_value % 100

En teoría se puede convertir todo el hash en un (muy grande) entero 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). Luego podrías aplicarle el módulo a este número grande para proyectarlo al espacio de los buckets. Uno puede notar entonces que tomar el módulo de i se puede descomponer en una operación distributiva y aditiva:

\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}

Answer 2

Tuve un problema similar y encontré una solución diferente que podría ser más rápida y fácil de implementar en cualquier lenguaje.

Mi primera idea fue distribuir elementos rápidamente y uniformemente en un número fijo de contenedores, y también para ser escalable, debería imitar la aleatoriedad.

Así que codifiqué esta pequeña función que devuelve un número decimal en [0, 1[ dado una cadena (o cualquier tipo de dato 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 pseudo aleatorio, los mismos datos siempre devolverán el mismo checksum. Pero actúa como aleatorio y es bastante rápido.

Puedes distribuir y más tarde recuperar elementos en N contenedores simplemente asignándole a cada elemento el número de contenedor math.floor(N * pseudo_random_checksum(item)).

Answer 3

Aquí puedes encontrar una distribución uniforme de cubetas sin ramificaciones que funciona con operaciones bit a bit.