Cómo uniformemente proyecto de un hash a un número fijo de segmentos

Question

Hola Compañeros Estadísticos,

Tengo una fuente de generación de hashes (por ejemplo, el cálculo de una cadena con una marca de tiempo y otra información y hash md5) y quiero proyecto en un número fijo de segmentos (digamos 100).

muestra hash: 0fb916f0b174c66fd35ef078d861a367

Lo que al principio pensé que era utilizar sólo el primer carácter de la hash para elegir un cubo, pero esto conduce a una salvajemente no uniforme de proyección (es decir, algunas de las letras apppear muy rara vez y otra muy frecuentemente)

Entonces, traté de convertir esta hexa cadena en un entero usando la suma de los char valores, a continuación, tomar el modulo para elegir un cubo:

import sys

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

Parece que funciona en la práctica, pero no sé si hay sentido común o teóricas de los resultados que podría explicar por qué y en qué medida esto es cierto ?

[Editar] Después de algún pensamiento que me vino a la siguiente conclusión: En teoría, usted puede convertir el hash en un (muy grande) entero por interpretarla 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 usted podría modulo este gran número de proyectar para el cubo espacio. [/Edit]

Gracias !

Answer 1

NB: la puesta en forma de la respuesta que surgió de la discusión en los comentarios, así que es más fácil de leer para las personas interesadas

(versión actualizada)

Supongamos que tenemos una fuente de generación de eventos independientes que queremos distribuir de manera uniforme a $B$ cubos.

Los pasos clave son:

1. hash de cada evento $e$ a un entero $i$ del tamaño de la $2^N$
2. proyecto en $\mathcal{R} \times [0, 1[$ $p = \frac{i}{2^N}$
3. encontrar coincidencia balde $b_i$, de modo que $\frac{b_i}{B} \le p \lt \frac{b_{i+1}}{B}$

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

3. una solución simple es recorrer en $j = 1..B$ y compruebe que $p$ $[\frac{b_j}{B}, \frac{b_{j+1}}{B}[$

En (python) pseudo-código 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

---

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

La primera observación es que la n-ésima letra de la hash deben estar distribuidos de manera uniforme con respecto a la del alfabeto (que es aquí 16 letras de largo - gracias a @leonbloy por señalarlo).

Entonces, para proyecto a un [0,100[ rango, el truco es tomar 2 cartas de el hash (por ejemplo, de 1ª y 2ª posiciones) y generar un entero con que:

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

Este valor se vive en el rango de [0,16+(16-1)*16[, por lo tanto sólo tenemos que modulo es de 100 a generar un cubo en el [0, 100[ rango: Como se señaló en los comentarios, haciendo así que el impacto de la uniformidad de la distribución desde la primera carta es más influyentes de la segunda.

bucket = int_value % 100

En teoría, usted puede convertir el hash en un (muy grande) entero por interpretarla 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 usted podría modulo este gran número de proyectar para el cubo espacio. Uno puede, a continuación, tenga en cuenta que tomar el módulo de i puede ser descompuesto en un distributiva y aditivos de operación:

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